sobota, 12 listopada 2011

Metoda pucharowa - algorytm turniejowy

Zadanie z publikacji Macieja M. Sysło, "Wyszukiwanie i porządkowanie informacji":
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