При
написании фрагментов программ использовались основные конструкции языка
Turbo Pascal (ветвления, циклы).
1. ПЕРЕМЕННЫЕ,
ВЫРАЖЕНИЯ, ПРИСВАИВАНИЯ.
1.1 ЗАДАЧИ
БЕЗ МАССИВОВ.
Задача 1.
Дано число
а и натуральное число n.
Вычислить
а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.
Решить предыдущую
задачу, если требуется, чтобы число действий (выполняемых операторов присваивания)
было порядка log2 n (то есть не превосходило бы C(log2
n, где С -константа, log2 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·log2 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 мест вправо, получим число (10k)/n.
Нам надо напечатать его целую часть, то есть разделить 10k на
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, требующую порядка log2 n операций (не более C·log2
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·log2 n.
УПРАЖНЕНИЯ:
1.
Последовательность Фибоначчи определяется так: a0=0, a1=1,
ak=ak-1+ak-2 при k>=2.
Дано n. Вычислить
an. Число операций должно быть порядка log2 n.
2.
Написать вариант алгоритма Евклида, использующий соотношения
НОД(2a,2b)=2НОД(a,b)
НОД(2a,b)=НОД(a,b)
при нечетном b, использующий лишь деление на 2 и проверку четности. Число
действий должно быть порядка log2 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.
|