|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Rustam Gadeyev 2:5008/14 19 Oct 2001 18:39:36
To : Evgeny Sharandin
Subject : 8 мирных ферзей
--------------------------------------------------------------------------------
18 Окт 01 12:17, Evgeny Sharandin wrote Rustam Gadeyev:
ES> Почти в 2 раза уже есть, как еще уже написал. Смена BP на spb или GPC
ES> еще раза в 2 пришпорит. Пусть будет, в сумме, в 4 раза (чего
ES> жадничать-то?). А если учесть симметрию, то для доски 8х8, в пределе,
ES> можно еще сократить время до 12/92. Короче, ускорение на порядок - это
ES> очень скромно.
Я что-то не совсем понял, как можно нормально пристроить проверку на симметрию и
получить при этом ускорение в 4 раза. А вот на другом компиляторе (BC3.1 и
WC10.0) программа заметно ускоряется. Hо это ведь не считается заслугой
программиста?
Вот переделанный 1 в 1 вариант на C. Вывод позиций работает только на BC.
//--- 8pherz.c ---\\
#include <conio.h>; //written by Rustam G. 19.10.2001
#define num 14 //BC3.1 P3-450: 14 11.75, 13 1.92
//WC10.0 /5 /oilr /s : 14 12.58, 13 2.08
unsigned char a[num+1]; //позиции ферзей
unsigned char p[num*2-1+1],d1[num*2-1+1],d2[num*2-1+1];
unsigned char i,j;
unsigned long int kol;
void work(void) {
unsigned int t,n;
n=1;a[n]=1;kol=0;t=a[n];
for (;;) {
//если сюда можно поставить ферзя
if (p[t] & d1[t+n-1] & d2[num-t+n]) {
if (n==num) { //если встал последний ферзь, комбинация достигнута
kol++;
//вывод на экран
/*удалить этот комментарий для вывода на экран
clrscr();
a[n]=t;
for (i=1;i<=num;i++)
for (j=1;j<=num;j++) {
gotoxy(j*2,i);
if (a[j]==i) cprintf("%u",j); else cprintf("* ");
}
if (getch()==27) return; //по позициям */
}
else { //если это не последний ферзь, попробуем поставить еще
p[t]=0; //запрет горизонтали и диагоналей
d1[t+n-1]=0; d2[num-t+n]=0;
a[n]=t; //этот ферзь будет стоять здесь
n++; //к следующем ферзю
t=1; //начиная с позиции 1
continue; //летим пробовать поставить еще один ферзь
}
}
//идем на новую позицию
for (;;) {
if (t<num) {
t++;
break; //еще есть позиции для перебора в столбце}
} else { //этот столбик уже весь перебрали
n--; //отступаем
if (n<1) return; //больше некуда?
t=a[n];
p[t]=1; //разрешить горизонталь и диагонали
d1[t+n-1]=1; d2[num-t+n]=1;
}
}
}
}
void main() {
for (i=1;i<=(num*2-1);i++) { p[i]=1; d1[i]=1; d2[i]=1; }
work();
cprintf("\r\n%lu вариантов\r\n",kol);
}
\\--- 8pherz.c ---//
Good Bye.
--- ---
* Origin: Ulan-Ude. Buryatia. (2:5008/14)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
