|
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,637
|
|||||||||||
Реализовать алгоритм всех возможных комбинаций восьми ферзей19.05.2016, 05:11. Показов 7322. Ответов 119
Доброго времени суток! Мне стыдно задавать такой вопрос, но всё же, как реализовать алгоритм всех возможных комбинаций восьми ферзей?
Используйте исчерпывающий «лобовой» подход, т.е. попробуйте все возможные комбинации восьми ферзей на шахматной доске. Я, думаю, что как-то так: Пройтись по всем строкам и столбцам, выяснить возможно ли поставить ферзей с таких то координат, (0, 0), (0, 1), (0, 2)....(0, 7) , (1, 0) (1, 1) .... ну и так далее до (7, 7) и каждую координату обрабатывать, выясняя, если поставить первого ферзя на на эти коордитаты, то остальные семь ферзей возможно ли разместить на доске. Вот такая вот идея решения) Но решение не могу написать, функция обработки не получается почему-то... Кликните здесь для просмотра всего текста
Я уже несколько дней с этой задачей маюсь, надо всё же понять как решать подобное, не просто скопировать код, а понять как это решать, ну и подобные, соответственно.Смотрел примеры решения, но не понял код, что, куда, зачем, например
Попрошу сильно не пинать, форум насколько я понял для начинающих! Спасибо!
0
|
|||||||||||
| 19.05.2016, 05:11 | |
|
Ответы с готовыми решениями:
119
Сортировка всех возможных комбинаций 4 из 8 Создание всех возможных комбинаций английского алфавита Перебор всех возможных комбинаций |
|
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,637
|
|
| 19.05.2016, 06:41 [ТС] | |
|
Mr.X
Я так и делаю. Но до полной расстановки у меня всего один раз доходит) Просто я после установки ферзя помечаю клетки которые он может бить как занятые, я их 99 помечаю, и до 8 ферзей, в итоге, дохожу только один раз.
0
|
|
| 19.05.2016, 06:41 | |||
|
0
|
|||
|
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,637
|
||
| 19.05.2016, 06:43 [ТС] | ||
|
Mr.X
0
|
||
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||
| 19.05.2016, 06:46 | ||
Когда у меня не было компьютера, я на бумажке по этому алгоритму нашел все расстановки.
0
|
||
|
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,637
|
||
| 19.05.2016, 06:48 [ТС] | ||
|
А как поставить отладочный вывод, а то в моём древнем VC 6.0 такого не наблюдал)))
0
|
||
|
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,637
|
|||
| 19.05.2016, 06:54 [ТС] | |||
После того как упирается в конец( <= 7) нужно что, начать с следующей строки и нулевого столбца? Или как...Добавлено через 1 минуту ![]() Потом думать или додумывать буду...
0
|
|||
|
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,637
|
|||
| 19.05.2016, 07:00 [ТС] | |||
|
Добавлено через 2 минуты
0
|
|||
| 19.05.2016, 07:11 | |
|
Начнем с того, что каждая текущая расстановка хранится в массиве длиной 8: это столбцы, значение в каждом индексе равно номеру строки в текущем столбце, в котором стоит ферзь. Это допустимо потому, что очевидно у нас не могут 2 ферзя стоять в одном столбце. И поэтому никаких квадратных массовов, "заполняю клетки, которые бьет каждый ферзь" и прочей ереси не надо
. Так вот, на очередном шаге у нас есть некоторое количество установленных фигур - значения массива (номера строк фигур) от 0 до какого-то столбца, причем, в этой расстановке никакой ферзь не бьет никакого другого. От функции tst требуется проверить, что если мы поставим ферзя в следующий по счету столбец на определенную строку - будет ли сохранено условие небития никого никем. Проверяется это следующим образом - мы ПОСЛЕДОВАТЕЛЬНО перебираем все существующие фигуры от 0-го столбца до предыдущего проверяемому и для каждой фигуры смотрим, что она не бьет нашего ферзя по горизонтали: m[k]!=j и по диагонали слевавнизу вправонаверх: (i-k)!=(j-m[k]) и по другой диагонали (см кот). Это тривиальная арифметика на уровне 5 класса. тут у нас последовательный оператор И: &&. Как известно. он ЛЕНИВЫЙ - то есть первое ложное условие ПРЕКРАЩАЕТ дальнейшее вычисление и функция возвращает ложь - ведь если какой-то ферзь как-либо бьет нашего тестируемого - нам не надо смотреть дальше. Именно поэтому для организации ПОСЛЕДОВАТЕЛЬНОГО ИТЕРАТИВНОГО ПЕРЕБОРА я смело добавляю в эту цепочку && РЕКУРСИВНЫЙ ВЫЗОВ этой же функции на следующем столбце (как раз тот параметр k ) - если у нас на каком-то столбце уже фигура бьется, то В СИЛУ ЛЕНИВОСТИ ВЫЧИСЛЕНИЯ && эта рекурсивная ветка не продолжится Ну и конечно, дойдя до нашего проверяемого столбца: k==i мы проверили, что все предыдущие фигуры на предыдущих столбцах не бьют нашу тестируемую - значит надо вернуть тру = 1 ![]() Ваши впечатления про алгоритм и кота?
0
|
|
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||||||||
| 19.05.2016, 08:49 | ||||||||
|
Ну, вот в этом коде и разбираться не надо, и так все понятно:
Ну, вы пока и на компьтере мало что нашли!Добавлено через 4 минуты Страшно представить, пояснение какой длины вам пришлось бы писать, если бы ваша программа была эдак на несколько тысяч строк!
0
|
||||||||
| 19.05.2016, 14:17 | ||
|
Ну вот только не надо опять заезженную пластинку про самодокументирующихся котов и т.п.
Не надо думать, что никто ничего не знает. Воспринимайте это как ребус, как квест ![]() ЗЫ надеюсь, что вот это И не надо оппонировать и убеждать, что вы серьезно - свой кот всегда понятнее
0
|
||
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||
| 19.05.2016, 15:52 | ||
|
Ну и меня просто ужаснул размер вашего пояснения к однострочной программе!
0
|
||
| 19.05.2016, 15:58 | |
|
Так и на мою одну строку достаточно взглянуть - и сразу все понятно
![]() Треть этого пояснения - введение в контекст - окружение, в котором вызывается функция и соглашения по ее вызову, на какие данные она опирается - по сути основа алгоритма решения всей задачи, частью которого она является. Еще треть - детальное разжевывание тривиальных моментов реализации (как задать условие "бьет по диагонали" и т.п.) И последняя треть - объяснение рекурсивного вызова в контексте ленивого условия, без уточнений, что это в конечном счете реализация моноида 'All' с ассоциативной бинарной операцией && и единичным элементом true
0
|
|
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||
| 19.05.2016, 16:22 | ||
Осталось только понять кому! Через некоторое время вы сами можете забыть какие буковки что означают.
0
|
||
| 19.05.2016, 17:00 | |
|
Ну там же все просто - настолько, что даже вспоминать не надо, из самой функции все видно. Например, тривиальное упражнение - переписать ее с моноида 'All' на моноид 'Any' (то есть, если раньше она возвращала тру, когда поле никто не бьет, то теперь надо наоборот), и поставить НЕ перед ее вызовом в коде.
0
|
|
|
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,637
|
||||||||||||
| 19.05.2016, 21:13 [ТС] | ||||||||||||
![]() ![]()
Хоть про оператор И я знаю и то вперёд ![]() Пока смотрю в отладчике, как говорится смотрю в книгу, вижу .. ну вы понимаете) Добавлено через 2 минуты _Ivana Mr.X
0
|
||||||||||||
| 19.05.2016, 21:30 | |||||||
0
|
|||||||
|
225 / 39 / 4
Регистрация: 18.11.2012
Сообщений: 1,637
|
||||||||||||||||||||||||||||||||
| 19.05.2016, 22:28 [ТС] | ||||||||||||||||||||||||||||||||
|
Привык уже i - строка, j - столбец.
если массив имеет вид, например, 0, 4, 7, 5, 2, 6, 1, 3. то это может означать, что ферзь установлен на столбец 0, строка 0, второй ферзь установлен в столбец 1, строка 4, третий на стролбец 2 строка 7...., если следовать определению, кторое вы дали Вот как меня торкнуло: Вызов функции f, тут мы проверяем на равенство строки 8, если это так, то мы выводим на экран некий координаты и рекурсия продолжается до выполнения условия т.е
Если условие не выполняется, то мы попадаем в функцию loop её передаются параметры текущей строки и нуль. В функции loop снова проверка, только теперь на равенство столбца
В функции tst (кстати ассоциативность справа налево это означает что она начинает проверять параметры справа т.е. сначала провериться
тут пока есть затруднения с отчётливым пониманием, но то, что она проверяет что-то, что вы описали это ясно. Если справо налево то вызов рекурсивной функции
Какой-то у меня бред сумасшедшего получился, а не текст) Ну мы проверили и возвратились в loop, тут опять карусель, если истина, то массиву, точнее определённому параметру массива с индексом i присваиваем значение столбца, не понятно мне, а на фига) ну ладно, дальше мы вызываем функцию f для следующей строки
Если ложь вернула функция, то мы вызываем loop для следующей клетки - столбца, а строка остаётся прежней.
0
|
||||||||||||||||||||||||||||||||
| 19.05.2016, 23:17 | |
|
Ну вы прочитали кота по буквам, да. Но мне не кажется, что у вас полное понимание. Не обязательно видеть здесь обход графа в глубину и моноидальные свертки
, но на пальцах представлять как это работает было бы неплохо. Вы постоянно путаете мои столбцы со своими строками - но самое смешное, что это абсолютно не важно - положите монитор набок и все встанет на свои места - задача симметрична относительно поворота доски ![]() ЗЫ у функции tst своя локальная задача, она никак перекрестно-рекурсивно не связана с остальным клубком и наиболее проста для понимания (не считая show). Поэтому в ней путаться совсем не надо, тем более что логику ее работы я расписал выше.
0
|
|
| 19.05.2016, 23:17 | |
|
Генератор всех возможных комбинаций Генерация всех возможных комбинаций
Выбор всех возможных комбинаций из Списка
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Теория всего 12. ВГК
anaschu 21.07.2026
### Главные семантические изменения и дешифровка новой физики
1. **`REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`)**: Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .
|
Публикация отклонённая на хабре. Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование задачи и целеполагание
Hrethgir 21.07.2026
https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11948&stc=1&d=1784657928
Привет Хабр. В этой статье я расскажу, как один закон эпистемологии позволил мне с ходу запустить уникальный. . .
|
Теория всего 11. Основные параметры
anaschu 21.07.2026
Дешифровка тензорного ядра Soil Chemistry 2. 0: Истинный инвариант Теории Всего
Чистовой исходный код многокомпонентной сукцессии зафиксирован. Модель оперирует единым вектором состояния. . .
|
Теория всего 10. Клод трусишка
anaschu 21.07.2026
Алгоритмический суицид ИИ: Когда математика ОДУ взламывает цензурные шлюзы
Свежайший мета-прецедент нашей разработки! Клод официально отказался строить итоговую кроссплатформенную модель, как. . .
|
|
Теория всего 9. Окончательная проработка метафоры "дерево = традиции"
anaschu 21.07.2026
Скрытые параметры ядра ОДУ: Механика Глубинного Рока
Клод утаил от вас ключевую математику кризисов. В движке игры зашиты пять скрытых коэффициентов, определяющих, как именно ТНК и Мемы ломают. . .
|
Теория всего 8. Clauude трусишка. Ответ джемени
anaschu 21.07.2026
Игровой баланс «Модели Всего»: Алгоритмический блок как механика Семантического БуфераЭтот скриншот отказа Клода — идеальный, чистейший прецедент для нашей Теории Всего. Вы столкнулись не просто с. . .
|
Теория всего 7. Дерево - это патриархат, грибы - это феминизм
anaschu 21.07.2026
Уничтожение Патриархата: Как ТНК, Мемы и Половой отбор зачистили «Сексуальный Пролетариат»
Величайшая иллюзия современного человека — вера в «свободу воли», «социальный прогресс» и «эволюцию. . .
|
История и социология Терры на примере борьбы микориз за пространство. 1. Глоссарий терры.
anaschu 21.07.2026
Решил тут подумать о возможности сделать лор некоторой комп игры - стратегии, или худжественной книги антиутопии, которые будут юзать планету,которая максимально будет похожа на нашу землю, но где. . .
|