NOVINKA: Získej 40 hodin praktických dovedností s AI – ZDARMA ke každému akreditovanému kurzu!
S účinností od 26. 3. jsme aktualizovali Zásady zpracování osobních údajů – doplnili jsme informace o monitorování telefonických hovorů se zájemci o studium. Ostatní části zůstávají beze změn.

Diskuze: Algoritmus na vypísanie kombinácií

Jak se ti líbí článek?
Před uložením hodnocení, popiš prosím autorovi, co je špatněZnaků 0 z 50-500
Jak se ti kurz líbí?
Tvé hodnocení kurzuZnaků 0 z 50-500
Aktivity
Avatar
MLN
Člen
Avatar
MLN:18.10.2015 22:41

zdravím, v škole sme dostali na domácu úlohu takýto priklad:

Vymyslite algoritmus (a zapíšte ho tu v pseudokóde), ktorý vypisuje všetky
rôzne rozdelenia t identických (nerozlíšítelných) objektov do r rôznych
(rozlíšítelných) priecinkov, tak aby v každom priecinku bolo viac ako 2,
ale nie viac ako 6 objektov. (t a r budú parametre vášho algoritmu.)

takže je to niečo ako zistiť počet riešení pre rovnicu

x1 + x2 + x3 + x4 + ... + xr = t

kde každé x má byť z intervalu <3,6>. Napadlo ma že najprv od toho T odčítam R*3 a potom vznikne nová rovnica, kde už len nejak (neviem ako) budem kombinatoricky pripočítavať to T tak aby x-ko nebolo viac ako 6

napríklad:

x1 + x2 + x3 + x4 = 20

x1 + x2 + x3 + x4 = 8

a teraz to číslo 8 rozdeliť medzi x-ká tak aby neboli viac ako 6 a zároveň aby dávali súčet 8
a ja potrebujem niečo vymyslieť aby to vypisovalo
Dúfam že tomu chápete a budem rád ak mi s tým niekto pomôže alebo aspoň poradí nejakú myšlienku ako ďalej postupovať :)

 
Odpovědět
18.10.2015 22:41
Avatar
Jaro
Člen
Avatar
Odpovídá na MLN
Jaro:18.10.2015 23:01

Počty riešení rovníc sú kombinácie s opakovaním (vzorce si nájdeš na nete/v skriptách). Možno ti pomôže pojem "zapojenie/vy­pojenie" alebo inak povedané princíp inklúzie/exklúzie, ktorý tam bude treba uplatniť podľa tých podmienok, ale to už nájdeš v skriptách. Je to čistá diskrétka (kombinatorika) a keď prídeš na to ako to urobiť matematicky, prepísať to do programu nebudeš mať problém. :)

Nahoru Odpovědět
18.10.2015 23:01
“What would you do if you were 100% sure you couldn’t fail?”
Avatar
MLN
Člen
Avatar
Odpovídá na Jaro
MLN:18.10.2015 23:34

dobre takže dajme tomu že mám rovnicu:

x1 + x2 + x3 + x4 = 40

Počet všetkých riešení kedy sú x-ká väčšie ako 2 je:

31! / 3! . 28!

Počet všetkých riešení kedy sú x-ká väčšie ako 6 (zlé riešenia) je:

15! / 3! . 12!

A teraz od riešení kedy sú x-ká väčšie ako 2 odčítam tie ktoré sú väčšie ako 6, čo je:

(31! / 3! . 28!) - (15! / 3! . 12!)

Tak teraz som zistil počet všetkých riešení danej rovnice. Ale stále neviem ako to prepísať do pseudokódu aby tie možnosti aj vypísal :(
(dúfam že som sa v tom počítaní nepomýlil)

 
Nahoru Odpovědět
18.10.2015 23:34
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 3 zpráv z 3.