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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Вальман Марина
0 / 0 / 0
Регистрация: 30.10.2013
Сообщений: 10
#1

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

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

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

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

Найти количество тех элементов массива, которые не являются простыми числами - C++
Найти количество тех элементов массива, которые не являются простыми числами, а также найти минимальный элемент среди них. Указания к...

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

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Matan!
248 / 99 / 20
Регистрация: 31.05.2013
Сообщений: 879
Записей в блоге: 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,поскольку имеет экспоненциальную(?) сложность алгоритма.
Байт
Эксперт C
15639 / 9981 / 1499
Регистрация: 24.12.2010
Сообщений: 18,749
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!
248 / 99 / 20
Регистрация: 31.05.2013
Сообщений: 879
Записей в блоге: 2
Завершенные тесты: 1
31.10.2013, 21:00     Найти все натуральные числа меньше N, которые одновременно являются числами Фибоначчи и простыми числами. #5
Цитата Сообщение от Байт Посмотреть сообщение
Можно сильно сократить вычислительную сложность, воспользовавшись тем, что для простоты Fn необходима простота n
Ответ мне не много дал,а автору темы тем более...
Ты мне не сложность скажи(это я и сам могу вычислить),а реализацию.
salam
160 / 141 / 12
Регистрация: 10.07.2012
Сообщений: 720
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++
Пусть задан массив натуральных чисел из n компонент. Определить количество и сумму его компонент,которые не являются простыми числами

Вычислить индексы и минимальное значение только тех сумм элементов массива, которые являются простыми числами. - C++
Вычислить индексы и минимальное значение только тех сумм элементов массива (a1 + a2, a2 + a3, ..., an-1 + an), которые являются простыми...

Определить номера строк матрицы, все элементы которых являются простыми числами - C++
Дано: прямоугольная матрица A. Определить номера строк все элементы которых являются простыми числами. Проверку каждой строки на...

Используя функции сформировать одномерный массив и отсортировать по возрастанию только те элементы массива, которые являются простыми числами - C++
Помогите закончить две задачи. 1. Используя функции сформировать одномерный массив и отсортировать по возрастанию только те элементы...

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

Составить программу, которая выводит на экран все натуральные числа в диапазоне от 1 до n, которые являются степенью числа 2 - C++
Составил задачу которая только увеличивает на один ну тое сть выводит:1,2,3,4,...n Пытаюсь изменить чтоб выводило квадрат и тут...


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

Или воспользуйтесь поиском по форуму:
Matan!
248 / 99 / 20
Регистрация: 31.05.2013
Сообщений: 879
Записей в блоге: 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, которые одновременно являются числами Фибоначчи и простыми числами.
Ответ Создать тему
Опции темы

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