Форум программистов, компьютерный форум CyberForum.ru

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

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

C++ Вывод на экран элементов массивов, которые являются простыми числами
C++ Используя функции сформировать одномерный массив и отсортировать по возрастанию только те элементы массива, которые являются простыми числами
Найти сумму тех элементов массива, которые являются простыми числами C++
C++ Даны натуральные числа N, K, L (K<L). Вывести на экран все делители числа N, которые меньше K или больше L
Составить программу, которая выводит на экран все натуральные числа в диапазоне от 1 до n, которые являются степенью числа 2 C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Matan!
13 / 13 / 1
Регистрация: 31.05.2013
Сообщений: 206
Записей в блоге: 2
Завершенные тесты: 1
31.10.2013, 08:32     Найти все натуральные числа меньше N, которые одновременно являются числами Фибоначчи и простыми числами. #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,поскольку имеет экспоненциальную(?) сложность алгоритма.
Байт
 Аватар для Байт
13970 / 8801 / 1226
Регистрация: 24.12.2010
Сообщений: 15,944
31.10.2013, 08:56     Найти все натуральные числа меньше N, которые одновременно являются числами Фибоначчи и простыми числами. #3
Цитата Сообщение от Matan! Посмотреть сообщение
Кстати,данная программа будет работать медленно при больших N,поскольку имеет экспоненциальную(?) сложность алгоритма.
Можно сильно сократить вычислительную сложность, воспользовавшись тем, что для простоты Fn необходима простота n
ShadowFirst
54 / 47 / 1
Регистрация: 31.10.2013
Сообщений: 161
31.10.2013, 11:09     Найти все натуральные числа меньше N, которые одновременно являются числами Фибоначчи и простыми числами. #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;
}
Этот вариант должен работать быстрее так как не рассчитывает заново предыдущие результаты а хранит их в массиве.

А если говорить по теме топика то вначале нужно определить максимальное число ваше Фибоначчи потом это максимальное число взять как конечный массив для нахождения простых чисел и потом сравнить содержимое одного и другого массива, те что совпали будет вашим результатом.
Matan!
13 / 13 / 1
Регистрация: 31.05.2013
Сообщений: 206
Записей в блоге: 2
Завершенные тесты: 1
31.10.2013, 21:00     Найти все натуральные числа меньше N, которые одновременно являются числами Фибоначчи и простыми числами. #5
Цитата Сообщение от Байт Посмотреть сообщение
Можно сильно сократить вычислительную сложность, воспользовавшись тем, что для простоты Fn необходима простота n
Ответ мне не много дал,а автору темы тем более...
Ты мне не сложность скажи(это я и сам могу вычислить),а реализацию.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
31.10.2013, 21:09     Найти все натуральные числа меньше N, которые одновременно являются числами Фибоначчи и простыми числами. #6
учитывая, что числа Фибоначчи растут экспоненциально, то можно каждое проверять на простоту элементарно за корень. итоговая асимптотика вроде все равно около ln(n) * sqrt(n).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.11.2013, 06:19     Найти все натуральные числа меньше N, которые одновременно являются числами Фибоначчи и простыми числами.
Еще ссылки по теме:

Вычислить индексы и минимальное значение только тех сумм элементов массива, которые являются простыми числами. C++
Найти количество тех элементов массива, которые не являются простыми числами C++
C++ Найти в файле слова длины которых являются числами Фибоначчи

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

Или воспользуйтесь поиском по форуму:
Matan!
13 / 13 / 1
Регистрация: 31.05.2013
Сообщений: 206
Записей в блоге: 2
Завершенные тесты: 1
01.11.2013, 06:19     Найти все натуральные числа меньше N, которые одновременно являются числами Фибоначчи и простыми числами. #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 Посмотреть сообщение
вначале нужно определить максимальное число ваше Фибоначчи потом это максимальное число взять как конечный массив для нахождения простых чисел...
В этом и состоит задача-найти числа Фибоначчи максимально эффективным способом.
Yandex
Объявления
01.11.2013, 06:19     Найти все натуральные числа меньше N, которые одновременно являются числами Фибоначчи и простыми числами.
Ответ Создать тему
Опции темы

Текущее время: 18:06. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru