Clasa a V-a lecția 39 - 3 mai 2018
Tema - comentarii
Problema pyk
Mulți dintre voi nu au rezolvat punctul doi, care era de fapt problema. Este de înțeles în timpul concursului, deoarece problema este grea. Nu este de înțeles la temă, unde ați avut șase zile, o lecție în care ați vorbit despre rezolvare, algopedia unde puteați să recitiți ceea ce nu ați înțeles, sau chiar să vedeți filmul lecției si lista clubul curioșilor unde puteați să puneți întrebări.
În aceste condiții consider că toți cei ce au luat 15p sau mai puțin nu au avut chef să își facă tema. Această lipsă de chef se va reflecta desigur în selecția grupei IQ Academy anul 2018-2019.
Mai concret, cei care au luat sub 15p sînt:
Grupa de dimineață: Aizic, Dumitrescu, Cojocaru, Petcu, Rughiniș
Grupa de după amiază: Cadîr, Ogrezeanu
Nu uitați: IQ Academy este un club al celor ce vor să lucreze și nu al vedetelor care își fac tema cînd au chef.
Căutare scrisă greșit
Iată niște secvențe de instrucțiuni luate din rezolvările voastre la teme care testează dacă un număr a citit este format dintr-o singură cifră. Găsiți problemele în aceste programe.
Elisa Ipate:
ok=0;
while(a>9 && ok==0){
if((a/10)%10!=a%10)
ok=1;
a=a/10;
}
if(ok==0) ...Alex Benescu:
f=0;
if(ca>=10){
while(ca>=10 && f==0){
if(ca%10!=ca/10%10)
f=1;
ca/=10;
}
}
if(f==0) ...David Stancu:
ok=1;
while(t>0 && ok==1)
{
if(t%10!=x%10)
{
ok=0;
}
t=t/10;
}
if(ok==1) ...Andreea Chivu:
uc=x%10;
ok=1;
while(cx!=0 && ok==1) {
if(cx%10!=uc)
ok=0;
cx=cx/10;
}
if(ok==1)Teodor Togan:
aux=x%10;
x=x/10;
for(;x>0;x=x/10){
if(aux!=(x%10)){
st=1;
x=0;
}
}
if(st==0) ...
...
st = 0;Ilinca Marcu:
cf1=cnr%10;
cnr=cnr/10;
nrc++;
while(cnr!=0)
{
cf2=cnr%10;
if(cf1==cf2)
nre++;
nrc++;
cnr=cnr/10;
cf1=cf2;
}
if(nre+1==nrc)Ana-Maria Petcu:
g = 0;
cv = a % 10;
ac /= 10;
while( ac > 0 && g == 0 ) {
g = g + ac % 10 - cv;
cv = ac % 10;
ac /= 10;
}
if( g == 0 ) ...Armin Asgari:
ok = 0;
uc = a % 10;
a = a / 10;
while ( a > 0 && ok == 0 ) {
if ( a % 10 != uc )
ok = 1;
a = a / 10;
}
if ( ok == 0 ) ...Care sunt problemele în aceste secvențe de cod? Cum puteau fi ele scrise mai simplu și mai elegant?
Iată un exemplu de cod corect:
Vlad Burac:
x = a % 10;
while ( a > 0 && a % 10 == x )
a = a / 10;
if ( a == 0 ) ...Greșeli de începător, la o problemă de lecția 4. Avem pretenții de olimpici? Ce-ar fi să ne însușim mai întîi bazele programării?
Descompunere în factori primi greșită
Iată exemple de secvențe care descompun în factori primi un număr. Am eliminat testul de împărțire la 2, pentru simplitate.
Elisa Ipate:
j=3;
while(a>1){
while (a%j==0) {
a=a/j;
v[j]++;
}
j=j+2;
}David Stancu:
d=3;
while(x>1)
{
p=0;
while(x%d==0)
{
x=x/d;
p++;
}
if(p>0)
ap[d]=ap[d]+p;
if(d*d>x)
d=x;
else
d=d+2;
}Alex Hossu:
j = 2;
while (x > 1) {
while ((x % j == 0) && (x > 0)) {
x = x / j;
v[j]++;
}
flag = 1;
ii = j + 1;
while (flag == 1) {
if (ciur[ii] == 0) {
flag = 0;
} else
ii++;
}
j = ii;
}Nu am idee ce face partea de la flag = 1 încolo...
Mihai Mocanu:
while(a>1){
if(a%d==0){
v[d]++;
a/=d;
}else{
d++;
}
}Ana-Maria Petcu:
d = 2;
while ( a > 1 ) {
p = 0;
while ( a % d == 0 ) {
p++;
a /= d;
}
ciur[d] += p;
d++;
}Care sunt problemele în aceste secvențe de cod? Cum puteau fi ele scrise eficient și simplu?
Iată un exemplu de cod corect:
Andreea Chivu:
d=2;
while(d*d<=x) {
p=0;
while(x%d==0) {
p++;
x=x/d;
}
v[d]=v[d]+p;
d++;
}
if(x!=1)
v[x]++;Greșeli de începător, din nou. Am rezolvat descompunerea în factori primi de ceva vreme.
Tema - rezolvări
Rezolvări aici [1]
Lecţie
<html5media height="720" width="1280">https://www.algopedia.ro/video/2017-2018/2018-05-03-lectie-info-39-720p.mp4</html5media>
Constante in C
Constante în C: #define. Atunci cînd o constantă apare des în program este bine să îi dăm un nume cu #define. În felul acesta programul devine mai citibil, iar în cazul unei modificări ulterioare a constantei putem modifica într-un singur loc.
Exemplu: să se ordoneze n numere cu valori între 0 și 100.
| Input | Output |
|---|---|
| 8
3 2 9 6 3 2 9 6 |
2 2 3 3 6 6 9 9 |
Rezolvare: vom folosi sortarea bazată pe vector de frecvență (counting sort). Construim vectorul de frecvență al numerelor de la intrare, apoi îl parcurgem afișînd pozițiile cu valori nenule de cîte ori arată acea valoare. Ca noutate vom folosi o constantă pentru valoarea maximă a unui element, adică 100. Iată programul:
// ordonare crescatoare a n numere cu valori intre 0 si 100
#include <stdio.h>
#define VAL_MAX 100
int v[VAL_MAX + 1];
int main() {
int n, i, j;
scanf( "%d", &n );
for ( i = 0; i < n; i++ ) {
scanf( "%d", &j );
v[j]++;
}
for ( i = 0; i <= VAL_MAX; i++ )
for ( j = 0; j < v[i]; j++ )
printf( "%d ", i );
printf( "\n" );
return 0;
}Avantajul folosirii constantei VAL_MAX este că, dacă ulterior enunțul problemei se schimbă, valoarea maximă devenind 200 sau alt număr, vom modifica doar VAL_MAX, într-un singur loc în program.
Un mod special de a folosi constantele este la debug: cît timp facem corecții la program putem defini o constantă care să "activeze" instrucțiuni de tipărire de debug:
#define D 1
...
if ( D )
printf( "x=%d y=%d a=%d\n", x, y, a )
...La final, cînd considerăm că programul este corect tot ce avem de făcut este să modificăm constanta D în zero:
#define D 0Observați folosirea lui 0 și 1 ca valori adevărat, respectiv fals.
Instrucțiunea switch
Precum ştim instrucţiunea if implementează structura alternativă. Uneori avem nevoie de decizii multiple, de exemplu cînd vrem să ştim dacă o variabilă are valoarea 1, 2 sau 3. În aceste cazuri putem folosi o combinaţie de instrucţiuni if:
if ( n == 1 ) {
cod pentru cazul 1;
} else if ( n == 2 ) {
cod pentru cazul 2;
} else if ( n == 3 ) {
cod pentru cazul 3;
}Deoarece situaţiile cînd vrem să executăm diverse acţiuni în funcţie de valoarea unei variabile limbajul C se oferă instrucţiunea switch a cărei formă este:
switch ( n ) {
case constantă1:
cod de executat dacă n este egal cu constantă1;
break;
case constantă2:
cod de executat dacă n este egal cu constantă2;
break;
.
.
.
default:
cod de executat dacă n nu este egal cu nici una din constante;
}Exemplu: se citesc pe aceeaşi linie, în ordine, un caracter şi apoi două numere întregi, toate separate printr-un spaţiu. Dacă caracterul este una din operaţiile +, -, * sau / să se afişeze rezultatul acelei operaţii pe cele două numere. În caz contrar să se afişeze cuvîntul eroare.
| Input | Output |
|---|---|
| + 12 191 | 203 |
| * 12 11 | 132 |
| % 20 8 | eroare |
Rezolvare:
#include <stdio.h>
int main() {
int a, b;
char ch;
ch = fgetc( stdin );
scanf( "%d%d", &a, &b );
switch ( ch ) {
case '+':
printf( "%d\n", a + b );
break;
case '-':
printf( "%d\n", a - b );
break;
case '*':
printf( "%d\n", a * b );
break;
case '/':
printf( "%d\n", a / b );
break;
default:
printf( "eroare\n" );
}
return 0;
}De menţionat că nu este obligatoriu să avem o variabilă testată în switch, putem avea o expresie, cu condiţia ca ea să aibă o valoare întreagă, nu reală.
Numere palindrom
Cum aflăm dacă un număr este palindrom (simetric)? Algoritmul clasic răstoarnă numărul şi testează dacă numărul este egal cu răsturnatul său:
#include <stdio.h>
int main() {
long long p, c, r;
scanf( "%lld", &p );
c = p;
r = 0;
while ( p > 0 ) {
r = r * 10 + p % 10;
p = p / 10;
}
if ( c == r )
printf( "DA\n" );
else
printf( "NU\n" );
return 0;
}Acest algoritm poate depăși valoarea maximă reprezentabilă pe tipul long long.
Ce alt algoritm putem folosi? O idee ar putea fi să comparăm prima cifră cu ultima, apoi le eliminăm şi reluăm. Iată programul:
#include <stdio.h>
int main() {
int n, nc, p10;
scanf( "%d", &n );
nc = n;
p10 = 1;
// Calculam 10 la puterea nr. cifre - 1
while ( nc > 9 ) {
p10 = p10 * 10;
nc = nc / 10;
}
// cita vreme mai avem macar doua cifre si prima cifra este egala cu ultima
while ( p10 > 1 && (n / p10 == n % 10) ) {
n = n % p10; // Taiem prima si ultima cifra din numar
n = n / 10;
p10 = p10 / 100; //Actualizam puterea
}
if ( p10 <= 1 ) // daca am ajuns la o cifra sau nici una este palindrom
printf( "DA\n" );
else
printf( "NU\n" );
return 0;
}Avem şi o metodă mai apropiată de cea originală, în care răsturnăm numărul numai pînă la jumate:
#include <stdio.h>
int main() {
long long p, r;
scanf( "%lld", &p );
r = 0;
while ( p > r ) {
r = r * 10 + p % 10;
p = p / 10;
}
// cînd numărul are un număr par de cifre testăm dacă p == r
// cînd numărul are un număr impar de cifre testăm dacă p == r / 10
if ( p == r || p == (r / 10) )
printf( "DA\n" );
else
printf( "NU\n" );
return 0;
}Secvență crescătoare prin rotație
Verificare secvență crescătoare prin rotație. O secvență este crescătoare prin rotație dacă fie este crescătoare (nedescrescătoare, include mai mic sau egal), fie poate fi făcută crescătoare prin rotații succesive (permutări circulare). Am discutat despre rezolvarea liniară, care nu necesită vectori.
#include <stdio.h>
int main() {
int n, i, a, b, primul, caderi;
scanf( "%d%d", &n, &a );
primul = a;
caderi = 0; // de cite ori gasim un numar mai mic ca cel din-naintea lui
i = 1;
while ( i < n && caderi < 2 ) {
scanf( "%d", &b );
if ( a > b )
++caderi;
a = b;
++i;
}
if ( caderi == 0 ) // daca e complet crescatoare, OK
printf( "DA\n" );
else if ( caderi > 1 ) // daca descreste de doua ori, nu este crescatoare
printf( "NU\n" );
else if ( primul >= b ) // daca descreste o data depinde de capete
printf( "DA\n" );
else
printf( "NU\n" );
return 0;
}Discuţie probleme temă
Am discutat despre problemele pe care le aveţi ca temă.
Temă
Tema 39: să se rezolve următoarele probleme (program C trimis la vianuarena):
Rezolvări aici [2]
