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
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.
OdpowiedzUsuń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 ;-)
Ahh, posiekało mój program, nie można wrzucić kodu do komentarza ;\ No trudno.
OdpowiedzUsuń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.
OdpowiedzUsuń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
linijka
OdpowiedzUsuń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.
Co do twojego programu to wklej go na jakąś stronkę która podkreśla kod i daj link do niego np. http://pastebin.com/
OdpowiedzUsuńObjaśnienie algorytmu być może pojawi się za kilka dni ;)