Алгоритми розв'язання лабіринтних та ігрових задач
Міністерство
освіти і науки України
Національний
університет "Львівська політехніка"
Кафедра
автоматизованих систем управління
Звіт
до
розрахункової роботи
з
теорії алгоритмів
"Алгоритми
розв’язання лабіринтних та ігрових задач"
Виконала:
ст. групи КН-21
Прач Ю.О.
Прийняв:
Цимбал Ю.В.
Львів-2011
Мета:
ü навчитися
розробляти алгоритми лабіринтних та ігрових задач.
Індивідуальне завдання:
.(Прач) Числа від 1 до 15
розставлені в клітинках на дошці, як зображено на рисунку. Використовуючи одну вільну
комірки (в центрі), перемістіть числа, щоб розставити їх у такому ж порядку,
але з числом 15 в центральній комірці.
Алгоритм
Рухаємо числа і пробуємо різні
варіанти розміщень, але з одною умовою - 14, 15 і 1 завжди мають бути в
особливих позиціях. Інакше задача не буде мати розв’язку.
ігровий задача інформація стратегія
#include<stdio.h>
#include<stdlib.h>
#include<clocale>
#include<Windows.h>[16]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0};()
{(LC_CTYPE,
"ukr");(1251);(1251);,i;("Початковий стан:\n");(i=0;
i<16; i++)("%d ", mas[i]);("\n");
// 1-а
перестановка=mas[15];[15]=mas[0];[0]=mas[14];(i=14; i>10;
i--)[i]=mas[i-1];[i]=mas[15];[15]=temp;("Перша
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 2-а
перестановка=mas[15];[15]=mas[10];(i=10; i>5;
i--)[i]=mas[i-1];[i]=mas[15];[15]=temp;("Друга
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 3-я
перестановка=mas[15];[15]=mas[0];[0]=mas[14];(i=14; i>10;
i--)[i]=mas[i-1];[i]=mas[15];[15]=temp;("Третя
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 4-а
перестановка=mas[15];[15]=mas[10];(i=10; i>5;
i--)[i]=mas[i-1];[i]=mas[15];[15]=temp;("Четверта
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 5-а перестановка=mas[15];[15]=mas[0];[0]=mas[14];(i=14;
i>10; i--)[i]=mas[i-1];[i]=mas[15];[15]=temp;("П\'ята
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 6-а
перестановка=mas[15];[15]=mas[5];(i=5; i>0;
i--)[i]=mas[i-1];[i]=mas[15];[15]=temp;("Шоста перестановка:\n");(i=0;
i<16; i++)("%d ", mas[i]);("\n");
// 7-а
перестановка=mas[15];[15]=mas[10];(i=10; i>5;
i--)[i]=mas[i-1];[i]=mas[15];[15]=temp;("Сьома
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 8-а
перестановка=mas[15];[15]=mas[0];[0]=mas[14];(i=14; i>10;
i--)[i]=mas[i-1];[i]=mas[15];[15]=temp;("Восьма
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 9-а
перестановка=mas[15];[15]=mas[5];(i=5; i>0;
i--)[i]=mas[i-1];[i]=mas[15];[15]=temp;("Дев\'ята
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 10-а
перестановка=mas[15];[15]=mas[10];(i=10; i>5;
i--)[i]=mas[i-1];[i]=mas[15];[15]=temp;("Десята
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 11-а
перестановка=mas[15];[15]=mas[0];[0]=mas[14];(i=14; i>10; i--)[i]=mas[i-1];[i]=mas[15];[15]=temp;("Одиннадцята
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 12-а
перестановка=mas[15];[15]=mas[5];(i=5; i>0;
i--)[i]=mas[i-1];[i]=mas[15];[15]=temp;("Дванадцята
перестановка:\n");(i=0; i<16; i++)("%d ", mas[i]);("\n");
// 13-а
перестановка=mas[15];[15]=mas[10];(i=10; i>5;
i--)[i]=mas[i-1];[i]=mas[15];[15]=temp;("Тринадцята
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 14-а
перестановка=mas[15];[15]=mas[0];[0]=mas[14];(i=14; i>10; i--)[i]=mas[i-1];[i]=mas[15];[15]=temp;("Чотирнадцята
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 16-а
перестановка=mas[15];[15]=mas[10];(i=10; i>5;
i--)[i]=mas[i-1];[i]=mas[15];[15]=temp;("Шістнадцята
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 17-а
перестановка=mas[15];[15]=mas[5];(i=5; i<10; i++)[i]=mas[i+1];[i]=mas[15];[15]=temp;("Сімнадцята
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 18-а
перестановка=mas[15];[15]=mas[0];[0]=mas[14];(i=14; i>5;
i--)[i]=mas[i-1];[i]=mas[15];[15]=temp;("Вісімнадцята
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 19-а
перестановка=mas[15];[15]=mas[10];(i=10; i<14;
i++)[i]=mas[i+1];[i]=mas[0];[0]=mas[15];[15]=temp;("Дев\'ятнадцята
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 20-а
перестановка=mas[15];[15]=mas[0];(i=0; i<5; i++)[i]=mas[i+1];[i]=mas[15];[15]=temp;("Двадцята
перестановка:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\n");
// 21-а
перестановка=mas[15];[15]=mas[10];j=10;(mas[0]!=1)
{(i=j; i>0;
i--)[i]=mas[i-1];[0]=mas[14];(i=14; i<j; i--)[i]=mas[i-1];=i;
}[14]=0;("Кінцевий
результат:\n");(i=0; i<16; i++)("%d ",
mas[i]);("\nЗадача розв’язана!\n");("pause");0;
}
Приклад виконання: