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

Рекурсия: для числа n вывести все суммы, состоящие из чисел Фибоначчи

14.12.2017, 17:02. Показов 582. Ответов 0
Метки нет (Все метки)

Задача.
Для числа n вывести все суммы, состоящие из чисел Фибоначчи.
Код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
using namespace std;
int f[1000];
void cnt(int n, vector<int> A, int i)
{
    if (n == 0)
    {
        for (int j = 0; j < A.size(); j++)
        {
            cout << A[j];
            if (A.size() - j > 1) cout << "+";
        }
        cout << endl;
    }
    else
    {
        while (f[i] <= n)
        {
            A.push_back(f[i]);
            cnt(n-f[i], A, i);
            i++;
        }
    }
}
int main()
{
    int n, i;
    cin >> n;
    vector<int> A(0);
    f[0] = 1;
    f[1] = 2;
    i = 1;
    while (f[i] <= n)
    {
        i++;
        f[i] = f[i-1] + f[i-2];
    }
    i = 0;
    while (f[i] <= n)
    {
        cnt(n, A, i);
        i++;
    }
    return 0;
}
Ввод:
Код
6
Вывод:
Код
1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+2+3
1+1+1+2+2
1+1+2+2+3
1+1+2+3+5
1+2+2+2
1+2+3+3
2+2+2
2+3+3
3+3
То есть, из правильных сумм выводятся только те, которые состоят из одного и того же числа. На мой взгляд, проблема состоит именно в том, что из вектора не всегда убираются числа, полученные после очередной интерации рекурсии. Как это можно исправить?
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.12.2017, 17:02
Ответы с готовыми решениями:

Рекурсия: вычисление суммы k элементов последовательности чисел Фибоначчи
Помогите пожалуйста с последней задачкой справиться, непонятна она мне.Нужно составить программу,...

Вывести все различные представления числа N в виде суммы натуральных чисел
Программа должна вывести все различные представления натурального числа N в виде суммы натуральных...

Вывести все возможные представления натурального числа N в виде суммы других натуральных чисел
Написать программу, выводящую все возможные представления натурального числа N в виде суммы...

Вывести на экран все возможные различные способы представления числа в виде суммы натуральных чисел
Дано натуральное число N. Требуется получить и вывести на экран все возможные различные способы...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.12.2017, 17:02
Помогаю со студенческими работами здесь

Найти все натуральные числа, состоящие из N цифр, для которых верно утверждение "все цифры числа различны"
Дано натуральное число N (2&lt;=N&lt;=8). Найти все натуральные числа, состоящие из N цифр, для которых...

Дан целый массив. выяснить имеются ли в нем числа, состоящие только из четных цифр. Если да, то вывести все найденные числа и их порядковые номера
#include &lt;iostream&gt;#include &lt;clocale&gt;using namespace std;bool f (int num){ bool fl=false; while...

Вывести на экран все числа, номера которых есть числа Фибоначчи
Вывести на экран все числа заданной последовательности, номера которых есть числа Фибоначчи.

Вывести в обратном порядке все строки, состоящие только из чисел одного знака
Задача: Дан двумерный массив целых чисел. Вывести в обратном порядке все строки, состоящие...

Выделить из строки все слова, состоящие из чисел, и вывести оставшиеся по возрастанию длин
Всем привет! Вернулся сюда опять за помощью , вот условие программы : &quot;Выделить из строки все...

Вывести в обратном порядке все строки, состоящие только из чисел одного знака
Дан двумерный массив целых чисел. Вывести в обратном порядке все строки, состоящие только из чисел...


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

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

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