zadanie 1
Podaj algorytm, w pseudokodzie, który wyznacza element minimalny w tablicy \(\displaystyle{ A \left[ 1...n \right]}\)
Użyj pętli:
a) while
b) for
Podaj złożoność swojego algorytmu, mierzoną liczbą porównań kluczy.
zadanie 2
Podaj algorytm, w pseudokodzie, który wyznacza najmniejszy indeks elementu minimalnego w tablicy \(\displaystyle{ A \left[ 1...n \right]}\)
zadanie 3
Podaj algorytm, w pseudokodzie, który wyznacza największy indeks elementu minimalnego w tablicy \(\displaystyle{ A \left[ 1...n \right]}\)
algorytm w pseudokodzie
-
- Użytkownik
- Posty: 6607
- Rejestracja: 16 sty 2007, o 19:42
- Płeć: Mężczyzna
- Podziękował: 119 razy
- Pomógł: 1823 razy
algorytm w pseudokodzie
Wszystko opiera się na tym samym i ma tą samą złożoność. Polega to na przejściu jeden raz tablicy w ten sposob:
I na końcu mamy wartość minimalną.
2 i 3 działa na takiej samej zasadzie, tylko że trzeba dodać zmienną zapamiętująca i wtedy gdy znajdziemy mniejszy indeks. I tyle
Pozdrawiam.
Kod: Zaznacz cały
int min=A[1]
for(i=2;i<=N;++i)
{
if(A[i]<min)
{
min=A[i];
}
}
2 i 3 działa na takiej samej zasadzie, tylko że trzeba dodać zmienną zapamiętująca i wtedy gdy znajdziemy mniejszy indeks. I tyle
Pozdrawiam.
-
- Użytkownik
- Posty: 860
- Rejestracja: 18 cze 2007, o 20:57
- Płeć: Kobieta
- Lokalizacja: Rybnik
- Podziękował: 86 razy
- Pomógł: 57 razy
algorytm w pseudokodzie
zadanie5
Załóżmy, że dana tablica liczb \(\displaystyle{ A[1,...,n]}\) . Podaj algorytm, w pseudokodzie, który zwraca indeks pierwszego elementu, który jest mniejszy od swojego poprzednika. jeżeli\(\displaystyle{ n=1}\) lub taki element nie istnieje, to algorytm ma zwrócić \(\displaystyle{ 0}\).
zadanie6
Podaj w pseudokodzie oraz w C++, algorytm wyszukania binarnego klucza key w posortowanej rosnąco tablicy \(\displaystyle{ T[1,...,n]}\).
Jeżeli key znajduje się w tablicy \(\displaystyle{ T[1,...,n]}\), to algorytm powinien zwrócić taki indeks \(\displaystyle{ k}\), że \(\displaystyle{ T[k]=}\)key.
Jeżeli key nie znajduje się w tablicy \(\displaystyle{ T[1,...,n]}\), to algorytm powinien zwrócić \(\displaystyle{ -1}\). Jaka jest złożoność czasowa optymistyczna i pesymistyczna podanego algorytmu?
Załóżmy, że dana tablica liczb \(\displaystyle{ A[1,...,n]}\) . Podaj algorytm, w pseudokodzie, który zwraca indeks pierwszego elementu, który jest mniejszy od swojego poprzednika. jeżeli\(\displaystyle{ n=1}\) lub taki element nie istnieje, to algorytm ma zwrócić \(\displaystyle{ 0}\).
zadanie6
Podaj w pseudokodzie oraz w C++, algorytm wyszukania binarnego klucza key w posortowanej rosnąco tablicy \(\displaystyle{ T[1,...,n]}\).
Jeżeli key znajduje się w tablicy \(\displaystyle{ T[1,...,n]}\), to algorytm powinien zwrócić taki indeks \(\displaystyle{ k}\), że \(\displaystyle{ T[k]=}\)key.
Jeżeli key nie znajduje się w tablicy \(\displaystyle{ T[1,...,n]}\), to algorytm powinien zwrócić \(\displaystyle{ -1}\). Jaka jest złożoność czasowa optymistyczna i pesymistyczna podanego algorytmu?
-
- Użytkownik
- Posty: 6607
- Rejestracja: 16 sty 2007, o 19:42
- Płeć: Mężczyzna
- Podziękował: 119 razy
- Pomógł: 1823 razy
algorytm w pseudokodzie
5. Chyba takie coś (jeśli dobrze zrozumiałem polecenie):
6.
Pozdrawiam.
Kod: Zaznacz cały
int previous=A[1];
for(int i=2;i<=n;++i)
{
if(A[i]<previous)
return i;
previous=A[i];
}
return 0;
Kod: Zaznacz cały
int first=1;
int last=n;
int middle=0;
while(first<=last)
{
middle=(first+last)/2;
if(key==T[middle])
return middle;
if(key>T[middle])
first=middle+1;
else if(key<T[middle])
last=middle-1;
}
return -1;