Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.
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.