Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.53/17: Рейтинг темы: голосов - 17, средняя оценка - 4.53
0 / 0 / 0
Регистрация: 14.04.2009
Сообщений: 19

Активный Эскадрон(Задача)

14.04.2009, 19:21. Показов 4229. Ответов 37
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте товарищи
Прошу помочь в задаче
Сам очень долго думал, носил наброски преподавателю, но всё оказывалось не то
единстенную подсказку которую я услышал это было, что нада строить программну, не отталкиваясь от ответа.
Текст задачи
Из какого наименьшего числа коней можно создать активный эскадрон?
Пояснения:
Эскадрон -- Группа коней , размещенный на бесконечной шахметной доске
Активный Эскадрон -- это эскадрон, который может сделать любое число ходов на шахматной доске и занять одним из своих коней любое поле доски, не оставляя ни на один ход ни одного коня без защиты.
_http://sputnik.master-telecom.ru/Seans/Kvant/1978/11/p37.htm -- Задача(внизу)

_http://sputnik.master-telecom.ru/Seans/Kvant/1978/12/p61.htm -- Ответ

буду рад любой подсказке и напутствию, т.к. уже давно не посещало идей по этой задаче
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
14.04.2009, 19:21
Ответы с готовыми решениями:

Ловим активный select и ставим, что он активный
есть select с двумя option.Задание - нужно сделать так чтобы по нажатию на один option с "ближайшее время "не чего не...

Access отчислить студента ( активный/ не активный )
Вот и добрались мы до истины, и заглохли....https://www.cyberforum.ru/ms-access/thread1706793.html Задача - Нужно отчислить студента:...

Активный спинбокс
Доброго времени суток, как увидел сразу пришла идея в голову, но после я понял что это не так работает. Можно ли узнать какой сейчас...

37
0 / 0 / 0
Регистрация: 14.04.2009
Сообщений: 19
07.05.2009, 20:42  [ТС]
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от Yurii_74 Посмотреть сообщение
Весь прикол в том, что кони должны ходить последовательно. Нужно строить граф состояний, при этом состояние характеризуется положением коней и номером коня, который должен ходить. При этом повороты/отражения/перемещения эскадрона не должны считаться за разные состояния. Если после некоторого числа ходов мы вернемся в исходное состояние, то решение найдено. Поиск в ширину неплохо подойдет для решения.

P.S.: Забыл сказать, что решение существует и для конечного кол-ва коней находится за конечное число итераций, так как число состояний весьма ограничено.
Очень сложно графы..
ты я думаю догадался какой у меня уровень посмотрев код моей программы
почему то кстати его все игнорируют, может его никто не читал? xD
но я все равно в него верю
0
paladin
 Аватар для Yurii_74
286 / 187 / 7
Регистрация: 25.02.2009
Сообщений: 589
08.05.2009, 13:13
Цитата Сообщение от JoSkream Посмотреть сообщение
Очень сложно графы..
ты я думаю догадался какой у меня уровень посмотрев код моей программы
Все же лучше будет изучить работу с указателями, классы, поиск в глубину/ширину. Реализовать класс "направленный граф", класс "состояние" и переопределить операцию сравнения для него, если, конечно, на это еще есть время.

Замечание по программе:
сравнение осуществляется с помощью ==, у тебя же везде в проверках идет присваивание.
C
1
2
if (r=1) //r присваивается значение 1, условие всегда выполняется (насколько я помню)
if (r==1) //правильное сравнение
Добавлено через 6 часов 45 минут 51 секунду

В программе очень много ошибок:

C
1
2
3
4
for(a=0, a<90, a++); //пустой цикл, наверно надо убрать точку с запятой
c=a++2; //это равносильно следующему: c = a + 2; a = a + 1; 
//думается мне, что задумывалось нечто наподобие c = a + 2;
r == random(7); //снова сравнение
И множество им подобных. Может быть после исправления их всех прога и заработает? Хотя я не уверен. Больно уж непонятно, как в ней все должно делаться.
0
0 / 0 / 0
Регистрация: 14.04.2009
Сообщений: 19
19.05.2009, 12:48  [ТС]
Up! к теме,
долго думал но к сожалению не нашел пути к решению
помогите пожалуйста

Добавлено через 18 минут 43 секунды
Цитата Сообщение от Yurii_74 Посмотреть сообщение
Все же лучше будет изучить работу с указателями, классы, поиск в глубину/ширину. Реализовать класс "направленный граф", класс "состояние" и переопределить операцию сравнения для него, если, конечно, на это еще есть время.

