Strona główna » Kursy » Zadania » Czołg
 

Czołg

https://mattomatti.com/a19

Zadanie

Oryginalna treść zadania

Spostrzeżenia

Bak nie ma ograniczenia pojemności (co ułatwia znacznie zadanie). Każda stacja znajduje się w odległości 100 km od siebie. Pozwala to nam wysnuć prosty wniosek, że podróż się kończy jeśli w baku będzie mniej niż 100 l po wyjeździe ze stacji.

Druga kwestia, która może początkowo nie być oczywista to długość podróży. Niezależnie od tego czy zatrzyma się gdzieś po drodze czy za ostatnią stacją należy pamiętać, że przejedzie 100·n km, gdzie n to numer stacji do której dojechał czołg i będzie jechał, aż spali wszystko w baku.

Rozwiązanie

Ile przejedzie?

Funkcja ile_przejedzie() sprawdza jak daleko czołg zajedzie. Funkcja przyjmuje dwa argumenty: tab - ilość paliwa na kolejnych stacjach benzynowych oraz n - ilość stacji.

  1.   for(int i = 1; i < n; i++){
  2.     if(bak < 100)
  3.       return przebieg + bak;
  4.     bak = bak - 100 + tab[i];
  5.     przebieg += 100;
  6.   }
  7.   return przebieg + bak;
  8. }
  10. int ile_paliwa(int* tab, int n){

(2.) Deklarujemy dwie zmienne: przebieg, która przechowuje ile przejechał już pojazd oraz bak, która przechowuje ile paliwa znajduje się w baku. Zaczynamy przy pierwszej stacji z pustym bakiem, dlatego dolewamy paliwa czyli przypisujemy zmiennej bak pierwszą wartość z tablicy. Potem (3.) rozpoczynamy pętle, która (4.) sprawdza czy czołg dojedzie do stacji. Jeśli nie to funkcja kończy działanie (5.) zwracając sumę przebiegu i odległości do przejechania na pozostałym baku. W przeciwnym wypadku należy pamiętać, że (6.) po zatrzymaniu na i-tej stacji w baku będzie 100l mniej paliwa i uzupełnimy bak przez i-tą wartość z tablicy. Przebieg należy zwiększyć o 100. Jeśli pętla nie zostanie przerwana to zwracamy sumę przebiegu i baku co da nam ostateczny rezultat, którego szukamy.

Ile paliwa?

Druga funkcja ile_paliwa() odpowiada na pytanie z jaką ilością czołg musi zacząć podróż, aby móc zatankować na ostatniej stacji. Zadanie można sprowadzić do zadania znalezienia odcinków drogi pomiędzy stacjami, gdzie zabraknie paliwa, a następnie zliczyć sumę brakującego paliwa.

  1.   for(int i = 1; i < n; i++){
  2.     if(bak < 100){
  3.       brakuje += (100 - bak);
  4.       bak = 100;
  5.     }
  6.     bak = bak - 100 + tab[i];
  7.   }
  8.   return tab[0] + brakuje;
  9. }

(2.) Propozycja rozwiązania deklaruje dwie zmienne: brakuje, która będzie przechowywać sumę odcinków na których zabrakło paliwa, aby dojechać do stacji oraz bak, która pozwala nam kontrolować ile paliwa znajduje się w baku przy rozpoczęciu każdego etapu.

(2.) Podobnie jak w poprzedniej funkcji najpierw nalewamy paliwa do baku na pierwszej stacji i (3.) rozpoczynamy pętle. Jej zasada działania jest identyczna co w funkcji ile_przejedzie(). Różnica polega na nie zliczaniu przejechanych kilometrów, a znalezienia odcinków (4.) kiedy zabraknie paliwa. Wtedy (5.) zliczamy ile paliwa zabrakło, a następnie (6.) sztucznie uzupełniamy bak. Dzięki temu mamy pewność, że jeśli po drodze zabrakło paliwa więcej niż raz to wszystkie takie wyjątki zostaną zliczone. Funkcja kończy się po zakończeniu pętli i (10.) należy zwrócić sumę paliwa, którą zatankowaliśmy na pierwszej stacji i sumę paliwa brakującego po drodze.

Testowanie funkcji

Napisane funkcję można przetestować przy pomocy poniższej funkcji main():

  1. int main () {
  2.   setlocale(LC_ALL,"");
  3.   int n;
  4.   cout << "Podaj liczbe stacji: ";
  5.   cin >> n;
  6.   int* tab = new int[n];
  7.   cout << "Podaj ilości paliwa na kolejnych stacjach: ";
  8.   for(int i = 0; i < n; i++)
  9.     cin >> tab[i];
  10.   cout << "Czołg pokona " << ile_przejedzie(tab,n);
  11.   cout << " km" << endl;
  12.   cout << "Minimalna ilość paliwa na I stacji";
  13.   cout << ile_paliwa(tab,n) << endl;
  14.   system("pause");
  15.   return 0;
  16. }

Optymalizacja rozwiązania

Funkcja ile_przejedzie nie musi zliczać przebiegu. Jeśli przerywamy pętle wiemy, że nie do jedziemy to i-tej stacji czyli przejechaliśmy 100·(i - 1) km i dodatkowo przejedziemy tylko tyle ile paliwa mamy w baku. Po zakończeniu pętli wiemy, że przejechaliśmy wszystkie stacje czyli wtedy i = n. Ten sposób optymalizacji wyliczania przedstawia poniższy kod:

  1. int ile_przejedzie(int* tab, int n){
  2.   int bak = tab[0];
  3.   for(int i = 1; i < n; i++){
  4.     if(bak < 100)
  5.       return 100 * (i - 1) + bak;
  6.     bak = bak - 100 + tab[i];
  7.   }
  8.   return 100 * (n - 1) + bak;
  9. }