Скачать программы Все программы автораЛАБОРАТОРНАЯ РАБОТА 9АЛГОРИТМЫ НАД ЦЕЛОЧИСЛЕННЫМИ ТИПАМИ ДАННЫХЦель работы: познакомить с классическими алгоритмами над целочисленными типами данных и их реализацией на языке программирования Pascal.
В основе обучения классическим алгоритмам лежит следующая схема [Бороненко, Рыжова,1997,с.74]. 1. Студентам предлагается задача, рассчитанная на использование программирования, решаемая с помощью некоторого классического алгоритма. Важно отметить, что при этом алгоритм студенту не сообщается. 2. Студент решает задачу, программируя алгоритм, разработанный им самостоятельно. 3. Только после этого преподаватель сообщает классический алгоритм (как нам кажется, после этого повышается внутренняя мотивация деятельности студентов, направленная на изучение классического алгоритма): (а) в вербальной форме записи, либо на языке программирования той же парадигмы, что и изучаемый; (б) на языке программирования той же парадигмы, что и изучаемый (при этом в реализации умышленно пропущены некоторые строки) или на изучаемом языке программирования, при этом в реализации умышленно пропущены некоторые строки. 4. Студент реализует классический алгоритм и делает вывод о степени эффективности своей реализации (по времени выполнения).
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
1. Даны две целые переменные a и b. Составить фрагмент программы, после исполнения которого значения переменных поменялись бы местами (новое значение a равно старому значению b и наоборот). 2. Решить предыдущую задачу, не используя дополнительных переменных (и предполагая, что значениями целых переменных могут быть произвольные целые числа). 3. Найти большее (меньшее) из двух целых чисел без использования условного оператора. 4. Дано целое число а и натуральное (целое неотрицательное) число n. Вычислить а в степени n. Другими словами, необходимо составить программу, при исполнении которой значения переменных а и n не меняются, а значение некоторой другой переменной (например, b) становится равным а в степени n (разрешается использовать и другие переменные.) 5. Дано целое число а и натуральное (целое неотрицательное) число n. Вычислить а в степени n. Другими словами, необходимо составить программу, при исполнении которой значения переменных а и n не меняются, а значение некоторой другой переменной (например, b) становится равным а в степени n (разрешается использовать и другие переменные). Однако необходимо, чтобы число действий (выполняемых операторов присваивания) было порядка (не превосходило бы для некоторой константы C; - это степень, в которую нужно возвести 2, чтобы получить n). 6. Даны два натуральных числа a и b, не равные нулю одновременно. Вычислить НОД (a,b) - наибольший общий делитель а и b. 7. Написать модифицированный вариант алгоритма
Евклида, использующий соотношения: 8. Найти наименьшее общее кратное целых чисел a и b. Написать вариант
алгоритма Евклида, использующий соотношения: 9. Составить программу, печатающую разложение на простые множители заданного натурального числа n>0 (другими словами, требуется печатать только простые числа и произведение напечатанных чисел должно быть равно n; если n=1, печатать ничего не надо). 10. Разрешим использовать команды write(i) лишь при i=0,1,...,9. Составить программу, печатающую десятичную запись заданного натурального числа n>0. (Случай n=0 явился бы некоторым исключением, так как обычно нули в начале числа не печатаются, а для n=0 - печатаются.) 11. Разрешим использовать команды write(i) лишь при i=0,1,...,9. Составить программу, печатающую десятичную запись заданного натурального числа n>0 в обратном порядке. (Для n=173 надо напечатать 371.) 12. Даны натуральные числа n и k, n>1. Напечатать k десятичных знаков числа 1/n. (При наличии двух десятичных разложений выбирается то из них, которое не содержит девятки в периоде.) Программа должна использовать только целые переменные. 13. Дано натуральное число n>1. Определить длину периода десятичной записи дроби 1/n. 14. Проверить, является ли заданное натуральное число n>1 простым. 15. Задача Диксона. Будем говорить, что три натуральных числа образуют дружественную тройку, если сумма собственных делителей каждого числа равна сумме двух других чисел. Отыскать хотя бы одну дружественную тройку натуральных чисел.
УКАЗАНИЯ К РЕШЕНИЮ ЗАДАЧ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
1. Введем дополнительную целую переменную t. Далее: t:=a; a:=b; b:=t; 2. Начальные значения a и b обозначим a0, b0. a:=a+b; {a=a0+b0, b=b0}
b:=a-b; {a=a0+b0, b=a0}
a:=a-b; {a=b0, b=a0}
3. Для нахождения большего из двух значений a и b выполняется присваивание m:=(a+b+Abs(a-b)) DIV 2, для нахождения меньшего - m:=(a+b-Abs(a-b)) DIV 2. Введем целую переменную k, которая меняется от 0 до n, причем поддерживается такое свойство: b=(a в степени k). Первый вариант решения : Второй вариант решения : k := 0; b := 1; { b=a в степени k} k := n; b := 1; {a в степени n=b*(a в степени k)} while k<>n do begin while k<>0 do begin
| k := k+1; | k := k - 1;
| b := b*a; | b := b * a;
end; end;
Внесем некоторые изменения во второе из предложенных решений предыдущей задачи: k := n; b := 1; c:=a; { a в степени n=b*(c в степени k) } 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;
#include<stdio.h> main ()
{
int a,b,x,y,z;
int odd();
/* ------------------------------- */
printf ("Возведение в степень...\n"); printf ("Введите x... "); scanf ("%d",&x); printf ("Введите y... "); scanf ("%d",&y); a = x; b = y; z = 1;
while (b!=0)
if (odd(b))
{
z *= a; b--;
}
else
{
a *= a; b /= 2;
}
printf ("%d",z);
}
/* ------- */
int odd (t)
int t;
{
return ((t%2==0) ? 0 : 1); } Приведем два варианта реализации алгоритма решения задачи на некотором алгоритмическом языке. Первый вариант решения : if a>b then begin
| k := a;
end else begin
| k := b;
end;
{ k=max (a,b) } { инвариант: никакое число, большее k, не является общим делителем }
while not (((a mod k)=0) and ((b mod k)=0)) do begin
| k := k - 1;
end; { k - общий делитель, большие - нет } Второй вариант решения (алгоритм Евклида): Будем считать, что НОД (0,0)=0. Тогда:НОД (a,b)=НОД (a-b,b)=НОД (a,b-a); НОД (a,0)=НОД (0,a)=a для всех a,b>=0. m := a; n := b; {инвариант: НОД (a,b)=НОД (m,n); m,n>=0 } while not ((m=0) or (n=0)) do begin
| if m >= n then begin
| | m := m - n;
| end else begin
| | n := n - m;
| end;
end;
if m = 0 then begin
| k := n;
end else begin
| k := m;
end;
FUNCTION Nod (a,b: Integer): Integer;
BEGIN
If a=b
then Nod := a
else begin
If a>b
then Nod := Nod(a-b,b)
else Nod := Nod(b-a,a)
end
END; Программа языке C: #include<stdio.h>
main ()
{
int x,y;
/* ---------------------------------------- */
printf ("Введите первое натуральное число: "); scanf ("%d",&x); printf ("Введите второе натуральное число: "); scanf ("%d",&y);
while (x!=y)
if (x>y)
x = x-y;
else
y = y-x;
printf ("НОД = %d",x); }
4. Решение данной задачи достаточно очевидно. FUNCTION N_O_D (N,M: Integer): Integer;
BEGIN
If M=0
then N_O_D := N
else If N>=M
then N_O_D := N_O_D (М,N MOD M) else N_O_D := N_O_D (М,N) END;
Добавим в алгоритм Евклида дополнительные переменные u,v,z: m := a; n := b; u := b; v := a;
{ инвариант: НОД (a,b)=НОД (m,n); m,n>=0 } while not ((m=0) or (n=0)) do begin
| if m>=n then begin
| | m := m - n; v := v + u;
| end else begin
| | n := n - m; u := u + v;
| end;
end;
if m=0 then begin
| z:= v;
end else begin {n=0}
| z:= u;
end; 5. Приведем фрагмент реализации алгоритма решения задачи на некотором алгоритмическом языке. m:= a; n:=b; d:=1;
{НОД(a,b) = d * НОД(m,n)} while not ((m=0) or (n=0)) do begin
| if (m mod 2 = 0) and (n mod 2 = 0) then begin
| | d:= d*2; m:= m div 2; n:= n div 2;
| end else if (m mod 2 = 0) and (n mod 2 = 1) then begin
| | m:= m div 2;
| end else if (m mod 2 = 1) and (n mod 2 = 0) then begin
| | n:= n div 2;
| end else if (m mod 2=1) and (n mod 2=1) and (m>=n)then begin
| | m:= m-n;
| end else if (m mod 2=1) and (n mod 2=1) and (m<=n)then begin
| | n:= n-m;
| end;
end;
{m=0 => ответ=d*n; n=0 => ответ=d*m} k := n; { инвариант: произведение напечатанных чисел и k равно n, напечатаны только простые числа } while not (k=1) do begin | l := 2; | { инвариант: k не имеет делителей в интервале (1,l) } | while k mod l<>0 do begin
| | l := l + 1;
| end; | { l - наименьший делитель k, больший 1, следовательно, | простой } | writeln (l);
| k:=k div l;
end;
k:=n; l:=2; { произведение k и напечатанных чисел равно n; напеча- танные числа просты; k не имеет делителей, меньших l } while not (k=1) do begin
| if k mod l = 0 then begin
| | { k делится на l и не имеет делителей,
| | меньших l, значит, l просто } | | k := k div l;
| | writeln (l);
| end else begin
| | { k не делится на l } | | l := l + 1;
| end;
end; PROGRAM Razlogenie;
var x,m: Integer;
BEGIN
Write ('Введите целое число... '); Readln (x); m := 2; WriteLn ('Разложение числа ',x,' на простые множители'); While m<=x do
If (x Mod m)=0
then begin Write(' * ',m); x := x Div m end
else m := m + 1
END.
Приведем реализацию алгоритма решения задачи на некотором алгоритмическом языке. base:=1; { base - степень 10, не превосходящая n } while 10*base<=n do begin
| base:= base*10;
end;
{ base - максимальная степень 10, не превосходящая n } k:=n; { инвариант: осталось напечатать k с тем же числом знаков, что в base; base = 100..00 } while base<>1 do begin
| write(k div base);
| k:= k mod base;
| base:= base div 10;
end;
{ base=1; осталось напечатать однозначное число k }
write(k); Замечание . Типичная ошибка при решении этой задачи: неправильно обрабатываются числа с нулями посередине. Приведенный инвариант допускает случай, когда k<base; в этом случае печатание k начинается со старших нулей. Приведем реализацию алгоритма решения задачи на некотором алгоритмическом языке. k := n; { инвариант: осталось напечатать k в обратном порядке } while k<>0 do begin
| write (k mod 10);
| k:= k div 10;
end;
Первый вариант решения . Сдвинув в десятичной записи числа 1/n запятую на k мест вправо, получим число (10 в степени k)/n. Нам надо напечатать его целую часть, т. е. разделить (10 в степени k) на n нацело. Стандартный способ требует использования больших по величине чисел, которые могут выйти за границы диапазона представимых чисел. Поэтому мы сделаем иначе (следуя обычному методу "деления уголком") и будем хранить "остаток" r:l := 0; r := 1; { инвариант: напечатано l разрядов 1/n, осталось напечатать k-l разрядов дроби r/n } while l<>k do begin
| write ((10*r) div n);
| r := (10*r) mod n; | l := l+1; end;
Второй вариант решения .
Период дроби равен периоду в последовательности остатков (докажите это; в частности, надо доказать, что он не может быть меньше). Кроме того, в этой последовательности все периодически повторяющиеся все члены различны, а предпериод имеет длину не более n. Поэтому достаточно найти (n+1)-ый член последовательности остатков и затем минимальное k, при котором (n+1+k)-ый член совпадает с (n+1)-ым. l := 0; r := 1; { инвариант: r/n = результат отбрасывания l знаков в 1/n } while l<>n+1 do begin
| r := (10*r) mod n;
| l := l + 1;
end; c := r; { c = (n+1)-ый член последовательности остатков } r := (10*r) mod n; k := 0; { r = (n+k+1)-ый член последовательности остатков } while r<>c do begin
| r := (10*r) mod n;
| k := k + 1;
end; 6. Вместо описания алгоритма приведем программу PROGRAM S_i_m_p_l_e (Input,Output);
{ Нахождение всех простых чисел на заданном отрезке }
var M : Integer; { Нижняя граница отрезка } N : Integer; { Верхняя граница отрезка } i,j: Integer; { Параметры циклов } kl : Integer; BEGIN
Write ('Введите нижнюю границу отрезка... '); ReadLn (M);
Write ('Введите верхнюю границу отрезка... '); ReadLn (N); WriteLn ('Перед Вами все простые числа из отрезка [',M,',',N,']'); For i:=M to N do
begin kl:=0;
For j:=2 to Round (Sqrt(i)) do
If i MOD j =0 then kl := kl+1;
If kl=0 then Write (i,' ')
end
END.
PROCEDURE PROSTOE (X: Integer; var W: Boolean);
{ X - формальный параметр-значение, }
{ W - формальный параметр-переменная } { X передается по значению, а } { W - по имени (по ссылке) } var k: R;
BEGIN
W:=TRUE;
For k:=2 to Trunc(Sqrt(X)) do
If X MOD k =0 then W:=FALSE
END;
|