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
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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 17. 11. 2018 21:20 — Editoval jirick (17. 11. 2018 21:43)

jirick
Zelenáč
Příspěvky: 11
Reputace:   
 

Možnost implementace Diofantické rovnice nebo Čínské věty o zbytcích

Ahoj, potřeboval bych poradit ohledně implementace a řešení jednoho problému a jeho podobných. Narazil jsem na 2 věty, které si myslím, že budou nápomocné. Jedná se o čínskou větu o zbytcích a diofantickou rovnici, ale nevím, jak přesně je v řešení problému uplatnit.

Představím tento problém dejme tomu na kanalizačním potrubí, pokusím se to popsat jako slovní úlohu:

Potřebujeme navrhnout potrubí o přesné délce 127 m. Máme k dispozici trubky od 3 různých dodavatelů. Každý dodavatel vyrábí trubky o různé fixní délce, kterou nelze nijak zkracovat ani prodlužovat:

první dodavatel: 12 m
druhý dodavatel: 8 m
třetí dodavatel: 10 m

Na začátku potrubí a na konci potrubí se musí vyskytovat přemosťující trubky, které mají délku 3 m. Mezi každou trubkou musí být rovněž tato přemosťovací trubka.

Pro názornou ukázku si znázorníme délky jako proměnné:
(první dodavatel)           X = 12 m
(druhý dodavatel)          Y = 8 m
(třetí dodavatel)            Z = 10 m
(přemosťovací trubka)   A = 3 m

Tudíž schéma by vypadlo nějak takto:

A Y A Z A Y A Z A X A X A

Ptáme se, kolik potřebujeme objednat trubek od daných dodavatelů a zároveň, kolik existuje řešení? Tato řešení si představme, jako počet různých přípustných objednávek ( jedno řešení může vypadat jako např. od prvního objednám 5, od druhého 3 a od třetího 7). Přemosťovacích trubek je vždy dostatek a neobjednávají se.

Jak vyřešíte tuhle úlohu? Jakým algoritmem se zde dá jednoduše dosahovat očekávaných výsledků v obdobných úlohách? Připomínám, že řešení, které nechci je postupné zkoušení a postupné přičítání, to je naivní řešení, hledám efektivní algoritmus.

Díky.

Offline

 

#2 17. 11. 2018 22:30 — Editoval edison (17. 11. 2018 22:31)

edison
Příspěvky: 1604
Reputace:   36 
 

Re: Možnost implementace Diofantické rovnice nebo Čínské věty o zbytcích

Mě tedy připadá, že to "naivní řešení" je zcela nejvhodnější, protože naprogramování bude snadné, rychlé a jakýkoli běžný počítač projde všechna řešení do pár (mili)sekund.

Pro větší délky se pak může udělat optimalizace, že se většina postaví z nejlevnějších a program pak vybere jen jak dlouhá bude ta poslední část a co v ní bude.

Offline

 

#3 15. 12. 2018 00:33

Kondr
Moderátor
Místo: Linz, Österreich
Příspěvky: 4246
Škola: FI MU 2013
Pozice: Vývojář, JKU
Reputace:   38 
Web
 

Re: Možnost implementace Diofantické rovnice nebo Čínské věty o zbytcích

Pokud počty trubek označíme x,y,z, máme rovnici
12x+8y+10z+3*(x+y+z+1)=127
po úpravě
15x+11y+13z=124
Pokud bychom měli jen dvě neznámé, vyřešili bychom jime ji snadno Euklidovým algoritmem. Pokud máme neznámých více, můžeme jejich počet postupně redukovat, viz https://math.stackexchange.com/a/145348 .


BRKOS - matematický korespondenční seminář pro střední školy

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson