Вывести сумму int > 0

avatar
Karl
7 апреля 2018 в 21:51
99
1
1

Дано число S ( int > 0 ) и n ( int > 0 ), выведите все разностные подмножества len n , сумма которых равна S. Для S = 7 и n = 3 вывод следующий, вывод должен быть в порядке убывания:

5 + 1 + 1
4 + 2 + 1 
3 + 3 + 1
3 + 2 + 2

Вот что я пробовал до сих пор:

vector<vector<int> > partitions(int X, int Y)
{
    vector<vector<int> > v;
    if (X <= 1 && X <= X - Y + 1)
    {
        v.resize(1);
        v[0].push_back(X);

        return v;
    }
    for (int y = min(X - 1, Y); y >= 1; y--)
    {
        vector<vector<int> > w = partitions(X - y, y);
        for (int i = 0; i<w.size(); i++)
        {
            w[i].push_back(y);
            v.push_back(w[i]);
        }
    }
    return v;


}

int main()
{
    vector<vector<int> > v = partitions(7, 3);
    int i;
    for (i = 0; i<v.size(); i++)
    {
        int x;
        for (x = 0; x<v[i].size(); x++)
            printf("%d ", v[i][x]);
        printf("\n");
    }
}

первый элемент в матрице равен s-n+1 и равен 1 до тех пор, пока не будет достигнута сумма, или если s-n+1 равно s, то n равно 1, поэтому решением будет только s .

ps: я не знаю, есть ли у этой проблемы конкретное имя

Источник
woz
7 апреля 2018 в 21:52
0

Не размещайте ссылки на то, что вы пробовали. Разместите здесь свой код. Также: coderhelper.com/help/mcve

Karl
7 апреля 2018 в 21:56
0

Хорошо, вы можете дать мне подсказку, идею или что-то в этом роде?

user4581301
7 апреля 2018 в 22:01
2

Практически все среды разработки поставляются с программным обеспечением для отладки, которое вы можете использовать для управления выполнением программы, проходя ее пошагово, инструкция за инструкцией, если необходимо, и позволяя вам проверять ее состояние (см. переменные). Запустите отладчик. Шагайте по программе, пока не увидите в программе то, чего не ожидали. Поздравляем! Вы нашли ошибку. Теперь используйте переменные, чтобы выяснить, почему программа поступила неправильно. Начните работать в обратном порядке, чтобы выяснить, как переменные получили значения, которые вызвали неправильное поведение. Смывать. Повторить.

Ответы (1)

avatar
woz
7 апреля 2018 в 23:04
0

Возможно, это не лучшее решение для вашей проблемы, поскольку это решение не основано на динамическом программировании. В этом случае я использую рекурсию для заполнения массива, пока не уменьшу нужное число до 0. В этом решении каждая комбинация будет храниться в порядке возрастания элементов, поэтому мы предотвращаем перестановки уже вычисленного решения.

#include <iostream>
void findCombinationGivenSize(int numbersArray[], int index, int num, int reducedNum, int maxNum){
    if (reducedNum < 0)
        return; // this is our base case
    if (reducedNum == 0 && index == maxNum){ // both criteria were attended: 
                                           //the sum is up to num, and the subset contain maxNum numbers
        for (int i = index - 1; i>=0; i--)
            std::cout<< numbersArray[i] << " + ";
        // here we will have a problem with an extra '+' on the end, but you can figure out easily how to remove it :)
        std::cout<<std::endl;
        return;
    }
    // Find the previous number stored in arrayNumber[]
    int prev;
    if(index == 0)
        prev = 1;
    else
        prev = numbersArray[index-1];
    for (int k = prev; k <= num; k++){
        // next element of array is k
        numbersArray[index] = k;
        // call recursively with reduced number
        findCombinationGivenSize(numbersArray, index + 1, num,reducedNum - k, maxNum);
    }
}
void findCombinations(int number, int maxSubset){
    int arrayNumbers[number];
    findCombinationGivenSize(arrayNumbers, 0, number, number, maxSubset);
}

int main(){
    int number = 7;
    int maxPartitions = 3;
    findCombinations(number, maxPartitions);
    return 0;
}
woz
7 апреля 2018 в 23:16
0

И, конечно же, вы можете добавить в свой main условия для number и maxPartitions.