Задача "Хід коня"
Задача про хід коня, відома ще з XVIII сторіччя: спосіб знаходити безліч розв’язків для ходів коня, не роблячи спроб. Алгоритм першої спроби ходіння конем. Алгоритм та блок-схема задачі "Хід коня" та її підпрограми. Розробка лістингу програми "Хід коня".
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | задача |
| Язык | русский |
| Дата добавления | 21.04.2011 |
| Размер файла | 20,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
8
Міністерство освіти і науки України
Полтавський державний педагогічний університет
імені В.Г. Короленка
Задача
Хід коня
Підготували студенти групи Ф-52
Татушенко М.В., Прудка І.І., Кириченко І.О.
Полтава - 2009
План
- Вступ
- Умова задачі
- Блок-схема задачі "Хід коня"
- Підпрограма
- Лістинг програми
Вступ
Зовсім не обов'язково бути шахматистом, щоб знати, яка шахматна фігура найдивовижніша. Звісно, це кінь! Не випадково вислів "хід конем" став крилатим. А один із відомих гросмейстерів, С. Тартаковер, вважав, що "вся шахматна партія - це один замаскований хід конем".
Задача про хід коня відома ще з XVIII століття. Леонард Ейлер присвятив їй велику працю "Розв'язання одного цікавого питання, яке, здається, не підкоряється ніякому дослідженню" (26.04.1757). В листі до Гольдбаха він писав: "Спогади про запропоновану колись мені задачу послугували для мене недавно приводом до деяких витонченостей, в яких звичайний аналіз здавалося б немає ніякого застосування… Я знайшов нарешті ясний спосіб знаходити безліч розв'язків (хоча їх кількість небезкінечна), не роблячи спроб".
Умова задачі
Задача про хід коня відома ще з XVIII століття. Леонард Ейлер присвятив їй велику працю "Розв'язання одного цікавого питання, яке, здається, не підкоряється ніякому дослідженню" (26.04.1757). В листі до Гольдбаха він писав: "Спогади про запропоновану колись мені задачу послугували для мене недавно приводом до деяких витонченостей, в яких звичайний аналіз здавалося б немає ніякого застосування… Я знайшов нарешті ясний спосіб знаходити безліч розв'язків (хоча їх кількість небезкінечна), не роблячи спроб".
Тож розглянемо задачу про хід коня.
Здійснимо постановку задачі. Дано дошку n*n, яка містить n2 полів. Коня, який ходить згідно шахових правил, поміщують на поле з початковими координатами х0 та у0. Потрібно покрити всю дошку ходами коня, тобто обчислити обхід дошки, якщо він існує, з n2-1 ходів, такий, щоб кожне поле відвідується єдиний раз. Очевидно, задачу покриття n2 полів можна звести до більш простої: або виконати черговий хід, або встановити, що ніякий хід далі неможливий. Перша спроба виглядатиме так:
Procedure спроба наступного кроку;
Begin ініціація вибірки ходів;
Repeat вибір наступного можливого ходу зі списку чергових ходів;
If він прийнятний then
Begin запис ходу;
If дошка незаповнена then
Begin спроба наступного кроку;
If невдачаthen стирання попереднього кроку
End
End
Until (хід був удалим) && (немає інших можливих ходів)
End.
Блок-схема задачі "Хід коня"
Размещено на http://www.allbest.ru/
8
хід коня лістинг алгоритм
Підпрограма
Размещено на http://www.allbest.ru/
8
Лістинг програми
Program tyr_konia;
Uses crt'
Const
dx: array [1.8] of integer= (2,1,-1,-2,-2,-1,1,2);
dy; array [1.8] of integer= (1,2,2,1,-1,-2,-2,-1);
var
i,j,n,Nsqr: integer;
q: boolean;
h: array [1.8,1.8] of integer;
procedure Try (i,x,y: integer; var q: boolean);
var k, u, v: integer;
q1: boolean;
begin
k: =0;
repeat
k: =k+1;
q1: =false;
u: =x+dx [k];
v: =y+dy [k];
if (l<=u) and (u<=n) and (l<=v) and (v<=n) and (h [u,v] =0) then
begin
h [u,v]: =i-1;
if i<Nsqr then
begin
Try (i+1,u,v,q1);
If not q1 then h [u,v]: =0;
End
Else q1: =true;
End;
Until q1 or (k=8);
q: =q1;
end;
begin
clrscr;
for i: =1 to 8 do
for j: =1 to 8 do
h [i,j]: =0;
write (`n='); readln (n);
write (`i='); readln (i);
write (`j='); readln (j);
Nsqr: =n*n;
h [i,j]: =1;
Try (2, i,j,q);
Writeln (`Po4atkove polo*ennnia kon9: [', i,'; ',j,'] ');
If q then
Begin
h [i,j]: =0;
for i: =1 to n do
begin
for j: =1 to n do write (h [i,j]: 3);
writeln;
end;
end
else
writeln (`path not found');
readln;
end.
Размещено на Allbest.ru
Подобные документы
Створення програми "Шаховий кінь" в системі програмування Turbo Pascal. Генерування відповідно до заданих початкових кординат маршруту руху коня. Алгоритм задачі: початок, виведення зображення та пошук. Реалізація програми та демонтрація її роботи.
курсовая работа [1,3 M], добавлен 23.06.2010Создание программы движения коня по шахматной доске, ее функциональное и эксплуатационное назначение, требования пользователя к программному изделию. Виды скриншотов, информационная совместимость, программные ограничения и требования к документации.
курсовая работа [1,4 M], добавлен 17.02.2010Технологія візуального проектування. Аналітичне розв’язання задачі в загальному вигляді. Програмування в консольному режимі. Сценарій розв’язання задачі в Delphi та блок-схема алгоритму. Програмний код додатку та опис інтерфейсу з екранними копіями.
курсовая работа [2,4 M], добавлен 22.06.2009Задача на пошук найкоротшої відстані, маршруту і шляху холостого пробігу машин. Обгрунтування вибору методу та алгоритм розв'язання задачі. Опис математичної моделі задачі. Інтерфейс та лістинг программи. Заповнення таблиці суміжності для заданого графу.
курсовая работа [315,5 K], добавлен 26.05.2015Дослідження методу сплайнів для вирішення задачі інтерполяції. Вибір методів технічних та інструментальних засобів вирішення задачі, їх алгоритми. Розробка логічної частини програми, результати обчислень. Розв’язання задачі в пакетах прикладних програм.
курсовая работа [278,5 K], добавлен 03.12.2009Розробка, налагоджування, тестування і документування програми на мові високого рівня С++ при рішенні на комп'ютері прикладної інженерної задачі. Використання принципів модульного і структурного програмування, зображення алгоритму у вигляді блок-схеми.
курсовая работа [1,1 M], добавлен 07.08.2013Розробка програми для вирішення графічної задачі. При вирішенні задачі необхідно cтворювати програму у середовищі програмування Turbo Pascal. Розробка алгоритму функціонування програми і надання блок-схеми алгоритму. Демонстрація роботи програми.
курсовая работа [1,3 M], добавлен 23.06.2010Исследование методов решения задачи о ходе коня. Описание алгоритмов для итеративной и рекурсивной программ. Генерация перестановок элементов по индексам. Построение эйлерова цикла на графе. Поиск кратчайшего пути на графе. Программная реализация задачи.
курсовая работа [411,6 K], добавлен 25.04.2013Розв’язання нелінійних алгебраїчних рівнянь методом дихотомії. Вирішення задачі знаходження коренів рівняння. Розробка алгоритму розв’язання задачі і тестового прикладу. Блок-схеми алгоритмів основних функцій. Інструкція користувача програмою мовою С++.
курсовая работа [2,0 M], добавлен 24.09.2010Розбиття загальної задачі на під задачі. Вибір засобу реалізації кожної з підзадач. Обґрунтування вибору ОМК для вирішення задачі. Функціональна схема пристрою та її короткий опис. Алгоритм роботи МКП. Розподіл пам’яті даних та програм. Текст програми.
контрольная работа [508,3 K], добавлен 21.01.2009
