Neregistrovaný Přihlásit Registrovat

Přidat otázku mezi oblíbenéZasílat nové odpovědi e-mailem Greedy algorithm - java

Dobrý deň, chcel by som poprosiť o pomoc pri práci jedného projektu. Riešenie si viem predstaviť, popripade "spraviť" na papier, ale moje programovacie schopnosti sú slabé a neviem sa pohnúť. Zadanie:

Auto cestuje zo štartového do cieľového mesta a zastavuje iba kvôli čerpaniu benzínu alebo v cieli. Napíšte program, ktorý vypočíta, na ktorých benzínových čerpadlách na trase sa má auto zastaviť, aby počet nutných zastávok bol čo najmenší.

Na vstupe vášho programu bude maximálny počet kilometrov, ktoré vie auto prejsť s plnou nádržou a kilometráž možných zastávok auta na ceste (stúpajúca postupnosť kilometrov, na ktorých sa nachádzajú benzínové čerpadlá a posledné číslo predstavuje cieľ).

Príklad zadania:

Auto prejde najviac 100 km na plnú nádrž. Kilometráž možných zastávok: (0, 56, 99, 144, 184, 204, 259, 320, 328, 378) je napríklad trasa z Bratislavy do Popradu. Použite pažravý algorytmus.

Som vďačný za každú pomoc a radu. Ďakujem

Předmět Autor Datum
Jak jsi pokročil od minula? http://pc.poradna.net/q/view/951094-pazravy-algori tmus
MaSo 23.01.2013 13:17
 MaSo
Venoval som sa tomu algorytmu, ako tak som to myslím pochopil. Problém je v nakódení :/ nový
Anton45 23.01.2013 13:21
 Anton45
Suppose that you will drive your car for a long trip between Worcester, Massachusetts and San Franci… nový
MaSo 23.01.2013 13:51
 MaSo
Maso dík moc, nejak takto to plánujem spraviť, aspon si ma v tom utvrdil :). Ale ako hovorím, problé… poslední
Anton45 23.01.2013 13:59
 Anton45

Suppose that you will drive your car for a long trip between Worcester, Massachusetts and San Francisco, California along Interstate Highways. In preparation for your trip, you have downloaded a map that contains the distances in miles between all the gas stations in your route. Assume that your car's gas tank, when full, holds enough gas to travel n miles. Assume that the value n is given. The distance between Worcester and San Francisco is irrelevant for this problem.

Assume that you want to make the minimum number of stops possible along the way, without running out of gas at any point. Describe in detail an efficient method by which you can determine at which gas stations you should stop.

Solution:
The following greedy approach works: Start your trip in Worcester with a full tank. Check your map to determine the farthest away gas station in your route within n miles. Stop at that gas station, fill up your tank and check your map again to determine the farthest away gas station in your route within n miles from this stop. Repeat the process until you get to San Francisco.

Maso dík moc, nejak takto to plánujem spraviť, aspon si ma v tom utvrdil :). Ale ako hovorím, problém je u mňa v nakódení programu. Idem skúšať, experimentovať, snáď to nejak spravím, do zajtra to musí byť.

Zpět do poradny Odpovědět na původní otázku Nahoru