Разные задачи

Пример 1. Составить программу определения всех делителей числа n.

Когда ставится такая задача, то очень часто учащиеся предлагают такой способ решения.

Надо испробовать все натуральные числа, начиная от 1 до n и, если какое-то из них будет являться делителем числа n, тогда выдавать его на экран. Например, для числа 36, берем для проверки числа 1, 2, 3, ..., 36 и выбираем из них делители 36. Делители будут следующими: 1, 2, 3, 4, 6, 9, 12, 18 и 36.

Такой способ возможен. Но, если вы внимательно посмотрите на делители числа 36, то обнаружите, что все они находятся в интервале от 1 до 18, т.е. до половины числа 36 и лишь последний делитель - это само число.

Да и простая логика рассуждений убеждает нас, что делители будут располагаться именно в этом интервале: от 1 до

.

Если допустить мысль, что есть делитель больше половины числа, тогда умножив его только лишь на 2, мы получим число большее заданного.

Итак, становится ясным, что все делители числа, кроме самого, находятся в промежутке от 1 до

, а значит надо проверять числа на возможные делители именно из этого промежутка.

Отсюда возникает такой план составления программы: организовать цикл от 1 до

; если

число n делится на число из этого промежутка, тогда вывести этот делитель на экран; продолжить цикл; выдать на экран само число.

Программа

Program

Problem1; { Простой алгоритм. 1 - способ }

      uses WinCrt;

    var

       n, d : integer;

    begin

       write('Введите целое число '); readln(n);

       d := 1;

       writeln('Делители числа ', n);

          repeat

             if n mod d = 0 then write(d, ' ');

             d := d + 1

          until d > n div 2;

       write(n)

    end.

Но и при решении этой задачи машине можно помочь и облегчить ее работу. Здесь на помощь снова приходит математика.

Оказывается, для того чтобы найти делители числа n, достаточно обнаружить делители не превышающие

.

Все остальные делители получаются в результате деления числа n на найденные делители.

Например, если n = 30, то достаточно найти делители 1, 2, 3, 5 (натуральный квадратный корень из 30 равен 5), а все прочие делители получаются делением на найденные:

30 div 1 = 30;

30 div 2 = 15;

30 div 3 = 10;

30 div 5 = 6.

При составлении программы возникает проблема - нет встроенной функции извлечения квадратного корня в множестве целых чисел. Это препятствие легко обойти, если организовать цикл для выбора делителей d от 1 до тех пор пока

d*d<n (что является тем же, что и < n), а если корень квадратный извлекается нацело, тогда этот случай надо рассмотреть отдельно после завершения основного цикла.

Почему надо сделать именно так. Это становится понятным на примере для числа 36. = 6, цикл - пока dd < 6;

d = 1, dd = 11 = 1 < 36 (истина),

цикл продолжается;

находится остаток от деления 36 mod 1 = 0; выдается 1 и частное от деления 36 на 1, 36 div 1 =36;

d = 2, dd = 22 = 4 < 36 (истина),

цикл продолжается;

36 mod 2 = 0;

выдается 2 и частное от деления 36 на 2, 36 div 2 = 18;

d = 3, dd = 33 = 9 < 36 (истина),

цикл продолжается;

36 mod 3 = 0;

выдается 3 и частное от деления 36 на 3, 36 div 3 = 12;

d = 4, dd = 44 = 16 < 36 (истина),

цикл продолжается;

36 mod 4 =0;

выдается 4 и 36 div 4 = 9;

d = 5, dd = 55 = 25 < 36 (истина),

цикл продолжается;

36 mod 5 <>0, ничего не выдается на экран,

цикл продолжается;

d = 6, dd = 66 = 36 < 36 (ложь), цикл заканчивается.

Проверяется d = 6 (dd = n), 66 = 36 (истина), выдается 6.

Если бы цикл продолжался, пока dd <= n, тогда при d = 6 на экран выдавалось бы - 6 и 36 div 6 = 6, т. е. две шестерки, что было бы ошибкой.





Программа

Program

Problem1a;    { Делители числа. 2 - способ }

    uses WinCrt;

    var

       n, d : integer;

    begin

       write('Введите целое число '); readln(n);

       writeln('Делители числа ', n);

         d := 1;

         while d*d < n do

             begin

                if n mod d=0 then write(d, ' ', n div d, ' ');

                d := d + 1

             end;

         if d*d = n then write(d);  writeln

    end.


Содержание раздела

---