Замечание по программе:
сравнение осуществляется с помощью ==, у тебя же везде в проверках идет присваивание.
C
1
2
if (r=1) //r присваивается значение 1, условие всегда выполняется (насколько я помню)
if (r==1) //правильное сравнение
Добавлено через 6 часов 45 минут 51 секунду

В программе очень много ошибок:

C
1
2
3
4
for(a=0, a<90, a++); //пустой цикл, наверно надо убрать точку с запятой
c=a++2; //это равносильно следующему: c = a + 2; a = a + 1; 
//думается мне, что задумывалось нечто наподобие c = a + 2;
r == random(7); //снова сравнение
И множество им подобных. Может быть после исправления их всех прога и заработает? Хотя я не уверен. Больно уж непонятно, как в ней все должно делаться.
спасибо за замечания,
на самом деле код простой
там 80% копипаст с минимальными исправлениями
0
0 / 0 / 0
Регистрация: 14.04.2009
Сообщений: 19
19.07.2009, 10:08  [ТС]
Внимание, ищю Человека который напигет мне вышеуказанную задачю на С++, а так же составить блок схему и математическое решение за деньги
icq 230197595
0
0 / 0 / 0
Регистрация: 14.04.2009
Сообщений: 19
28.07.2009, 11:26  [ТС]
еще раз поднимаю тему
не могу понять как доказываеться активность эскадрона.
я понял чтобы доказать активность нужно доказать что эскадрон может сделать ход на C-З и С-В(по диоганали) с переворотом(по оси y)
и может сдлеть ход на З или В тоже с переворотом
но как доказать что он может сделать такие ходы я не могу, помогите пожалуйста
0
paladin
 Аватар для Yurii_74
286 / 187 / 7
Регистрация: 25.02.2009
Сообщений: 589
28.07.2009, 12:02
Доказывается полным перебором.
Сначала ставим на доску двух коней, защищающих друг друга (всего один вариант расстановки), пытаемся сходить по правилам. Не должно получиться. Вариант с 2 конями отпадает. Перебираем варианты с 3мя (разные варианты расстановки + разный порядок) поиском вглубину. То же самое для 4 и 5 коней. Саму прогу писать не буду (нет времени на написание немаленького количества кода, нет компилятора для проверки решения, нет в самой задаче ничего нового и действительно интересного). Обратись в соответствующий раздел этого форума с сылкой на эту тему. За деньги точно найдутся желающие помочь.

P.S.: модераторам: прошу не считать отсылку в "заказ программ и что-то там еще" нарушением. Человек сам это уже предложил.
0
0 / 0 / 0
Регистрация: 14.04.2009
Сообщений: 19
28.07.2009, 12:37  [ТС]
ты слегка не понял вопроса
у меня есть эскадрон, я знаю что он активен, а доказать этого не могу
0
paladin
 Аватар для Yurii_74
286 / 187 / 7
Регистрация: 25.02.2009
Сообщений: 589
28.07.2009, 13:37
Нужно показать, что состояние через несколько ходов полностью повторяет некоторое предыдущее.
Введи операцию сравнения состояний: конь, который должен сделать ход всегда стоит в определенной точке: (0, 0) например. Проверить 4 поворота + их отражения со всеми предыдущими состояниями, совпадать должны кони + порядок, в котором они ходят.
0
0 / 0 / 0
Регистрация: 14.04.2009
Сообщений: 19
28.07.2009, 17:30  [ТС]
все слишком просто у тебя
если доказывать на совесть, то нада доказывать что Активный эскадрон может встать одним из своих коней на любую точку бесконечной шахматной доски
а то что он может сдлатьход это не доказательство его активности,
ниже приведу свой алгоритм , пожалуйста отцените

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
для доказательства активности эскадрона используем следующие леммы:
1)Эскадрон активен, если он может сдвинуться со своего начального положение на 1 клетку на C-B или C-З  а так же на 1 клетку на В или на З, при этом перевернувшить (ось вращение OX)
2)активный Эскадрон может двигаться только на 1 клетку на C-B или C-З  а так же на 1 клетку на В или на З, при этом перевернувшить (ось вращение OX), и никуда больше, все остальные вариации ходов его коней приведут к тупиковой ситуации
 
