Clasa a V-a lecția 13 - 16 noi 2019

Comentarii generale

• Chiar dacă unele probleme sunt mai grele, nu trebuie să vă descurajați. Procesul de învățare presupune să vă loviți de lucruri pe care nu le știți, ca să înțelegeți care vă este nivelul și unde trebuie plusați. Vă felicit pe toți care ați participat în concursul de săptămâna trecută, chiar dacă nu ați știut să le faceți.
• Vă reamintesc că la acest cerc se studiază limbajul de programare C. Nu accept surse trimise în C++. Vreți să faceți C++, sunt convins că alți profesori vă pot acomoda cu asta. Dacă reușiți să faceți un cod în C++ și nu știți să îl scrieți și in C, înseamnă că nu știți algoritmul din spatele programului și l-ați copiat de undeva. Avertisment David Poterașu. La următoarea abatere, cartonaș roșu.
• Dacă se întâmplă să sărim o lecție, asta nu înseamnă că voi aveți voie să nu vă faceți temele. O parte dintre voi ați ignorat tema și ați participat doar la o parte din concursuri. Avertisment: David Poterașu, Vladimir Gavriș și Mara Florian.

Tema – rezolvări lecția 11 - 2 noi 2019

Rezolvări aici [1]

Tema – rezolvări lecția 12 - 9 noi 2019

Rezolvări aici [2]

Lecție

<html5media height="720" width="1280">http://algopedia.ro/video/2019-2020/2019-11-16-clasa-5-lectie-info-13-720p.mp4</html5media>

Instrucțiunea de incrementare/decrementare

Atunci cînd adunăm unu la o variabilă se cheamă că o incrementăm. De asemenea, cînd scădem unu, se cheamă că o decrementăm. Deoarece aceste două operații apar foarte frecvent limbajul C ne permite să le scriem mai scurt.

Instrucțiune	Instrucțiune echivalentă
i = i + 1;	i++;
i = i - 1;	i--;

Instrucțiunea for

Precum am văzut în exemplele anterioare de multe ori avem nevoie să executăm o buclă WHILE-DO de n ori, folosind un contor. Aceasta este un tip particular de buclă WHILE-DO, și anume o buclă cu număr cunoscut de pași. Pentru acest tip de bucle limbajul C ne permite o prescurtare, folosind instrucțiunea for.

Schemă logică	Implementare cu while	Implementare cu for
	i = 0; while ( i < n ) { ... execută corpul buclei... i = i + 1; }	for ( i = 0; i < n; i++ ) { ... execută corpul buclei... }

Atenție! Observații importante:

• Instrucțiunea de incrementare a contorului (i++) se execută întotdeauna la finalul buclei for, imediat înainte de revenirea la condiție.
• Cele două implementări sînt absolut echivalente, nu este una mai bună ca cealaltă. În fapt, atunci cînd scrieți o instrucțiune for compilatorul o traduce automat în instrucțiunea echivalentă while. Nu este absolut nici o problemă dacă nu vreți să folosiți instrucțiunea for, este doar o opțiune mai succintă pentru cei ce vor să scrie mai puțin, dar nu este obligatorie.
• La cercul nostru vom respecta următoarele convenții:
  • Vom folosi instrucțiunea for strict pentru buclele cu număr cunoscut de pași. Atunci cînd bucla WHILE-DO se poate executa de un număr necunoscut de ori vom folosi instrucțiunea mai generală while.
  • În interiorul unei instrucțiuni for nu avem voie să modificăm variabila contor a ciclului, adică i ! Dacă dorim să facem acest lucru vom folosi în loc o instrucțiune while.

Exerciții cu secvențe

Elementul maxim într-o secvență

Dată o secvență de n numere să se afișeze elementul cel mai mare (maxim) din secvență. Exemple:

maxim.in	maxim.out
6 4 2 0 4 7 1	7
8 3 12 10 12 8 3 6 8	12

Rezolvare:

Numărul maxim în secvență

#include <stdio.h> int main() { FILE *fin, *fout; int n, i, a, max; fin = fopen( "maxim.in", "r" ); fscanf( fin, "%d", &n ); fscanf( fin, "%d", &max ); for ( i = 1; i < n; i++ ) { fscanf( fin, "%d", &a ); if ( max < a ) max = a; } fclose( fin ); fout = fopen( "maxim.out", "w" ); fprintf( fout, "%d", max ); fclose( fout ); return 0; }

Observații:

• Elementul maxim se inițializează cu primul element al șirului nu cu valoarea zero. Întotdeauna vom inițializa maximul cu un element al secvenței. De ce?
  • Este bine să fim ordonați și consecvenți: max este doar un candidat la maxim, dintre elementele secvenței, pînă la final, cînd devine chiar maximul. Ce fel de candidat este el dacă este un străin, nici măcar nu face parte din secvență?
  • În viitor putem avea și elemente negative.
  • Dacă avem o greșeală în program detecția ei și corectura sînt mai grele atunci cînd max poate lua valori în afara elementelor din secvență.
• Pentru a calcula elementul minim într-o secvență singurul lucru care se modifică în schema de mai sus este semnul comparației max < a, din mai mic < în mai mare >.

Secvență în ordine crescătoare

Dată o secvență cu n numere să se spună dacă cele n numere din secvență sînt in ordine crescătoare (fiecare număr este mai mic sau egal cu cel de după el).

crescatoare.in	crescatoare.out
6 2 7 7 10 15 15	da
8 3 3 6 8 8 10 12 11	nu

Rezolvare:

Secvență crescătoare

#include <stdio.h> int main() { FILE *fin, *fout; int n, i, a, b, cresc; fin = fopen( "crescatoare.in", "r" ); fscanf( fin, "%d", &n ); fscanf( fin, "%d", &a ); cresc = 1; i = 1; while ( i < n && cresc == 1) { fscanf( fin, "%d", &b ); if ( b < a ) cresc = 0; a = b; i++; } fclose( fin ); fout = fopen( "crescatoare.out", "w" ); if ( cresc == 1 ) fprintf( fout, "da\n" ); else fprintf( fout, "nu\n" ); fclose( fout ); return 0; }

Observații:

• Nu folosim instrucțiunea for deoarece nu se știe de cîte ori se va executa bucla while (nu avem un ciclu cu număr cunoscut de pași).
• Trebuie să ținem minte elementul anterior în secvență, pentru a-l putea compara cu elementul curent. Vom vedea că în alte probleme vom avea nevoie să ținem minte două sau chiar și trei elemente anterioare.
• Încercaţi să scrieţi algoritmul fără a folosi steguleţe.

Temă

• Tema 13: să se rezolve următoarele probleme (schemă logică + program C în CodeBlocks, trimis la vianuarena):
  • Problema monotonă
  • Problema mulțimi dată la OJI 2005 clasa a 5^a.
• Problemă de logică: ne aflăm în întuneric total (nu putem vedea nimic). Avem în față un pachet de 52 de cărți de joc. Ele sînt amestecate, dar se știe că 42 de cărți sînt cu fața în jos, iar 10 sînt cu fața în sus. Cum facem să împarțim cele 52 de cărți în două gramezi, astfel încît ambele grămezi să conțină un număr egal de cărți cu fața în sus? Explicați de ce soluția voastră funcționează, altfel nu vi se acordă punctajul!

Rezolvări aici [3]