Задача 12. Найти НОД двух чисел по алгоритму Евклида

Решение

Алгоритм решения. Пусть a  b  0 и a > 0. Тогда применение алгоритма Евклида происходит так: если b = 0, то НОД(a, b) = a. Иначе вычисляем r, равное остатку от деления a на b, и сводим задачу отыскания НОД(a, b) к задаче отыскания НОД(r, b). При r>0 этот процесс можно продолжить. Имеем: b > r > r₁ > r₂ > r₃ >,..., но так как b, r, r₁, r₂, r₃ - неотрицательные целые числа, то найдется n такое, что rn = 0. В соответствии с высказанным утверждением

НОД(a, b) = НОД(b, r) = НОД(r₁, r) =... = НОД(r_n-1, 0) = r_n-1.

Практически это выглядит так. Надо найти НОД чисел 888 и 351.

Большим из них является 888, a = 888, b = 351.

Находим остаток от деления a на b: 888 mod 351 = 186, r = 186;

заменим a на b и b на остаток r, получим: a = 351, b = 186;

снова находим остаток от деления a на b: 351 mod 186 = 165, r = 165;

заменим a на b и b на остаток r, получим: a = 186, b = 165;

находим остаток от деления a на b: 186 mod 165 = 21, r = 21;

заменим a на b и b на остаток r, получим: a = 165, b = 21;

находим остаток от деления a на b; 165 mod 21 = 18, r = 18;

заменим a на b и b на остаток r, получим: a = 21, b = 18;

находим остаток от деления a на b; 21 mod 18 = 3, r = 3;

заменим a на b и b на остаток r, получим: a = 18, b = 3;

находим остаток от деления a на b: 18 mod 3 = 0, r = 0;

заменим a на b и b на остаток r, получим: a = 3, b = 0.

Как только b стало равным нулю, цикл заканчивается, выдается значение a, которое и является наибольшим общим делителем, НОД(888, 351) = a = 3.

Этот процесс можно записать в виде следующей цепочки, которая в общем виде была записана выше:

НОД(888, 351) = НОД(351, 186) = НОД(186, 165) =

= НОД(165, 21) = НОД(21, 18) = НОД(18, 3) = НОД(3, 0) = 3.

Program Problem12; { Алгоритм Евклида }

uses WinCrt;

var

   a, b, r, a1, b1: integer;

begin

   write('Введите первое число '); readln(a);

   write('Введите второе, не равное нулю, число ');

   readln(b);

      a1:= a; b1:= b;

      repeat

         r:= a mod b;

         a:= b; b:= r

      until b = 0;

   writeln(' НОД чисел ', a1, ' и ', b1, ' равен ', a)

end.

 

Задача 13. Составить программу, которая определяет является ли данное число n простым.

Решение

Program Problem 1 3;

uses Crt;

var

  n, i, k: integer;

begin

  write('Введите натуральное число большее 2 ');

  readln(n);

     i:= 2; k:= 0;

     repeat

        if n mod i=0 then k:= k + 1;

        i:= i + 1

     until i>n div 2;

  if k = 0 then writeln('Число ', n, ' является простым')

               else writeln(' Число ', n, ' составное ')

end.

Задача 14. Составить программу нахождения всех простых чисел из заданного промежутка [n, m].

Решение

Program Problem14; { Простые числа из промежутка [n; m] }

uses Crt;

var

   n, m, p, i, k: integer;

begin

   write('Введите левую границу промежутка '); readln(n);

   write('Введите правую границу промежутка '); readln(m);

    writeln('Простые числа из промежутка [', n, ' ', m, ']');

   p:= n; if p = 1 then p:= p + 1;

repeat

if p = 2 then write(p:4, ' ')

             else if p = 3

                     then write(p:4, ' ')

                      else  

                      if p mod 2 <> 0

                          then

                             begin

                                i:= 3; k:= 0;

                                repeat

                                    if p mod i = 0 then k:= k + 1;

                                   i:= i + 2

                                 until i > p div 2;

                                 if k = 0 then write(p:4, ' ')

                              end;

         p:= p + 1

      until p = m;

   writeln

end.

Задача 15. Составить программу вычисления факториала числа n, т. е. n!.

Решение

Способ

Program Problem15; { Вычисление факториала числа n! }

uses Crt;

var

  n, f, i: longint;

begin

  write('Введите натуральное число '); readln(n);

  f:= 1;

    if n <> 0 then for i:= 1 to n do f:= f*i;

  writeln('Факториал числа ', n, ' равен ', f)

end.

Способ

Program Problem1a;

uses WinCrt;

var

   n, i, f: longint;

begin

   write('Введите натуральное число '); readln(n);

   f:= 1;

   if n <> 0 then for i:= n downto 1 do f:= f*i;

  writeln('Факториал числа ', n, ' равен ', f)

end.

 

Задача 16. Квадрат любого натурального числа n равен сумме n первых нечетных чисел:

12 = 1

22 = 1 + 3

32 = 1 + 3 + 5

42 = 1 + 3 + 5 + 7

52 = 1 + 3 + 5 + 7 + 9

 ...................

Основываясь на этом свойстве, составить программу, позволяющую напечатать квадраты натуральных чисел от 1 до n.

Решение

Program Problem16;

uses Crt;

var

   i, n, s, k: integer;

begin

   writeln('Введите натуральное число, до которого надо');

   write('выводить квадраты чисел '); readln(n);

   writeln('Квадраты чисел следующие:');

   s:= 0; k:= 1;

      for i:= 1 to n do

          begin

             s:= s + k;

             writeln(' Квадрат числа ', i, ' равен ', s);

             k:= k + 2

          end

end.

Задача 17.  Напечатать все четырехзначные числа, в десятичной записи которых нет двух одинаковых цифр.

Решение

Способ

Program Problem 17; { 1 - й способ }

uses WinCrt;

var

  t, s, d, e: integer;

begin

  writeln('Все четырехзначные числа из разных цифр');

  for t:= 1 to 9 do

    for s:= 0 to 9 do

      for d:= 0 to 9 do

        for e:= 0 to 9 do

           if (t <> s) and (t <> d) and (t <> e) and (s <> d) and

              (s <> e) and (d <> e)

           then write(t*1000 + s*100 + d*10 + e, ' ')

      end.

 

Способ

Program Problem17a; { 2 - й способ }

uses WinCrt;

var

  t, s, d, e: integer;

   begin

  writeln('Все четырехзначные числа из разных цифр');

  for t:= 1 to 9 do

    for s:= 0 to 9 do if s <> t then

      for d:= 0 to 9 do if (d <> s) and (d <> t) then

        for e:= 0 to 9 do

          if (e <> d) and (e <> s) and (e <> t)

            then write((((t*10 + s)*10 + d)*10) + e, ' ')

end.