ПОМОГИТЕ СОСТАВИТЬ АЛГОРИТМ "ХОД КОНЯ КРУГОМ"!

← →
Konstantin555 © (2006-09-27 23:05) [0]

Если визуализировать ход коня кругом, то это будет так (начиная с 11 по часовой стрелке):
18 28 38 48 58 68 78 88
17 27 37 47 57 67 77 87
16 26 36 46 56 66 76 86
15 25 35 45 55 65 75 85
14 24 34 44 54 64 74 84
13 23 33 43 53 63 73 83
12 22 32 42 52 62 72 82
11 21 31 41 51 61 71 81

Необходимо написать алгоритм (НЕ КОД!)
А просто метод решения данной задачи!

HELP!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

← →
Konstantin555 © (2006-09-27 23:09) [1]

Добавлю - это изображена шахматная доска
Конь ходит так:
11
23
15
27
48
67
88
76
84
72
51
32

← →
ArtemESC © (2006-09-27 23:18) [2]

из заданной точки?

← →
TUser © (2006-09-27 23:19) [3]

Задача-то какая? Конь должен вернуться в исходную позицию - это я понял. Но есть тривиальное решение - любой ход, потом ход назад. Опиши подробно условия, ... или скопируй откуда взял задачу.

← →
Konstantin555 © (2006-09-27 23:22) [4]

ArtemESC © (27.09.06 23:18) [2] из заданной точки?
Не сказано, возможно что да

> TUser © (27.09.06 23:19) [3]
> Задача-то какая? Конь должен вернуться в исходную позицию
> - это я понял. Но есть тривиальное решение - любой ход,
> потом ход назад. Опиши подробно условия, ... или скопируй
> откуда взял задачу.

Задача - составить алгоритм "Ход коня кругом"
ВСЁ! Больше никакого условия!

Задачу дал препод

← →
ArtemESC © (2006-09-27 23:22) [5]

Вроде бы понял, рассмотрим:
18 28 38 48 58 68 78 88
17 27 37 47 57 67 77 87
16 26 36 46 56 66 76 86
15 25 35 45 55 65 75 85
14 24 34 44 54 64 74 84
13 23 33 43 53 63 73 83
12 22 32 42 52 62 72 82
11 21 31 41 51 61 71 81

из 11 в 23 у нас 2 клетки вверх и вправо - 3 шага, потом по аналогии, ищещь такой путь до исходной клетки, длина которого кратна 3 ...

← →
ArtemESC © (2006-09-27 23:26) [6]

Вообще бред какой-то написал...

Скажи как задачу звучит полностью..

← →
Pavia © (2006-09-27 23:29) [7]

Рекурсивный метод. При каждом последующем ходе следует придерживаться условия, что бы выбранный ход был таков что бы конь выбирал как можно левый ход.
Вся доску можно разбить на 4 участка. Так вот в кажом кводрате нужно придерживаться своей стороны перебора вариантов.
18 28 38 48 58 68 78 88 17 27 37 47 57 67 77 87 16 26 36 46 56 66 76 86 15 25 35 45 55 65 75 85 14 24 34 44 54 64 74 84 13 23 33 43 53 63 73 83 12 22 32 42 52 62 72 82 11 21 31 41 51 61 71 81

← →
Pavia © (2006-09-27 23:32) [8]

> Скажи как задачу звучит полностью..

Объесняю, что требуется автора. конь ставится в клетку 11 за 64 хода конь должен обойти всю доску на 65 вернуться в исходную клетку. Задачу вывести путь коня. Обходить доску надо по кругу. Собственно решения тут два по часовой стрелки и против.

Еще можно обойти сначала один квадрат из 4 и так все 4 квадрата.

← →
Konstantin555 © (2006-09-27 23:36) [9]

> ArtemESC © (27.09.06 23:26) [6]
> Вообще бред какой-то написал...
>
> Скажи как задачу звучит полностью..

Название задачи в одну строчку - составить алгоритм "Ход коня кругом"

> Pavia © (27.09.06 23:29) [7]
> Рекурсивный метод. При каждом последующем ходе следует придерживаться
> условия, что бы выбранный ход был таков что бы конь выбирал
> как можно левый ход.
> Вся доску можно разбить на 4 участка. Так вот в кажом кводрате
> нужно придерживаться своей стороны перебора вариантов.
>
> 18 28 38 48 58 68 78 88
> 17 27 37 47 57 67 77 87
> 16 26 36 46 56 66 76 86
> 15 25 35 45 55 65 75 85
>
> 14 24 34 44 54 64 74 84
> 13 23 33 43 53 63 73 83
> 12 22 32 42 52 62 72 82
> 11 21 31 41 51 61 71 81

Согласен...

