Здравствуйте, Pushkin, Вы писали:

<>

// примитивные функции
bool test_cell(int c, int r);
void set_col(int c);
void set_row(int r);

// линеаризация индекса
int max_index();
int row(int i);
int col(int i);

// а теперь!
void work(int i)
{
  while(i < max_index() && !test(col(i), row(i))) ++i;
  work(i+1);
  set_col(col(i));
  set_row(row(i));
}

void work()
{
  work(0);
}

Привет, Pushkin!

P>Есть битовая матрица. Её нужно преобразовать.
P>В каждой ячейке новой матрицы должна стоять единица, если либо в этом столбце, либо в этой строке старой матрицы была хоть одна единица.
P>Важное условие: преобразовывать надо "по месту", нельзя заводить новую матрицу.
P>Более того, нельзя вообще заводить никаких переменных кроме счётчиков циклов.

Осноная идея: собрать в некоторой строке и столбце информацию о тех столбцах и строках, где есть единицы.

Вариант 1.
1. В зависимости от того, есть ли единицы в первом столбце и в первой строке попадаем в одну из 4-х частей кода (фактически запоминаем эту информацию без лишних переменных — теперь я понимаю, почему в микрософте такие программы пишут).
2. В цикле бежим по строкам, начиная со второй, и в каждой ищем единицу. Если есть, то ставим в соответствующем месте первого столбца 1, иначе 0.
3. То же самое со столбцами... Испохабили левый столбец и верхнюю строку? Не страшно (см.п.1)!
4. Бегаем по всем ячейкам матрицы, начиная со второй строки и второго столбца, и смотрим, есть ли единица в соответствующей строке первого столбца или соответствующем столбце первой строки. Если есть — единица, иначе — ноль (хотя он и так стоит).
5. Если мы в той части кода, где предполагается наличие хоть одной единицы в первом столбце, то весь этот столбец заполняем единицами, иначе оставляем как есть.
6. То же самое с первой строкой!

Вариант 2.
1. Ищем самую левую-верхнюю ячейку с единицей и сокращаем дальнейший поиск в оставшейся матрице. Преймущество в том, что одна часть кода!
Далее по аналогии (вместо первого столбца и первой строки используем найденные) с соответствующими исправлениями.

Здравствуйте, VVV, Вы писали:

...

VVV>Идея классная, хорошая

VVV>Просто замечание: а где же терминатор рекурсии?

А их здесь аж два:

