Тема 2 Производящие функции и ряды
При построении алгебраических рядов используют так называемые производящие функции. Основным способом решения этого класса задач является порождение множителей с помощью циклических конструкций и, возможно, проверка того, удовлетворяет ли данный член заданному условию или нет.
К подобным задачам относят и проверки различных свойств натуральных чисел, например проверку того, является ли число простым, совершенным, автоморфным и т. д.
Алгоритмы решения для таких задач сходны между собой. Они состоят из трех шагов:
■ ввода и проверки данных;
■ цикла, который порождает множители с проверкой на выполнение какого-либо свойства;
■ вывода результатов.
Например, вывод на экран
последовательности следующего вида:
может быть организован
следующей программой:
PROGRAM ROW;
Var n, I: integer;
F : BOOLEAN;
BEGIN
REPEAT
WRITE('BBEДИTE НАТУРАЛЬНОЕ ЧИСЛО N = ');
READLN (N);
UNTIL N>2;
IF N MOD 2 = 0 THEN F := FALSE
ELSE F := TRUE;
WRITE('S =');
FOR I := 1 TO N-2 DO
IF(NOT F) AND (I MOD 2 = 0)THEN WRITE(l, '*');
ELSE
IF F AND (I MOD 2 <>0) THEN WRITE(I,'*');
WRITELN(N)
END.
Вначале описываются переменные N, I как целые, где N - заданное число, а I - переменная цикла. Вводим вспомогательную логическую переменную (флаг) F, с помощью которой учитываем четность числа N.
Тело программы начинается с ввода целого числа и проверки того, является ли оно натуральным и большим двух:
REPEAT
WRITE('BBEДИTE НАТУРАЛЬНОЕ ЧИСЛО N = ');
READLN (N);
UNTIL N>2;
Оператор REPEAT... требует ввода данных до тех пор, пока пользователь не введет положительное число большее двух.
Флаг F устанавливается в зависимости от четности числа. Для определения четности используется стандартная функция MOD, которая вычисляет остаток от деления
(N MOD 2) числа N на 2.
На втором шаге, в цикле
FOR I := 1 ТО N-2 DO
IF(NOT F) AND (I MOD 2 = 0)THEN WRITE(I,'*')
ELSE
IF F AND (I MOD 2 <>0) THEN WRITE(I,'*');
мы порождаем натуральное число i в интервале от 1 до N-2 и в зависимости от четности числа формируем требуемый ряд, выводя его на экран в одну строку.
По выходе из цикла на экран выводится N как завершающий член ряда и строка закрывается: WRITELN(*', N);
Эту же задачу можно решить по-другому. Тело цикла выглядит следующим образом:
IF N MOD 2=0 THEN
BEGIN
l:=2;
REPEAT
I := 1+2;
WRITE(*', I)
UNTIL I = N-2
END
ELSE
BEGIN
WRITE(1);
I:= 1;
REPEAT
I := I+2;
WRITE(*', I)
UNTIL I = N-2
END;
Несмотря на то что программа выглядит длиннее, в ней не порождаются лишние члены, а в зависимости от четности числа выбирается тот цикл, который необходим. В отличие от первого примера для любого их этих циклов переменная I увеличивается на 2 за каждый проход.
Рассмотрим несколько примеров, использующих метод производящих функций.
Задача 2.1 Дано натуральное число N. Определить, является ли оно простым.
"Число 1 может быть отнесено к простым числам; однако предпочтительно выделять его особо, не относя ни к простым, ни к составным" (М. Я. Выгодский. Справочник по элементарной математике, 1965 г.).
PROGRAM PRG2_1;