Задачи,советы и ответы - часть 4

Совет 1 (общий)

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

MoveAll(k,from,to,tmp) MoveOne(from,to)

Первая из них выполняет шаги по переносу пирамиды из k дисков со шпильки from на шпильку to, используя в качестве рабочей шпильку tmp. Вторая переносит один диск со шпильки from на шпильку to.

Совет 2 (QBasic)

Переменная т% введена для нумерации ходов. Для того чтобы ее значение сохранялось после очередного перемещения одного диска в заголовке подпрограммы MoveOne использован указатель STATIC.

Совет 3 (Паскаль)

В программе нельзя использовать идентификатор to, т. к. он занят под служебное слово в операторе цикла for.

Программа 5_03.bas

DECLARE SUB MoveAll(k%,from$,to$,tmp$)

DECLARE SUB MoveOne(from$,to$)

CLS

INPUT "Введите количество дисков ",k%

MoveAll k%,"A","C","B"

END

SUB MoveAll (k%, from$, to$,tmp$)

IF k%=0 THEN EXIT SUB

MoveAll k%-l,from$,tmp$,to$

MoveOne from$,to$

MoveAll k%-l,trap$,to$,from$ END SUB

SUB MoveOne(from$,to$) STATIC

m%=m%+l

PRINT USING "#### : &--> & ";m%;from$;to$ END SUB

Программа 5_03.с

#include <stdio.h>

#include <conio.h>

void MoveAll(int k,char from,char to,char trap);

void MoveOne(char from,char to);

int m=0;

main () {

int k;

clrscr () ;

printf("\n Введите количество дисков - ");

scanf("Id",&k);

MoveAll(k,'A','C','B');

getch(); }

void MoveAll(int k,char from,char to,char tmp)

{

if(k==0) return; MoveAll(k-1,from,tmp,to);

MoveOne(from,to); MoveAll(k-1,tmp,to,from); }

void MoveOne(char from,char to) {

m++;

printf("\n%4d : %c --> %c",m,from,to); }

Программа 5_03.pas

program Hanoi; uses Crt; var

k:integer; const

m: integer=0;

procedure MoveOne(from,tol:char);

begin

inc (m) ;

writeln(m:4,from:2, ' —> ',tol);

end;

procedure MoveAll(k:integer;from,tol,tmp:char);

begin

if k = 0 then exit;

MoveAll(k-1,from,tmp,tol);

MoveOne(from,tol);

MoveAll(k-1,tmp,tol,from);

end;

begin

clrscr;

write('Введите количество дисков - ') ;

readln(k);

MoveAll(k, 'А', 'С', 'В');

readln;

end.

Содержание Назад