Matematické Fórum

honza_t · 18. 12. 2011 00:46

Zdravím. Dostal jsem za úkol naprogramovat následující program a nevím jak to realizovat:

Jste zahradníci a chcete sázet jeden dlouhý řádek cibule a česneku
● Nechcete sázet dva česneky těsně vedle sebe, vždy mezi ně zasadíte minimálně jednu cibuli
● Kolika různými způsoby můžete řádek osázet?
● Vypište všechny možnosti a spočtěte jejich počet
● Řádek bude vždy obsahovat N sazeniček

Snažím se to splácat v Javě a už mi z toho jde hlava kolem. Budu rád za jakékoli popíchnutí.

Dioxid · 18. 12. 2011 12:55

Zdravím, napadá mne jen řešení s asymptotickou časovou složitostí $O(2^N)$ . A sice zkoušení všech možností. Využil bych pole jedniček a nul s délkou N (1 bude česnek, 0 bude cibule). Na začátku bude celé pole vypadat takto: (pro N=4)
0000
To pole si můžeme představit jako číslo v dvojkové soustavě, které budeme zvyšovat o 1. Další stavy budou vypadat takto:
0001
0010
0011 (neodpovídá zadání)
0100
0101
0110 (neodpovídá zadání)
0111 (neodpovídá zadání)
1000
1001
1010
1011 (neodpovídá zadání)
1100 (neodpovídá zadání)
1101 (neodpovídá zadání)
1110 (neodpovídá zadání)
1111 (neodpovídá zadání)

Daná časová složitost se ale může trochu vylepšit (jak je vidět z příkladu) - pokud jsou v poli dvě jedničky za sebou tak již nemá cenu dělat operace, které by změnily hodnoty "za nimi" - když řešení není 1100 tak nebude řešením ani 1101 ani 1110 nebo 1111. Tak si můžeme (v tomto případě) zlepšit počet ověřování z 16 na 11.

Kondr · 18. 12. 2011 13:37

Pro n sazenic vyjde n-té Fibonacciho číslo. To jde samo o sobě spočítat rychle, ale pokud chceme možnosti vypsat, nedostaneme se se složitostí pod 1.6^n.

Matematické Fórum

#1 18. 12. 2011 00:46

algoritmus zahradník

#2 18. 12. 2011 12:55

Re: algoritmus zahradník

#3 18. 12. 2011 13:37

Re: algoritmus zahradník

Zápatí