4. Размен денег 2

К условию предыдущей задачи добавим, что монет каждого номинала может быть несколько.

В этом случае изменится только перебор очередных монет

const n = 6; {число монет} s = 33; {требуемая сумма} a : array[1..n]of integer = (1,2,3,5,10,15); {номиналы монет} b : array[1..n]of integer = (1,1,5,1,3,1); {количество монет} var kol : array[1..n] of integer; {сколько взято таких монет} found : boolean; { признак, что хотя бы одно решение найдено} procedure rec(k,s1:integer); {k – число уже использовавшихся номиналов, s1 – набранная сумма} var i, p : integer; begin if s=s1 then begin {вывод найденного решения} found:=true; for i:=1 to n do if kol[i]>0 then write(a[i] ,':',kol[i],' '); writeln; exit end; for i:=k+1 to n do {цикл по всем еще неиспользовавшимся монетам} begin {самое критичное место рекурсивного перебора – «взять-проверить-вернуть обратно, чтобы взять следующие»} p:=b[i]; {запомнить количество i-х монет} while (b[i]>0) do begin inc(kol[i]); {взять следующую i-ю монету} dec(b[i]); {уменьшить число оставшихся i-х монет} rec(i,s1+a[i]*kol[i]); end; b[i]:=p; {восстановить количество i-х монет} kol[i]:=0; {вернуть все i-е монеты} end; end; begin found:=false; rec(0,0); if not found then writeln(‘Разменять невозможно’) end.

5. Вычисление суммы элементов линейного массива

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

{Программа на языке Pascal} Program Rec2; Type LinMas = Array[1..100] Of Integer; Var A : LinMas; I, N : Byte; {Рекурсивная функция} Function Summa(N : Byte; A: LinMas) : Integer; Begin If N = 0 Then Summa := 0 Else Summa := A[N] + Summa(N - 1, A) End; {Основная программа} Begin Write('Количество элементов массива? '); ReadLn(N); Randomize; For I := 1 To N Do Begin A[I] := -10 + Random(21); Write(A[I] : 4) End; WriteLn; WriteLn('Сумма: ', Summa(N, A)) End.

3. Рекурсивное определение наибольшего общего делителя двух натуральных чисел на основе алгоритма Евклида

Алгоритм Евклида — алгоритм для нахождения наибольшего общего делителя двух целых чисел или наибольшей общей меры двух однородных величин.

Пусть a и b целые числа, не равные одновременно нулю, и последовательность чисел a, b, r₁ > r₂ > r₃ > ... >rn определена тем, что каждое r_k — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть:

a = bq₀ + r₁ b = r₁q₁ + r₂ r₁ = r₂q₂ + r₃ ... r_k−2 = r_k−1q_k−1 + r_k ... r_n−1 = r_nq_n

Тогда НОД(a,b), наибольший общий делитель a и b, равен r_n, последнему ненулевому члену этой последовательности.

1. Реализация Pascal в рекурсивном виде

program Project1;

{$APPTYPE CONSOLE}

uses

SysUtils,

Windows;

var

n,m,k:LongInt;

depth:Word;

function gcd_rec(m,n:LongInt):LongInt;

begin

Inc(depth);

if n=m then

gcd_rec:=m

else

if m<n then

gcd_rec:=gcd_rec(m,n-m)

else

gcd_rec:=gcd_rec(m-n,n);

end;

begin

SetConsoleOutPutCP(1251);

depth:=0;

writeln('Алгоритм Евклида');

writeln('Алгоритм для нахождения наибольшего общего делителя двух целых чисел.');

writeln;

writeln('Введите первое число: ');

readln(n);

writeln('Введите второе число: ');

readln(m);

k:=gcd_rec(m,n);

writeln;

writeln('Наибольший общий делитель: ',k);

writeln('Глубина рекурсии: ',depth);

readln

end.