Вимоги до звіту

При оформленні звіту про виконану за час практики роботу необхідно дотримуватися наступних вимог:

1. Титульний лист оформлюється згідно зразка, наданого у Додатку А.

2. Текст реферату та аналітичної записки (документи MS Word) мають бути відформатовані за такими параметрами:

• шрифт (фонт, гарнітура) Times New Roman, розмір (кегль) 12 пт, стиль Звичайний;

• міжрядковий інтервал одинарний;

• поля зліва – 3 см; справа, зверху, знизу – 1.5 см;

• розмір сторінки А4;

• орієнтація книжкова.

3. Презентаційний ролик має бути готовий для демонстрації навіть в умовах відсутності на комп’ютері програми MS Power Point.

4. Виконання четвертої частини індивідуального завдання оформлюється за зразком, що надається у Додатку Б.

5. До звіту додається гнучкий диск (диски) з файлами звіту: рефератом (1 частина завдання), презентаційним роликом (3 частина завдання), аналітичними записками (2 та 4 частини завдання), розробленими програмами.

Додаток а

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ЗАПОРІЗЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ

Кафедра інформаційних технологій

ЗВІТ

ПРО НАВЧАЛЬНУ ОБЧИСЛЮВАЛЬНУ ПРАКТИКУ

Виконав:

студент 1 курсу факультету математики

групи 8114-7

Молодцов Віктор Олександрович

Перевірив:

викладач кафедри ІТ

Володимиров Євген Сергійович

Запоріжжя 2005

Додаток б

Завдання. Ханойські вежі. У центрі світу у вершинах правильного трикутника стоять три діамантових шпилі. На одному з них нанизано 64 золотих диски, радіуси яких зменшуються (найбільший – нижній). Працьовиті буддійські ченці безперервно переносять диски з цього шпиля на другий, використовуючи третій шпиль для проміжних перекладань. Диски треба переносити по одному і не можна класти більший диск на менший. Коли всі диски перенесуть на інший шпиль, наступить кінець світу (задача математика Люка 1883 р.).

Необхідно скласти алгоритм і програму розв'язання задачі про Ханойські вежі для кількості дисків N<20, графічно проілюструвавши кожен етап розв’язку.

Постановка задачі. Розробити рекурсивний алгоритм перекладання кінцевої множини упорядковано розміщених дисків з одного шпиля на другий, підтримуючи при перекладанні встановлений порядок, якщо є тільки один проміжний (третій) шпиль. Виконати програмну реалізацію розробленого алгоритму.

Метод розв’язання. Якщо алгоритм Р(m, a, b, с) повинний перенести верхні m дисків із шпиля а на шпиль b, то (у припущенні, що всі диски лежать правильно, менший на більшому, і що інші диски на всіх трьох шпилях не менші ніж верхні m на шпилі а) алгоритм можна представити в наступному вигляді:

Р(m, а, b, с)

якщо m=1

то перенести верхній диск із шпиля а на шпиль b

інакше

Р(m-1, а, с, b)

Р(1, а, b, с)

Р(m-1, с, b, а)

Цей алгоритм не складний. Якщо m=1, то перенести один диск із a на b. Якщо ж m > 1, то перенести тимчасово m–1 верхніх дисків з а на с. Потім перенести один диск, що залишився, з а на b і, нарешті, перенести m–1 дисків, що зберігаються на с, на шпиль b. Що стосується перенесення m–1 дисків, то для цього підійде той же алгоритм, але зі зменшеним (від m до m–1 ) числом дисків. Таким чином, ми перейдемо від m до m–1 , від m–1 до m–2, m–3,... і дійдемо до одиниці.

Прослідкувавши за переміщеннями дисків у рекурсивному алгоритмі, можна написати алгоритм без рекурсій:

МІТКА: Перший (найменший) диск перекласти за годинною стрілкою.

З двох інших (верхніх) дисків менший перекласти на більший (якщо залишився один, то перекласти його на порожній шпиль, а якщо не залишилося жодного, то задача вирішена).

Якщо задача ще не вирішена, то повторити дії, починаючи з пункту МІТКА:

Цей алгоритм також приводить до розв'язання. Доказ можна провести за індукцією.

Блок-схема рекурсивної частини алгоритму

Текст програми

