[C] Poprawność programu

Nuna
Użytkownik
Użytkownik
Posty: 40
Rejestracja: 7 gru 2019, o 19:36
Płeć: Kobieta
wiek: 19
Podziękował: 17 razy

[C] Poprawność programu

Post autor: Nuna » 25 sty 2020, o 15:47

Mam taki fragment programu:

Kod: Zaznacz cały

int licznik = 0 ; 
int i = 0 ;
while ( i<n ) {
  while ( t [i] == 0 && i<n )
    i = i +1
if ( i<n )
  if ( t [ i ] > 0 ) 
    licznik ++;
  else 
    licznik −−;
i = i +1;
}
bool tyle_samo = ( licznik == 0 ) ;
Zadanie polega na znalezieniu w nim błędu i napisaniu dla jakich danych nie zadziała. Tablica jest int t[n], gdzie \(\displaystyle{ n \le 1}\). Siedzę nad tym i błędu nie widzę, rozważałam przypadki dla tablic jednoelementowych, wypełnionych tylko zerami czy liczbami dodatnimi i nadal nic.
Ostatnio zmieniony 25 sty 2020, o 16:58 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3129
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 152 razy
Pomógł: 475 razy

Re: [C] Poprawność programu

Post autor: leg14 » 26 sty 2020, o 18:13

while ( t [i] == 0 && i<n )

Załóżmy, że masz tablicę, która ma tylko zera.
Co się stanie w pętli powyżej?

Dojdzie do ewaluacji t[n]
Ostatnio zmieniony 26 sty 2020, o 18:34 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.

Nuna
Użytkownik
Użytkownik
Posty: 40
Rejestracja: 7 gru 2019, o 19:36
Płeć: Kobieta
wiek: 19
Podziękował: 17 razy

Re: [C] Poprawność programu

Post autor: Nuna » 26 sty 2020, o 22:10

leg14 pisze:
26 sty 2020, o 18:13
while ( t [i] == 0 && i<n )

Załóżmy, że masz tablicę, która ma tylko zera.
Co się stanie w pętli powyżej?

Dojdzie do ewaluacji t[n]
No właśnie dlaczego? Przecież w pętli mam warunek while( t[i] == 0 && i < n), zatem jeżeli tablica ma same zera, to i == n, wtedy pętla zakończy działanie (wydaje mi się, że poprawniej byłoby napisać while(i<n && t[i] == 0), choć i tak czy siak będzie fałsz). No ok, to mamy i równe n. Omijamy więc if i zwiększamy znów i o jeden. Zatem i == n +1, wracamy na początek "głównej" pętli, warunek jest fałszywy, zatem z niej wychodzimy. Czy coś źle rozumiem?

Awatar użytkownika
leg14
Użytkownik
Użytkownik
Posty: 3129
Rejestracja: 5 lis 2014, o 20:24
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 152 razy
Pomógł: 475 razy

Re: [C] Poprawność programu

Post autor: leg14 » 27 sty 2020, o 22:38

Przecież w pętli mam warunek while( t[i] == 0 && i < n), zatem jeżeli tablica ma same zera, to i == n, wtedy pętla zakończy działanie
Pętla zakończy działanie, ale najpierw sprawdzi, co znajduje się w tablicy \(\displaystyle{ t}\) pod indeksem \(\displaystyle{ n}\).
wydaje mi się, że poprawniej byłoby napisać while(i<n && t[i] == 0), choć i tak czy siak będzie fałsz
Tak, to by było poprawnym rozwiązaniem (zaznaczę, że while( t[i] == 0 && i < n) jest absolutnie niepoprawne)

Żeby zrozumieć czemu 2 opcja jest dobra, a pierwsza nie, musisz wiedzieć, że w C jest coś takiego jak "lazy evaluation" i kolejność obliczania wyrażeń.
W momencie, gdy i staje się równe n, program przejdzie do sprawdzenia warunku pętli. Warunek pętli składa się z koniunkcji dwóch wyrażeń logicznych i te wyrażenia będą ewaluowane od lewej do prawej.

