Site-ul cu rezumatul cursurilor și teme: algopedia
Timpul este scurt și avem de recapitulat din anii trecuți, plus de invățat materie nouă.Trebuie să lucrați mult acasă. Vă sfătuiesc să vă apucați deja de ONI-urile trecute. Trimiteți cît mai multe probleme pe campion. Cronometrați-vă, pentru a vedea cît vă ia, exact ca la concurs.Cereți-mi ajutorul pe email dacă vă împotmoliți sau dacă vreți indicații la probleme.
Tema
Am trecut prin temă, cu analiza complexității timpului:
Cîți ani bisecți între anul a și anul b. Interval închis [a, b].
Cîte zile sînt între două date calendaristice corecte (maxim 2 miliarde zile).
Declararea vectorilor cu inițializare, ca în rezolvarea problemei anterioare.
Dimensiunile diverselor tipuri: int are 4 octeți, long long are 8 octeți.
Estimarea numărului care încape pe un număr dat de biți folosind formula 210 ≈ 103
Automatele sînt un instrument matematic. Cercurile cu numere se numesc "stări", iar săgețile se numesc "tranziții". Automatul funcționează astfel: în starea curentă, în funcție de ce primește la intrare, automatul trece într-o stare nouă, efectuînd o eventuală acțiune.
Problema 'numere cu 2 cifre' de la test: spuneți dacă numărul n este format din exact două cifre repetate de oricâte ori. 23223 și 900990 sînt astfel de numere, pe cînd 593 și 44002 nu. Am rezolvat problema folosind următorul automat: Automatul pentru problema numere cu două cifre Rezultă programul:
#include <stdio.h>
int main() {
FILE *fin, *fout;
int n, stare, c, c1, c2;
fin = fopen( "nr2cifre.in", "r" );
fscanf( fin, "%d", &n );
fclose( fin );
stare = 0;
while ( (n > 0) && (stare < 3) ) {
c = n % 10;
n /= 10;
switch ( stare ) {
case 0:
c1 = c;
stare = 1;
break;
case 1:
if ( c != c1 ) {
stare = 2;
c2 = c;
}
break;
case 2:
if ( (c != c1) && (c != c2) )
stare = 3;
break;
}
}
fout = fopen( "nr2cifre.out", "w" );
if ( stare == 2 )
fprintf( fout, "numar format din fix doua cifre\n" );
else if ( stare < 2 )
fprintf( fout, "numar format din %d cifre\n", stare );
else
fprintf( fout, "numar format din 3 sau mai multe cifre\n" );
fclose( fout );
return 0;
}
Temă
Spuneți dacă o secvență de numere este monotonă. O secvență este monotonă dacă numerele ei sînt fie în ordine crescătoare fie în ordine descrescătoare. Rezolvați problema folosind automate. Nu aveți voie să folosiți tablouri (vectori sau matrice). Exemple:
3 3 3 6 8 8 10 14 14 20 este o secvență monotonă
5 5 5 este o secvență monotonă
20 20 20 14 14 10 8 8 6 3 3 3 este o secvență monotonă
2 este o secvență monotonă
3 3 3 8 8 6 7 8 nu este o secvență monotonă
Automatul pe care îl veți folosi este: Automatul pentru problema secvență monotonă
Se dă un fișier care conține un șir de caractere. Caracterele permise sînt litere mici, cifre, spațiu, tab (\t) și linie nouă (\n). Să se numere cîte cuvinte și cîte numere se află în fișier. Creați un automat și apoi scrieți programul care îl implementează. Rezolvarea temei constă atît in desenul automatului cît și în program. Exemple:
'abc123abc53zx' conține cuvintele abc abc zx și numerele 123 53
'asd 1 bx 120020ccc' conține cuvintele asd bx ccc și numerele 1 120020
Date numerele naturale a și b, a < b, b diferit de zero, să se afișeze fracția a / b în notație zecimală cu virgulă și perioadă. Algoritmul folosit trebuie să aibă complexitate proporțională cu numărul de cifre afișate. Atenție: dacă veți folosi un vector pentru a memora resturile parțiale veți ajunge la o complexitate pătratică, nu liniară, așa încît nu folosiți vectori.