while(i < max_index() ...

и "Stack overflow"...

Здравствуйте, Кодт, Вы писали:


К>

К>// а теперь!
К>void work(int i)
К>{
К>  while(i < max_index() && !test(col(i), row(i))) ++i;
К>  work(i+1);
К>  set_col(col(i));
К>  set_row(row(i));
К>}

К>void work()
К>{
К>  work(0);
К>}
К>

Идея классная, хорошая

Просто замечание: а где же терминатор рекурсии?

Есть битовая матрица. Её нужно преобразовать.
В каждой ячейке новой матрицы должна стоять единица, если либо в этом столбце, либо в этой строке старой матрицы была хоть одна единица.

Важное условие: преобразовывать надо "по месту", нельзя заводить новую матрицу.
Более того, нельзя вообще заводить никаких переменных кроме счётчиков циклов.

PS
Говорят, задача из собеседования в Майкрософт.

Здравствуйте, Apapa, Вы писали:


A>Вариант 1.
A>1. В зависимости от того, есть ли единицы в первом столбце и в первой строке попадаем в одну из 4-х частей кода (фактически запоминаем эту информацию без лишних переменных — теперь я понимаю, почему в микрософте такие программы пишут).

столбец ни к чему — строки достаточно, поэтому всего 2 части кода, а не 4

A>Вариант 2.
A>1. Ищем самую левую-верхнюю ячейку с единицей и сокращаем дальнейший поиск в оставшейся матрице. Преймущество в том, что одна часть кода!

...но по сути запоминаем место этой ячейки..
...хотя конечно можно сказать, что это тоже счётчики...

Здравствуйте, Кодт, Вы писали:

// а теперь!
void work(int i)
{
  while(i < max_index() && !test(col(i), row(i))) ++i;
  work(i+1);
  set_col(col(i));
  set_row(row(i));
}

Забавно, конечно
Но я бы не стал это запускать для max_index()==2^30
Да и вообще рекурсивные алгоритмы они какие-то малость второго сорта.
А вот кстати давно хотел спросить, они второго сорта? С точки зрения высокой науки?

Здравствуйте, Кодт, Вы писали:

...



Мне понравилось.
С помощью рекурсии решается проблема "затирания" ячеек.
Хотя и несколько противоречит условиям — наличием локальных переменных.

Привет, Pushkin!

A>>Вариант 1.
A>>1. В зависимости от того, есть ли единицы в первом столбце и в первой строке попадаем в одну из 4-х частей кода (фактически запоминаем эту информацию без лишних переменных — теперь я понимаю, почему в микрософте такие программы пишут).
P>столбец ни к чему — строки достаточно, поэтому всего 2 части кода, а не 4

В этом случае для каждой ячейки каждой строки, начиная со второй, надо пробегать целиком строчку, или устраивать две части кода внутри цикла просмотра ячеек...

A>>Вариант 2.
A>>1. Ищем самую левую-верхнюю ячейку с единицей и сокращаем дальнейший поиск в оставшейся матрице. Преймущество в том, что одна часть кода!
P>...но по сути запоминаем место этой ячейки..
P>...хотя конечно можно сказать, что это тоже счётчики...

Внутри цикла поиска нужной части матрицы, или поиска крайней ячейки, у которой в строке или в столбце есть единица, мы, как находим, попадаем внутрь некоего if (...). Там делаем все остальное и в конце концов <b>superbreak</b>

Автор: LeonGorbachev
Дата: 27.05.02

!

Здравствуйте, Apapa, Вы писали:

P>>столбец ни к чему — строки достаточно, поэтому всего 2 части кода, а не 4

A>В этом случае для каждой ячейки каждой строки, начиная со второй, надо пробегать целиком строчку, или устраивать две части кода внутри цикла просмотра ячеек...

Поясняю идею Pushkin-а.
После разветвления по анализу первой строки сперва анализируем первый стобец и записываем результат анализа в левую верхнюю ячейку. После этого первый столбец можно спокойно забивать информацией.

Здравствуйте, mrhru, Вы писали:

...

Но если можнА, то ...

// примитивные функции
bool test_cell(int c, int r);
void test_and_set_col(int c, int r);
void test_and_set_row(int c, int r);

void sub_matrix(int minС, int maxC, int minR, int maxR)
{
  for(int r = minR; r <= maxR; r++)
  {
    for(int c = minC; c <= maxC; c++)
      if( test(c, r) ){

        // левая нижняя подматрица
        if( c > minC)
        {
          sub_matrix(minC, c - 1, r + 1, maxR);
        }

        // правая нижняя подматрица
        if( c < maxC)
        {
          sub_matrix(c + 1, maxC, r + 1, maxR);

          // проверяем остаток строки
          for(int i = c + 1; i <= maxC; i++) test_and_set_col(i, r);
        }

        // проверяем остаток столбца
        if( r < maxR)
        {
          for(int i = r + 1; i <= maxR; i++) test_and_set_row(r, i);
        }

        // усё! :)
        return;
      }
    }
  }
}

void matrix(int Cols, int Rows)
{
  sub_matrix(0, Cols - 1, 0, Rows - 1);
}

Фактически, вначале происходит полное тестирование матрицы, а затем заполнение.

Глубина рекурсии не более чем Rows — 1, точнее говоря не более min(Cols — 1, Rows — 1) (это верхняя оценка).
Ни одна ячейка не тестируется более одного раза.

Здравствуйте, mrhru, Вы писали:

M>...

Гм, все наврал. (Где таких программистов берут?)

Вот, надеюсь правильно.

процедура SubMatrix(LeftCol, RightCol, TopRow, BottomRow)
  перебирая строки row от TopRow до BottomRow ищем первую строку, в которой есть 1
    перебирая столбцы col от LeftCol до RightCol ищем первый столбец, в котором есть 1

      //для нижней левой подматрицы
      вызываем SubMatrix(сol + 1, RightCol, row + 1, BottomRow) 

      для i от col + 1 to RightCol
        test_and_set_col(i, row)

      для i от row + 1 to BottomRow
        test_and_set_row(col, i)
   
      set_col_and_row(col, row)

      return;