[pseudokód]Všechny způsoby,jak sčítáním dostat daný výsledek

C++, C#, Visual Basic, Delphi, Perl a ostatní

Moderátor: Moderátoři Živě.cz

Odeslat příspěvekod AbcdXyz 20. 3. 2015 12:48

Zdravím,

potřebuji napsat funkci, která mi vypíše všechny způsoby, jak sčítáním libovolného počtu přirozených čísel dostat dané číslo n s tím, že nezáleží na pořadí sčítanců.

Tedy např. pro n=6 by se mělo vypsat postupně:
1 1 1 1 1 1
2 1 1 1 1
2 2 1 1
2 2 2
3 1 1 1
3 2 1
3 3
4 1 1
4 2
5 1
6

Je mi jedno, jakým způsobem je to napsané, nepotřebuju ty možnosti ani nikam ukládat. Pořebuju jen získat první možnost, s tou pak provést další operace, které už mám naprogramované, následně najít další možnost a opět s ní provést ty operace a tak pokračovat, dokud je nepoužiju všechny.

Vypsat si to na papír je celkem jednoduché, ale nevím, jak ten algoritmus zapsat do pc.
AbcdXyz
Kolemjdoucí

Odeslat příspěvekod KineCZek 20. 3. 2015 14:30

Domácí úkoly na fóru neřešíme, máme to i v pravidlech...
Don't think you are. Know you are. (Morpheus)

PC sestavy hracum i profesionalum na miru - nyni nove i na Facebooku. (KineCZek Work)
KineCZek
Odborník PC sestav a ULN, Ex-administrátor
Uživatelský avatar

Odeslat příspěvekod AbcdXyz 20. 3. 2015 14:55

Není to domácí úkol. Počítám něco přes Burnsideovo lemma a tohle se v tom používá. Nemusím to ani programovat, stačí mi to spočítat na papír, ale pro vysoká n už to trvá hrozně dlouho, tak jsem si to zkusil usnadnit naprogramováním. Celý ten výpočet už mám hotový, takže aktuálně si prostě můžu ty jednotlivé možnosti sepisovat sám a dát je jako parametr funkce, která to počítá, nicméně když už u n=10 existuje 42 možností, jak ten součet 10 dostat, tak prostě musím 42x zavolat funkci s parametrem, který si sám 42x změním, a pak ty výsledky ještě mezi sebou posčítat. A chtěl bych to počítat i pro vyšší n. Kdyby se to generovalo automaticky, tak by mi to práci dost urychlilo...

Napadlo mě něco jako udělat si cyklus for (od 1 do n), ve kterém by se nejdříve udělal součet n jedniček a při i-tém průchodu cyklem by se tam vždycky v cyklu while přidávaly hodnoty [i], takže např. v druhém průchodu cyklu for by se tím cyklem while přidaly všechny možnosti, které mají jako nejvyšší prvek dvojku a s každou přidanou dvojkou odeberu dvě jedničky. Jenže už u trojky pak narážím na problém s tím, že tímto způsobem vygeneruju všechny možnosti, které obsahují trojky a jedničky, ale pořád jsou i možnosti, které obsahují kromě trojek a jedniček i dvojky a u těch už nevím, jak zajistit, aby se vypsaly.
AbcdXyz
Kolemjdoucí

Odeslat příspěvekod JirkaVejrazka 20. 3. 2015 15:35

To je skoro ukazkovy priklad na rekurzi, ne?
JirkaVejrazka
Mírně pokročilý

Odeslat příspěvekod tomko 20. 3. 2015 16:16

V jakém výstupu to pak chceš mít? Dvojrozměrné pole?
lepší být bohatý zdravý než chudý nemocný
tomko
Mírně pokročilý
Uživatelský avatar

Odeslat příspěvekod AbcdXyz 20. 3. 2015 16:39

Třeba. Já ty jednotlivé kombinace potřebuju jenom k tomu, abych je použil jako parametr další funkce. Takže jestli se vygenerujou všechny najednou do dvourozměrného pole nebo se vygeneruje vždycky jenom jedna do jednorozměrného pole, pak se zavolá druhá funkce, a pak se kombinace přepíše na jinou, je mi celkem jedno.
AbcdXyz
Kolemjdoucí

Odeslat příspěvekod tomko 20. 3. 2015 16:56

Zkusím na to večer skočit. Vidím to na 3 vnořené cykly. Rekurce by to asi taky řešila, ale mám strach, pokud by to číslo bylo větší, jak malé... A musí to být v tom pořadí, jak jsi to tady popsal?
lepší být bohatý zdravý než chudý nemocný
tomko
Mírně pokročilý
Uživatelský avatar

Odeslat příspěvekod AbcdXyz 20. 3. 2015 17:04

Ne, může to být v libovolném pořadí. Díky za případnou pomoc.
AbcdXyz
Kolemjdoucí

Odeslat příspěvekod JirkaVejrazka 20. 3. 2015 18:14

Tady je reseni v Pythonu, ale musim priznat, ze jsem se docela zapotil :)

Kód: Vybrat vše
import sys

def combinations(xlen):
    if xlen:
        for i in range(1, xlen+1):
            internal_combinator = combinations(xlen - i)
            for sol in internal_combinator:
                if sol and sol[0] > i:
                    break
                yield [i] + sol
    else:
        yield []

if __name__ == '__main__':
    combinator = combinations(int(sys.argv[1]))
    for solution in combinator:
        print solution


Mimochodem, rekurze fakt neni problem - uz pro 50 prvku to ma pres 204 tisic reseni, takze nez se priblizite poctu prvku, kdy by rekurze byla problem, zabije vas mnozina moznych reseni ;-)
JirkaVejrazka
Mírně pokročilý

Odeslat příspěvekod AbcdXyz 20. 3. 2015 18:45

Díky, python neumím, ale zkusím to nějak pochopit.
AbcdXyz
Kolemjdoucí

Odeslat příspěvekod JirkaVejrazka 20. 3. 2015 20:13

princip je v tom, ze pro n=10 projdes cyklus od jedne do deseti, s tim ze na prvni misto dosadis postupne jedna az deset a spocitas vsechna reseni pro "zbytek rady", tj:
1 (vsecha reseni pro n=9)
2 (vsechna reseni pro n=8)
3 (vsechna reseni pro n=7)
...
9 (vsechna reseni pro n=1)
10

Pomohlo to trochu?
JirkaVejrazka
Mírně pokročilý

Odeslat příspěvekod AbcdXyz 20. 3. 2015 22:08

Jo, chápu. Snad se mi to podaří přepsat.
AbcdXyz
Kolemjdoucí

Odeslat příspěvekod Wikan 21. 3. 2015 22:53

Narychlo spíchnuté řešení v C#
Kód: Vybrat vše
public class Generator
{
    public IEnumerable<IEnumerable<uint>> Generate(uint total)
    {
        return Generate(total, total);
    }

    IEnumerable<IEnumerable<uint>> Generate(uint total, uint max)
    {
        if (total == 0)
            yield return Enumerable.Empty<uint>();

        for (uint i = 1; i <= total && i <= max; i++)
        {
            var subResults = Generate(total - i, i);
            foreach (var subResult in subResults)
            {
                var result = new List<uint> { i };
                result.AddRange(subResult);
                yield return result;
            }
        }
    }
}
Wikan
Moderátor
Uživatelský avatar


Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 0 návštevníků