Паскаль. Основы программирования


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


Пример 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 на найденные делители.




Начало  Назад  Вперед



Книжный магазин