|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
21.02.2012, 19:03 | #1 |
Пользователь
Регистрация: 14.09.2011
Сообщений: 93
|
N ферзей
Расставить N ферзей на шахматном поле N на N, так чтобы они не били друг друга.
Написал программу, использовав алгоритм с возвратом, но еще не оптимизировал его(пока не до этого). Но есть ошибка Вот код: Код:
Ошибка: Необработанное исключение в "0x004119c9" в "nferz.exe": 0xC00000FD: Stack overflow. когда вызывается int krutaya_fun(int i, int j, int s, int matrix[N][N]) |
21.02.2012, 19:27 | #2 |
Форумчанин
Регистрация: 11.07.2010
Сообщений: 914
|
Неудивительно, ведь krutaya_fun вызывает саму себя с одними и теми же параметрами.
Результат - бесконечная рекурсия и переполнение стека. Вы отладчиком-то пользуетесь? |
21.02.2012, 20:21 | #3 |
Пользователь
Регистрация: 14.09.2011
Сообщений: 93
|
а где с теми же параметрами?
|
21.02.2012, 20:37 | #4 |
Форумчанин
Регистрация: 11.07.2010
Сообщений: 914
|
В окне отладки, называемом Call Stack.
krutaya_fun(int i=4, int j=4, int s=1,.... |
22.02.2012, 01:12 | #5 |
Форумчанин
Регистрация: 23.12.2011
Сообщений: 117
|
Вот тебе рабочая версия... делал когда то, мб поможет
Код:
|
22.02.2012, 01:40 | #6 | |
Форумчанин
Регистрация: 11.07.2010
Сообщений: 914
|
Цитата:
Код:
return (i==k); // ведь это скучно |
|
22.02.2012, 01:55 | #7 |
Форумчанин
Регистрация: 23.12.2011
Сообщений: 117
|
|
22.02.2012, 12:58 | #8 |
Пользователь
Регистрация: 14.09.2011
Сообщений: 93
|
2AlexDark
спасибо, а ты не можешь описать сам алгоритм расстановки ферзей, почему используется такое условие в while? и не могу понять, почему он выводит все варианты расстановок ферзей для каждого N. |
22.02.2012, 13:39 | #9 |
Форумчанин
Регистрация: 23.12.2011
Сообщений: 117
|
Если честно признатся сам не очень помню подробности
Смысл там в том что к-вертикаль, а y-горизонталь функция P - это, проверка позиции (комент неправильный)... т.е. для k-й вертикали, и y-й горизонтали while ((i<k)&&(y!=X[i])&&(abs(k-i)!=abs(y-X[i]))) {i++;} (i<k) - проверяем шо там понаставляли на предыдущих вертикалях (y!=X[i]) не на одной горизонтали (abs(k-i)!=abs(y-X[i])) - не на одной диагонали т.е. если на предыдущих вертикалях нет ферзей которые бъют ферзя на [k,y], то цикл выйдет с i=k; значит позиция есть. функция backtracking выполняет именно перебор позиции на очередной вертикали и когда доходит до k = N-1 т.е. последней вертикали, и находит там позицию то выводит что получилось, ну и вся эта рекурсия катится дальше, поэтому выводятся все полученные. |
22.02.2012, 14:37 | #10 |
Пользователь
Регистрация: 14.09.2011
Сообщений: 93
|
а где происходит возврат, при неудачной попытке расстановки? тут же только увеличивается k, я что-то не заметил
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Расстановка ферзей. Delphi | Lucky2011 | Помощь студентам | 4 | 11.02.2013 05:04 |
задача ферзей | Математик_Лена | Общие вопросы C/C++ | 1 | 05.02.2012 18:04 |
8 ферзей | Роза!!! | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 23.02.2011 10:54 |
8 ферзей | battlefrogg | Помощь студентам | 5 | 06.05.2010 15:28 |
8 ферзей | slim5 | Общие вопросы Delphi | 0 | 15.06.2008 11:46 |