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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
KulVario
0 / 0 / 0
Регистрация: 26.12.2013
Сообщений: 3
#1

Подсчитать количество различных разбиений числа N на натуральные слагаемые - C++

23.06.2014, 19:57. Просмотров 1168. Ответов 4
Метки нет (Все метки)

Условие: требуется подсчитать количество различных разбиений числа 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
#include "stdio.h"
#include "stdafx.h"
#include <iostream>
#include <cstring>
 
using namespace std;
 
int F(int **array, int n, int k, int i){
    int s;
    if (array[n][k] < 0){
        array[n][k] = 0;
        for (i = 0; i < k; i++) array[n][k] += F(array, n - k, k, i);
    }
    return array[n][k];
}
 
int main(){
    int i, j, k, n, m, sum;
    cout << "n = "; cin >> n;
    cout << "m = "; cin >> m;
    int **array = new int *[m];
    memset(array, sizeof(array), 0);
    for (i = 0; i < n; i++){
        array[i][i] = 1;
        array[i][1] = 1;
    }
    for (i = 1; i < n; i++)
    for (j = 1; j < (i - 1); j++)
        array[i][j] = -1;
    sum = 0;
    for (i = 0; i < n; i++)
        sum = sum + F(array, n, i, i);
    cout << "sum = " << sum;
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.06.2014, 19:57     Подсчитать количество различных разбиений числа N на натуральные слагаемые
Посмотрите здесь:

C++ Подсчитать количество различных цифр в десятичной записи натурального числа.
Подсчитать количество различных пар букв C++
Подсчитать количество различных по значению элементов в массиве C++
C++ Подсчитать количество различных элементов в очереди и вывести их на экран
Подсчитать количество различных цифр в десятичной записи натурального числа C++
Найти все натуральные числа в диапазоне между m и n (m<n), в записи которых нет двух одинаковых цифр. Подсчитать количество таких чисел. C++
Подсчитать количество различных элементов C++
C++ Подсчитать количество различных цифр и вывести их
Подсчитать количество различных слов состоит данное предложение C++
Число разбиений на слагаемые C++ C++
Подсчитать количество различных слов, входящих в заданный текст C++
Подсчитать количество различных значащих цифр в десятичной записи натурального числа C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IrineK
Заблокирован
23.06.2014, 20:06     Подсчитать количество различных разбиений числа N на натуральные слагаемые #2
Массив как структура не подходит для решения этого задания: вы же не знаете ни количества сумм, ни количества слагаемых в каждой сумме. Если хотите запоминать, нужен стек (пусть даже и на массиве).

Кстати, можно ничего не запоминать. Просто выводить суммы и подсчитывать их количество.
Genn55
342 / 189 / 37
Регистрация: 26.12.2012
Сообщений: 661
23.06.2014, 21:33     Подсчитать количество различных разбиений числа N на натуральные слагаемые #3
Посмотрите здесь
Показать все возможные комбинации чисел составляющих сумму заданного числа
Возможно вам поможет.
SlavaSSU
214 / 159 / 45
Регистрация: 17.07.2012
Сообщений: 587
24.06.2014, 02:50     Подсчитать количество различных разбиений числа N на натуральные слагаемые #4
C++ (Qt)
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
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
 
using namespace std;
 
typedef long long li;
 
li dp[1111][1111];
 
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        dp[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 ni = i + k;
                if(ni <= n)
                    dp[ni][k] += dp[i][j];
            }
        }
 
    li ans = 0;
    for(int i = 1; i <= n; i++)
        ans += dp[n][i];
 
    cout << ans << endl;
    return 0;
}
Добавлено через 1 минуту
погоди! тебе надо разбить число ровно на M слагаемых? мой код учитывает разбиения любой длины.
KulVario
0 / 0 / 0
Регистрация: 26.12.2013
Сообщений: 3
24.06.2014, 10:45  [ТС]     Подсчитать количество различных разбиений числа N на натуральные слагаемые #5
Спасибо всем за ответы. Здесь суть моей задачи даже не столько в разбиениях, а сколько в том, что мне нужно запоминать значения, да.
Yandex
Объявления
24.06.2014, 10:45     Подсчитать количество различных разбиений числа N на натуральные слагаемые
Ответ Создать тему
Опции темы

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