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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
KulVario
0 / 0 / 0
Регистрация: 26.12.2013
Сообщений: 3
23.06.2014, 19:57     Подсчитать количество различных разбиений числа N на натуральные слагаемые #1
Условие: требуется подсчитать количество различных разбиений числа 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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IrineK
Заблокирован
23.06.2014, 20:06     Подсчитать количество различных разбиений числа N на натуральные слагаемые #2
Массив как структура не подходит для решения этого задания: вы же не знаете ни количества сумм, ни количества слагаемых в каждой сумме. Если хотите запоминать, нужен стек (пусть даже и на массиве).

Кстати, можно ничего не запоминать. Просто выводить суммы и подсчитывать их количество.
Genn55
341 / 188 / 37
Регистрация: 26.12.2012
Сообщений: 658
23.06.2014, 21:33     Подсчитать количество различных разбиений числа N на натуральные слагаемые #3
Посмотрите здесь
Показать все возможные комбинации чисел составляющих сумму заданного числа
Возможно вам поможет.
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
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 на натуральные слагаемые
Ответ Создать тему
Опции темы

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