[PJATK] ASD – wiosna 2016 – Zadanie 5 – Prawie rozwiązanie

Problemy z algorytmem podobne jak w ‚problem liszaja’ [ https://www.youtube.com/watch?v=4pdBHJYf3Hw ] – setki rozwiązań w internecie. Tylko, że na ASD zamiast tablicy 2-wymiarowej mamy graf.
Chodzi o to, że mamy jakieś wierzchołki grafu ‚zarażone’ [założone sztaby wyborcze] i one zarażają te z którymi mają kontakt [miasta sąsiedzkie]. Jednak, żeby nie było za łatwo, wszystko trzeba podzielić na tury. Wierzchołki zarażone w danej turze zaczynają zarażać dopiero w następnej. Jak już się zrozumie o co chodzi to napisanie programu jest bardzo proste.

Jeśli uda mi się na jutro dokończyć artykuł o list/vector/map w C++ to wrzucę, żeby trochę rozjaśnić temat dlaczego korzystam z tylu ‚map’ i jakie cudowne właściwości one mają.

 
Jednak dla osób które mają problem udostępniam pseudokod/trochę jak C++. Do niedzieli, do północy, jest jeszcze czas na przerobienie tego na działający program.

Jeśli kod poniżej jest kiepsko wyświetlany, to można też go obejrzeć na pełnej szerokości okna z kolorowaniem składni [głównie komentarzy]:

http://hastebin.com/kodekiwita.php

 

klasa Kandydat
{
	- id
	- koszt kampanii metoda A
	- koszt kampanii metoda B
};

klasa Miasto
{
	- id
	- zwyciezca metoda A
	- zwyciezca metoda B
	- lista sasiadow
};

funckja wczytajLiczbe()
{
	// wczytuje liczbe z wejscia do zmiennej
}

int main()
{
	// 1. tworzymy liste/tablice zawierajaca wszystkie miasta
	var iloscMiast;
	wczytajLiczbe >> iloscMiast;

	// musi byc mozliwosc latwego zaladowania miasta o numerze X
	var listaMiast = (lista miast o wielkosci 'iloscMiast');
	for(i < iloscMiast, i++)
	{
		// dodajemy do listy miasta, zapamietujac w miastach ich ID
		listaMiast[i] = new Miasto(i);
	}
	
	// 2. wczytujemy sasiadow miast
	var sasiad_1;
	var sasiad_2;
	wczytajLiczbe >> sasiad_1;
	wczytajLiczbe >> sasiad_2;

	// do czasu az wystapi koniec listy sasiadow
	while(sasiad_1 != -1)
	{
		// oba miasta sasiedzkie musza miec dodane siebie nawzajem do list sasiadow
		listaMiast[sasiad_1]->lista_sasiadow->dodaj(sasiad_2);
		listaMiast[sasiad_2]->lista_sasiadow->dodaj(sasiad_1);
		
		wczytajLiczbe >> sasiad_1;
		wczytajLiczbe >> sasiad_2;
	}

	// 3. tworzymy liste/tablice kandydatow od razu wczytujac ich startowe miasto
	var iloscKandydatow;
	wczytajLiczbe >> iloscKandydatow;
	
	// musi byc mozliwosc latwego zaladowania kandydata o numerze X
	var listaKandydatow = (lista kandydatow o wielkosci 'iloscKandydatow');

	map<Miasto*, char> listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda; // bez powtorzen = 'map', klucz musi byc unikalny, a wartosc moze byc dowolna

	for(i < iloscKandydatow, i++)
	{
		var miastoStartoweKandydata;
		wczytajLiczbe >> miastoStartoweKandydata;

		for(sasiad in listaMiast[miastoStartoweKandydata])
		{
			// przeprowadz wybory u kazdego sasiada startowego miasta
			listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda[miastoStartoweKandydata] = ' ';
		}

		// dodajemy do listy kandydatow, zapamietujac w kandydatach ich ID
		listaKandydatow[i] = new Kandydat(i);

		// w miescie startowym zapamietujemy kto jest zwyciezca
		listaMiast[miastoStartoweKandydata]->zwyciezcaKampaniiMetodaA = listaKandydatow[i];
		listaMiast[miastoStartoweKandydata]->zwyciezcaKampaniiMetodaB = listaKandydatow[i];

		// w kandydacie zapisujemy zmiane kosztu kampanii, zalozenie sztabu w startowym miescie
		listaKandydatow[i]->kosztKampaniiMetodaA++;
		listaKandydatow[i]->kosztKampaniiMetodaB++;
	}

	// 4. tworzymy 'mapy' do przechowywania wielu danych
	
	// tak samo jak 'listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda', lista bez powtorzen miast do przeprowadzenia wyborow
	map<Miasto*, char> listaMiastDoPrzeprowadzeniaWyborow_aktualnaRunda;
	
	// dla kazdego miasta bedziemy potrzebowac tymczasowa liste kandydatow na zwyciezce i ilosc glosow na nich oddanych [przez sasiednie miasta]
	map<Kandydat*, short int> glosyNaKandydataMetodaA;
	map<Kandydat*, short int> glosyNaKandydataMetodaB;
	
	// zwyciezcow wyborow mozemy zapisac dopiero po przeprowadzeniu wszystkich glosowan w 'danej rundzie'
	// inaczej glosowania z danej rundy mogly by wplywac na wyniki glosowan w tej samej rundzie
	map<Miasto*, Kandydat*> zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaA;
	map<Miasto*, Kandydat*> zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaB;
	
	// 5. mielimy dane (przegladamy graf)
	while(nie pusta 'listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda')
	{
		// przepisujemy miasta z 'nastepnej rundy' do 'aktualnej rundy'
		wyczysc 'listaMiastDoPrzeprowadzeniaWyborow_aktualnaRunda';
		listaMiastDoPrzeprowadzeniaWyborow_aktualnaRunda = listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda;
		wyczysc 'listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda';

		// przeprowadzamy wybory w kazdym
		for(miasto in listaMiastDoPrzeprowadzeniaWyborow_aktualnaRunda)
		{
			// sprawdzamy czy w miescie nie ma jeszcze zwyciezcy
			// po poczatkowym dodawaniu kandydatow do miast startowych na liscie moga byc miasta w ktorych juz sa zwyciezcy
			if(czy nie ma zwyciezcy w 'miasto')
			{
				// czyscimy glosy oddane przy poprzednim liczeniu
				wyczysc 'glosyNaKandydataMetodaA';
				wyczysc 'glosyNaKandydataMetodaB';

				// dla kazdego miasta w sasiedztwie
				for(miastoSasiedzkie in miasto->lista_sasiadow)
				{
					if(czy jest zwyciezca w 'miastoSasiedzkie')
					{
						// jesli jest zwyciezca to oddaje on glosy metoda A i B
						
						// korzystamy z 'magicznej' wlasciwosci 'map',
						// operator ++: dla elementu ktory nie istnieje w mapie ustawia jego wartosc na 1 (startowa wartosc int to 0)
						// a dla elementu ktory juz jest w mapie zwieksza wartosc powiazanego 'inta'
						// nie musimy sie martwic o to czy cos jest w mapie itp., wszystko dziala tak jak bysmy chcieli
						
						// glos metoda A oddaje zwyciezca metoda A
						glosyNaKandydataMetodaA[miastoSasiedzkie->zwyciezcaKampaniiMetodaA]++;
						// glos metoda B oddaje zwyciezca metoda B
						glosyNaKandydataMetodaB[miastoSasiedzkie->zwyciezcaKampaniiMetodaB]++;
					}
					else
					{
						// jesli w miescie nie ma zwyciezcy to znaczy, ze w nastepnej rundzie nalezy w tym miescie przeprowadzic wybory
						listaMiastDoPrzeprowadzeniaWyborow_nastepnaRunda[miastoSasiedzkie] = ' ';
					}
				}

				// glosy przez wszystkich sasiadow zostaly oddane, teraz trzeba ustalic ktory kandydat wygral metoda A i B
				
				
				// Metoda A: kandydat ma miec najmniej glosow, a dla tych o takiej samej ilosci glosow wybieramy tego z wyzszym ID
				int minimalnaIloscGlosow = 100000; // ustawiamy jakas wartosc wieksza, niz maksymalna ilosc glosow [ilosc miast]
				Kandydat* zwyciezajacyKandydatMetodaA;
				for(map<Kandydat*, short int>::iterator it in glosyNaKandydataMetodaA)
				{
					if(it->second < minimalnaIloscGlosow || 
						(it->second == minimalnaIloscGlosow && it->first->id > zwyciezajacyKandydatMetodaA->id))
					{
						zwyciezajacyKandydatMetodaA = it->first;
						minimalnaIloscGlosow = it->second;
					}
				}
				// zapamietujemy kto wygral, ale nie zapisujemy w miescie, to zrobimy po zakonczeniu wyborow we wszystkich miastach w tej rundzie
				zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaA[miasto] = zwyciezajacyKandydatMetodaA;
				// zwiekszamy koszt kampanii metoda A
				zwyciezajacyKandydatMetodaA->kosztKampaniiMetodaA++;
				
				
				// Metoda B: kandydat ma miec najwiecej glosow, a dla tych o takiej samej ilosci glosow wybieramy tego z nizszym ID
				int maksymalnaIloscGlosow = 0;
				Kandydat* zwyciezajacyKandydatMetodaB;
				for(map<Kandydat*, short int>::iterator it in glosyNaKandydataMetodaB)
				{
					if(it->second > maksymalnaIloscGlosow || 
						(it->second == maksymalnaIloscGlosow && it->first->id < zwyciezajacyKandydatMetodaB->id))
					{
						zwyciezajacyKandydatMetodaB = it->first;
						maksymalnaIloscGlosow = it->second;
					}
				}
				// zapamietujemy kto wygral, ale nie zapisujemy w miescie, to zrobimy po zakonczeniu wyborow we wszystkich miastach w tej rundzie
				zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaB[miasto] = zwyciezajacyKandydatMetodaB;
				// zwiekszamy koszt kampanii metoda B
				zwyciezajacyKandydatMetodaB->kosztKampaniiMetodaB++;
			}
		}
		// skonczyly sie wybory tej rundy, pora przypisac zwyciezcow do miast
		for(map<Miasto*, Kandydat*>::iterator it in zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaA)
		{
			// metoda A
			it->first->zwyciezcaKampaniiMetodaA = it->second;
		}
		for(map<Miasto*, Kandydat*>::iterator it in zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaB)
		{
			// metoda B
			it->first->zwyciezcaKampaniiMetodaB = it->second;
		}
		
		wyczysc 'zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaA';
		wyczysc 'zwyciezcyDoZapisaniaPrzedNastepnaRundaMetodaB';
		
		// mozna zaczac kolejna ture wyborow
	}
	// wszystkie wybory sie skonczyly, pora wypisac koszty kampanii
	for(i < iloscKandydatow, i++)
	{
		wyswietl << listaKandydatow[i]->kosztKampaniiMetodaA;
		wyswietl << "spacja";
		wyswietl << listaKandydatow[i]->kosztKampaniiMetodaB;
		wyswietl << "znak nowej linii 🙂 ";
	}
}
Ten wpis został opublikowany w kategorii PJWSTK, PJWSTK - ASD. Dodaj zakładkę do bezpośredniego odnośnika.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *