0 / 0 / 0
Регистрация: 30.10.2013
Сообщений: 10
1

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

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

Дано натуральное число N. Найти все натуральные числа меньше N, которые одновременно являются числами Фибоначчи и простыми числами.
Помогите, пожалуйста...желательно, с объяснениями. Спасибо заранее)
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
31.10.2013, 00:31
Ответы с готовыми решениями:

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

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

Вывести на экран числа, являющиеся одновременно простыми числами и числами Фибоначчи
Помогите составить программу: С клавиатуры вводится натуральное число N(N<=1 000 000 000)....

Среди всех делителей числа N найти и вывести те, которые являются простыми числами
1)задано натуральное число N. Среди всех делителей числа N найти и вывести те,которые являются...

6
Модератор
1436 / 1011 / 228
Регистрация: 31.05.2013
Сообщений: 6,645
Записей в блоге: 6
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
26949 / 16830 / 3698
Регистрация: 24.12.2010
Сообщений: 37,768
31.10.2013, 08:56 3
Цитата Сообщение от Matan! Посмотреть сообщение
Кстати,данная программа будет работать медленно при больших N,поскольку имеет экспоненциальную(?) сложность алгоритма.
Можно сильно сократить вычислительную сложность, воспользовавшись тем, что для простоты Fn необходима простота n
0
55 / 48 / 13
Регистрация: 31.10.2013
Сообщений: 166
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
Модератор
1436 / 1011 / 228
Регистрация: 31.05.2013
Сообщений: 6,645
Записей в блоге: 6
31.10.2013, 21:00 5
Цитата Сообщение от Байт Посмотреть сообщение
Можно сильно сократить вычислительную сложность, воспользовавшись тем, что для простоты Fn необходима простота n
Ответ мне не много дал,а автору темы тем более...
Ты мне не сложность скажи(это я и сам могу вычислить),а реализацию.
0
193 / 173 / 30
Регистрация: 10.07.2012
Сообщений: 800
31.10.2013, 21:09 6
учитывая, что числа Фибоначчи растут экспоненциально, то можно каждое проверять на простоту элементарно за корень. итоговая асимптотика вроде все равно около ln(n) * sqrt(n).
0
Модератор
1436 / 1011 / 228
Регистрация: 31.05.2013
Сообщений: 6,645
Записей в блоге: 6
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.11.2013, 06:19
Помогаю со студенческими работами здесь

На заданном интервале найти все числа Фибоначчи, которые являются простыми
На заданном интервале найти все число Фибоначчи, которые являются простыми числами

Удалить из вектора все элементы, которые не являются простыми числами
Люди добрые! Помогите решить контрольную в Pascal 1. С клавиатуры вводятся длина (&lt;=100) вектора и...

Сформировать массив из всех делителей числа, которые являются простыми числами
Помогите, пожалуйста, написать программу на языке С. Буду признателен за помощь. Вот условие: С...

Среди чисел 1,2,...,n найти те, которые являются простыми числами
Дано натуральное число n. Среди чисел 1,2,...,n найти те, которые являются простыми числами....

Найти количество элементов массива, которые являются простыми числами
Здраствуйте!!!Решите пожалуйста задачки!Заранее благодарен!!! Задачка №1 Сформировать массив из...

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru