Dacă aș avea mai mult timp,
Aș scrie mai scurt ...
Blaise Pascal
Nu este un secret faptul că, în comparație cu alte discipline ale cursului școlar, informatica Olimpiadă are o serie de caracteristici. Și anume:
- sarcinile în informatică se află la intersecția mai multor discipline;
- elevii de diferite vârste rezolvă aceleași sarcini;
- cunoașterea cognitivă a limbajului de programare nu este o garanție a performanței de succes (chiar și la Olimpiada de nivel municipal).
Toate aceste aspecte ar trebui să fie luate în considerare de către profesor atunci când pregătesc studenții pentru concursurile de olimpiadă.
În acest articol vom vorbi despre sistemul de pregătire a elevilor școlari de clasele 7-8 pentru un discurs la Olimpiada de Informatică. De unde să încep? La ce să mă concentrez atunci când lucrez cu elevii din clasele a VII-a și a VIII-a, pentru ca ei să-și poată începe cu discurs la Olimpiada de Informatică? După cum se știe, primul succes este o motivație puternică pentru a ajuta elevii să nu pentru a opri calea de programare, pune un fundament bun, care, în viitor, va fi posibil să aducă câștigătorii tuturor etapelor olimpiadei All-rus la informatică.
Deci, pregătirea olimpiadei studenților de clasa a VII-a are ca scop realizarea lor la Olimpiada de nivel municipal. Clasa problemelor de Olimpiada de acest nivel are propriile sale specificități. Nu este necesar să stăpânești tehnica de programare în oricare dintre limbile. Sarcinile olimpiadei sunt proiectate astfel încât principala parte să găsească ideea originală a soluției și, din punct de vedere tehnic, astfel de probleme sunt rezolvate pur și simplu (algoritm liniar sau bucle imbricate), chiar fără a folosi matricea. Această idee de bază se aplică la etapa inițială de pregătire a studenților de la gimnaziu.
Scena principală este dezvoltarea logicii. (Apendicele 1)
În această etapă, consider că soluția unui număr mare de probleme logice interesante este o prioritate. Sarcinile logice sunt foarte populare la studenții de această vârstă, cu condiția ca fiecare dintre ei profesorul va încerca să pună sub forma oricărui ajutor de joc interactiv. Desigur, acest lucru necesită mult timp pentru profesorul însuși, dar totuși această lucrare trebuie făcută pentru a crește interesul elevilor. Atunci când sarcina vine la viață și se transformă într-un joc de computer captivant, nu puteți numi matematica plictisitoare. Astfel, sarcina profesorului în această etapă este de a împacheta cunoștințele într-o formă interesantă și relevantă pentru copiii moderni. Desigur, sarcinile nu sunt alese din întâmplare, fiecare ar trebui să ascundă unul dintre algoritmii de programare olimpiade de bază pe care profesorul și-a planificat să le studieze într-o anumită lecție. Voi da un exemplu de fragment dintr-o astfel de lecție folosind jocul logic "Vizitând Lewis Carroll".
Fragmentul lecției: "Numerele Fibonacci. Programare dinamică »
Mergând după iepurele alb și Alice, ajungem în zona de minuni, unde, ca o încălzire, vom trece un mic test logic interactiv, bazat pe cartea lui Lewis Carroll "The Story with Nodules". Așa cum am menționat deja, cea mai importantă abilitate a acestei etape este dezvoltarea abilității de a gândi în afara casetei, a scăpa de orice stereotip, și cine altcineva decât acest scriitor, matematician, logician și filosof ne va ajuta în acest sens.
Există zece saci de monede de aur, în fiecare pungă sunt 10 monede. Toate monedele cântăresc 10 grame. Un sac de zece cu monede contrafăcute. Monetele contrafăcute cântăresc 11 grame. Cum într-o singură cântărire pe cântare cu săgeți pentru a determina sacul cu monede fals?
După încălzirea, care include soluția la o sarcină logică homosexuală (Anexa 2), ajungem în cele din urmă la tema lecției noastre: "NUMBERING NUMBERING OF FIBONACCI"
Scop: Explicați metoda de programare dinamică folosind un exemplu de problemă cunoscută anterior. Găsiți cea mai bună modalitate de ao rezolva, evaluați viteza diferitelor metode de soluționare. (Apendicele 1)
Răspuns: 377 de perechi. În prima lună de iepuri vor exista deja două perechi: o pereche inițială care a dat un pui și un cuplu născut. În cea de-a doua lună de iepuri vor fi 3 perechi: 1 original, dând din nou un descendent, 1 crescător și 1 născut. În a treia lună - 5 perechi: 2 perechi, dând un copil, 1 crescând și 2 născuți. Continuând examinarea pe luni, puteți stabili o legătură între numărul de iepuri din luna curentă și cei doi anteriori. Dacă numărăm numărul de perechi cu N și cu m este numărul de serie al lunii, atunci Nm = Nm-1 + Nm-2. Folosind această expresie, calculați numărul de iepuri pe lună a anului: 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377.
Această sarcină a fost inventată de omul de știință italian Fibonacci, care a trăit în secolul al XIII-lea.
Calculati numărul N-lea din sirul lui Fibonacci, - 1, 1, 2, 3, 5, 8 - în care primii doi termeni sunt egali cu unul, iar toate celelalte sunt suma celor două anterioare.
Formatul de intrare
Numărul unic 0 Formatul de ieșire Un număr este al doilea termen al secvenței. Amintiți-vă că scopul lecției noastre este dezasamblarea, într-un exemplu simplu și familiar, a principiului programării dinamice, dar nu găsirea soluției celei mai simple și eficiente a problemei. TS Abordarea este importantă pentru noi. Noi scriem o funcție recursivă în forma următoare: dacă (X = 1) sau (X = 2) În acest caz, în jurul celui de-al patrulea deceniu, programul "atârnă" cel mai rapid computer, în timp ce, conform regulilor olimpiadei, durează rareori mai mult de 10 secunde pentru a trece testul. Elevii sunt rugați să răspundă la întrebarea, de ce se întâmplă acest lucru? Odată ce aflăm că principala noastră greșeală este că valoarea funcției la aceeași valoare a argumentului este considerat a fi atât de multe ori, se propune să rescrie această funcție cu utilizarea de matrice pentru a face mult mai eficient, eliminând dubla contabilizare a acestora valori. Var D. Array [1..50] din LongInt; Din nou, legea de aur a programării funcționează - câștigând în viteză, pierzând în memorie. În primul rând, matricea este umplută cu valori care evident nu pot fi valorile funcției noastre (permiteți-le să fie zero). Când încercați să calculați o valoare, programul analizează dacă a fost evaluat anterior și, dacă da, ia rezultatul finalizat. Funcția are următoarea formă. Funcția F (X. Integer). LongInt; dacă D [X] = 0 Să simplificăm și această decizie, după ce am scăpat de recursivitate în general: Pentru i: = 3 la X face D [i]: = D [i-1] + D [i-2]; Această metodă este de câteva ori mai rapidă decât cele precedente. Deci, metoda de programare dinamică ajută adesea la rezolvarea eficientă a unei probleme, un algoritm exhaustiv pentru care ar necesita timp exponențial. Ideea metodei este de a reduce problema inițială la rezolvarea unor submăsuri cu o dimensiune mai mică și a folosi tehnici tabulare pentru a stoca răspunsurile deja găsite. Soluția de sub-sarcini în acest caz are loc în ordinea cresterii dimensiunii lor - de la mai mică la cea mai mare. Avantajul programării dinamice este că orice subtasc este rezolvat o dată, soluția sa este salvată și nu este recalculată niciodată. Și, desigur, este foarte important în fiecare lecție pentru a arăta că există mai multe moduri de a rezolva o problemă, și să știți despre existența unei metode sofisticate, programul secret faptul că există întotdeauna o modalitate alternativă de a rezolva chiar si sarcina cea mai dificilă este important doar să fie persistente. Și chiar și în clasa a 7-a, fără să știe absolut nimic despre programarea dinamică, sarcina clasică a acestei metode poate fi rezolvată de mai mulți operatori de buclă imbricată sau de o anumită formulă. De exemplu, problema de a număra numărul de triunghiuri echilaterale, atunci când intrarea programului este dată numărului de nivele din figura (1 ≤ N ≤ 105). Figura arată o cifră formată din 4 nivele de triunghiuri.
apoi F: = 1
altfel F: = F (X - 1) + F (X - 2)
atunci
dacă (X = 1) sau (X = 2)
apoi D [X]: = 1
altfel D [X]: = F (x - 1) + F (x - 2);
F: = D [X]
Iată două exemple:
Exemplul 1 (limbaj de programare Delphi (Pascal)):
readln (n);
k: = n * n;
dacă n> 1 atunci
pentru i: = 2 până la n
pentru j: = i la n
dacă j<2*i then k:=k+j-i+1
altfel k: = k + 2 * j-3 * i + 2;
scriteln (k);
Exemplul 2 (limbaj de programare Delphi (Pascal)):
O sarcină complexă este rezolvată foarte simplu: fără a folosi metode speciale, adică există întotdeauna un mod alternativ! După cum bine-cunoscutul matematician D.Poya a spus: "Nu faceți mai mult decât ceea ce se poate face cu ajutorul celui mai mic."
Astăzi, tehnologiile informaționale vizează simplificarea și facilitarea utilizării tuturor produselor software, în timp ce olimpiada informatică are drept scop predarea copiilor să gândească și să rezolve nu sarcini simple. Prin urmare, acordând o atenție deosebită pregătirii olimpiadelor, păstrăm tradițiile informaticii clasice la nivel de profil.
Articole similare
Trimiteți-le prietenilor: