Практика программирования (Бейсик, Си, Паскаль)



         

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


main() {

long m,n;

printf("\n Введите 2 натуральных числа, разделяя их пробелом\n");

scanf("%ld %ld",&n,&m);

printf("Их наибольший общий делитель равен %ld",nod(m,n));

getch(); }

long nod(long n1,long n2) {

if(nl==0) return n2;

return nod(n2%nl,nl); }

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

program Euclid;

var

n,m:longint;

function nod(nl,n2:longint):longint;

begin

if nl=0 then nod:=n2

else nod:=nod(n2 mod n1,n1);

end;

begin

writeln('Введите два натуральных числа');

readln(n,m);

writeln{'Иx наибольший общий делитель равен ',nod(n,m));

readln; end.

Задание 5.03. Ханойские башни

Игра "Ханойские башни" была придумана французским математиком Э. Люка в конце XIX в. На подставке установлены три шпильки, которые

мы условно назовем А, в и с. На шпильку А надето k дисков разного диаметра таким образом, что они образуют "правильную" пирамиду (каждый диск, расположенный выше, имеет диаметр меньший, чем у всех, лежащих ниже). Цель игры заключается в переносе пирамиды на шпильку с. При этом за один ход разрешается переложить один диск, надевая его на одну из шпилек таким образом, чтобы верхний диск всегда был меньшего диаметра.

Можно показать, что число ходов, необходимое для решения этой задачи, равно 2k-i. Для k=1 и k=2 это легко проверяется. Дальнейшие рассуждения выполняются по индукции: если это справедливо для любого k-1, то докажем справедливость утверждения о числе шагов и для любого k. Предположим, что мы умеем переносить пирамиду из k-1 дисков за 2k-1-1 ходов. Тогда для переноса башни из k дисков можно поступить следующим образом:

  • переносим верхние k-l диски со шпильки А на шпильку в;

  • переносим оставшийся самый большой диск со шпильки А на шпильку с (это еще один ход);

  • используя освободившуюся шпильку А в качестве рабочей, переносим пирамиду из k-1 диска со шпильки в на шпильку с.

    Таким образом, число ходов, которое мы затратили для переноса пирамиды из k дисков, равно:

    2k-1 - 1 + 1 + 2k-1 -1 = 2k-l




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