Avatar
MLN
Člen
Avatar
MLN:

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:

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
A ship is safe in harbor. But then again, that´s not what ships are for.
Avatar
MLN
Člen
Avatar
Odpovídá na Jaro
MLN:

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.