Zapisz w postaci listy kroków algorytm służący do znajdowania największej liczby w ciągu „metodą pucharową”; dany ciąg może mieć dowolną długość, nie koniecznie będąca potęgą liczby 2. Przyjmij, że na początku ciąg liczb jest dany w tablicy i postaraj się, by w trakcie algorytmu pozostałe z ciągu liczby także były pamiętane w tej samej tablicy. Zaimplementuj opisany algorytm w wybranym języku programowania.
Czyli piszemy program na znalezienie osoby która wygra turniej.
Dla ułatwienia dodałem dużo cout-ów służących jedynie analizie działanie programu.
Implementacja w C++ metody pucharowej:
#include <iostream> using namespace std; int main() { srand(time(NULL)); int n; cin >> n; int tab[n]; for ( int i = 0 ; i < n ; i++) { tab[i] = rand()%100+1; cout << tab[i]<< " "; } int p = n; // dodatkowa zmienna p int j = 0; do{ for (int i = 0; i < n; i += 2) { if (i+1 < p ){ cout << endl<< "walczy:" << tab[i] << " z : " << tab[i +1] ; //wygranych ustawiamy na poczatku tabeli w miejsca poprzednich przegranych if(tab[i] > tab[i+1] ) swap(tab[i/2], tab[i]); else swap(tab[i/2], tab[i+1]); cout << " wygral: " << tab[i/2]; j++; // zwiekszamy licznik meczy } else swap(tab[i], tab[i/2]) ; // w przypadku nieparzystej liczby zawodnikow, ostatniego zawodnika umieszczamy na miejscu ostatniego przegranego } cout <<endl<<"Tabela po "<< j << " meczach: " << endl; for ( int i = 0 ; i < p ; i++) { cout << tab[i]<< " "; } n = n/2; }while (j != p-1); // ilosc meczy ktore musza byc rozegrane to n-1 cout << endl << "Ostateczny wyglad tabeli: " <<endl; for ( int i = 0 ; i < p ; i++) { cout << tab[i]<< " "; } cout << endl<< "Zwyciezca turnieju: " << tab[0]; return 0; }
Brak komentarzy:
Prześlij komentarz