niedziela, 9 października 2011

Algorytm szukania najmniejszej i największej liczby w podanym zbiorze

Algorytm 1 - min

Zadanie: Znajdź najmniejszą liczbę spośród podanego zbioru i podaj jej miejsce w zbiorze.

Specyfikacja:
Dane: Liczba naturalna n i zbiór n liczb
Wynik: Najmniejsza spośród liczb w zbiorze i jej miejsce w zbiorze.

Implementacja w C++

#include <iostream>

using namespace std;

int main()
{
    unsigned int n, min, miejsce;
    cout << "Podaj ilosc elementow: " << endl;
    cin >> n;
    unsigned int t[n];
    for (unsigned int i = 1; i<=n; i++ )
    {
        cout << i << ": ";
        cin >> t[i-1];
        cout << endl;
    }

    min = t[0];

    for (int i = 1; i<n; i++ )
    {
        if(t[i] < min)
        {
            min = t[i];
            miejsce = i;
        }
    }


    cout << "Najmniejsza: "<< min << endl<< "Jest " << miejsce+1<< " liczba w zbiorze";
    return 0;
}

Złożoność algorytmu: T(n) = n - 1

Algorytm 2 - min i max - metodą dziel i zwyciężaj

Zadanie: Znajdź najmniejszą i największą liczbę spośród podanego zbioru.

Specyfikacja:
Dane: Liczba naturalna n i zbiór n liczb
Wynik: Najmniejsza i największa spośród liczb w zbiorze

Implementacja w C++
#include <iostream>

using namespace std;

int main()
{
    unsigned int n, min, max;

    cout << "Podaj ilosc elementow: " << endl;
    cin >> n;
    unsigned int t[n];

    for (unsigned int i = 1; i<=n; i++ )
    {
        cout << i << ": ";
        cin >> t[i-1];
        cout << endl;
    }

  if (n % 2){ t[n] = t[n-1] }

     min = t[0];
     max = t[0];

    for (unsigned int i = 0; i<n; i=i+2 )
    {
        if (t[i]<t[i+1])
        {
            if(t[i] < min)
                min = t[i];
            if(t[i+1] > max)
                max = t[i+1];
        }

       else //if (t[i] > t[i+1])
       {
            if(t[i+1] < min)
                min = t[i+1];
            if(t[i] > max)
                max = t[i];
       }

    }

    cout << "Najmniejsza: "<< min << endl;
    cout << "Najwieksza: "<< max << endl;

    return 0;
}


Złożoność algorytmu: 3/2 * n

5 komentarzy:

  1. U mnie ten przykład się nie kompiluje. Nie możemy użyć zmiennej do określenia wielkości tablicy, tam musi być stała, wielkość tablicy musi być znana jeszcze przed kompilacją, chyba że użyjemy tablicy dynamicznej, jak się mylę to mnie poprawcie.

    A co do reszty, nie kumam czemu to ma służyć:
    if(n % 2) t[n] = t[n-1];
    Będę wdzięczny za wyjaśnienie tej linijki.

    Ja napisałem ten program tak:

    #include
    #include
    using namespace std;

    int main()
    {
    const int n=10; //ilosc elementow zbioru
    int tab[n];
    int min,max;

    //wypelnienie tablicy wartosciami z klawiatury

    for(int i=0; i>tab[i];
    cout< tab[i]) min=tab[i];
    if(max <= tab[i]) max=tab[i];
    }
    cout<<"najmniejsza wartosc: "<<min<<endl<<"najwieksza wartosc: "<<max;
    getch();
    }

    Czy mój program realizuje założenie szukania min i max zbioru? Czy to algorytm optymalny?
    No i czy wszystko gra? Z góry dzięki za odpowiedź.

    Aha, miałbym prośbę, mógłbyś jakoś bardziej objaśniać na czym dany algorytm polega itp, sam przykład to jednak trochę mało żeby się wszystkiego nauczyć. Pozdrawiam ;-)

    OdpowiedzUsuń
  2. Ahh, posiekało mój program, nie można wrzucić kodu do komentarza ;\ No trudno.

    OdpowiedzUsuń
  3. Adam możemy użyć zmiennej ale tylko wtedy gdy wartość będzie podana przez użytkownika tylko raz, jeśli chciałbyś napisać ten program tak by działał tak długo aż użytkownik nie będzie chciał go skończyć, to wtedy musiałbyś użyć tablicy dynamicznej.

    Co do błędów w kompilacji mogą być 2 przyczyny:
    1. inny kompilator, ja używam Code::Block
    2. złe kodowanie, wklejenie kodu do notatnika i przekopiowanie go z niego do kompilatora może naprawić problem

    OdpowiedzUsuń
  4. linijka
    if(n % 2) t[n] = t[n-1];
    sprawdza czy n jest liczbą parzystą czy nieparzystą poprzez odczytanie reszty z dzielenia n/2 jeśli jest większa od 0 to liczba jest nieparzysta i wykona się dalsza część kodu czyli:
    t[n] = t[n-1];
    który z kolei do ostatniego elementu przypisuje przedostatni, wcześniej stworzyliśmy wczytywaliśmy liczby od użytkownika od 0 do n-1 i teraz zapełniamy ten brak.

    Jestem Ci Adam również bardzo wdzięczny za ten komentarz bo zmusił mnie do ponownej analizy tego programu i udało mi się wyłapać parę błędów, po napisaniu tego komentarza zmienię kod we wpisie na poprawny.

    OdpowiedzUsuń
  5. Co do twojego programu to wklej go na jakąś stronkę która podkreśla kod i daj link do niego np. http://pastebin.com/
    Objaśnienie algorytmu być może pojawi się za kilka dni ;)

    OdpowiedzUsuń