Matematické Fórum

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.