Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
ДОДАТОК В Приклад вирішення завдання частини 3⇐ ПредыдущаяСтр 12 из 12
Умова Ханойські вежі. У центрі світу у вершинах правильного трикутника стоять три діамантових шпилі. На одному з них нанизано 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.{кінець основної програми}
Приклади екранних копій, що ілюструють роботу програми
РЕКОМЕНДОВАНА ЛІТЕРАТУРА
ЗМІСТ
ВСТУП................................................................................................................. 3 ЗАВДАННЯ ПРАКТИКИ ТА РЕКОМЕНДАЦІЇ ЩОДО ЇХ ВИКОНАННЯ 3 Частина 1. РОЗВ’ЯЗУВАННЯ МАТЕМАТИЧНИХ ЗАВДАНЬ ЗАСОБАМИ ПРИКЛАДНИХ ПРОГРАМ.............................................................................. 3 Перелік завдань для індивідуального розв'язування:.................................. 3 Частина 2. СТВОРЕННЯ ПРЕЗЕНТАЦІЙНИХ МАТЕРІАЛІВ ЗАСОБАМИ ПРИКЛАДНИХ ПРОГРАМ.............................................................................. 3 Перелік тем проектів................................................................................... 3 Частина 3. РОЗРОБКА ПРИКЛАДНИХ ОБЧИСЛЮВАЛЬНИХ ПРОГРАМ 3 Етапи розв’язування задачі з використанням комп’ютера.................... 3 Технологія програмування............................................................................ 3 Правила стильового оформлення програм................................................ 3 Додаткові правила........................................................................................ 3 Варіанти завдань третьої частини практики........................................ 3 ВИМОГИ ДО ЗВІТНИХ МАТЕРІАЛІВ.......................................................... 3 РЕФЛЕКСІЯ........................................................................................................ 3 ГЛОСАРІЙ.......................................................................................................... 3 ДОДАТОК А Зразок титульного аркуша........................................ 3 ДОДАТОК Б Основи користування програмою MathCad.. 3 ДОДАТОК В Приклад вирішення завдання частини 3........... 3 РЕКОМЕНДОВАНА ЛІТЕРАТУРА................................................................ 3
Навчально-методичне видання (українською мовою)
Борю Сергій Юрійович
Циммерман Геннадій Анатолійович
Методичні рекомендації до виконання завдань навчальної обчислювальної практики для студентів освітньо-кваліфікаційного рівня «бакалавр» напряму підготовки «Математика»
Рецензент Н.В. Матвіїшина Відповідальний за випуск С.Ю. Борю Коректор Г.А. Циммерман
|