итак, при каждом новом положении коней эскадрон нуждаеться в проверке на активность
не забывая про 2 леммы  эскадрон начинает перемещаться
в последствии перемещения он может переместиться только в 2 положения (см. Лемму2)
и переместившись в 1 из положений мы получаем половину доказательства(получили доказательство 1,1)
запомнив это положение мы ставим эскадрон в первоначальное положение 
и проделываем ту же операцию до тех пор, пока не получим второе положение(дказательство 1,2)
при поиске доказательства 1,2 мы не повторяем ходы эскадрона когда искали доказательство 1,1
\\ПОяснение разница как сходит эскадрон в доказательство 1,1 или в доказательство 1,2 в самом первом ходу, так что смело исключаем все последующие ходы
и получив 2 доказательства мы смело заявляем что эскадрон активен
 
цикл увеличения количества коней
{
цикл расстановки коней
{
цикл ходов коней
{
проверка на активность эскадрона
{
копирование матрицы четырежды(создание еще четырех таких же матриц)
корректировка первой матрицы: замена координат всех коней на координаты x+1 y+1, (то есть до этого были координаты N и M то сейчас N+1;M+1)
корректировка второй матрицы: замена координат всех коней на координаты x-1 y+1(аналогично как при корректировке первой матрицы)
корректировка третей матрицы: замена координат всех коней на координаты x+1 y+1(аналогично как при корректировке первой матрицы)
корректировка четвертой матрицы: замена координат всех коней на координаты x+1 y+1(аналогично как при корректировке первой матрицы)
цикл хода коней // естветсвенно по всем правилам типа ходы не должны повторяться и ходы откатываються если все заходит в тупик
{
после каждой новой позиции идет сравнение с четырьмя другими матрицами
если есть совпадение отлично 0,5 доказательства готово
}
в противном случае
{ 
мы возвращаемся к пердыдущим переборам и выходим из проверка данного эскадрона
}
// следующий шаг я не знаю как осуществить програмно,
// вообщем нада чтобы первым ходил не тот конь который который был в первой части доказательства (а то мы докажем снова первую часть)
// а именно другой конь, чтобы доказать вторую часть
цикл хода коней
{
 после каждой новой позиции идет сравнение с четырьмя другими матрицами
и когда снова мы получаем совпадение то мы с уверенностью можем сказать что этот эскадрон активен
}
в противном случае
{ 
мы возвращаемся к пердыдущим переборам и выходим из проверка данного эскадрона
}
}
}
}
}
}
}
}
 
 
 
этот алгоритм проверки расчитан на 1 единственный активный эскадрон
я давал картинку, дак вот он изображен на картинке #1 
и еще меня оч смущает насчет пункта где должен ходить другой конь, а не этот же
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
28.07.2009, 21:25
у меня есть эскадрон, я знаю что он активен, а доказать этого не могу
Строго говоря если не можешь доказать, значит его нет или он не активен
0
paladin
 Аватар для Yurii_74
286 / 187 / 7
Регистрация: 25.02.2009
Сообщений: 589
28.07.2009, 21:53
Сорри. Невнимательно прочитал условие.
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
28.07.2009, 21:59
По ссылке в самом первом посте ничего про то, что он должен быть способен переместиться в любую точку не сказано
Там написано:
Эскадрон назовем активным, если, перемещаясь по шахматной доске, он может занять одним из своих коней любое наперед заданное поле.
0
paladin
 Аватар для Yurii_74
286 / 187 / 7
Регистрация: 25.02.2009
Сообщений: 589
28.07.2009, 22:07
Только вот в приведенном решении на бесконечной доске не получится уйти левее. По крайней мере той же последовательностью коней. Получается, что эскадрон сможет покрыть только половину бесконечной доски.
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
28.07.2009, 23:46
Тут они немного промахнились - не нарисовали как именно уходить влево.
Но очевидно что приведенный эскадрон может уходить влево по доске.
В 1 и 5a есть две клетки поля, которые заняты конями на обоих позициях. Если смотреть на 1, то это самая верхняя клетка и клетка вправо вниз от нее.
В силу симметричности фигуры очевидно, что из позиции 1 можно перейти в позицию где неподвижными будут две клетки: самая верхняя клетка и клетка влево вниз от нее. Сделав еще один аналогичный (аналогичный переходу 1->5a) переход влево мы получим эскадрон, находящийся ровно на две клетки левее.
Аналогично из позиции 1 можно перейти в 5a и оттуда перейти в другую позицию - ровно на две клетки правее.
Таким образом мы можем двигать эскадрон на две клетки влево или вправо.
Так как мы можем двигать эскадрон вверх и вниз, то не важно, что через две клетки.
Этого достаточно чтобы покрыть все бесконечное поле.
1
paladin
 Аватар для Yurii_74
