algorytm w pseudokodzie

Hania_87
Użytkownik
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

Post autor: Hania_87 »

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]}\)
soku11
Użytkownik
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

Post autor: soku11 »

Wszystko opiera się na tym samym i ma tą samą złożoność. Polega to na przejściu jeden raz tablicy w ten sposob:

Kod: Zaznacz cały

int min=A[1]

for(i=2;i<=N;++i)
{
  if(A[i]<min)
  {
    min=A[i];
  }
}
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.
Hania_87
Użytkownik
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

Post autor: Hania_87 »

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?
soku11
Użytkownik
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

Post autor: soku11 »

5. Chyba takie coś (jeśli dobrze zrozumiałem polecenie):

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;
6.

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;
Pozdrawiam.
ODPOWIEDZ