Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.72/25: Рейтинг темы: голосов - 25, средняя оценка - 4.72
2 / 2 / 0
Регистрация: 06.08.2013
Сообщений: 50
1

Алгоритм автоматического сбора "пятнашек"

09.10.2015, 19:54. Просмотров 4755. Ответов 8
Метки нет (Все метки)


Программу, в ее стандартном виде(для пользователя) я написал. Теперь нужно прикрутить возможность автоматической сборки игры машиной. Хочу узнать, где можно найти информацию/алгоритмы, для реализации данной задачи?!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.10.2015, 19:54
Ответы с готовыми решениями:

Дан массив строк: "red", "green", "black", "white", "blue". Запишите в файл элементы массива построчно (в новой строке)
пишу так но не помогает: static void Main(string args) { string...

Описать класс "поезд", содержащий поля "пункт назначения", "номер поезда", "время отправления"
Помогите пожалуйста с классом Описать класс «поезд», содержащий следующие закрытые поля:...

Построить иерархию классов "Студент", "преподаватель", "персона", "заведующий кафедрой"
Построить иерархию классов: Студент, преподаватель, персона, заведующий кафедрой 1) Разработать...

Проблема при сравнении: "Оператор ">" не может применяться к операндам типа "Т" и "Т""
Добрый день , пишу сортировку , все делаю на основе Т , но вот в чем проблемма public class...

__________________
Помогаю в написании студенческих работ здесь.
Записывайтесь на профессиональные курсы С#-разработчиков‌
8
1 / 1 / 2
Регистрация: 16.06.2014
Сообщений: 70
09.10.2015, 20:45 2
Вот интересный способ:

http://uggway.ru/?drv=view&art=90

Написано на паскале, но разобраться можно.
0
162 / 101 / 30
Регистрация: 19.01.2013
Сообщений: 821
10.10.2015, 07:59 3
Посмотрите как вообще решаются эти задачи. в книге перельман живая математика об этом написано. Там собственно все задачи 15ек сводятся к двум случаям: решаемому и принципиально не решаемому. Это зачисит но количества цифр находящихся не на своих местах. По моему если это кол-во чётно, то задача решаема, если нет- то не решаема. т.е. в конце вы получите 1 2 ... 12 13 15 14 и никак по другому. Обратите на это внимание.
0
2 / 2 / 0
Регистрация: 06.08.2013
Сообщений: 50
10.10.2015, 09:20  [ТС] 4
Насколько я понял, там берется не кол-во цифр, находящихся не на своем месте, а расстояние каждой цифры от своего правильного места ("беспорядок"). И если сумма таких беспорядков четная, то задача решаема, если нечетная - нерешаемая. Т.е. вначале нужно еще организовать проверку на это условие.
0
2508 / 1129 / 582
Регистрация: 07.06.2014
Сообщений: 3,281
10.10.2015, 10:36 5
Цитата Сообщение от dan24 Посмотреть сообщение
Это зачисит но количества цифр находящихся не на своих местах. По моему если это кол-во чётно, то задача решаема,
не цифр, а чисел. но суть не в этом.
ты сам себе противоречишь
если это так, тогда скажи, для твоего примера:
1 2 3 4 5 6 7 8 9 10 11 12 13 15 14
сколько плашек стоит не на своём месте?
Это число чётно? Задача имеет решение?
только без обид! Платон мне друг, но истина дороже...

погуглил. пишут, что должно быть число инверсий чётное.
число инверсий можно посчитать так:

код на псевдо языке:
Код
inv = 0   ! inv - число инверсий
для i = 1 до 14
  для j = i+1 до 15
    если фишки[i] > фишка[j] то inc(inv)
если число инверсий чётное, то расстановка решаема,
если число инверсий нечётное, то решений нет.
0
2 / 2 / 0
Регистрация: 06.08.2013
Сообщений: 50
10.10.2015, 10:50  [ТС] 6
В приведенном тобой примере показано конечное положение для начальных позиций, имеющих нечетное кол-во "беспорядков"/инверсий. Как я понял, задачу надо решать с помощью эвристического поиска.
0
2508 / 1129 / 582
Регистрация: 07.06.2014
Сообщений: 3,281
10.10.2015, 10:57 7
Цитата Сообщение от cruim Посмотреть сообщение
В приведенном тобой примере показано конечное положение для начальных позиций, имеющих нечетное кол-во "беспорядков"/инверсий.
прости, я тебя не понял.
можешь пояснить, что ты имел в виду?! Или хотя бы расшифруй "конечное положение для начальных позиций"?
0
2 / 2 / 0
Регистрация: 06.08.2013
Сообщений: 50
10.10.2015, 11:17  [ТС] 8
имеем рандомное расположение пятнашек, для одних позиций, конечным положением будет 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15, для других 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14. конечное положение(в моем понимании), это при котором дальнейшее улучшение позиции не представляется возможным(не имеет смысла).
0
2508 / 1129 / 582
Регистрация: 07.06.2014
Сообщений: 3,281
10.10.2015, 11:55 9
cruim, помни про бритву Оккама, не надо плодить сущности!
я же дал конкретный, простой, работающий алгоритм.
заносишь значения пятнашек в простой линейный массив, считаешь по предложенному алгоритму (фактически это простой готовый код) некое число.
если это число получилось чётное, решение есть, если нечётное - решения нет.
всё просто.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.10.2015, 11:55

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

Методом вычислить тип треугольника: "не существует", "тупоугольный", "прямоугольный", "остроугольный"
Помогите пожалуйста С помощью метода вычислить тип треугольника::cry: 1) если первый параметр...

Напишите программу, которая подсчитывает, сколько учащихся получило "2", "3", "4" и "5"
Помогите, пожалуйста, с решением следующей задачи: учащиеся сдают экзамены по нескольким...

Составить программу по управлению манипулятором "мышь". Выбор типа курсора организовать по нажатию на клавиши "q","w","r
Составить программу по управлению манипулятором "мышь". Выбор типа курсора организовать по нажатию...

Поиск в массиве. Ошибка "Оператор "&&" не может применяться к операндам типа "bool" и "double""
Найти номер последнего минимального элемента среди положительных четных элементов, лежащих правее...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.