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

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

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

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

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

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

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

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

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

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Matan!
274 / 124 / 25
Регистрация: 31.05.2013
Сообщений: 1,135
Записей в блоге: 2
Завершенные тесты: 1
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
16062 / 10331 / 1540
Регистрация: 24.12.2010
Сообщений: 19,472
31.10.2013, 08:56 #3
Цитата Сообщение от Matan! Посмотреть сообщение
Кстати,данная программа будет работать медленно при больших N,поскольку имеет экспоненциальную(?) сложность алгоритма.
Можно сильно сократить вычислительную сложность, воспользовавшись тем, что для простоты Fn необходима простота n
0
ShadowFirst
55 / 48 / 1
Регистрация: 31.10.2013
Сообщений: 161
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!
274 / 124 / 25
Регистрация: 31.05.2013
Сообщений: 1,135
Записей в блоге: 2
Завершенные тесты: 1
31.10.2013, 21:00 #5
Цитата Сообщение от Байт Посмотреть сообщение
Можно сильно сократить вычислительную сложность, воспользовавшись тем, что для простоты Fn необходима простота n
Ответ мне не много дал,а автору темы тем более...
Ты мне не сложность скажи(это я и сам могу вычислить),а реализацию.
0
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 728
31.10.2013, 21:09 #6
учитывая, что числа Фибоначчи растут экспоненциально, то можно каждое проверять на простоту элементарно за корень. итоговая асимптотика вроде все равно около ln(n) * sqrt(n).
0
Matan!
274 / 124 / 25
Регистрация: 31.05.2013
Сообщений: 1,135
Записей в блоге: 2
Завершенные тесты: 1
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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.11.2013, 06:19
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
01.11.2013, 06:19
Ответ Создать тему
Опции темы

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