e-olymp 192. Просто Фибоначчи

Задача взята с сайта  e-olymp.com.

Найти [latex]N[/latex]-е по порядку простое число Фибоначчи.

Во входном файле число [latex]N[/latex], [latex]\left(1\leq N\leq 10 \right)[/latex] В выходной файл следует записать [latex]N[/latex]-е по порядку простое число Фибоначчи.

Тесты

[latex]N[/latex] Простое число Фибоначчи
 3  5
5 89
7 1597
9 514229
10 433494437

Код программы

Код на ideone.com

Выполненное задание на сайте  e-olimp.com здесь.

Алгоритм решения

  1. Нам необходимо вычислить первые десять элементов  последовательности Фибоначчи.  Для этого будем использовать цикл.   Пусть  [latex] a<b<c [/latex] , где [latex] a, b, c [/latex] являются членами последовательности Фибоначчи.  Обозначим, что элемент последовательности  равен сумме двух ему предшествующих элементов.  Далее присвоим переменным [latex]a, b[/latex] значения следующих элементов последовательности соответственно.  Таким образом присваиваем переменной [latex] a [/latex] значение переменной [latex] b [/latex] , переменной [latex] b[/latex] — значение переменной [latex] c [/latex] , а  переменной [latex] c [/latex] —  значение равное  [latex](a+b)[/latex].
  2. Но не каждый элемент последовательности Фибоначчи является простым числом. Следовательно, нам необходимо проверить делится ли без остатка полученное нами число на какое-либо число, отличное от [latex] 0 [/latex] , [latex] 1 [/latex] и самого себя.  Таким образом, если найденный элемент [latex] c [/latex] делится без остатка на целые  числа, принадлежащие отрезку [latex]\left[2;\sqrt{c} \right][/latex] , то найденный элемент не является простым числом. Тогда необходимо рассмотреть следующий элемент последовательности Фибоначчи. Для этого введем логическую переменную [latex] (bool x) [/latex] , которая будет принимать значение истинны только тогда, когда число простое.
  3. Когда логическая переменная принимает значение истины, то увеличим счетчик на единицу.  А искать последующие значения элемента[latex] c [/latex] будем до тех пор, пока значение счетчика не станет равным числу [latex] N [/latex].

4 thoughts on “e-olymp 192. Просто Фибоначчи

  1. Зачтено, но есть замечания по проверке на простоту:
    — Зачем искать делители после [latex]\sqrt{c}[/latex]?
    — Зачем Вы проверяете деление на чётные числа (4, 6, 8, …) если установлено, что на 2 число не делится?
    С учётом того, что 10-е простое число Фибоначчи очень велико (433494437), нужно экономить время и не делать лишних вычислений.

    Да! И не нужно проверять «x == true». Это слишком по-одесски: «Таки да истина?» Просто пишите x.

  2. Справедливости ради скажу, что в практике олимпиадного (не учебного!) программирования такую задачу иногда решают очень просто. Причина этого — очень небольшое количество возможных вариантов. Т.е. решение может быть совершенно парадоксальным:

    Засчитано.
    — Только сделайте что-то с этой фразой «Нам необходимо вычислить все элементы последовательности Фибоначчи». Если бы это было действительно необходимо для перехода на второй курс, нам пришлось бы ждать довольно долго. Я бы сказал — бесконечно долго.
    — Так не говорят «двух ему предыдущих». Возможно, Вы имели в виду «двух ему предшествующих».

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