Clasa a VI-a lecția 14 - 20 dec 2018
Tema - rezolvări
Problema figura
Comentarii generale
- Felicitări celor ce au reușit o soluție optimă: Grecu, Mușat, Rebengiuc, Ilie (surprinzător de puțini).
- Unii din voi ați declarat matricea mai mare pentru a nu avea excepții la testarea punctelor de pe margini. Dar ați declarat-o greșit cu doar o linie și o coloană în plus. Trebuia să o declarați cu două linii și coloane în plus.
- Mulți dintre voi testat cele patru puncte din jurul punctului curent pentru a aduna sau a scădea unu la rezultatul final, dar nu v-ați prins că nu erau necesare teste, ci puteați scrie o formulă. Vedeți soluția de mai jos.
- Unii din voi au căutat perechi de puncte adiacente. Pentru aceasta au generat toate perechile de puncte. Atenție, complexitatea acestei soluții este foarte rea: 'O(D4)!
- Avertisment pentru programe aproape identice: Calotă și Stoian.
- Avertismente celor ce nu au trimis nici o soluție la această problemă: Coman.
Comentarii individuale
Grupa de dimineață
- Aizic: ai declarat matricea de latură 21. Pentru a putea accesa elementul n+1 trebuia să o declari de latură 22. Atenție! Motivul pentru care soluția nu funcționează este faptul că modifici valorile din matrice. Uneori un element '4' poate să ajungă la zero (atunci cînd este înconjurat de pătrate pline). Drept care elementele învecinate lui vor apărea ca neavînd vecin, motiv pentru care nu scazi laturile comune. Soluția ta este una încîlcită. Era mai bine să memorezi în matrice doar 1 sau zero, dacă aveai sau nu căsuța marcată.
- Badea: simpatică metoda. Ai grijă la complexitate, cît este ea? O(D4). Dacă D ar fi puțin mai mare nu te-ai încadra în timp. Condiția de vecinătate poate fi simplificată puțin:
(abs(x[i]-x[j])+abs(y[i]-y[j]))==1) - Benescu: însănătoșire grabnică!
- Burac: program foarte bun, bravo. Însă la citire ai o goangă mare. În loc să scrii:
for ( i = 0; i < n; i++ )
fscanf ( fin, "%d%d", &v1[i], &v2[i] );
for ( i = 0; i < d; i++ ) {
for ( j = 0; j < d; j++ ) {
for ( x = 0; x < n; x++ ) {
if ( i + 1 == v1[x] && j + 1 == v2[x] )
a[i][j] = 1;
}
}
}Era mai simplu și mult mai eficient să citești cele două valori și să le folosești direct ca linie și coloană în matrice, nu? Adică:
for ( i = 0; i < n; i++ ) {
fscanf ( fin, "%d%d", &l, &c );
a[l-1][c-1] = 1;
}- Calotă: program identic cu al lui Stoian. Aveți inclusiv aceeași ciudățenie, scădeți inutil unu din linie și din coloană. Cine este originalul? Ai grijă la complexitate, cît este ea? O(D4). Dacă D ar fi puțin mai mare nu te-ai încadra în timp.
- Chivu: program aproape perfect, bravo! Păcat că nu ai închis fișierele.
- Cojocariu: foarte drăguță metoda. O singură observație, în loc să scrii
if(f[l-1][c]==0)
p++;
else
p--;era mai simplu și mai eficient să scrii:
p += 1 - 2 * f[l-1][c];Mai mult, cele patru adunări s-ar fi transformat într-una singură:
p += 4 - 2 * (f[l-1][c] + f[l+1][c] + f[l][c-1] + f[l][c+1]);Ai grijă la matematică, este necesară foarte des.
- Cojocaru: o soluție bună, sper că este a ta. Indentarea este absolut neglijentă, ceea ce tu nu greșești. Ca observație, codul:
for ( i = 1; i <=n; i++ ){
for ( j = 1; j <= n; j++ ){
if(a[i][j]==1){
if(a[i-1][j]==0)
s++;
if(a[i][j-1]==0)
s++;
if(a[i+1][j]==0)
s++;
if(a[i][j+1]==0)
s++;
}
}
}ar fi putut fi scris mult mai simplu:
for ( i = 1; i <=n; i++ )
for ( j = 1; j <= n; j++ )
if(a[i][j]==1)
s += 4 - a[i-1][j] - a[i+1][j] - a[i][j-1] - a[i][j+1];- Coman: nimic?
- Dragomir: nu mi-e clar ce ai vrut să faci. Nu are sens să compari o linie cu ultima linie, căsuțele marcate nu vin în nici o ordine specială. Pe orice ai fi testat ai fi văzut că algoritmul nu funcționează. Cum e posibil să iei 100p la leduri și 10p la figura?
- Grecu: rezolvare foarte bună, Bravo!
- Hossu: Program foarte bun, bravo. Atenție la declararea matricei, trebuia de 22x22 elemente. În loc de:
rez = 0;
for (al = 1; al <= d; al++) {
for (ac = 1; ac <= d; ac++) {
if (v[al][ac] == 1) {
if (v[al][ac - 1] == 0)
rez++;
if (v[al][ac + 1] == 0)
rez++;
if (v[al + 1][ac] == 0)
rez++;
if (v[al - 1][ac] == 0)
rez++;
}
}
}puteai să scrii mai simplu:
rez = 0;
for (al = 1; al <= d; al++)
for (ac = 1; ac <= d; ac++)
if (v[al][ac] == 1)
rez += 4 - v[al][ac - 1] - v[al][ac + 1] - v[al + 1][ac] - v[al - 1][ac];- Iordache: o soluție foarte bună. Vezi mai jos cum se poate simplifica în continuare.
- Mocanu: o soluție foarte interesantă, în care parcurgi doar elementele unu din matrice. Se putea simplifica. În loc de:
p=0;
for(i=0;i<m1;i++){
if(m[v[0][i]+1][v[1][i]]==0){
p++;
}
if(m[v[0][i]-1][v[1][i]]==0){
p++;
}
if(m[v[0][i]][v[1][i]+1]==0){
p++;
}
if(m[v[0][i]][v[1][i]-1]==0){
p++;
}
}puteai scrie, mai simplu și mai eficient:
p=0;
for(i=0;i<m1;i++)
p += 4 - m[v[0][i]+1][v[1][i]] - m[v[0][i]-1][v[1][i]] - m[v[0][i]][v[1][i]+1] - m[v[0][i]][v[1][i]-1];- Mușat: o soluție perfectă, bravo.
- Nicola: însănătoșire grabnică!
- Petcu: o soluție corectă, bravo! De ce ai declarat vectorii de 441 de elemente? Corect era de 400 de elemente. Ai grijă la complexitate, cît este ea? O(D4). Dacă D ar fi puțin mai mare nu te-ai încadra în timp. La testarea adiacenței a două puncte calculezi diferențele pe x si pe y, dar apoi nu le testezi pentru egalitatea cu zero, ci compari chiar liniile între ele, sau coloanele. Codul se poate simplifica. În loc de:
if( ( l[i] == l[j] && x == 1 ) || ( c[i] == c[j] && y == 1 ) )
p -= 2;ai putea scrie altceva. Tu ai deja diferențele în valoare absolută în x și y. Vrei să testezi ca una din ele să fie 0 și cealaltă să fie 1. Singurul mod în care acest lucru este posibil este dacă suma lor este 1. Deci:
if( ( x + y == 1 ) )
p -= 2;- Rebengiuc: Program perfect, bravo! Comentarii bune.
- Rughiniș: vacanță plăcută. Era bine să faci tema.
- Stoian: program identic cu al lui Calotă. Aveți inclusiv aceeași ciudățenie, scădeți inutil unu din linie și din coloană. Cine este originalul? Ai grijă la complexitate, cît este ea? O(D4). Dacă D ar fi puțin mai mare nu te-ai încadra în timp.
- Ștefănescu: program foarte bun, bravo. Atenție mare la copy/paste, ultimul
ifdin buclele de calcul al perimetrului este incorect, ai duplicat penultimulifdar ai uitat să schimbi semnul minus în plus. Programul se poate simplifica. În loc de:
for (l=1; l<=d; l++) {
for (c=1; c<=d; c++) {
if (a[l][c] == 1) {
if (a[l-1][c] == 0) {
nr++;
}
if (a[l+1][c] == 0) {
nr++;
}
if (a[l][c-1] == 0) {
nr++;
}
if (a[l][c-1] == 0) {
nr++;
}
}
}
}puteai să scrii mai simplu:
for (l=1; l<=d; l++) {
for (c=1; c<=d; c++) {
if (a[l][c] == 1)
nr += 4 - a[l-1][c] - a[l+1][c] - a[l][c-1] - a[l][c+1];- Togan: program foarte bun. Atenție mare la limitele buclelor
for! Ele nu sînt de la zero la d+1 ci de la 1 la d. Programul se poate simplifica. În loc de:
a=0;
for(l=0;(d+2)>l;l++){
for(c=0;(d+2)>c;c++){
if(m[l][c]==0){
if((m[l+1][c]==1)&&(l+1<(d+2))){
a++;
}
if((m[l][c-1]==1)&&(c-1>=0)){
a++;
}
if((m[l-1][c]==1)&&(l-1>=0)){
a++;
}
if((m[l][c+1]==1)&&(c+1<(d+2))){
a++;
}
}
}
}puteai să scrii mai simplu:
a=0;
for(l=1;l<=d;l++)
for(c=0;c<=d;c++)
if(m[l][c]==0)
a += m[l+1][c] + m[l][c-1] + m[l-1][c] + m[l][c+1];- Voicu: programul este foarte bun. Dar atenție la limitele matricei, ai declarat-o de dimensiune 21, dar trebuia de 22. Ai grijă că
!a[i][j+1]este mai ineficient decît1-a[i][j+1], deoarece conține teste.
Grupa de după-amiază
- Asgari: program foarte bun. Parantezele pătrate ale vectorilor se lipesc de expresia din interior, nu mai lăsa spații. Programul se poate simplifica. Dacă nu foloseai funcții te prindeai de asta. În loc de:
p = 0;
for( i = 1; i <= d; ++i )
for( j = 1; j <= d; ++j )
if( mat[ i ][ j ] == 1 )
p = p + test( i - 1, j ) + test( i, j - 1 ) + test( i + 1, j ) + test( i, j + 1 );puteai să scrii:
p = 0;
for( i = 1; i <= d; ++i )
for( j = 1; j <= d; ++j )
if( mat[ i ][ j ] == 1 )
p = p + 4 - mat[i-1][j] - mat[i][j-1] - mat[i+1][j] - mat[i][j+1];Această variantă este mai eficientă pentru că nu conține teste.
- Cadîr: o soluție corectă, bravo! Codul se poate simplifica. În loc de:
sol = 0;
for (i = 1; i <= d; i++){
for (j = 1; j <= d; j++){
if (a[i][j] == 1){
if (a[i][j - 1] == 0)
sol++;
if (a[i - 1][j] == 0)
sol++;
if (a[i + 1][j] == 0)
sol++;
if (a[i][j + 1] == 0)
sol++;
}
}
}puteai scrie:
sol = 0;
for (i = 1; i <= d; i++){
for (j = 1; j <= d; j++){
if (a[i][j] == 1)
sol += 4 - a[i][j - 1] - a[i - 1][j] - a[i + 1][j] - a[i][j + 1];- Dobre: ideea este foarte bună. Dar implementarea este cam încîlcită. Tu cauți în matrice primul element nenul. Pe care îl prelucrezi testînd dacă și vecinii lui la dreapta și jos sînt și ei unu. Apoi treci la următorul element 1. Puteai să faci același lucru, mai simplu, parcurgînd matricea pe linii, în două bucle
for, și testînd valoarea fiecărui element. Dacă este 1 îl prelucrezi. - Fares: o soluție corectă, bravo! Codul se poate simplifica. În loc de:
sol = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (mat[i][j] == 1) {
if (mat[i + 1][j] == 0)
sol++;
if (mat[i - 1][j] == 0)
sol++;
if (mat[i][j + 1] == 0)
sol++;
if (mat[i][j - 1] == 0)
sol++;
}puteai scrie:
sol = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (mat[i][j] == 1)
sol += 4 - mat[i + 1][j] - mat[i - 1][j] - mat[i][j + 1] - mat[i][j - 1];- Ilie: Program perfect, bravo!
- Ipate: foarte drăguță metoda. O singură observație, în loc să scrii
if( l == 0 )
rez ++;
else if( m[l-1][c] == 0 )
rez ++;
else
rez --;era mai simplu și mai eficient să scrii:
rez += 1 - 2 * m[l-1][c];Pentru a scăpa de cazul limită (l == 0) puteai să declari matricea mai mare cu două elemente pe fiecare direcție. Apoi, cele patru adunări s-ar fi transformat într-una singură:
rez += 4 - 2 * (m[l-1][c] + m[l+1][c] + m[l][c-1] + m[l][c+1]);Atenție la matematică.
- Marcu: rezolvare foarte bună. Vezi mai jos cum puteai face ceva mai simplu și fără condiții.
- Nicu: codul tău este aiurit. Declari 5 matrice în loc de una singură, din care folosești doar 4. Îmi este neclar cum funcționează, dar pare că e corect. Vezi mai jos o soluție mai simplă.
- Stancu: un program foarte bun, bravo! Ar fi luat 100p dacă parcurgeai toată matricea. Însă ai uitat că ai două coloane și două linii în plus, iar parcurgerea trebuia făcută de la 1 la d, nu de la 0 la d-1.
- Tatomir: program aproape perfect. Păcat că ai declarat matricea prea mică și ieși din ea (dimensiune 21 în loc de 22).
- Teodorescu: soluție foarte bună, bravo! Ai fi putut simplifica programul dacă observai că poți scrie o formulă. Vezi mai jos cum.
Suprapuneri 1
Comentarii generale
- Avertismente celor ce nu au trimis nici o soluție la această problemă, sau au trimis o soluție de zero puncte: Aizic, Coman, Cojocariu (0p), Cojocaru, Grecu (0p), Iordache (0p), Stoian, Cadîr.
Rezolvări aici [1]
Lecţie
<html5media height="720" width="1280">https://www.algopedia.ro/video/2018-2019/2018-12-20-clasa-6-lectie-info-14-720p.mp4</html5media>
Vectori de direcţie
Atunci cînd avem de parcurs o matrice într-o ordine complexă, sau atunci cînd avem de simulat deplasarea unui obiect pe o tablă, trebuie să codificăm într-un fel direcţia de mers. Aceasta se poate face folosind teste multiple, cu instrucţiuni if sau switch. Programul nostru devine mai mare şi, posibil, mai lent.
Soluţia? Vom codifica direcţiile posibile folosind doi vectori preiniţializaţi, care memorează valorile de adunat la linie, respectiv la coloană. De exemplu, dacă un obiect se poate deplasa într-o matrice pe linie sau pe coloană, vom declara vectorii diferenţă pe linie, respectiv pe coloană astfel:
int dlin[4] = { 0, 1, 0, -1 };
int dcol[4] = { 1, 0, -1, 0 };Dacă codificăm direcţiile astfel:
0 - dreapta 1 - jos 2 - stînga 3 - sus
Atunci, pentru a ne deplasa în direcţia d va trebui să adunăm dlin[d] la linie şi dcol[d] la coloană:
lin = lin + dlin[d];
col = col + dcol[d];Dar dacă ne putem deplasa şi pe diagonale? Atunci vom avea opt direcţii şi opt elemente în vector. De exemplu:
int dlin[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int dcol[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };Exemplu: problema medalion
Pentru a rezolva primul punct al problemei medalion, completarea matricei spirală, vom declara matricea și apoi vectorii de direcție astfel:
int a[301][301];
int dlin[4] = { 1, 0, -1, 0 };
int dcol[4] = { 0, -1, 0, 1 };Pentru a completa o matrice de dimensiune nxn:
l = c = n / 2;
a[l][c] = contor = 1;
for ( len = 2; len < n; len += 2 ) {
// trasam patru segmente de lungime len incepind cu patratica imediat
// la dreapta ultimei patratele
l--; // ne deplasam diagonal in sus
c++;
for ( dir = 0; dir < 4; dir++ ) // pentru fiecare din cele patru directii
for ( i = 0; i < len; i++ ) { // trasam len patratele
l += dlin[dir]; // avansam conform vectorului de directie
c += dcol[dir];
contor++;
if ( contor > k )
contor = 1;
a[l][c] = contor;
}
}Vom vedea și alte exemple mai jos.
Bordarea matricelor
Atunci cînd avem de parcurs o matrice într-o ordine complexă, sau atunci cînd avem de simulat deplasarea unui obiect pe o tablă, trebuie să testăm dacă nu cumva coordonatele actuale sînt în afara matricei. Aceasta înseamnă că în bucla noastră va trebui să avem patru teste: dacă linia este mai mică decît zero sau mai mare decît numărul de linii, sau coloana este prea mică sau prea mare. Aceste patru condiţii trebuie testate la fiecare iteraţie, încetinind programul nostru şi adăugînd cod suplimentar. De exemplu, dacă vrem să executăm o buclă while pînă ce ieşim din matrice vom scrie ceva de genul:
int tabla[200][200];
while ( lin >= 0 && lin < m && col >= 0 && col < n ) {
// execută corpul buclei
}Soluţia? Vom declara matricea cu o bordură de un element, avînd grijă ca acea bordură să conţină valori care nu se pot afla în matrice. Astfel, testele de ieşire din matrice se transformă într-unul singur: vom verifica dacă elementul curent este diferit de cel din bordură. Pentru exemplul anterior, presupunînd că matricea conține doar elemente strict mai mari decît zero, vom folosi o bordură cu elemente zero, iar codul se poate scrie astfel:
int tabla[202][202];
while ( tabla[lin][col] > 0 ) {
// execută corpul buclei
}Exemplu: problema ținta
Simulare
Simularea pe calculator înseamnă reprezentarea unor aspecte din lumea reală într-un program pe calculator. Programul de simulare îşi propune să calculeze nu numai rezultatele finale, cît şi rezultate de pe parcursul simulării. Deşi simularea variază în funcţie de sistemul simulat, există unele caracteristici comune:
- Trebuie să avem un model, numit sistem. Sistemul evoluează, își schimbă starea. Deci avem o stare a sistemului. Ea trebuie descrisă complet, prin variabile.
- Avem un ceas, așa numitul tact al sistemului, bătaia lui de inimă, precum are și procesorul. De obicei tactul sistemului este impus de problemă.
- Avem o buclă, care avansează timpul cu un tact și modifică starea sistemului. Bucla testează un steguleț de oprire. În buclă se determină condiția de terminare și se setează stegulețul.
Aplicaţii
Aplicații, cu explicația variabilelor care descriu complet starea:
Problema robinson
Problema robinson a fost dată la ONI 2005 clasa a 6-a. Este o problemă tipică de parcurgere a unui drum în matrice. Drumul este predeterminat, nu avem opţiuni. Care este starea sistemului nostru? Ea este linia şi coloana lui Robinson precum şi matricea ce ţine minte pe unde a mai fost.
Iată un model de simulare clasică:
// incepe simularea
gata = 0;
while ( !gata ) {
// avem coordonate valide, deci le afisam
fprintf( fout, "%d %d\n", l, c );
dir = teren[l-1][c-1] % 4; // calculam restul
teren[l-1][c-1] = -1; // marcam faptul ca am mai fost aici
l += ldif[dir]; // calculam noua linie
c += cdif[dir]; // calculam noua coloana
if ( l < 1 || l > m || c < 1 || c > m ) // setam conditia de oprire
gata = 1;
else if ( teren[l-1][c-1] == -1 )
gata = 1;
}Acesta este un program didactic, şcolăresc. Desigur că în acest caz putem simplifica foarte mult codul, deviind de la simularea standard. În primul rînd putem folosi tehnica bordării. Vom înconjura matricea cu o bordură de elemente -1. În acest caz condiţia de oprire este cînd întîlnim un element -1. Această condiţie se poate testa direct în bucla while.
Codul rezultat va fi:
// incepe simularea
while ( teren[l][c] != -1 ) { // nu am mai fost aici, continuam
// avem coordonate valide, deci le afisam
fprintf( fout, "%d %d\n", l, c );
dir = teren[l][c] % 4; // calculam restul
teren[l][c] = -1; // marcam faptul ca am mai fost aici
l += ldif[dir]; // calculam noua linie
c += cdif[dir]; // calculam noua coloana
}Problema joc3
Problema joc3 a fost dată la ONI 2011 clasa a 6-a. Starea constă din poziția celor doi copii și din cîte un vector de fiecare copil care memorează pentru fiecare poziție dacă copilul a fost acolo. Simularea se termină fie cind indicii celor doi copii devin egali, fie cînd unul din copii sare pe un element 1 în vectorul său. Vom număra de cîte ori s-a executat bucla pentru a putea răspunde de cîte ori au sărit copiii. La ieșirea din bucla de simulare, vom calcula numărul de elemente zero în ambii vectori.
// incepe simularea
b = r = 0;
bogdan[b] = 1; // bogdan a fost aici
rares[r] = 1; // rares a fost aici
sarituri = 0;
gata = 0;
while ( !gata ) {
b = (b + x) % n; // il avansam pe Bogdan
r = (r - y + n) % n; // il avansam pe Rares
sarituri++; // am mai avansat o saritura pina la pozitia curenta
if ( bogdan[b] == 1 || rares[r] == 1 || b == r )
gata = 1;
bogdan[b] = 1; // bogdan a fost aici
rares[r] = 1; // rares a fost aici
}Din nou, acesta este un exemplu şcolăresc de simulare. Şi în acest caz putem simplifica programul observînd că dacă un copil se întoarce pe propriile sale urme aceasta se poate întîmpla numai pe căsuţa unu. Astfel condiţia de oprire devine fie ca unul din copii sa ajunga la unu fie ca ambii copii să fie pe aceeaşi căsuţă, condiţie ce poate fi incorporată chiar în while:
// incepe simularea
b = r = 0;
t = n - 1; // n - 1 sectoare necalcate
calcat[0] = 1; // sector calcat de macar unul din copii
sarituri = 0;
do {
b = (b + x) % n; // il avansam pe Bogdan
r = (r - y + n) % n; // il avansam pe Rares
sarituri++; // am mai avansat o saritura pina la pozitia curenta
if ( calcat[b] == 0 ) // scadem numar sectoare calcate
t--;
if ( r != b && calcat[r] == 0 ) // scadem numar sectoare calcate
t--;
calcat[b] = calcat[r] = 1; // marcam sectoare calcate
} while ( b != 0 && r != 0 && b != r );Temă
Rezolvaţi următoarele probleme introductive de simulare. Folosiţi tehnicile nou învăţate: vectori de direcţie și bordarea matricei.
- robinson dată la ONI 2005 clasa a 6a
- joc3 dată la ONI 2011 clasa a 6a
- furnica dată la OJI 2007 clasa a 6a
Rezolvări aici [2]
