Kombinacje sumy

[AndrzejBo]

Mam liczby 2 3 4.
Mam sume 2 na 1 sposob, 3 tez. 4 to 4 lub 22, 5 to 23 lub 32, 6 to 42 33 222 224.itd.
Jak generowac takie kombinacje?

[kerajs]

Jeśli to zadanie na informatykę, to na każde miejsce ciągu o długości k (gdzie\(\displaystyle{ \lceil \frac{S}{4} \rceil \le k \le \lfloor \frac{S}{2} \rfloor}\) , a S to wartość sumy) komputer wstawia dostępne cyfry , zlicza ich sumę i wy/zapisuje tylko układy o sumie S.

[AndrzejBo]

A w ten sposób: zaczynam od najwiekszej liczby tu 4, jak mam 6 to wpisuje 4, zostaje 2. Drugie, wpisuje 3 zostaje 3. Trzecie, wpisuje 2, zostaje 4, ktore teraz wolam rekurencyjnie dla 4. Mogę również cachowac rezultaty, gdy wczesniej wylicze dla sumy równej 4.

[kerajs]

Owszem, liczność układów o sumie \(\displaystyle{ S}\) wyraża się rekurencją: \(\displaystyle{ L_S=L_{S-2}+L_{S-3}+L_{S-4}}\) , jednak pisałeś o generowaniu układów. Dla większych S musisz wygenerować i zapisywać w pamięci układy o sumach niższych. Może to zabrać więcej czasu i zajmować zdecydowanie więcej pamięci niż sposób który sugerowałem wcześniej.

[AndrzejBo]

Jest "miejsce ciągu ... wstawia dostępne cyfry", czy to nie prowadzi do złożoności wykładniczej?

[kerajs]

Nie.

[AndrzejBo]

Napisałem program unikając rekurencji, zamiast tego wskaźnik poruszający się w przód i tył:
ostatnią cyfrę wstawia bez próbowania jeśłi mieści się w zakresie.

Kod: Zaznacz cały

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

const int minDigit=2;
const int maxDigit=4;

void out(const vector<int> &vec) {
    for (int d: vec)
        printf("%d",d);
    printf(" ");
    fflush(stdout);
}

void KombinacjeLen(int n,int len) {
    if (len==1) {
        if (n >= minDigit && n <= maxDigit) printf("%d ",n);
        return;
    }
    int sum=0;
    vector<int> vec(len);
    for (int i=0; i<len-1; i++) {
        vec[i] = minDigit;
        sum+=minDigit;
    }
    int stackpos=len-1;
    int k;
    while(stackpos>=0) {
        if (stackpos==len-1) {
            k = n-sum;
            if (k>=minDigit && k<=maxDigit) {
                vec[stackpos] = k;
                out(vec);
            }
            stackpos--;
        }
        else {
            vec[stackpos] = minDigit;
            sum+=minDigit;
            stackpos++;
            continue;
        }
        while (stackpos>=0 && vec[stackpos]==maxDigit) {
            vec[stackpos] = minDigit;
            stackpos--;
            sum-=maxDigit;
        }
        if (stackpos<0) break;
        vec[stackpos]++;
        sum++;
        stackpos++;
    }
}

void Kombinacje(int n) {
    int minlen=ceil(n/(double)maxDigit);
    int maxlen=floor(n/(double)minDigit);
    for (int i= minlen; i<=maxlen; i++)
        KombinacjeLen(n,i);
    printf("\n");
}

int main() {
    for (int i=2; i<10; i++)
        Kombinacje(i);
    return 0;
}

wynik od 2 do 9 jest:

2
3
4 22
23 32
24 33 42 222
34 43 223 232 322
44 224 233 242 323 332 422 2222
234 243 324 333 342 423 432 2223 2232 2322 3222

Czy dobrze? wygląda że dobrze.