Portal Kombat (omówienie)
03.03.2010
Pierwsza obserwacja jaką warto uczynić - Hektor w każdym momencie powinien walczyć z najsilniejszym przeciwnikiem, którego może pokonać. W p.p. na własne życzenie uzyskałby po walce mniejszy wzrost siły, co mu się oczywiście nie opłaca. Na podstawie tej obserwacji nietrudno opracować rozwiązanie zadania - wystarczy symulować optymalną grę Hektora wg algorytmu: Dopoki nie pokonales najsilniejszego przeciwnika
Wypisz liczbę stoczonych walk
W jaki sposób można sprawnie zaprogramować takie rozwiązanie? Rozwiązanie wzorcowe działa w następujący sposób. Przechodzimy tablicę kolejnych przeciwników (w kolejności podanej na wejściu - od najsłabszego do najsilniejszego). Cały czas utrzymujemy specjalną listę przeciwników, których możemy pobić ( są od nas słabsi a przy tym jeszcze ich nie pokonaliśmy ). Za każdym razem, kiedy napotykamy przeciwnika słabszego od nas, odkładamy go na powyższą listę (nie walczymy z nim od razu zgodnie z obserwacją z pierwszego akapitu - być może potrafimy pokonać kogoś silniejszego). Jeśli napotkany przeciwnik jest silniejszy od nas, to znak, że przed zmierzeniem się z nim lub kimkolwiek silniejszym musimy zwiększyć swoją siłę. Aby to zrobić pokonujemy przeciwnika, którego dodaliśmy do naszej listy jako ostatniego (czyli najsilniejszego na liście) i usuwamy go z listy. Poniżej możesz zobaczyć przykładową implementację ze wspomnianą listą realizowaną przy pomocy struktury STL stack:
#include <cstdio> using namespace std; int main(){
|
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com