Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 12. 05. 2011 16:37
Dělení kořisti
Dobrý den, mám za úkol zjistit zda se daný počet předmětů o daných cenách dá spravedlivě rozdělit mezi tři lidi. Tzn. že potřebuju obecný výpočet a počet předmětů a jejich ceny se bude měnit. Je mi trapné, že píšu bez jakýchkoliv vlastních poznatků, ale já si vůbec nevím rady...čáčám si tu na papír různé nesmysly a nemůžu najít spráný směr :/
Offline
- (téma jako vyřešené označil(a) Moonchild)
#2 12. 05. 2011 16:40
- harryharry
- Příspěvky: 204
- Reputace: 2
Re: Dělení kořisti
Procvič si EXCEL a vypočítej to v něm :-)
“Kde nic není ani smrt nebere.”
Offline
#4 12. 05. 2011 16:45
- harryharry
- Příspěvky: 204
- Reputace: 2
Re: Dělení kořisti
http://leteckaposta.cz/218242910 něco takového? Máš příliš krátké a nepřesné zadání :-)
“Kde nic není ani smrt nebere.”
Offline
#5 12. 05. 2011 17:00
Re: Dělení kořisti
Pardon, upřesnim:
Je zadán počet předmětů (n)
Zadány ceny jednotlivých předmětů (tzn. n čísel)
Mám zjistit, zda se dají předměty (celé) rozdělit mezi tři osoby tak, aby měla každá osoba předměty ve stejné hodnotě
Např. ceny předmětů: 2 1 1 1 1 - lze rozdělit (2, 1+1, 1+1)
ceny předmětů: 1 1 1 1 - nelze rozdělit (jeden předmět přebývá a musí zůstat celý)
Offline
#6 12. 05. 2011 17:05
- harryharry
- Příspěvky: 204
- Reputace: 2
Re: Dělení kořisti
Tak to je jiná. Ale stejně to vypadá jako příklad na programování, pomocí IF a ELSE. Matematickou formulaci dohromady nemám.
“Kde nic není ani smrt nebere.”
Offline
#8 13. 05. 2011 07:01
Re: Dělení kořisti
↑ Moonchild:
Zkus se zamyslet nad zbytkem po dělení třemi ze součtu cen všech předmětů, a potom nad tím, zda je možné ze třetiny celkové ceny udělat součty cen celých předmětů.
Dám příklad
1.máme předměty za ceny 2,2,3,2 součet je 9 mod 3 =0 (to by mohlo jít)
ale 9/3=3 tzn., že musíme umět udělat součty cen celých předmětů tak, aby byla ta celková cena pro
každého z těch tří rovna třem. To ale nejde.
2.máme předměty za ceny 2,2,3,1,1 součet je 9 mod 3 =0 (to by mohlo jít)
9/3=3, a tady umíme udělat hromádky 2+1=3, 2+1=3,3
Offline
#10 13. 05. 2011 11:24
- OiBobik
- Moderátor
- Místo: Brno/Praha
- Příspěvky: 1013
- Škola: MFF UK Mat. struktury
- Pozice: student
- Reputace: 82
Re: Dělení kořisti
↑ Moonchild:
Tohle je celkem dost obtížná úloha (alespoň podle mě), která pokud se má řešit efektivně, je třeba užít dynamického programování (samozřejmě, že rekurzí to lze řešit taky, ale bude to hodně časově náročné).
"The first rule of Tautology Club is the first rule of Tautology Club." [xkcd]
Offline
#11 13. 05. 2011 12:02
Re: Dělení kořisti
To odpovídá, dostali jsme k tomu následující nápovědu:)
Nápověda:
- Jedná se o variantu problému "dělení kořisti".
- Úloha "dělení kořisti" patří mezi tzv. úlohy NP-úplné, tedy mezi úlohy, pro které neznáme efektivní obecný algoritmus řešení.
- Vaším úkolem je realizovat program pracující na principu "hrubé síly", tedy zkusit systematicky všechny možnosti přidělení předmětů jednotlivým loupežníkům a vyhodnotit, zda lze dosáhnout takového přidělení, že jejich podíly jsou stejné.
- Pro generování přiřazení předmětů použijte rekurzi.
- Řešení hrubou silou má velkou (exponenciální) časovou složitost, je použitelné pouze pro malý počet předmětů (cca 20).
Offline