Rambler's Top100
 

Скачать программы    Все программы автора

ЛАБОРАТОРНАЯ РАБОТА 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 (разрешается использовать и другие переменные). Однако необходимо, чтобы число действий (выполняемых операторов присваивания) было порядка $\log n$(не превосходило бы $C\cdot log n$для некоторой константы C; $\log n$- это степень, в которую нужно возвести 2, чтобы получить n).

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

7. Написать модифицированный вариант алгоритма Евклида, использующий соотношения:
НОД (a,b)=НОД (a mod b,b) при a>=b,
НОД (a,b)=НОД (a,b mod a) при b>=a.

8. Найти наименьшее общее кратное целых чисел a и b.

Написать вариант алгоритма Евклида, использующий соотношения:
НОД(2a,2b)=2 НОД(a,b)
НОД(2a,b) =НОД(a,b) при нечетном b,
не включающий деления с остатком, а использующий лишь деление на 2 и проверку четности. (Число действий должно быть порядка $\log k$для исходных данных, не превосходящих k.)

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;
Каждый второй раз (не реже) будет выполняться первый вариант оператора выбора (если k нечетно, то после вычитания единицы становится четным), так что за два цикла величина k уменьшается по крайней мере вдвое.  Программа на языке  C.: 
   #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;
Можно воспользоваться следующей рекурсивной функцией, записанной на языке Pascal: 
   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;
Доказать, что после исполнения алгоритма z равно удвоенному наименьшему общему кратному чисел a и b, т.е. z=2*НОК(a,b).  Указание . Заметим, что величина $m\cdot u+n\cdot v$не меняется в ходе выполнения алгоритма. Остается воспользоваться тем, что вначале она равна 2*a*b и что $НОД (a,b)\cdot НОК (a,b)=a\cdot b.$

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}
Оценка числа действий: каждое второе действие делит хотя бы одно из чисел m и n пополам. Приведем два варианта реализации алгоритма данной задачи на некотором алгоритмическом языке.  Первый вариант решения : 
   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;
  Программа на языке  Pascal .:     
   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;

 Второй вариант решения .

Для выделения периода десятичной дроби целесообразно воспользоваться следующей известной теоремой.  Теорема: Для того, чтобы правильная несократимая дробь представлялась чистой периодической дробью, необходимо и достаточно, чтобы ее знаменатель не делился нацело на 2 и 5. Использовать эту теорему можно следующим образом. Началу периода будет соответствовать тот момент разложения обыкновенной дроби в десятичную, когда у оставшейся неразложенной части знаменатель не будет делиться нацело ни на 2, ни на 5. Концу периода - момент, когда остаток от деления совпадает с остатком, соответствующим началу периода.

Период дроби равен периоду в последовательности остатков (докажите это; в частности, надо доказать, что он не может быть меньше). Кроме того, в этой последовательности все периодически повторяющиеся все члены различны, а предпериод имеет длину не более 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;
 

Вверх

Белорусский рейтинг MyMinsk.com Сайты беларуси Регистр "ЗУБР" Каталог на TIGA.BY, а также новости, работа, объявления, фото и многое другое Rambler's Top100 Белорусский каталог программ Faststart - рейтинг сайтов, каталог интернет ресурсов, счетчик посещаемос­ти Яндекс.Метрика
Hosted by uCoz