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

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

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

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

23.06.2014, 19:57. Просмотров 1300. Ответов 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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.06.2014, 19:57
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Подсчитать количество различных разбиений числа N на натуральные слагаемые (C++):

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

Подсчитать количество различных цифр в десятичной записи натурального числа. - C++
Подсчитать количество различных цифр в десятичной записи натурального числа.

Подсчитать количество различных цифр в десятичной записи натурального числа - C++
Тема: Строки.Множества. 3.1. Напишите программу, которая вводит строку и выводит ее, сокращая каждый раз на 1 символ до тех пор, пока в...

Подсчитать количество различных значащих цифр в десятичной записи натурального числа - C++
Составить программу подсчета количества различных значащих цифр в десятичной записи натурального числа.

Найти все натуральные числа в диапазоне между m и n (m<n), в записи которых нет двух одинаковых цифр. Подсчитать количество таких чисел. - C++
Найти все натуральные числа в диапазоне между m и n (m&lt;n), в записи которых нет двух одинаковых цифр. Подсчитать количество таких чисел.

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

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

Кстати, можно ничего не запоминать. Просто выводить суммы и подсчитывать их количество.
0
Genn55
368 / 215 / 41
Регистрация: 26.12.2012
Сообщений: 708
23.06.2014, 21:33 #3
Посмотрите здесь
Показать все возможные комбинации чисел составляющих сумму заданного числа
Возможно вам поможет.
0
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
24.06.2014, 02:50 #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 слагаемых? мой код учитывает разбиения любой длины.
0
KulVario
0 / 0 / 0
Регистрация: 26.12.2013
Сообщений: 3
24.06.2014, 10:45  [ТС] #5
Спасибо всем за ответы. Здесь суть моей задачи даже не столько в разбиениях, а сколько в том, что мне нужно запоминать значения, да.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.06.2014, 10:45
Привет! Вот еще темы с ответами:

Подсчитать количество различных пар букв - C++
Помогите решить задачу, вернее переделать))) Во введенном слове подсчитать количество различных пар букв. ( например, в слове вавасавасd...

Подсчитать количество различных цифр и вывести их - C++
В записи данного натурального числа подсчитать количество различных цифр и вывести их. Есть программа, которая считает количество...

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

Подсчитать количество различных по значению элементов в массиве - C++
Дан одномерный массив x, состоящий из 20 целых чисел. Составить программу,которая подчитывает количество различных по значению элементов в...


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

Или воспользуйтесь поиском по форуму:
5
Yandex
Объявления
24.06.2014, 10:45
Ответ Создать тему
Опции темы

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