Clasa a VI-a lecția 14 - 12 ian 2016
Lecție
Concurs
Test recapitulativ clasa a 6-a
Tema
Tema 14 clasa a 6-a Tema contine cele 2 probleme din concursul de astazi si 2 probleme de simulare.
Rezolvări aici: [1]
Cateva cuvinte despre simulare
Cu siguranta mulți dintre voi deja ați rezolvat cele 2 probleme de simulare. Le propunem insa aici cu scopul introducerii intr-o categorie noua de probleme si anume "Probleme de 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.
Descrierea problemelor
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.