Такой алгоритм - сойдёт или нет?:
1) начало в клетке 11
2) цикл:
*перейти на 2 клетки вверх и на 1 клетку вправо
*перейти на 2 клетки вверх и на 1 клетку влево
3) цикл:
*перейти на 2 клетки вправо и на 1 клетку вверх
*перейти на 2 клетки вправо и на 1 клетку вниз
4) цикл:
*перейти на 2 клетки вниз и на 1 клетку влево
*перейти на 2 клетки вниз и на 1 клетку вправо
5) цикл:
*перейти на 2 клетки влево и на 1 клетку вниз
*перейти на 2 клетки влево и на 1 клетку вверх
6) стоп

← →
TUser © (2006-09-27 23:36) [10]

> Задача - составить алгоритм "Ход коня кругом"
> ВСЁ! Больше никакого условия!
>
> Задачу дал препод

Я уже смекнул, что не любимая девушка задачу тебе выдумала :)

Фтопку препода, котрый не может объяснить задачу. Или студента, который не может понять объяснения и донести его до форума, где просит совета.

Судя по тому, что некоторые уже врубились, - наверное не тебе первому ее (задачу эту) дают. Может общество разъяснит? Многие такие задачи сводятся к динамическому программированию. Или граф обходить как-нибудь.

← →
TUser © (2006-09-27 23:37) [11]

> Обходить доску надо по кругу.

Что это значит - не быть два раза на одной клетке (кроме первой, которая и последняя)?

← →
Konstantin555 © (2006-09-27 23:38) [12]

> Pavia © (27.09.06 23:32) [8]
>
> > Скажи как задачу звучит полностью..
>
> Объесняю, что требуется автора. конь ставится в клетку 11
> за 64 хода конь должен обойти всю доску на 65 вернуться
> в исходную клетку. Задачу вывести путь коня. Обходить доску
> надо по кругу. Собственно решения тут два по часовой стрелки
> и против.
>
> Еще можно обойти сначала один квадрат из 4 и так все 4 квадрата.
>

64 хода?? Ого... зачем обходить всю доску? Задание другое стоит - обойти конём шахматную доску кругом

> 64 хода?? Ого... зачем обходить всю доску? Задание другое стоит - обойти конём шахматную доску кругом

Вот и расскажи, чем ешение, данное в [3] - не круг? Что значит обойти доску кругом? Какой обход круглый, а какой - не круглый? Без этого нельзя решить задачу, т.к. задачи нет.

Зы. Допускаю, что это какая-нибудь общеизвестная задача, но некоторым она не известна.

> > Обходить доску надо по кругу.
>
> Что это значит - не быть два раза на одной клетке (кроме
> первой, которая и последняя)?

Да. Есть такое условие.
В обще задача обычна дается так есть доска нужно обойти ее конем на клетке на которой побывал вставть нельзя. Обойти значит побывать на кажой клетки доски.
Другой вариант нужно вернуться в исходную клетку.
Тут собственно даже подсказку дали- даже можно сказать алгоритм. Обходить кругом. Метод кругового обхода существует всего два. Так что ходы можно и записать. =) Правдо про круговой метод обхода читал дввно. Так что помню плохо.

> TUser © (27.09.06 23:36) [10]
> > Задача - составить алгоритм "Ход коня кругом"
> > ВСЁ! Больше никакого условия!
> >
> > Задачу дал препод
>
> Я уже смекнул, что не любимая девушка задачу тебе выдумала
> :)
>
> Фтопку препода, котрый не может объяснить задачу. Или студента,
> который не может понять объяснения и донести его до форума,
> где просит совета.
>
> Судя по тому, что некоторые уже врубились, - наверное не
> тебе первому ее (задачу эту) дают. Может общество разъяснит?
> Многие такие задачи сводятся к динамическому программированию.
> Или граф обходить как-нибудь.

> Фтопку препода, котрый не может объяснить задачу. - вернее всего %)

> TUser © (27.09.06 23:37) [11]
> > Обходить доску надо по кругу.
>
> Что это значит - не быть два раза на одной клетке (кроме
> первой, которая и последняя)?

Сам точно не знаю, но думаю что надо по кругу обойти доску и попасть в исходящую клетку

> Pavia © (27.09.06 23:43) [14]
>
> > > Обходить доску надо по кругу.
> >
> > Что это значит - не быть два раза на одной клетке (кроме
>
> > первой, которая и последняя)?
>
> Да. Есть такое условие.
> В обще задача обычна дается так есть доска нужно обойти
> ее конем на клетке на которой побывал вставть нельзя. Обойти
> значит побывать на кажой клетки доски.
> Другой вариант нужно вернуться в исходную клетку.
> Тут собственно даже подсказку дали- даже можно сказать алгоритм.
> Обходить кругом. Метод кругового обхода существует всего
> два. Так что ходы можно и записать. =) Правдо про круговой
> метод обхода читал дввно. Так что помню плохо.

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

Мне кажется, что наиболее правдоподобное решение приведено в [7]. Весьма полно соответствует простому человеческому пониманию выражения «обход кругом».

ПОМОГИТЕ СОСТАВИТЬ АЛГОРИТМ "ХОД КОНЯ КРУГОМ"! Найти похожие ветки