Matematické Fórum

Variacemi asi myslíš variace s opakováním, že?
Lze to, např. elegantně rekurzí - v každém rekurentním volání zvětšíš hodnotu na i-tém místě a zavoláš rekurzivní funkci pro i+1-ní místo.
Řekl jsem to stručně, možná i trochu nepřesně, ale myšlenka by mohla být jasná.

↑ sifik:
No, jestli tomu dobře rozumím.. Jaké číslo bude následovat po 99999?

Jinak nápad na ilustraci jak to funguje - spusť si ve windows kalkulačku, dej tam +1, podrž si enter a sleduj vývoj jednotlivých míst. Tam se taky protočí všechny možnosti (před číslem si představ nuly). Lépe je to podle mého vidět v binární soustavě (kalkulačka do ní jde přepnout - je to ten přepínač Bin).

Algoritmus existuje. Protože velikost výsledku je exponenciální (, kde n je počet možných znaků, k je délka hesla), tak i algoritmus má exponenciální složitost (a určitě neexistuje algoritmus s lepší složitostí, protože by nemohl ani stihnout vypsat tak velký výsledek).

Řekněme že znaky jsou jenom číslice (obecně si prostě zvolíš nějaké pořadí znaků, abys mohl jít "o jeden znak dál").

Začneš s posloupností 00...0. Pak zvětšuješ první člen, dokud ti nedojdou znaky: 10...0, 20...0, ..., 90...0. Pak ťukneš druhý člen o jedna nahoru, první resetuješ na 0 a pokračuješ: 01...0, 11...0, ..., 91...0. Pak zas ťukneš druhý člen, první resetuješ. Atd. Pokaždé, když ti v i-tém členu dojdou znaky, tak (i + 1)-ní pošoupneš o znak výš a resetuješ i-tý na 0.

Tenhle princip jsem už určitě viděl v některých hodinářských přístrojích (implementovaný mechanicky) -- tuší někdo, jak se tomu říká? Ještě lépe -- najde někdo animaci tohohle mechanismu?

↑ check_drummer:

No jasně. :) Že mě to hned nenapadlo.

A už jsem našel i hezké video takového počítadla.

↑ sifik:

Ano, je to správná metoda. A řekl bych, že moc jiných se vymyslet nedá -- kromě rekurzivní variace na stejné téma.

↑ sifik: Ahoj, nech chceme variácie s opakovaním tretej triedy z prvkov označených znakmi 0,1,2,....9, 10=A, 11=B, 12=C, 13,14

Potom napr. v jazyku Basic to generuje

For a=0 to 14 step 1
For b=0 to 14 step 1
For c=0 to 14 step 1
print a,b,c
next c
next b
next a


ale sú aj online generátory variácií.

↑ check_drummer: Dík, rozumiem....... naštudujem ...rekurziu... (tachometer s variabilným počtom pozícií)

Zkusil jsem tedy napsat program, na Procházení všech variací, jak je popsán na straně 39 ve skriptech. Kód vypadá následovně:

            int i, j;
            int[] select = { 1, 2, 3, 4 };
            select[i = 0] = -1;
            while (i >= 0)
            {
                if (++select[i] >= 100000) { i--; continue; }
                for (j = 0; j < i; j++)
                    if (select[i] == select[j]) break;
                if (j < i) continue;
                if (++i < select.Length) { select[i] = -1; continue; }
                Console.WriteLine(select[j]);
                i--;
            }
            Console.ReadLine();

Tento skript vypíše všechny čísla od 1 do 100000, jak je nastaveno.

Jenže vůbec netuším k čemu tam je číselné pole select, protože ať dám to zmíněného pole jakýkoliv číslo, výstup je vždy stejný. (Pokud jsem dobře pochopil, že v tomto poli by měli být čísla, z kterých by se měli výsledné variace skládat? Protože jinak by šlo použít pouze pravidlo přičítání jendičky)

Další problém je, že smyčka while nikdy neskončí. Nebo-li jakmile se vypíše poslední variace (číslo 100 000) program začne vypisovat zase od začátku (od 1).

↑ pietro:
Povedlo se ti něco postavit pomocí rekurzí?

↑ sifik:Pole select bude *vždy* obsahovat čísla 1..n. Můžeme jej však použít jako indexové pole pro jinou množinu, která může obsahovat libovolné prvky. Proto řádek "  int[] select = { 1, 2, 3, 4 };" nemá očekávaný efekt.
Dále bylo chybou nahradit N číslem 10000. N je počet prvků, ne počet variací. Asi mělo být N=10, ale obecně N je tolik, kolik je prvků, ze kterých vybíráme. Proto cyklus neskončil....