 BluePink XHost |
Gazduire site-uri web nelimitata ca spatiu si trafic lunar la doar 15 eur / an. Inregistrare domenii .ro .com .net .org .info .biz .com.ro .org.ro la preturi preferentiale. Pentru oferta detaliata accesati site-ul BluePink |
|
BluePink XHost |
Gazduire site-uri web nelimitata ca spatiu si trafic lunar la doar 15 eur / an. Inregistrare domenii .ro .com .net .org .info .biz .com.ro .org.ro la preturi preferentiale. Pentru oferta detaliata accesati site-ul BluePink |
Disciplina şcolara (din catalog) = Programare
(Informatică), NU TIC !
SCOPUL (ţinta programării în liceu) NU ESTE
(numai) SĂ MEMOREZI (informaţia) CI SĂ ÎNŢELEGI CEEA CE AI
IN FAŢĂ (obiecte) ŞI SĂ POŢI FOLOSI (să-ţi
fie util) + să îţi funcţioneze mintea - să gândeşti!!!
(un algoritm) după un plan şi să poţi să îţi
înbunătăţeşti "performanţele" => (“tot omul“, adică tu) să ai un
portofoliu (o bază) peste care să poţi să aduni! (să
construieşti)
Cuprinsul (sumarul) lecţiei (pt.2ore la X C)
task 1: Înmulţirea pe caiet a
două numere
task 2: Rezolvarea problemei 1
task 2.1
Enunţ problema 1 (Identificarea monedei mai uşoare)
task 2.2 Exemple de rezolvări pe date de test
task 2.2.1 set
1 (de) date de test:
task 2.2.2 set
2 (date de test)
task 2.3 Algoritmul pentru metoda 1
task 2.4 “Tema de casă” : elevul va
rezolva (exersa) singur
task 3: Problema “cu monezile” - a
doua metodă
task 3.1
Algoritmul, numit în continuare "maxim n/2 comparaţii"
pt.problema “cu monezile”
task 3.2 Exemple de rezolvări pe date de test
(a doua metodă)
task 3.2.1 set
1 (de) date de test:
task 3.2.2 set 2 (de) date de test:
task 3.2.3 set 3 (de) date de test:
task 3.3 “Tema de casa” : elevul va rezolva
(exersa) singur
task 4: Problema
„cu monezile” - a treia metoda
task 4.2 Exemple de rezolvari pe date de test (a
treia metoda)
task 4.3 (optional) ("exercitiu" de
gandire logico-matematica)
task 5:
Rezolvarea problemei 2
task 6: Rezolvarea problemei 3
Enuntul “îmbrăcat” al problemei :
Enuntul “dezbracat” al problemei (adica
enuntul “matematic, informatic, abstract” al problemei):
Algoritmul (metoda de rezolvare):
Efectuează
înmulţirea 123 x 423 în CAIET, FĂRĂ calculator!!! (trebuie să
gândim!!! singuri!!!) - când ai terminat, poţi să te verifici cu
calculatorul!!!
Denumirea problemei: “Identificarea
monedei mai uşoare”-
UVT.RO_dzah_S1_4
Elevul va citi şi va studia
"teoria"-explicaţiile şi va întelege modul de rezolvare (se dă enunţul problemei = task 2.1, sunt date
exemple de rezolvări pe date de test =task 2.2, se dă algoritmul
(metoda) de rezolvare = task 2.3; se cere să rezolve elevul problema
pentru alte date de test = task 2.4)
Se consideră un set de n monede identice, cu
excepţia uneia care are greutatea mai mică decât celelalte. Folosind
o balanţă simplă să se identifice moneda cu greutatea mai
mică folosind cât mai puţine comparaţii.
n=8; moneda (k=) a
3-a este mai uşoară
rezolvare
metoda 1: compar moneda 1 cu moneda 2, balanţa arată egalitate =>
am făcut o cântărire (şi va trebui să continui)
compar
moneda 1 cu moneda 3, balanţa arată talerul drept mai uşor =>
am găsit a două monedă mai uşoară, din 2
cântăriri
n=6, k=5 (alte date
de test!, NU au nici o legătura cu primul set de date de test, cu n=8
şi k=3)
rez.met.1: compar m1 cu m2, sunt egale, am
făcut o cântărire
compar m1 cu m3,
sunt egale, am făcut a doua cântărire
compar m1 cu m4, =, 3
cântăriri
compar
m1 cu m5, diferă, moneda căutată este pe talerul drept, 4
cântăriri
n=15, k=8
rez.met.1: m1 cu m2,
=, 1 cântărire
m1
cu m3, =, 2 cântăriri
....
m1
cu m7, =, 6 cântăriri
m1
cu m8, diferă, 7 cântăriri, moneda căutată este a 8-a, 7
cântăriri
Se selectează la întâmplare două monede şi
se pun pe balanţă. Dacă una dintre ele are greutatea mai
mică atunci este chiar moneda căutată. Dacă ambele au
aceeaşi greutate se păstrează una dintre ele pe un taler al
balanţei iar pe celălalt taler se pun succesiv monedele rămase.
Prelucrarea se opreşte în momentul în care se găseşte o
monedă cu greutatea mai mică. Numărul de comparaţii este
cel mult n-1. (ex: 35 de monezi, şi a 35-a este mai uşoară)
=> vom numi această metoda "maxim n-1 comparaţii"
Pe baza modelului de la task 2.2 câte comparaţii se
fac dacă
set
4 (date de test): n=25, k=24
set
5: n=321, k=209
În
metoda anterioară am comparat prima monedă cu cele care urmează
dupa ea. În loc să comparăm prima monedă cu altele, vom compara
două câte două monezi succesive, până când două monezi
diferă. Când diferă, atunci cea mai uşoară este
cea căutată.
n=40; moneda (k=) a
24-a este mai uşoară (notat m24)
rez.met.2:
compar m1 cu m2, =, 1 cântărire
compar
m3 cu m4, =, 2 cântăriri
compar
m5 cu m6, =, 3 cântăriri (din 3 cântăriri am eliminat
din 40 de monezi 6 monezi)
.........
compar
m21 cu m22, =, 11 cântăriri (din 11 cântăriri am eliminat din 40 de
monezi 22 monezi)
compar
m23 cu m24, diferă, moneda căutată este pe talerul drept, 12
cântăriri (în cazul în care ar fi fost a 23-a monedă cea mai
uşoară, !sunt alte date de test!, moneda căutată ar
fi fost pe talerul stâng! => în prima metodă de rezolvare, moneda
căutata tot timpul ar fi fost pe talerul drept, excepţie cazul când
ar fi fost prima monedă mai uşoară, iar în a doua metodă când
moneda căutată are numărul de ordine par va fi pe talerul din
dreapta, iar în cazul în care are numărul de ordine impar va fi pe talerul
din stânga)
n=60, k=35
rez.met.2: compar m1 cu m2, sunt
egale, am făcut o cântărire
compar m3 cu m4,
sunt egale, am făcut a 2-a cântărire
compar m5 cu m6, =,
3cântăriri
................
compar m33 cu m34,
sunt egale, am făcut a 17-a cântărire (am eliminat dintre monedele
posibile 34 de monede!)
compar m35 cu m36,
diferă, monedă căutată este pe talerul stâng, 18 cântăriri
n=45, k=38
rez.met.2: m1 cu m2,
=, 1 cântărire
m3
cu m4, =, 2 cântăriri
....
m35
cu m36, =, 18 cântăriri
m37
cu m38, diferă, 19 cântăriri, moneda căutată este a 38-a,
19 cântăriri
Pe baza
modelului de la task 3.2 câte comparaţii se fac dacă
set 4 (date de test): n=25, k=24
set 5: n=321, k=209
Numită în continuare "împărţire în
două subseturi egale" a problemei 1:
Se împarte setul de monede în două subseturi
(fiecare va avea n/2 elemente, dacă n e par, respectiv (n-1)/2 dacă n
este impar) care se pun pe cele două talere ale balanţei. Dacă
subseturile au aceeaşi greutate (ceea ce se poate întâmpla doar daca n
este impar) atunci moneda pusa deoparte este cea căutată. În caz
contrar se aplică acelaşi procedeu subsetului de greutate mai mică
şi se continuă până se ajunge la un set de două sau trei
monede. În acest moment este suficient să se mai efectueze o singură
cântărire. Numărul de cântăriri este cel mult [log2 n].
Descarcă fişierul monezi_metoda_injumatatirii_multimii_v_0_1_3.xls
şi completează valori (testează ”explicaţiile”) stabilite
de tine.
·
În metoda a treia numărul de cântăriri este cel
mult [log2 n]. Este adevărat acest rezultat pentru cazul în care se ştie
doar că una dintre monede este diferită dar nu se ştie dacă
este mai uşoară sau mai grea decât celelalte?
·
Tema de casa pt.cei "super-deştepti-inteligenti-logici" :
(pt. "încălzire": avem 12 monezi şi 1 mai uşoară.
Din 3 cântăriri se poate afla care este mai uşoară ?) Avem
11 monezi egale şi una diferă (NU
se ştie dacă e mai uşoară sau mai grea, doar că diferă).
Din (exact) 3 cântăriri putem afla care este cea diferită? Indicaţii : se pot pune şi 4 şi 4
monezi pe taler, sau altfel (de exemplu 5 cu 5).
·
Dacă găseşti alte probleme de logică
să le aduci la şcoală (prin email, stick, …) "că să
ne batem capul", adică "să ne stoarcem creierii"
(sudoku, sah, ...).
Denumirea
problemei: “înmulţirea a două numere prin metoda a la rousse” -
UVT.RO_dzah_S1_4
task 5.1 descarcă fişierul verificare_inmultire_a_la_rousse_v_0_1_2.xls
,
task 5.2 citeşte (studiază) prima foaie de
calcul (cu numele TO DO list (rom.cerinte))
task 5.3 exersează date de test „inventate” de tine în
a doua foaie de calcul (cu numele Verificare inmultire)
task 5.4 răspunde la întrebări (dacă vrei şi
în scris pe foaie sau pe calculator) la întrebările din a treia foaie de
calcul (cu numele Intrebari pt.elevi)
Denumirea
problemei: “clătite” - UVT.RO_dzah_S1_5
La un restaurant bucătarul a pregătit
clătite pe care le-a aşezat pe un platou sub forma unei stive. Din
păcate nu toate clătitele au acelaşi diametru astfel că
stiva nu arată prea frumos. Chelnerul ia platoul şi având la
dispoziţie o spatulă reuşeşte să aranjeze cu o
singură mână clătitele astfel încât să fie în ordinea
descrescătoare a diametrelor. Cum a procedat? Descrieţi
problema într-o manieră abstractă şi propuneţi un algoritm de
rezolvare.
(problema este identică cu cea a) Ordonaţi
descrescătoar un şir de valori prin inversarea ordinii elementelor
unor subsecvenţe de la sfârşitul şirului.
Rearanjarea se face efectuând doar mişcări de
răsturnare a unui "set" de clătite dintre cele aflate în
partea de sus a stivei.
Pentru a ordona descrescător şirul (5; 3; 4; 1;
6; 2) se aplică următoarea secvenţă de prelucrări în
care subsecvenţa care se "răstoarnă" este
încadrată:
Un
alt exemplu (set) de date de test rezolvat se află în fişierul clatite_1.xls
Metoda constă în determinarea valorii maxime şi
inversarea ordinii subsecvenţei care începe cu ea pentru a fi adusă
pe ultima poziţie în şir. Se răstoarnă întregul şir,
astfel că valoarea maximă ajunge pe prima poziţie. Se
aplică aceeaşi metodă pentru subsecvenţa care începe cu al
doilea element şi se continuă până se ajunge la o
subsecvenţă constituită dintr-un singur element.
Sursa algoritmilor (şi a unor explicaţii): http://web.info.uvt.ro/~dzaharie/alg2008_seminar1.pdf