Clasa a VI-a lecția 15 - 9 dec 2013
Tema - rezolvări
Rezolvări la cele probleme de la ultimele două teme.
Rezolvări la interval si alarma aici [1]
Rezolvări la leduri1 si gomoku aici [2]
Tema - comentarii
General
- Mă bucur că v-aţi îmbunătăţit: mai puţine submisii, mulţi luaţi 100 din prima.
- Folosiţi funcţii. Foarte frumos. Aveţi idee ce faceţi cu ele? Rareori. Eu nu folosesc funcţii. Oare de ce?
- Multe din programele voastre sînt dezlînate. Nu par gîndite, ci aproximate. Vă apucaţi de ele fără să ştiţi exact ce faceţi şi le ajustaţi pe parcurs. Aceasta se cheamă programare aproximativă şi este foarte rea. Puneţi metoda la punct înainte să vă apucaţi de program.
- Dacă programul vostru depăşeşte 100 de linii trebuie să vă îngrijoraţi. Metoda voastră este probabil în neregulă.
- Rezolvarea voastră este bine sa fie generală. Dacă scrieţi cod de genul if ( j == 2 || (i == 3 && j == 5) && (j == 5 || i == 8) ) cel mai probabil ca aţi pierdut din generalitatea problemei şi că ar trebui să vă gîndiţi la o soluţie care să se aplice pe toate cazurile, în loc să scrieţi cod separat pentru fiecare caz.
- Nu repetaţi cod. Nu este bine din multe motive. Copy/paste nu este prietenul vostru.
Interval
- Trei elevi au găsit o formulă corectă: Alexandra, Cella, Chris. Felicitări!
Alarma
- Surse de 4k-6k?? Cînd devin atît de mari este evident că greşiţi undeva.
- N-aţi ştiut să faceţi afişarea elegantă, fprintf cu "%02d".
- Mulţi dintre voi aţi greşit afişarea, cei care aţi luat 94p. Atenţie!
- Folosiţi cu încredere abs(): este în stdlib.h
- Nu ignoraţi warning-uri de genul: user.cpp:25:37: warning: format ‘%d’ expects argument of type ‘int*’, but argument 3 has type ‘char*’ [-Wformat]
- E greu să porniţi cu minimul unul din elemente - mult de scris. Porniţi cu ceva foarte mare, ce nu se poate atinge.
Leduri 1
- La fel, surse de 4k-6k?
- switch în loc de vector:
switch(i){
case 7:inm=1;break;
case 6:inm=10;break;
case 5:inm=100;break;
case 4:inm=1000;break;
case 3:inm=6000;break;
case 2:inm=60000;break;
case 1:inm=360000;break;
case 0:inm=3600000;break;
}- Care este rostul unui vector/matrice dacă pentru fiecare element scriem cod diferit? Alexandra?
- Unii au renunţat complet la vector, ajungînd la surse mari. Rareş? Bine că ceasul nu avea 30 de cifre :)
Gomoku
- Uimitor ce probleme v-a pus această problemă de bază. O problemă de parcurgere pe linii.
- Unii dintre voi nu au citit cu atenţie numele fişierelor: Maria, Andrei? Atenţie!
- N-ati folosit vectorii de direcţie! Cod lungit!
Bile 1
- Felicitari celor care au rezolvat cu sortare: Robert, sursă scurtă şi clară, bravo! V-aţi gîndit că există posibilitatea să picaţi testele mari?
- Unii aţi scris complicat despărţirea bilelor la obstacol. Nu aveţi nevoie de if.
Lecţie
Simulare
Am vorbit despre probleme de simulare.
- 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. Încercaţi voi această metodă.
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.
Temă
Rezolvaţi următoarele probleme introductive de simulare: Tema 15 clasa a 5a
Rezolvări aici [3]
