Задача взята с сайта 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 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#include <iostream> #include <cmath> using namespace std; int main() { int n; cin >> n; int a, b, c, d, k; a = 1; b = 1; c = 2; bool x; int counter = 0; while (counter < n){ x = true; c = a + b; a = b; b = c; for (int j = 2; j <= sqrt(c) && x; j++) { if((c%j) == 0){ x = false; } } if (x){ counter ++; } } cout << c; return 0; } |
Код на ideone.com
Выполненное задание на сайте e-olimp.com здесь.
Алгоритм решения
- Нам необходимо вычислить первые десять элементов последовательности Фибоначчи. Для этого будем использовать цикл. Пусть [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].
- Но не каждый элемент последовательности Фибоначчи является простым числом. Следовательно, нам необходимо проверить делится ли без остатка полученное нами число на какое-либо число, отличное от [latex] 0 [/latex] , [latex] 1 [/latex] и самого себя. Таким образом, если найденный элемент [latex] c [/latex] делится без остатка на целые числа, принадлежащие отрезку [latex]\left[2;\sqrt{c} \right][/latex] , то найденный элемент не является простым числом. Тогда необходимо рассмотреть следующий элемент последовательности Фибоначчи. Для этого введем логическую переменную [latex] (bool x) [/latex] , которая будет принимать значение истинны только тогда, когда число простое.
- Когда логическая переменная принимает значение истины, то увеличим счетчик на единицу. А искать последующие значения элемента[latex] c [/latex] будем до тех пор, пока значение счетчика не станет равным числу [latex] N [/latex].
Зачтено, но есть замечания по проверке на простоту:
— Зачем искать делители после [latex]\sqrt{c}[/latex]?
— Зачем Вы проверяете деление на чётные числа (4, 6, 8, …) если установлено, что на 2 число не делится?
С учётом того, что 10-е простое число Фибоначчи очень велико (433494437), нужно экономить время и не делать лишних вычислений.
Да! И не нужно проверять «x == true». Это слишком по-одесски: «Таки да истина?» Просто пишите x.
Спасибо за замечания, исправила код.
Справедливости ради скажу, что в практике олимпиадного (не учебного!) программирования такую задачу иногда решают очень просто. Причина этого — очень небольшое количество возможных вариантов. Т.е. решение может быть совершенно парадоксальным:
Засчитано.
— Только сделайте что-то с этой фразой «Нам необходимо вычислить все элементы последовательности Фибоначчи». Если бы это было действительно необходимо для перехода на второй курс, нам пришлось бы ждать довольно долго. Я бы сказал — бесконечно долго.
— Так не говорят «двух ему предыдущих». Возможно, Вы имели в виду «двух ему предшествующих».
Спасибо, Игорь Евгеньевич, исправила неточности.