{автор Молодцов Віктор Олександрович студент групи 8111-7 математичного факультету

Програма реалізована на мові програмування Turbo Pascal 7.0.

Розв'язання задачі про Ханойські вежі з використанням рекурсії та графічним супроводом.

Постановка задачі:

Дано. 3 вертикальних шпиля. На один із них нанизані N дисків, причому будь-який менший диск лежить на більшому, нижній диск найбільший.

Необхідно. Перемістити по одному всі диски на другий шпиль застосовуючи правила:

• для проміжних дій можна використовувати всі шпилі;

• диск меншого розміру може лежати тільки на диску більшого розміру.

{==================================================}

program main;{початок основної програми}

uses graph, crt;{підключення бібліотечних модулів}

{блок опису використовуваних у програмі об'єктів}

const kol=10;{максимальна кількість дисків}

chars:set of char=['0','1','2','3','4','5','6','7','8','9'];{множина припустимих символів для введення}

var gd,gm {робочі змінні для ініціалізації графіки},

i,j,{параметри циклів for}

n,{кількість дисків}

maxd,{довжина найбільшого диска}

code,{допоміжна змінна для процедури val}

step {лічильник кількості перестановок} :integer;

dl{масив довжин дисків}, col{масив кольорів дисків} :array[1..kol] of integer;

a{масив розміщення дисків на шпилях}:array[0..kol,1..3] of integer;

flag {робоча змінна для контролю введення}:boolean;

ns {рядок уведення вхідних даних}:string;

{===================================================}

procedure drawing;{процедура створення ілюстрації}

var i,j,x,z,h:integer;

st:string;

begin

x:=40+maxd div 2; z:=x;{установка абсциси для першого шпиля}

h:=30;{установка висоти кожного диска}

cleardevice;{очищення екрана перед виведенням чергової ілюстрації}

setcolor(14);{установка кольору для шпилей}

for i:=1 to 3 do

begin

line(z,30,z,300);{промальовування вертикального шпиля}

z:=z+2*x-20{обчислення абсциси для наступного шпиля}

end;

{промальовування поточного розміщення дисків на шпилях}

setcolor(15);

x:=40+maxd div 2; z:=x;

for j:=1 to 3 do

begin

i:=1;

while i<=a[0,j] do

begin

{промальовуємо профіль диска у вигляді прямокутника}

rectangle(z-(dl[a[i,j]] div 2),300-i*h,z+(dl[a[i,j]] div 2),300-i*h+h);

setfillstyle(1,col[a[i,j]]);{установка стилю для фарбування диска}

floodfill(z,300-(h*(2*i-1)) div 2,15);{фарбування диска}

inc(i)

end;

z:=z+2*x-20

end;

inc(step);

str(step,st);

outtextxy(300,getmaxy-20,'перестановка '+st)

end;

{===================================================}

procedure p(m,s,b,c:integer);{основний рекурсивний процес}

begin

if m=1 then begin

a[a[0,b]+1,b]:=a[a[0,s],s];

a[a[0,s],s]:=0;

dec(a[0,s]);{убрати диск зі шпиля}

inc(a[0,b]);{додати диск на шпиль}

drawing;{виклик процедури створення ілюстрації}

delay(2000) {фіксація малюнка на екрані}

end

else begin

p(m-1,s,c,b);

p(1,s,b,c);

p(m-1,c,b,s)

end

end;

{===================================================}

begin {початок основної програми}

{перевірка коректності введених даних}

repeat

flag:=true;

clrscr;

writeln('уведіть кількість дисків (1..10), будь ласка');

readln(ns);

for i:=1 to length(ns) do if not (ns[i] in chars) then flag:=false

until flag;

val(ns,n,code);

gd:=detect; initgraph(gd,gm,'');{ініціалізація графіки}

maxd:=((getmaxx-40) div 3)-40;

for i:=1 to kol do dl[i]:=0;

for i:=0 to kol do

for j:=1 to 3 do a[i,j]:=0;

dl[1]:=maxd;{довжина найбільшого диска}

{довжина кожного з інших дисків обчислюється через довжину попереднього диска}

for i:=2 to n do dl[i]:=dl[i-1]-20;

for i:=1 to kol do col[i]:=1+i;{закріплення кольору за кожним диском}

for i:=1 to n do a[i,1]:=i;{початкове закріплення номера за кожним диском}

a[0,1]:=n;

step:=0;{обнулення кількості перестановок}

drawing;{промальовування початкової позиції}

delay(2000);{фіксація початкової позиції на екрані на 2 секунди}

p(n,1,2,3);{виклик основного рекурсивного процесу перекладань дисків}

{очікування натискання будь-якої клавіші для завершення програми}

repeat

setcolor(green);

outtextxy(1,getmaxy-20,'натисніть будь-яку клавішу, будь ласка');

setcolor(white);

outtextxy(1,getmaxy-20,'натисніть будь-яку клавішу, будь ласка');

until keypressed;

closegraph{закриття графічного режиму}

end.{кінець основної програми}

Приклади екранних копій, що ілюструють роботу програми

Початкова позиція	Перша перестановка
Друга перестановка	Третя перестановка
Четверта перестановка	П’ята перестановка
Шоста перестановка	Сьома перестановка