При написании фрагментов программ использовались основные конструкции языка Turbo Pascal
(ветвления, циклы).

1. ПЕРЕМЕННЫЕ, ВЫРАЖЕНИЯ, ПРИСВАИВАНИЯ.  

1.1 ЗАДАЧИ БЕЗ МАССИВОВ.  

Задача 1.    
Дано число а и натуральное число n.  
Вычислить аⁿ (a в степени n).  

Решение:  

k:=0;b:=1; 
while k<>n do  
  begin  
       k:=k+1; b:=b·a;
   end;

Другое решение этой задачи:  

k:=n;b:=1;  
while k<>0 do  
 begin  

k:=k-1;  
b:=b·a;  

 end;

Число выполняемых операторов присваивания равно n.  

Задача 2.    
Решить предыдущую задачу, если требуется, чтобы число действий (выполняемых операторов присваивания) было порядка log₂ n (то есть не превосходило бы C(log₂ n, где С -константа, log₂ n - это степень, в которую нужно возвести 2, чтобы получить n).  

Решение:  

k:=n;b:=1;c:=a;  
while k<>0 do  
 begin  

if k mod 2=0  
then  
begin k:=k div 2; c:=c·c; end    
else  
begin k:=k-1; b:=b·c; end;  

 end;

За каждые два вхождения в цикл значение переменной k уменьшается по крайней мере вдвое. В цикле выполняется 2 операции присваивания. Поэтому общее число действий не превосходит 4·log₂ n.  

Задача 3.    
Дано натуральное число n, вычислить n! (1!=1, n!=n((n-1)!).  

Решение:  

k:=n;b:=1;  
while k<>0 do  
 begin    

b:=b·k;  
k:=k-1;  

 end;

Задача 4.    
Дано натуральное n, вычислить 1/1!+...+1/n! так, чтобы число операций (выполняемых команд присваивания) было бы порядка n (не более C·n для некоторой константы С).  

Решение:    
Важно не вычислять заново каждый раз n!.  
n!=1·2·3·...·(n-1)·n=(n-1)!·n. В нашем примере 1/n!=1/((n-1)!·n), т.е. каждый j элемент получается делением (j-1)-го элемента на j.  

k:=1; sum:=0; last:=1; {1/1!}  
while k<=n do  
begin  

sum:=sum+last;  
k:=k+1;  
last:=last/k;  

end;

Число выполняемых операций присваивания равно 3·n.  

Задача 5.  
Даны два натуральных числа а и b, не равные нулю одновременно. Вычислить d=НОД(а,b) - наибольший общий делитель а и b.  

Решение:    
Алгоритм Евклида. Будем считать, что  

1) НОД(0,0)=0;  
2) НОД(а,b)=НОД(а-b,b)=НОД(а,b-а);  
3) НОД(а,0)=НОД(0,а)=а

для всех а,b>=0.  
(см. Основы информатики и вычислительной техники, часть 1, под ред. А.П. Ершова и В.М. Монахова или А.Г. Кушниренко и др. Основы информатики и вычислительной техники)  

m:=a;n:=b;  
while not ((m=0) or (n=0)) do  

if m>=n then m:=m-n else n:=n-m;  

if m=0 then d:=n else d:=m;

Задача 6.    
Даны два натуральных числа а и b, не равные нулю одновременно. Найти d=НОД(а,b) и такие x и y, что d=a·x+b·y.  

Решение:    
Добавим переменные p,q,r,s такие, что m=p·a+q·b, n=r·a+s·b.  

m:=a; n:=b; p:=1; q:=0; r:=0; s:=1;  
while not ((m=0) or (n=0)) do  

if m>=n  
then  
begin m:=m-n; p:=p-r; q:=q-s; end  
else  
begin n:=n-m; r:=r-p; s:=s-q; end;  

if m=0  
then  
 begin k:=n; x:=r; y:=s; end  
else  
 begin k:=m; x:=p; y:=q; end;

Задача 7.  
Даны натуральные числа n и k, n>1. Напечатать k десятичных знаков числа 1/n. Программа должна использовать только целые переменные.  
Решение:  
Сдвинув в десятичной записи числа 1/n запятую на k мест вправо, получим число (10^k)/n. Нам надо напечатать его целую часть, то есть разделить 10^k на n нацело. Стандартный способ требует использования больших по величине чисел, которые могут выйти за границы диапазона представимых чисел.  
Воспользуемся методом "деления уголком" и будем хранить "остаток" r.  

t:=0; r:=1;  
while t<>k do  
begin  

write((10·r) div n);  
r:=(10·r) mod n;  
t:=t+1;  

end;

Задача 8.  
Функция f с натуральными аргументами и значениями определена так: f(0)=0, f(1)=1, f(2n)=f(n), f(2n+1)=f(n)+f(n+1). Составить программу вычисления f(n) по заданному n, требующую порядка log₂ n операций (не более C·log₂ n).  

Решение:  
Функцию f можно записать в общем виде: f(n)=a(f(k)+b(f(k+1).  
Если n - четное, то а=1, b=0 иначе а=1, b=1.  
Для k=2m: f(k)=f(m), f(k+1)=f(2m+1)=f(m)+f(m+1). Тогда  
f(n)=a·f(k)+b·f(k+1)=a·f(m)+b·(f(m)+f(m+1))=(a+b)·f(m)+b·f(m+1).  
Для k=2m+1: f(k)=f(m)+f(m+1), f(k+1)=f(2m+2)=f(2(m+1))=f(m+1).  
Тогда f(n)=a·f(k)+b·f(k+1)=a·f(m)+(a+b)·f(m+1).  

k:=n; a:=1; b:=0;  
while k<>0 do  

if k mod 2=0  
then begin m:=k div 2; a:=a+b; k:=m; end  
else begin m:=k div 2; b:=a+b; k:=m; end;  

{k=0: f(n)=af(0)+bf(1)=b, что и требовалось}

При каждом вхождении в цикл значение переменной k уменьшается вдвое.  
Поэтому число операций не более 3·log₂ n.  

УПРАЖНЕНИЯ:  

1. Последовательность Фибоначчи определяется так: a₀=0, a₁=1, a_k=a_k-1+a_k-2 при k>=2.  
Дано n. Вычислить a_n. Число операций должно быть порядка log₂ n.  
2. Написать вариант алгоритма Евклида, использующий соотношения  
НОД(2a,2b)=2НОД(a,b)  
НОД(2a,b)=НОД(a,b) при нечетном b, использующий лишь деление на 2 и проверку четности. Число действий должно быть порядка log₂ n для исходных данных, не превосходящих n.  
3. Функция f определена так: f(0)=13, f(1)=17, f(2n+1)=43f(n)+57f(n+1),  
f(2n+2)=91f(n)+179f(n+1) при n>=1.