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

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

Войти
Регистрация
Восстановить пароль
 
Hroniko
1 / 1 / 0
Регистрация: 24.04.2015
Сообщений: 6
#1

Число разбиений на слагаемые C++ - C++

20.12.2015, 23:07. Просмотров 732. Ответов 2
Метки нет (Все метки)

Подскажите, есть такая задача.
По данному целому числу 1≤n≤1000 найдите число способов представить n в виде суммы положительных целых чисел. Выведите данное число по модулю 10^9+7. Два представления, отличающиеся друг от друга только порядком слагаемых, считаем одинаковыми.

Например, подаем на вход 5, на выходе будет 7.

Рекурсивный алгоритм заваливается на тесте с таймлимитом,
сделал итеративный алгоритм, но валиться на одном из тестов как неверный ответ.

Не пойму, где же ошибка. Может быть, где-то переполнение, или что-то не учел? Вот код:

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
#include <iostream>
 
using namespace std;
 
 
long long D[1000][1000];
 
int main()
{
    int n; // Заданное число
    cin >> n; // Читаем заданное число
 
    // Заполняем главную диагональ матрицы
    for(int i = 1; i <= n; ++i)
    {
        D[i][i] = 1;
    }
 
 
    for(int i = 1; i < n; ++i)
        for(int j = 1; j < n; ++j)
        {
            for(int k = j; k <= n; ++k)
            {
                int ik = i + k;
                if(ik <= n)
                    D[ik][k] = D[ik][k] + D[i][j];
            }
        }
 
    long long m; // Количество разложений
    m = 0; // Вначале обнуляем количество разложений
    for(int i = 1; i <= n; i++) // Запускаем цикл подсчета разложений
    {
        m = m + D[n][i];
    }
 
    // Выводим результат
    cout << m << endl;
    return 0;
}
Добавлено через 5 минут
Вообще, что значит вывести число по модулю 10^9+7 ?

Добавлено через 7 минут
Хелп! Уходит время...

Добавлено через 9 минут
Имеется в виду такое разложение:
Например, число 5, можно представить в виде:
5= 1+1+1+1+1
5= 1+1+1+2
5= 1+1+3
5= 1+2+2
5= 2+3
5= 1+4
5= 5

Итого 7 различных разложений (перестановки слагаемых не учитываем)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.12.2015, 23:07
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Число разбиений на слагаемые C++ (C++):

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

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

Разложить заданное число на слагаемые, которые не будут повторяться - C++
#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; #include &lt;conio.h&gt; int main() { int f=0; do{ int one =...

Нахождение разбиений числа - C++
Все привет, ребят помогите. Суть задания: разбиений числа, есть число, нужно его разбить. Например, {3,1,1} или {3,2} — разбиения числа 5,...

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

Разбиение на слагаемые - C++
Задание:нужно вывести на экран в лексикографическом порядке все разбиения на слагаемые числа n от 1 до 20. пример: n=5 5=1+1+1+1+1 ...

2
wstud2
0 / 0 / 0
Регистрация: 20.12.2015
Сообщений: 2
20.12.2015, 23:21 #2
Привет. А ты 5 задачу по алгоритмам решил?
0
Hroniko
1 / 1 / 0
Регистрация: 24.04.2015
Сообщений: 6
20.12.2015, 23:22  [ТС] #3
Привет. Да
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.12.2015, 23:22
Привет! Вот еще темы с ответами:

различные слагаемые - C++
По данному числу 1≤n≤10^9 найдите максимальное число k, для которого n можно представить как сумму k различных натуральных слагаемых....

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

Разложение числа на слагаемые - C++
Разложение числа на слагаемые - используется во многих задачах (как мне кажется - это тривиальная задача). И мне стало интересно: какой...

Разложение натурального числа на слагаемые - C++
Я не силен в математике, но математику надоело вести математические методы и он начал давать задачки по созданию программ, все бы ничего,...


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

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

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