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

14.12.2017, 17:02. Показов 718. Ответов 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;
}

Ввод:

Code
1
6

Вывод:

Code
1
2
3
4
5
6
7
8
9
10
11
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

То есть, из правильных сумм выводятся только те, которые состоят из одного и того же числа. На мой взгляд, проблема состоит именно в том, что из вектора не всегда убираются числа, полученные после очередной интерации рекурсии. Как это можно исправить?

Programming

Эксперт

39485 / 9562 / 3019

Регистрация: 12.04.2006

Сообщений: 41,671

Блог

14.12.2017, 17:02

Ответы с готовыми решениями:

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

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

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

inter-admin

Эксперт

29715 / 6470 / 2152

Регистрация: 06.03.2009

Сообщений: 28,500

Блог

14.12.2017, 17:02

Помогаю со студенческими работами здесь

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

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

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

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

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

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

Или воспользуйтесь поиском по форуму:

Новые блоги и статьи Все статьи Все блоги /
сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и источниками (напряжения, ЭДС и тока). Найти токи и напряжения во всех элементах. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и. . .

Наверх