Clasa a V-a lecția 27 - 3 mar 2015

From Algopedia
Jump to: navigation, search

Tema - rezolvări

Rezolvări aici [1]

Lecţie

Discuţie despre problemele date anul trecut la OJI 2014. Ele vă vor rămîne ca temă.

Problema mărţişoare

Problema mărţişoare a fost dată la OJI 2014, clasa a 5a. Problema spune că se dau n numere care ar trebui să fie consecutive, dar este posibil să nu fie deoarece două cifre sînt interschimbate, între două din numere, sau, posibil, în interiorul aceluiaşi număr. Se cere să aflăm care sînt cele două cifre, precum şi care este numărul maxim din secvenţa din-nainte de modificare.

Cum rezolvăm această problemă? Să încercăm o idee simplă: să ne uităm la primele două numere. Ne putem da seama dacă vreunul dintre ele este schimbat? Am putea să calculăm diferenţa între ele. Dacă sînt consecutive înseamnă că ambele sînt neschimbate. În acest caz ştim care este primul număr din secvenţă şi, prin calcul, care ar trebui să fie celelalte numere. Apoi vom compara restul numerelor pentru a vedea care sint diferite, şi prin ce cifre diferă.

Dar dacă numerele nu sînt consecutive? Înseamnă că unul din ele este schimbat. Dar care? Sau dacă sînt cumva ambele schimbate?

Este clar că nu ne putem da seama de situaţie uitîndu-ne la primele două numere. Atunci să ne uităm la primele trei. Dacă toate trei sînt consecutive, e clar. Deducem numerele corecte. Dar dacă nu sînt? Atunci s-ar putea ca un număr să fie schimbat. Cum l-am putea găsi? Dacă un număr este schimbat atunci celelalte două nu sînt schimbate, aşa încît ele vor fi la distanţă corectă în şir. De exemplu, dacă primele trei numere sînt:

23 29 25

atunci ştim că numerele corecte sînt 23 şi 25 deoarece diferenţa lor este 2, iar ele sînt la două poziţii unul faţă de celălalt. Cum vom proceda pentru a detecta numărul schimbat? Vom compara fiecare număr cu fiecare şi vom găsi două cu diferenţa corectă. Atenţie! Este suficient să găsim două numere cu diferenţa corectă! În acel moment ştim că ambele sînt corecte şi putem deduce întreaga secvenţă originală.

Toate bune pînă aici. Dar dacă două numere din primele trei sînt schimbate? Atunci nu vom găsi două numere cu diferenţa corectă. Ce putem face? Deja ştim, nu? Vom mai adăuga un număr: ne vom uita la primele patru numere! Deoarece maxim două numere sînt schimbate, în mod sigur vom găsi două numere corecte, care au diferenţa egală cu numărul de poziţii dintre ele. Pe baza acestor două numere vom reconstitui secvenţa originală.

Dar stai! Avem oare patru numere în secvenţă? Verificînd enunţul aflăm că da. Ceea ce ne face încrezători că mergem către soluţia corectă.

Bun, să recapitulăm. Vom citi primele patru numere din secvenţă. Apoi vom forma toate perechile posibile, în număr de şase, comparînd diferenţa dintre numere cu diferenţa poziţiilor numerelor. Vom găsi, astfel, o pereche de numere corecte, din secvenţa originală. Mai departe: dacă ştim că numărul ci este corect, putem deduce atît primul număr din secvenţă, ca fiind ci-i, precum şi ultimul, ca fiind ci-i+n-1. Am considerat numerele numerotate de la zero.

Cum aflăm cifrele interschimbate? Să observăm că este deajuns să avem un singur număr incorect, precum şi corectura lui. Comparîndu-l cu numărul corect vom găsi două cifre care diferă. Ele sînt cifrele cu pricina, pe care le vom afişa. Dacă nu găsim nici un număr incorect înseamnă că nu avem cifre diferite şi vom afişa două zerouri.

Problema piramide

Problema piramide a fost dată la OJI 2014, clasa a 5a.

Problema descrie alcătuirea unor piramide şi cere date despre aceste piramide. Să luăm pe rînd cerinţele.

Punctul a) - piramida care îl conţine pe x

Dat un număr de cartonaş, x, se cere numărul piramidei ce conţine acel cartonaş. Pentru a rezolva acest punct vom calcula, pe rînd, numărul de cartonaşe din fiecare piramidă. Atunci cînd suma acestor cartonaşe depăşeşte x am găsit piramida care îl conţine. Cum calculăm numărul de cartonaşe din piramida curentă? Observăm că ea diferă de cea din-nainte doar prin baza sa, care se adaugă. Vom avea deci un contor, baza, care creşte cu unu la fiecare piramidă. Vom avea, de asemenea, un număr de cartonaşe în piramida curentă, cartp, căruia îi vom aduna baza la fiecare piramidă nouă. De asemenea vom avea grijă să adunăm cartp, cartonaşele fiecărei piramide, la o sumă totală, care ne va spune cîte cartonaşe am folosit pînă acum.

Pe măsură ce adunăm cartonaşe la sumă ne întrebăm dacă suma a depăşit x. Dacă da, am descoperit piramida care îl conţine!

Punctul b) - numărul de piramide complete, m

Acest punct se rezolvă similar. Vom adăuga piramida curentă la sumă doar dacă suma nu va depăşi n. Astfel vom afla cîte piramide am adăugat, folosind un contor m.

Punctul c) - numărul de cartonaşe nefolosite

Acest punct este banal. El este, desigur, n-suma.

Punctul d) - piramida cu număr maxim de cartonaşe albe

Acest punct este cel mai greu. Va trebui ca, pe măsură ce adăugăm piramide la sumă, să citim cartonaşe şi să vedem cîte fac parte din piramida adăugată. Pentru aceasta vom citi cartonaşe cîtă vreme ele sînt mai mici sau egale cu ultimul cartonaş din piramida curentă. Atenţie! Aceasta înseamnă că ultimul cartonaş citit va fi strict mai mare decît ultimul cartonaş din piramida curentă.

Dar dacă nu avem un astfel de cartonaş? Am putea să facem teste suplimentare, care ne vor complica programul. Sau, am putea să adăugăm la final un cartonaş fictiv care are un număr foarte mare. El nu va fi niciodata selectat în piramidă, dar ne va opri citirea de cartonaşe albe suplimentare. Astfel, avem un al k+1-lea cartonaş alb fictiv.

Temă

Tema 27 clasa a 5a, problemele date anul trecut la OJI 2014.

Rezolvări aici [2]