Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
Вальман Марина
0 / 0 / 0
Регистрация: 30.10.2013
Сообщений: 10
1

Найти все натуральные числа меньше N, которые одновременно являются числами Фибоначчи и простыми числами.

31.10.2013, 00:31. Просмотров 920. Ответов 6
Метки нет (Все метки)

Дано натуральное число N. Найти все натуральные числа меньше N, которые одновременно являются числами Фибоначчи и простыми числами.
Помогите, пожалуйста...желательно, с объяснениями. Спасибо заранее)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.10.2013, 00:31
Ответы с готовыми решениями:

В заданном интервале указать все числа, которые одновременно являются простыми и числами Фибоначчи
Посмотрите,пожалуйста, не знаю, как сделать правильно.. В заданном интервале...

Найти сумму тех элементов массива, которые являются простыми числами
Дан массив натуральных чисел А(N), значения элементов которого лежат в...

Найти количество тех элементов массива, которые не являются простыми числами
Найти количество тех элементов массива, которые не являются простыми числами, а...

Найти сверхпростые числа: простые числа, номера которых являются простыми числами.
Привет родные форумчане! Пожалуйста помогите решить буду особенно благодарен...

Вывод на экран элементов массивов, которые являются простыми числами
Здравствуйте! Пишу сюда в последней надежде на помощь! Нужно сдать две лабы...

6
Matan!
Delphi/Java/DB Dev + Math
447 / 311 / 118
Регистрация: 31.05.2013
Сообщений: 2,449
Записей в блоге: 5
Завершенные тесты: 2
31.10.2013, 08:32 2
Ну,как числа Фибоначчи задаются?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <stdio.h>
#include <conio.h>
 
using namespace std;
 
int fibonacci(int n)
{
    return (n<=2 ? 1 : fibonacci(n-1) + fibonacci(n-2));
}
 
int main(void)
{
    int N;
    cout << "Enter number" << endl;
    cin >> N;
    for (int n=1; n<=N; n++)
        cout << fibonacci(n) << ", ";
   cout << "..." << endl;
   _getch();
    return 0;
}
Проверку на простоту написать сможешь?
Кстати,данная программа будет работать медленно при больших N,поскольку имеет экспоненциальную(?) сложность алгоритма.
0
Байт
Эксперт C
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
31.10.2013, 08:56 3
Цитата Сообщение от Matan! Посмотреть сообщение
Кстати,данная программа будет работать медленно при больших N,поскольку имеет экспоненциальную(?) сложность алгоритма.
Можно сильно сократить вычислительную сложность, воспользовавшись тем, что для простоты Fn необходима простота n
0
ShadowFirst
55 / 48 / 13
Регистрация: 31.10.2013
Сообщений: 164
31.10.2013, 11:09 4
Мне одному кажется что рекурсия при использовании этого метода очень не хорошо?! Что проще все таки создать массив из N элементов и работать в нем. То есть сделать:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void fibonacci(char *mass, int size)
{
    if (size < 2) return;
    mass [0] = 0;
    mass [1] = 1;
    for (int i = 2; i < size; i++) {
        mass[i] = mass[i-1] + mass[i-2];
        cout << mass[i] << ", "<< "..." << endl;
    }
}
 
int main(void)
{
int N;
cout << "Enter number" << endl;
cin >> N;
char mass[N];
fibonacci(mass, N);
_getch();
return 0;
}
Этот вариант должен работать быстрее так как не рассчитывает заново предыдущие результаты а хранит их в массиве.

А если говорить по теме топика то вначале нужно определить максимальное число ваше Фибоначчи потом это максимальное число взять как конечный массив для нахождения простых чисел и потом сравнить содержимое одного и другого массива, те что совпали будет вашим результатом.
0
Matan!
Delphi/Java/DB Dev + Math
447 / 311 / 118
Регистрация: 31.05.2013
Сообщений: 2,449
Записей в блоге: 5
Завершенные тесты: 2
31.10.2013, 21:00 5
Цитата Сообщение от Байт Посмотреть сообщение
Можно сильно сократить вычислительную сложность, воспользовавшись тем, что для простоты Fn необходима простота n
Ответ мне не много дал,а автору темы тем более...
Ты мне не сложность скажи(это я и сам могу вычислить),а реализацию.
0
salam
175 / 156 / 29
Регистрация: 10.07.2012
Сообщений: 766
31.10.2013, 21:09 6
учитывая, что числа Фибоначчи растут экспоненциально, то можно каждое проверять на простоту элементарно за корень. итоговая асимптотика вроде все равно около ln(n) * sqrt(n).
0
Matan!
Delphi/Java/DB Dev + Math
447 / 311 / 118
Регистрация: 31.05.2013
Сообщений: 2,449
Записей в блоге: 5
Завершенные тесты: 2
01.11.2013, 06:19 7
Цитата Сообщение от salam Посмотреть сообщение
учитывая, что числа Фибоначчи растут экспоненциально, то можно каждое проверять на простоту элементарно за корень. итоговая асимптотика вроде все равно около ln(n) * sqrt(n).
Какие-то предложения насчёт реализации или хотя бы алгоритма?

Добавлено через 8 часов 22 минуты
Цитата Сообщение от ShadowFirst Посмотреть сообщение
void fibonacci(char *mass, int size) { if (size < 2) return; mass [0] = 0; mass [1] = 1; for (int i = 2; i < size; i++) { mass[i] = mass[i-1] + mass[i-2]; cout << mass[i] << ", "<< "..." << endl; } } int main(void) { int N; cout << "Enter number" << endl; cin >> N; char mass[N]; fibonacci(mass, N); _getch(); return 0; }
В строке
Цитата Сообщение от ShadowFirst Посмотреть сообщение
char mass[N];
выползает ошибка:
1 IntelliSense: выражение должно иметь константное значение
Цитата Сообщение от ShadowFirst Посмотреть сообщение
Этот вариант должен работать быстрее так как не рассчитывает заново предыдущие результаты а хранит их в массиве.
Очень даже возможно,что будет работать быстрее
Цитата Сообщение от ShadowFirst Посмотреть сообщение
вначале нужно определить максимальное число ваше Фибоначчи потом это максимальное число взять как конечный массив для нахождения простых чисел...
В этом и состоит задача-найти числа Фибоначчи максимально эффективным способом.
0
01.11.2013, 06:19
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.11.2013, 06:19

Получить в файле g только те компоненты, которые являются простыми числами
Дан файл f, компоненты которого являются целыми числами. Получить в файле g...

Вычислить сумму тех членов последовательности, которые являются простыми числами
Дана последовательность натуральных чисел длины n. Вычислить сумму тех из них,...

Определить количество и сумму элементов массива, которые не являются простыми числами
Пусть задан массив натуральных чисел из n компонент. Определить количество и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru