[Algorytmy] Ostatni element mniejszego od poprzednika

[saszaw90]

Witam, mam do napisania algorytm. Prosiłbym o sprawdzenie, czy są poprawne. Czy wcięcia też są ok.?

Mamy daną tablicę liczb \(\displaystyle{ A[1...n]}\).

Napisać algorytm, który zwraca indeks ostatniego elementu, który jest mniejszy od swojego poprzednika. Jeżeli taki element nie istnieje lub \(\displaystyle{ n=1}\), to algorytm ma zwrócić \(\displaystyle{ 0}\).

Daję swoje 2 różne wersje algorytmów z użyciem while i for:

<-- to jest to \(\displaystyle{ \leftarrow}\)

Kod: Zaznacz cały

i <-- 2;
while ( i <= n AND A[i] < A[i-1] ) 
do i <-- i + 1;
if (i <-- n + 1) 
   return 0
else 
return i

albo

Kod: Zaznacz cały

k <-- A[n-1]
for i <-- 2 to n
do if A[i]<A[i-1]
   return i
   k <-- A[i]
   else
return 0

Jeśli byłoby źle, prosiłbym o wskazanie. Będę wdzięczny za pomoc.

[royas]

W takiej konwencji, gdzie zagnieżdżenie instrukcji określone jest jedynie wcięciami, każde "else" musi mieć takie samo wcięcie co odpowiadający mu "if". Lepiej też pisać "do" w tej samej linii instrukcja pętli, lub wcale go nie pisać. Spróbuj sam po prostu popatrzeć na ten kod i spróbować zrozumieć, co jest wewnątrz pętli, co wewnątrz "if" co wewnątrz "else". Jeśli nie potrafisz tego jednoznacznie powiedzieć, to znaczy, że wcięcia są źle.

[saszaw90]

Właśnie z tym mam problem. W języku C++ nie trzeba tego robić, ale można, żeby było przejrzyste. A w pseudokodzie muszą być.

Może najpierw zostawmy te wcięcia. To poprawię z tymi "else". Szkoda, że edytowałeś swój post. Nie zdążyłem jeszcze go przeczytać.

Czy algorytm jest dobrze napisany? Czy trzeba coś zmienić?

[royas]

Nie ma jedynej słusznej definicji pseudokodu. Możesz stosować wersję jaką chcesz, byleby było czytelnie. Możesz zamiast wcięć używać {} możesz begin end. Ale wcięcia zazwyczaj zapewniają to co ważne w pseudokodzie: czytelność. Żeby mówić czy algorytm jest poprawny trzeba wiedzieć jaki on jest. Jak jest nieczytelnie zapisany to tego nie wiadomo.
Przypuszczam, że chodzi Ci o takie coś:

Kod: Zaznacz cały

i <-- 2;
while ( i <= n AND A[i] < A[i-1] ) 
    i <-- i + 1;
if (i <-- n + 1) 
   return 0
else 
    return i

I tak jest źle. Pierwsza sprawa: w warunku dla IF masz podstawienie, jak to rozumieć?
Druga: W ten sposób nie znajdziesz tego co masz znaleźć. Zakończysz przeglądanie tablicy na pierwszym elemencie, który nie jest mniejszy od swojego poprzednika. Skąd wiesz, że gdzieś dalej, w nieprzeglądniętym fragmencie, nie wystąpi znowu element mniejszy od poprzednika? Musisz przejść przez całą tablicę i zapamiętywać indeks ostatnio znalezionego pasującego elementu.

Nie edytowałem swojego poprzedniego wpisu.

[ksisquare]

a "dozory" Wirtha?