Czyli i staje się n. Program zaczyna sprawdzać warunek pętli. Pierwszym warunkiem w koniunkcji jest

Kod: Zaznacz cały

 t[i] == n 
wobec tego program sięga do n + 1 elementu tablicy, by sprawdzić, czy tam jest zero, ale ten element nie istnieje, w tym miejsciu pamięci znajduje się coś kompletnie innego!

Teraz czemu "lazy evaluation" pozwala nam ominąć ten problem w drugim przypadku. Zauważ, że jedyne co się zmieniło w warunku pętli, to kolejność składników koniunkcji.

Więc znowu...
Załóżmy, że i staje się n. Program przechodzi do poczatku pętli i zaczyna sprawdzać jej warunek.
Ewaluuje składniki od lewej do prawej. Pierwszym składnikiem jest i < n.
No więc ewaluujemy go i widzimy, że on jest fałszywy. Ale warunek pętli jest koniunkcją (!), czyli już na tym etapie wiemy, że warunek pętli jest niespełniony, dlatego nasz leniwy program (stąd "lazy evaluation") w ogóle nie sprawdzi, czy

Kod: Zaznacz cały

t[i] == 0 
, bo do niczego mu to nie jest potrzebne, więc w tym wypadku jesteśmy bezpieczni i nie dojdzie do sięgniecia do pamięci, do której nie powinniśmy sięgać
Ostatnio zmieniony 27 sty 2020, o 23:10 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.

Dudenzz
Użytkownik
Użytkownik
Posty: 87
Rejestracja: 8 mar 2009, o 18:21
Płeć: Mężczyzna
Pomógł: 19 razy

Re: [C] Poprawność programu

Post autor: Dudenzz » 29 sty 2020, o 13:12

Teraz może wydawać ci się, że tak nie jest, ale wierz mi - ważniejsze od istoty problemu są: brakujący na końcu piątej linii średnik; oraz, zdaje się, niepoprawny symbol przy warunku \(\displaystyle{ n \le 1}\).

Zanim opublikujesz, dasz komuś do sprawdzenia, oceny, po prostu komuś pokażesz swoje rozwiązanie - koniecznie je SKOMPILUJ(ew. zinterpretuj jeżeli język jest skryptowy), SKOPIUJ (nie przepisuj, skopiuj) i URUCHOM. W porównaniu do kogoś kto programuje, osoba nieprogramująca nie zwraca uwagi na błędy literowe... w ogóle. Szybkie rozpoznawanie i poprawa prostych błędów literowych (składniowych lub merytorycznych) to bardzo ważna umiejętność, w szczególności w programowaniu i, jak każdej innej umiejętności, trzeba jej się nauczyć. Aby jej się nauczyć musisz "nie wstawić średnika na końcu linii" wiele razy, i w zauważeniu tego błędu ma Ci pomóc IDE lub w ostateczności kompilator. Jeżeli będziesz prezentować zadania w których brakuje średnika, albo rozwiązanie, które realizuje treści inne niż te przedstawione w zadaniu, marnujesz czas osoby, która to rozwiązanie czyta i przede wszystkim swój czas. Który, jak zapewne już wiesz, w nauce programowania jest bezcenny.

Uprzedzając odpowiedź, to, że posługujesz się IDE nie jest żadnym usprawiedliwieniem. Pisanie bez konieczności zwracania uwagi na wszelkiego rodzaju kolory, podświetlenia i podkreślenia generowane przez edytor, a w szczególności bez konieczności kompilowania programu kilka razy, znacznie przyspiesza pracę i pozwala się skupić na rzeczach pozornie ważniejszych, czyli w tym wypadku istocie problemu.

Afish
Moderator
Moderator
Posty: 2817
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 353 razy

Re: [C] Poprawność programu

Post autor: Afish » 15 lut 2020, o 16:14

leg14 pisze:
27 sty 2020, o 22:38
C jest coś takiego jak "lazy evaluation"
To się nazywa short circuiting. Lazy evaluation w językach programowania jest dobrze określonym terminem i znaczy coś zupełnie innego.

ODPOWIEDZ