286 / 187 / 7
Регистрация: 25.02.2009
Сообщений: 589
29.07.2009, 07:21
Точно. Вчера мне следовало бы пребывать в спящем состоянии, нежели писать неверные суждения на форуме. Извините за ересь. Тогда нужно построить граф состояний + к каждому состоянию варианты перехода в такое же (или зеркальное) с сохранением информации о переносе (т. е. для перехода 1-5а запись примерно такая: 1; -1; mirrored; 90, для перехода 5а-10: -1; -2; mirrored; 90). Получим некий базис по которому в совокупности с расположением коней уже можно попытаться сделать хоть какие-то выводы.

Добавлено через 6 минут 46 секунд
Также при попадании в похожее состояние дальше копать уже не нужно. Возвращаемся на шаг назад и перебираем другие варианты. И так до тех пор пока не вернемся к начальному состоянию, из которого уже нельзя сделать новых уникальных ходов.
0
0 / 0 / 0
Регистрация: 14.04.2009
Сообщений: 19
30.07.2009, 18:42  [ТС]
Цитата Сообщение от Yurii_74 Посмотреть сообщение
Точно. Вчера мне следовало бы пребывать в спящем состоянии, нежели писать неверные суждения на форуме. Извините за ересь. Тогда нужно построить граф состояний + к каждому состоянию варианты перехода в такое же (или зеркальное) с сохранением информации о переносе (т. е. для перехода 1-5а запись примерно такая: 1; -1; mirrored; 90, для перехода 5а-10: -1; -2; mirrored; 90). Получим некий базис по которому в совокупности с расположением коней уже можно попытаться сделать хоть какие-то выводы.

Добавлено через 6 минут 46 секунд
Также при попадании в похожее состояние дальше копать уже не нужно. Возвращаемся на шаг назад и перебираем другие варианты. И так до тех пор пока не вернемся к начальному состоянию, из которого уже нельзя сделать новых уникальных ходов.
Это конечно все замечательно, но вот простому смерному непонятно
мне нужно доказательство в виде псевдокода программы
ЗЫ
вот над этим кодом я мучаюсь, в нем неправильная часть проверки на активность
http://codepad.org/IwD09TWM
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
30.07.2009, 18:47
Там было написано, что активный эскадрон - не менее 5 фигур.
У тебя в программе получилось, что есть активные эскадроны на 3 и 4 фигуры.
0
0 / 0 / 0
Регистрация: 14.04.2009
Сообщений: 19
30.07.2009, 19:26  [ТС]
Цитата Сообщение от odip Посмотреть сообщение
Там было написано, что активный эскадрон - не менее 5 фигур.
У тебя в программе получилось, что есть активные эскадроны на 3 и 4 фигуры.
я написал что там неправильная часть проверки на активность
смотри мой последний пост
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
30.07.2009, 19:26

Активный класс ul li?
Всем привет! Помогите пожалуйста) В общем как мне сделать так как на скрине? (ниже). 1-й скрин как сейчас, 2-й как нужно сделать...help)...

Активный фильтр на ОУ
Добрый день. Помогите с расчётом данного операционного усилителя, конкретно нужно построить АЧХ и ФЧХ и написать передаточную функцию. ...

Активный Label
Доброе утро! У меня такой вопросик: у меня 2 форме в делфи и на второй мне нужно поставить Label и сделать так чтобы при нажатии на него...

Активный таб
Ещё раз доброго дня, если можно, хочу продолжить тему этого поста А собственно, нашел в шаблоне компонента строки и, собственно,...

активный текст
Всем привет вот что имеется &lt;html&gt; &lt;head&gt; &lt;title&gt;Stabcoins Time Is Money&lt;/title&gt; &lt;style&gt; body { ...


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

Или воспользуйтесь поиском по форуму:
38
Ответ Создать тему
Новые блоги и статьи
Про "Windows must die!"
kumehtar 04.11.2026
Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .
Красочные поля с номером страницы svg+background-image
russiannick 04.11.2026
Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .
Вступаем в новую фазу генерации favicons, векторную.
russiannick 02.11.2026
Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .
Генератор паролей (вариант №4)
Maks 01.11.2026
После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков | 1 l I;. . .
Генератор паролей (вариант №3)
Maks 30.10.2026
Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .
Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени)
zorxor 30.10.2026
Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .
За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ)
zorxor 30.10.2026
Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .
Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени)
zorxor 30.10.2026
Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru