рекурсивный алгоритм.

[Nelson1992]

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

Задание

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


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


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

[Nelson1992]

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

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.

[Karabash]

На современных компьютерах вычисление итераций происходит настолько быстро, что и при 10 кольцах время на все перекладывания меньше чем может показать Windows.
Если при вычислениях задействовать вывод на экран "протокола работы", то можно увидеть и затраченное время. Но 99% этого времени уходит на вывод, а не на вычисления.

При 20-ти кольцах, без вывода на экран, на 1048575 итераций (2^20-1) тратится примерно 2000-2500 мск (Turbo Pascal; Delphi, при прочих равных условиях, делает это в 500-600 раз быстрее).
Примем для упрощения 2 сек.

Тогда можно рассчитать для 64 колец.

2^64-1 = 18 446 744 073 709 551 615 / 1 048 575 = 17 592 202 821 648 * 2 =
35 184 405 643 296 сек / 86400 = 407 226 917 суток

[Nelson1992]

Спасибо...а этот код только к 3 заданию,или ко всему???
И если можно...добавьте пожалуйста комментарии к некоторым строкам в тексте программы...

[Karabash]

Первое задание - уже было сделано в виде представленного вами текста.
Второе задание добавлено в этот текст. Все вместе в исходнике han.txt.
Третье задание не решается на Turbo Pascal - в нем нет "длинной арифметики". К тому же в 3-м задании ни гу-гу про TP или какую-либо среду разработки. Поэтому 3-е задание сделано в тексте сообщения в виде простого расчета.

К каким некоторым строчкам нужен комментарий?

[Nelson1992]

Большое спасибо)))

[Nelson1992]

Можете написать комментарии к этой программе...а,то я не могу разобраться в ней...пожалуйста...

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.

[Nelson1992]

А зачем в тут стоит { readln;} ????

Сообщение от Nelson1992

Inc(count_moves);
{ readln;}
end;

[Nelson1992]

Сообщение от Karabash

Тогда можно рассчитать для 64 колец.

2^64-1 = 18 446 744 073 709 551 615 / 1 048 575 = 17 592 202 821 648 * 2 =
35 184 405 643 296 сек / 86400 = 407 226 917 суток

А можно пожалуйста объяснить мне,откуда беруться эти числа...на,что всё делиться...я не могу понять...

[Nelson1992]

Вот вторая задача...похожая на первую...

Разработать нерекурсивный алгоритм решения задачи о ханойских башнях.
На языке программирования Pascal реализовать нерекурсивный алгорим решения задачи о ханойских башнях. Для представления ханойской башни необходимо использовать стек и его программную реализацию, выполненную в задаче:

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.

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


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

рекурсивно нерекурсивно
----- --- ---
----- --- ---