Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
nex17
0 / 0 / 0
Регистрация: 27.09.2009
Сообщений: 3
#1

2 хода конём - C++

27.09.2009, 12:38. Просмотров 1808. Ответов 13
Метки нет (Все метки)

Заданы координаты двух клеток шахматного поля (от 1 до 8 по обоим измерениям). Требуется вычислить, может ли конь дойти из одной клетки в другую за один ход, если нет, то за два хода. Если дойдет за 2 хода, то каков промежуточный ход.
Я почти решил задачу простым перебором комбинаций смещения второй клетки, осталось лишь найти промежуточную клетку при двух ходах.

Среда: Borland C++ 3.1
Программа может использовать только условный оператор и оператор выбора!
Прошу просто подсказать идею.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
kravam
быдлокодер
1690 / 877 / 44
Регистрация: 04.06.2008
Сообщений: 5,395
27.09.2009, 13:21     2 хода конём #2
Решать не стал пока.
Насчёт двух ходов. Можно предложить попробовать такое решение.
Пусть координаты первой клетки x, y координаты второй клетки x1, y1.

Тогда из первой клетки можно допрыгнуть во вторую, если соблюдается такое одно из СЕМИ условий

1) Если x== x1, y== y1 (простой прыжок туда-сюда)

2) Если x== x1, а расстояние между y и y1 две клетки (то есть клетки располагаются на одной вертикали). Это условие аналогично тому, как если бы y== y1, а расстояние между иксами было 2 клетки

3) Если расстояние между иксами 1, а между игреками 3 (или между игреками 1, а между иксами 3)

4)Если и между игреками и между иксами расстояние равно 3

5)Если меду иксами расстояние 2, а между игреками 4 (или наоборот)

6)Если расстояние между иксами 0, между игреками 4 (или наоборот)

7)Если расстояние между иксами и игреками 1

Вот тебе оператор выбора. Выясни, выполняется ли хоть одно из этих условий (они взаимоисключающие). Если не выполняется, то решения нет default или как там.
А если какое-то выполняется, то для каждого напиши формулку, как находить промежуточную клетку. И находи в соответвующем case ''
Помни, что иногда таких клеток 2 (если конь в середине доски).
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.09.2009, 13:23     2 хода конём #3
Очень рекомендую книгу "С++. Освой на примерах" М. Динман. Стр. 159, пример 2. Как раз описана Ваша задача.
nex17
0 / 0 / 0
Регистрация: 27.09.2009
Сообщений: 3
27.09.2009, 15:37  [ТС]     2 хода конём #4
Цитата Сообщение от kravam Посмотреть сообщение
А если какое-то выполняется, то для каждого напиши формулку, как находить промежуточную клетку.
Вот с этой формулкой то как раз и проблема, все остальное я ещё на лабе написал. Есть правда вариант тупо проверить все 8 возможных промежуточных клеток, но это будет уже пипец а не программа.

Насчет книги: там описан общий алгоритм алгоритм, к тому же на массивах
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
27.09.2009, 15:45     2 хода конём #5
Вот с этой формулкой то как раз и проблема, все остальное я ещё на лабе написал. Есть правда вариант тупо проверить все 8 возможных промежуточных клеток, но это будет уже пипец а не программа.
нормальная такая функция и не фига не тупо, а очень даже правильно
если тебе надо будет не одну позицию найти, а 10 что тогда?
я делал константный массив возможных приращений координат (8 пар) и перебирал все варианты.
nex17
0 / 0 / 0
Регистрация: 27.09.2009
Сообщений: 3
27.09.2009, 15:50  [ТС]     2 хода конём #6
в том то и проблема, что нельзя использовать ничего, кроме условий и выбора
kravam
быдлокодер
1690 / 877 / 44
Регистрация: 04.06.2008
Сообщений: 5,395
27.09.2009, 16:30     2 хода конём #7
Хорошо. Пусть шахматная доска это массив 8X8. Пусть координаты первой клетки x_1, y_1, коородинаты второй x_2, y_2.

Вот ты смотришь, выполняется ли какое-либо условие из предложенных мной. Для примера возьмём, что выполняется второе условие (две клетки лежат на одной прямой, расстояние между ними тоже две клетки). Пусть две клетки лежат на одной горизонтали (то есть ты выяснил, что y_1== y_2)

Вот тогда зашли в case 2 и ищем координаты промежуточной клетки (x1_пр, y1_пр, x2_пр, y2_пр ) так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
x2_пр= -1, y2_пр= -1;
//Во первых, помним, что если горизонталь вверху или внизу, то промежуточная клетка всего одна
//Сюда идём, если горизонталь вверху
if (y_1< 2) {
 y1_пр= y_1+2; 
}
 
//Так, а сюда идём если горизонталь внизу
else if (y_1>5 ) {
 y1_пр= y_1-2; 
}
 
//А сюда идём если горизонталь посредине 
else {
  y1_пр= y_1-2; 
   y2_пр= y_1+2; 
   x2_пр= (x_1+ x_2)/2;
}
 
//А x1_пр всегда вычислятся одинаково
x1_пр= (x_1+ x_2)/2;
 
//На выходе смотришь значения x2_пр и y2_пр Если они отрицательны- решение одно
Вот примерно так и ковыряешься. Ты просил идею, вот тебе идея. Согласно твоему условию.
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
27.09.2009, 18:21     2 хода конём #8
Ну если тупо делать на один ход - 8 вариантов.
Если тупо делать на два хода - 64 варианта.
Ну ерунда же - 8+64 варианта.
kravam
быдлокодер
1690 / 877 / 44
Регистрация: 04.06.2008
Сообщений: 5,395
27.09.2009, 18:26     2 хода конём #9
Ничё не понял.
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
27.09.2009, 18:29     2 хода конём #10
Тупая без циклов проверка куда с заданной позиции можно сделать ход конец - это 8 разных проверок.
В одной проверке будет несколько IF.

Чтобы сделать два хода конем - уже нужно сделать 64 проверки, хотя этот список можно несколько сократить.

Ну и будет 8+64 блоков очень тупого кода.
kravam
быдлокодер
1690 / 877 / 44
Регистрация: 04.06.2008
Сообщений: 5,395
27.09.2009, 18:38     2 хода конём #11
На всякий случай оправдаюсь.
В предложенном мною варианте писанины, может, и много, но действий мало.
Всякий раз будет осуществляться только ОДНА проверка. А именно- можно ли попасть из клетки в клетку за два хода.

Если можно, проверок как таковых не осуществляется больше. Ищутся две или одна промежуточные точки по умело разработанным формулам.
Ну, учитывая, что условий 7, тогда 7 раз максимум надо проверить, да.
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.09.2009, 19:03     2 хода конём #12
nex17,

Цитата Сообщение от nex17 Посмотреть сообщение
Насчет книги: там описан общий алгоритм алгоритм, к тому же на массивах
Наверняка Вы эту книгу не читали. Там написан готовый код программы с комментариями.
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
27.09.2009, 19:05     2 хода конём #13
Нужно еще координаты промежуточной точки найти.
А самый большой косяк в твоем алгоритме - ты забыл что ходом коня можно уйти за пределы доски
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.09.2009, 19:27     2 хода конём
Еще ссылки по теме:

Delphi Возможность хода конём
C++ Написать программу, реализующую обход доски шахматным конём
Количество обходов шахматной доски конём (с возвратом в начальную клетку) C++
C++ Проверка координат для хода слона

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

Или воспользуйтесь поиском по форуму:
kravam
быдлокодер
1690 / 877 / 44
Регистрация: 04.06.2008
Сообщений: 5,395
27.09.2009, 19:27     2 хода конём #14
Координаты промежуточной точки находятся с помощью умело написанных формулок. Если тредстартер попросит, и мне будет не лень я смогу выложить весь код.

То, что ходом коня можно уйти за пределы доски, я предусмотрел.
Так, в предложенном мной варианте (втором) рассматриваются три случая:

Когда клетки лежат 1) выше второй горизонтали, 2) ниже пятой или 3) где-то посредине.
В первых двух случаях я ищу одну промежуточную точку, когда конём действительно можно
прыгнуть за край доски.
Во третьем случае ищу две промежуточные точки. Когда хоть вверх, хоть вниз прыгай, за доску не выпрыгнешь.

Но даже если бы я этого не предусмотрел- реализовывать такие детали, сколь важными бы они не были это дело тредстартера. Он просил идею, он её получил. Привет.
Yandex
Объявления
27.09.2009, 19:27     2 хода конём
Ответ Создать тему
Опции темы

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