как развернуть рекурсию (8 ферзей)

[adav84]

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

Код: Выделить всё

#include <stdio.h>
#include <string.h>


int row[8], col[8], diag1[15], diag2[15];

void print(){
  int x,y;

  for(y=0;y<8;y++) {
    for(x=0;x<8;x++) {
      printf(" %c",row[y]==x?'*':'.');
    }
    putchar('\n');
  }
  putchar('\n');
}

void try(int y){
  int x;

  for(x=0;x<8;x++) {
    if(col[x] || diag1[x+y] || diag2[x-y+7])
      continue;
    row[y]=x; col[x]++; diag1[x+y]++; diag2[x-y+7]++;
    if(y==7)
      print();
    else
      try(y+1);
    row[y]=0; col[x]--; diag1[x+y]--; diag2[x-y+7]--;
  }

}

main(){

  memset(row,0,sizeof(row));
  memset(col,0,sizeof(col));
  memset(diag1,0,sizeof(diag1));
  memset(diag2,0,sizeof(diag2));

  try(0);

  return 0;

}

передачу y+1 я организовал так:

Код: Выделить всё

int a[100], sp=0;

#define x a[sp]  // это после объявления print() и до конца текста, так что это окей
#define y a[sp+1]

...

 if(y==7) print();
  else {
      sp+=2; y=a[sp-1]+1;  try(); sp-=2;
  }

, а дальше затрудняюсь... может, сначала надо хвостовую рекурсию сделать, т.е. чтобы try вызывалось в конце try, а там просто for(;;){...}?

[drBatty]

#define x a[sp] // это после объявления print() и до конца текста, так что это окей

за такое вы рискуете получить подсвечником по голове.

До свидания, быдлокод даже смотреть не стану.

Вы кого тут хотели запутать?

[NickLion]

1. При глубине вложенности 8 разворачивать рекурсию — особо нет смысла. Хотя в данном случае версия без рекурсии просто выглядит.
2. drBatty, может, резковат в словах, но по сути верно говорит. Такие define'ы — зло.
3. Для "развёртки" рекурсии в данном случае придётся эмулировать стек с локальными переменными для возврата. В качестве локальных переменных нужна только позиция ферзя по горизонтали, т.е. достаточно одного массива длиной 8. Код писать сейчас нет времени, но в целом суть такая:

Код: Выделить всё

const int N = 8;
int x[N]; // позиция ферзя на строке
for (int i = 0; i < N; i++)
    x[i] = -1;
int i = 0; // строка
do {
    // ищем допустимую позицию:
    if (x[i] >= 0) {
        // убираем признаки ферзя для позиции (i, x[i])
    }
    while (++x[i] < N)
        if (/*ферзя можно поставить в (i,x[i])*/)
            break;
    if (x[i] < N) {
        // "ставим" ферзя на позицию (i, x[i])
        i++; // идём на след. строку
    } else {
        x[i] = -1; // возврат
        i--;
    }
} while (i < N);

Как-то так.

[drBatty]

может, резковат в словах

надо было сразу предупреждать. В первой строке кода.

Хотя в данном случае версия без рекурсии просто выглядит.

с рекурсией ещё проще. Если кривые макросы убрать конечно.

[NickLion]

с рекурсией ещё проще.

Поэтому и говорил, что смысла разворачивать нет.

Если кривые макросы убрать конечно.

В рекурсивной версии их, вроде, не было. Это была попытка "развернуть".

[drBatty]

В рекурсивной версии их, вроде, не было. Это была попытка "развернуть".

ну можно было и не делать таких "попыток"...

Тогда можно заметить, что все эти массивы можно заменить одной матрицей 8*8 (как клетки на доске), и что каждый ферзь может увеличивать по двум диагоналям, по вертикали, и по горизонтали(не обязательно).

Тогда можно не хранить место, куда возвращаться, это первая 1 по горизонтали справа

Код: Выделить всё

K1211111
22K!1111
11210000
20111000
10101100
10100110
10100011
10100001

у меня сл. позиция обозначена "!", и искать её не нужно, просто надо перейти на прошлую горизонталь.