Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
TsarTsar
0 / 0 / 0
Регистрация: 11.10.2015
Сообщений: 7
1

Просчитать количество вариантов представления числа в виде суммы натуральных цифр 1, 2 и 3

11.10.2015, 20:42. Просмотров 951. Ответов 9
Метки нет (Все метки)

Дано натуральное число N. Необходимо просчитать количество вариантов представления числа в виде суммы натуральных цифр 1, 2 и 3.
К примеру число 4
1+1+1+1
1+1+2
2+2
1+3
4 варианта
Помогите пожалуйста.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.10.2015, 20:42
Ответы с готовыми решениями:

Найти все представления натурального числа в виде суммы натуральных чисел
Скласти програму, яка друкує всі різні представлення числа N у вигляді сум K...

Найти количество способов представления заданного числа N в виде суммы степеней двойки
Всем привет. Задача звучит так: Любое натуральное число можно представить в...

дано натуральное число N. Определить,во сколько раз произведение цифр числа больше суммы цифр.Найти количество чётных цифр в записи числа!!
дано натуральное число N. Определить,во сколько раз произведение цифр числа...

Вводятся 3 натуральных числа. Найти сумму цифр каждого из них *(создать рекурсивную функцию для нахождения *суммы цифр п
#include <iostream> using namespace std; int Sum(int n) { int...

Найти числа, которые представимы в виде суммы квадратов двух натуральных чисел
Используя операторы цикла while или do...while Дано натуральное число N. Среди...

9
Байт
Эксперт C
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
11.10.2015, 20:47 2
Глянь Разложить n шаров по m ящикам
0
TsarTsar
0 / 0 / 0
Регистрация: 11.10.2015
Сообщений: 7
11.10.2015, 20:56  [ТС] 3
Цитата Сообщение от Байт Посмотреть сообщение
Глянь Разложить n шаров по m ящикам
Штука вроде полезная, но там сложное математическое решение, к тому же условие задачи другое, а мне бы код ><
Программа насколько я знаю должна выйти небольшая
0
Dimension
Dimension
573 / 443 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
11.10.2015, 21:20 4
Цитата Сообщение от TsarTsar Посмотреть сообщение
насколько я знаю
у вас хоть какие=нибуду предположения есть по реализации?
0
TsarTsar
0 / 0 / 0
Регистрация: 11.10.2015
Сообщений: 7
11.10.2015, 21:44  [ТС] 5
Цитата Сообщение от Dimension Посмотреть сообщение
у вас хоть какие=нибуду предположения есть по реализации?
Я попытался составить блок-схему с помощью счетчика и блоков модификации, однако не особо продвинулся в этом плане. Я пытался эксперементировать с 3 блоками модификации вида
x=0;n;1
y=0;n/2;1
z=0;n/3;1
Потом я пытался использовать n div 2 и n div 3 во втором и третьем блоке, а также n mod 2 и n mod 3, однако ничего не добился =\ Если кто-нибудь поможет с составлением блок схемы, я буду очень признателен.
0
Байт
Эксперт C
18318 / 12029 / 2506
Регистрация: 24.12.2010
Сообщений: 24,293
11.10.2015, 21:54 6
TsarTsar, да, я погорячился, задача твоя и проще, и решабельней. Но вовсе не так уж и проста. Тут нужен хороший, умный перебор. Прямо так ничего в больную голову не приходит. Как придет - я тебе обязательно расскажу. Но ты особо на меня не рассчитывай, думай своей головой.

Не по теме:

Не оставляйте стараний, Маэстро, не убирайте ладони со лба

0
TsarTsar
0 / 0 / 0
Регистрация: 11.10.2015
Сообщений: 7
11.10.2015, 22:22  [ТС] 7
Цитата Сообщение от Байт Посмотреть сообщение
TsarTsar, да, я погорячился, задача твоя и проще, и решабельней. Но вовсе не так уж и проста. Тут нужен хороший, умный перебор. Прямо так ничего в больную голову не приходит. Как придет - я тебе обязательно расскажу. Но ты особо на меня не рассчитывай, думай своей головой.
Думаю уже целый день, да ничего путного не вышло, поэтому на форум и написал
Даже не нужен мне код уже, лишь бы блок-схема была, а там дело техники

Добавлено через 25 минут
Тема будет актуальна до завтрашнего утра
0
Redzep
197 / 133 / 88
Регистрация: 21.12.2014
Сообщений: 369
12.10.2015, 11:15 8
Как-то так я тут наговнокодил:
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <set>
#include <vector>
 
 
class Decomposition 
{
public:
    Decomposition (int number_, std::vector<int> summand_) : number (number_), summand(summand_) {}
    void calculate ();
    void output ();
 
private:
 
    std::set<std::multiset<unsigned short>> S; // Множество вариантов разложения (исключаются одинаковые разложения).
    bool decomposition (int current, int plus, std::multiset<unsigned short> tmp); // Рекурсивная функция разложения на слагаемые.
    std::vector<int> const summand; // Слагаемые.
    int const number; // Число для разложения.
};
 
 
 
void Decomposition::calculate ()
{
    std::multiset<unsigned short> tmp;
    for (int i = 0; i < summand.size(); i++) 
    decomposition (0, summand[i], tmp);
}
 
 
 
// Рекурсивная функция разложения на слагаемые.
bool Decomposition::decomposition (int current, int plus, std::multiset<unsigned short> tmp)
{
    tmp.insert(plus);
    current += plus;
 
    if (current == number) 
    {
        S.insert(tmp);
        return true;
    }
 
    if (current > number) 
    {
        return false; 
    }
 
 
    for (int i = 0; i < summand.size(); i++) 
    {
        decomposition (current, summand[i], tmp);
    }
    
}
 
 
// Вывод всех комбинаций.
void Decomposition::output ()
{
    for (auto i = S.begin(); i != S.end(); ++i)
    {
        for (auto j = i->begin(); j != i->end(); ++j)
        {
            std::cout << *j << " ";
        }
        std::cout << std::endl;
    }
}
 
 
int main() 
{
    std::vector<int> S;
 
    // Слагаемые.
    S.push_back(1);
    S.push_back(2);
    S.push_back(3);
 
    int const number = 18; // Число для разложения.
 
    Decomposition D (number, S);
 
    D.calculate();
    D.output();
    
 
    system("pause");
    return 0;
}
Использовал рекурсию, так что если число больше 15-20, то надо довольно долго ждать, так что решение не очень.
0
Barrent
246 / 122 / 54
Регистрация: 04.05.2013
Сообщений: 346
Завершенные тесты: 2
12.10.2015, 12:09 9
похожая задача решалась недавно
Декодирование строки
0
_Ivana
3233 / 1861 / 234
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
12.10.2015, 15:20 10
Ага, а здесь она же с дубль-пушем Основы динамического программирования

УПД:
C++
1
2
3
4
5
6
7
8
9
10
#include <iostream>
 
int main() {
    auto f = [](int n, int i, const auto& la) -> int {
        auto go = [&la,n](int j, const auto& lago) -> int {
            return j>3 ? 0 : la(n-j,j,la) + lago(j+1,lago);};
        return n<0 ? 0 : n==0 ? 1 : go(i,go);};
    
    int n; std::cin>>n; std::cout<<"without memoization: "<<f(n, 1, f)<<'\n';
}
и с дубль-пушем:
C++
1
2
3
4
5
6
7
8
9
10
11
    int dp[20000][3];
    auto f_dp = [&dp](int n, int i, const auto& la) -> int {
        auto go = [&la,n](int j, const auto& lago) -> int {
            return j>3 ? 0 : la(n-j,j,la) + lago(j+1,lago);};
            
        auto memo = [&]() mutable -> int {
            if (dp[n][i]==0) dp[n][i]=go(i,go); return dp[n][i];};
        
        return n<0 ? 0 : n==0 ? 1 : memo();};
    
    std::cout<<"with memoization = dp: "<<f_dp(n, 1, f_dp)<<'\n';
Для числа n=3000 без дп считает около 4 секунд, с дп - 0.02 сек - https://ideone.com/3pP2Ot
0
12.10.2015, 15:20
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.10.2015, 15:20

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

Найти все натуральные числа, представимые в виде суммы квадратов трёх натуральных чисел
Помогите пожалуйста в задаче: Найти все натуральные числа от 1 до N,...

Найти все числа, которые можно представить в виде суммы квадратов двух натуральных чисел
Дано натуральное число N. Среди чисел 1,2,...,N найти все те, которые можно...


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

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

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