Проверить, что среди первых n*n-1 чисел Фибоначчи есть хотя бы одно, делящееся на n

Задача

Написать программу, которая проверяла бы, что каково бы ни было натуральное число n, среди первых n2-1 чисел Фибоначчи найдется хотя бы одно, делящееся на n.

Решение

Алгоритм решения задачи: 

Пусть работа программы будет заключаться в том, что ряд Фибоначчи будет выводится до первого числа кратного n. При этом количество элементов ряда не может превысить n*n-1. Если цикл дойдет до конца и не будет найдено ни одно число, делящееся на n, то значит утверждение о том, что существует хотя бы одно число, делящееся на n, в ряде из n*n-1 элементов, ложно.

Поскольку в языке Паскаль нет очень длинных целых, а числа ряда Фиббоначи быстро возрастают, то n было ограничено числом 25.

Программа на языке Паскаль:

var i, a, b, c: longint;
    n: byte;
begin
    readln(n);
    if n > 25 then exit;
    writeln('Максимальное количество исследуемых элементов: n*n-1 = ', n*n-1);
    a := 1;
    b := 1;
    for i:=1 to n*n-1 do begin
        writeln(i,' - ',a);
        if a mod n = 0 then begin
            writeln(a,' делится на ', n);
            break;
        end;
        c := a + b;
        a := b;
        b := c;
    end;
end.

Пример:

19
Максимальное количество исследуемых элементов: n*n-1 = 360
1 - 1
2 - 1
3 - 2
4 - 3
5 - 5
6 - 8
7 - 13
8 - 21
9 - 34
10 - 55
11 - 89
12 - 144
13 - 233
14 - 377
15 - 610
16 - 987
17 - 1597
18 - 2584
2584 делится на 19

Тема

Циклы

Уровень

Комбинированные задачи

Теги

Добавить комментарий