Ханойские башни

@nelson1992 · Регистрация: 21.10.2009

Студворк — интернет-сервис помощи студентам

Помогите с заданием...

Задание

1)На языке программирования Pascal реализовать рекурсивный алгорим решения задачи о ханойских башнях. Для представления ханойской башни необходимо использовать стек и его программную реализацию. Программная реализация алгоритма решения задачи о ханойских башнях должна на каждой итерации выводить протокол работы, представляющий собой содержимое каждого из стеков (башен) после завершения очередной итерации.
2)Провести вычислительный эксперимент с реализованным алгоритмом путем изменения числа колец. При этом максимальное число колец не должно быть большим N=10. Для каждого N измерить время выполнения программы с точностью до милисекунд. Результаты эксперимента выдать из программы в виде таблицы:

Кол-во колец Время до наступления конца света
.... ......
.... ......

3)При N=64 потребуется огромное количество лет для выполнения данного алгоритма при помощи буддийских монахов. Интересно, сколько пртребуется времени для решения задачи на современной ЭВМ? (заметим мы, возвращаясь к вопросу о конце света). Вычислите это время аналитически. Для этого вычислите колическтво операций, необходимых для решения задачи о Ханойских башнях при m=N (метод математической индукции), и воспользуйтесь результатами задания 2 для составления простой пропорции.

Помогите доделать задачу...вот код:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
const
  maxDisks = 64;
type
  arrType = array[1 .. maxDisks] of integer;
 
var
  amount: Integer;
  arr   : ^arrType;
  count_moves: longint;
 
procedure DrawRings;
var
  i, j: integer;
  counters: array[0 .. 2] of integer;
begin
  for i := 0 to 2 do counters[i] := 0;
  for i := 1 to amount do
    inc(counters[Arr^[i]]);
 
  for i := 0 to 2 do
  begin
    write(succ(i), ': ');
    for j := 1 to counters[i] do write('*');
    writeln;
  end;
  writeln('----------');
end;
 
procedure PrintQuant(curr, _begin, _end: integer);
begin
  Arr^[curr] := _end;
  DrawRings;
  Inc(count_moves);
end;
 
procedure MoveDisk(curr, _begin, _end: integer);
begin
  if curr = 1 then PrintQuant(curr, _begin, _end)
  else begin
    MoveDisk(curr - 1, _begin, 3 - _begin - _end);
    PrintQuant(curr, _begin, _end);
    MoveDisk(curr - 1, 3 - _begin - _end, _end);
  end;
end;
 
var
  i: integer;
  start, finish: integer;
begin
  count_moves := 0;
  start := 0; finish := 2;
 
  amount := 3;
 
  GetMem(arr, amount * sizeof(integer));
  for i := 1 to amount do Arr^[i] := start;
  DrawRings;
  MoveDisk(amount, start, finish);
  Freemem(arr, amount * sizeof(integer));
 
  writeln('Count = ', count_moves);
  readln;
end.

@nelson1992 · 04.03.2010, 19:35 **[ТС]**

Вот код...это для 1-го и 2-го задания...но мне надо комментарии к ним...кто может напишите...

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
uses Dos;
 
const
  maxDisks = 64;
type
  arrType = array[1 .. maxDisks] of integer;
  TRes = record
    Num, Cnt, Tim : Longint;
  end;
 
var
  amount: Integer;
  arr   : arrType;
  count_moves: longint;
  res : array[3..10] of TRes;
 
procedure DrawRings;
var
  i, j: integer;
  counters: array[0 .. 2] of integer;
begin
  for i := 0 to 2 do counters[i] := 0;
  for i := 1 to amount do
    inc(counters[Arr[i]]);
 
  for i := 0 to 2 do begin
    write(succ(i), ': ');
    for j := 1 to counters[i] do write('*');
    writeln;
  end;
  writeln('----------');
end;
 
procedure PrintQuant(curr, _begin, _end: integer);
begin
  Arr[curr] := _end;
  DrawRings;
  Inc(count_moves);
{  readln;}
end;
 
procedure MoveDisk(curr, _begin, _end: integer);
begin
  if curr = 1 then PrintQuant(curr, _begin, _end)
  else begin
    MoveDisk(curr - 1, _begin, 3 - _begin - _end);
    PrintQuant(curr, _begin, _end);
    MoveDisk(curr - 1, 3 - _begin - _end, _end);
  end;
end;
 
var
  i, j: integer;
  M : Longint;
  start, finish: integer;
  Hour, Minute, Sec1, Sec2, MS1, MS2: Word;
begin
  for J := 3 to 10 do begin
    GetTime(Hour, Minute, Sec1, MS1);
    count_moves := 0;
    start := 0; finish := 2;
 
    amount := j;
 
    for i := 1 to amount do Arr[i] := start;
    DrawRings;
    MoveDisk(amount, start, finish);
 
    GetTime(Hour, Minute, Sec2, MS2);
    M := (Sec2*100+MS2) - (Sec1*100+MS1);
    res[j].Num := J;
    res[j].Cnt := count_moves;
    res[j].Tim := M;
  end;
 
  writeln('Number     Count  Time, msec');
  for J := 3 to 10 do
    writeln(res[j].Num:4, res[j].Cnt:11, res[j].Tim*10:8);
 
  writeln('----------');
 
  readln;
end.

Напишите пожалуйста к ним комментарии...

@shtynka · 26.02.2014, 18:20

решаю ту же задачу, не могу понять почему не попадают данные в стек. Модуль стека и основная программа ниже. Посмотрите пожалуйста, второй день голова ломается...

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//------------------------------------------------------------------
// ìîäóëü äëÿ ðàáîòû ñî ñòåêîì
//------------------------------------------------------------------
UNIT _Stack;
 
INTERFACE
CONST
  StackSize  = 10;      // ìàêñèìàëüíûé ðàçìåð ñòåêà
TYPE
  TStackElem = integer;    // òèï ýëåìåíòîâ ñòåêà - ñòðîêà
  TStack     = array [1..StackSize] of TStackElem;  // îïèñûâàåì ñòåê íà îñíîâå ìàññèâà
VAR
//  Stack      : TStack;  {ñòåê èç ìàññèâà}
  StackTop   : Integer; {âåðøèíà ñòåêà}
  StackDepth : Integer; {ãëóáèíà ñòåêà}
  e,i       : Integer; // ïîçèöèÿ â ñòåêå
 
PROCEDURE StackInit(var s:TStack; var StackDepth:Integer);
PROCEDURE ShowStack(s:TStack);
PROCEDURE push(var s:TStack; e: Integer);
procedure print(s1, s2, s3: TStack);
FUNCTION  pop(var s : TStack) : Integer;
 
IMPLEMENTATION
{ðåàëèçàöèÿ ñòåêà}
PROCEDURE StackInit(var S:TStack; var StackDepth);
BEGIN
  StackTop:=1;              {óñòàíàâëèâàåì âåðøèíó â ïåðâûé ýëåìåíò ìàññèâà}
  for i:= 1 to stackdepth do
      begin
           S[i]:=0;
      end;
//  StackDepth:=StackDepth;
writeln('stack initializing ok, depth=', stackdepth);
END;
//------------------------------------------------------------------
// ïðîöåäóðà çàïèñè â ñòåê
//------------------------------------------------------------------
PROCEDURE push(var s:TStack, e:Integer);   // çàíîñèì â ñòåê e
BEGIN
  if StackTop<=StackDepth
  then
  begin
    s[StackTop]:=e; // çàíîñèì çíà÷åíèå
    Inc(StackTop);  // ñäâèãàåì âåðøèíó ñòåêà +1
    writeln('push on stack ', e);
  end
  else begin
    writeln('Error, stack push false');
  end;
END;
//------------------------------------------------------------------
// ïðîöåäóðà èçâëå÷åíèÿ èç ñòåêà
//------------------------------------------------------------------
FUNCTION  pop(var s : TStack) : Integer;     // èçâëåêàåì èç ñòåêà
BEGIN
  if StackTop>1
  then begin
    pop:=s[StackTop];
    s[StackTop]:=0;
    Dec(StackTop);
  end
  else begin
    writeln('Error, stack pop false');
  end;
END;
//------------------------------------------------------------------
// ïðîöåäóðà ïîêàçà ñòåêà
//------------------------------------------------------------------
Procedure ShowStack(S:TStack);  // ïîêàçàòü ñòåê íà ýêðàí
BEGIN
i:=StackDepth;
while i>0 do begin
Write(S[i],' ');
Dec(i);
end;
writeln();
END;
 
//------------------------------------------------------------------
// ïðîöåäóðà ïå÷àòè òðåõ ñòåêîâ
//------------------------------------------------------------------
procedure print(s1, s2, s3: TStack);  // ïå÷àòü òðåõ ñòåêîâ
 begin
          write('s1: '); ShowStack(s1);
          write('s2: '); ShowStack(s2);
          write('s3: '); ShowStack(s3);
          writeln();
 end;
 
end.

основная программа

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
program hanoi;
uses crt, _Stack;  // ïîäêëþ÷àåì ìîäóëè
 
VAR
  s1,s2,s3      : TStack;  // òðè ñòåêà äëÿ ïåðåêëàäûâàíèÿ
  top,t1,t2,t3  : Integer; // âåðøèíà ñòåêà
  SDip          : Integer; // ãëóáèíà ñòåêà
  tmp           : Integer; // áóôåð
  i,n, rep             : integer; // èíäåêñ
 
//------------------------------------------------------------------
// ðåêóðñèâíàÿ ïðîöåäóðà ïåðåêëàäûâàíèÿ
//------------------------------------------------------------------
procedure move(n : byte; var source, aim, temp : TStack);
begin
 
     if n=1 then begin
          tmp:=pop(source);
          push(aim, tmp);
          end
     else begin
          move (n-1,source,temp,aim);
          move (1,source,aim,temp);
          move (n-1,temp,aim,source);
          end;
     print(source, aim, temp);
end;
 
//------------------------------------------------------------------
// òåñòîâûé çàïóñê ïðîãðàììû
//------------------------------------------------------------------
BEGIN
     clrscr;
     writeln ('Hanoyskaya bashnya');
     repeat
     writeln ('skolko diskov?');
             readln(n);
             StackInit(s1, n);
             StackInit(s2, n);
             StackInit(s3, n);
 
             push(s1,n);
 
             
             showStack(s1);
             //move (n,s1,s2,s3);  // çàïóñê ðåêóðñèâíîé ôóíêöèè
             writeln ('prodolzhut (1-da, 0-net)');
             read(rep);
           until rep=0;
END.

Сорри за крокозябки в комментарии, нет времени поправить, компилировала в АВС на Вин7

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .