Difference between revisions of "Clasa a V-a lecția 3 - 8 sep 2017"

From Algopedia
Jump to: navigation, search
 
Line 1: Line 1:
 
= Tema - rezolvări =
 
= Tema - rezolvări =
 
* Puzzle: ce urmează în secvență: [[Image:puzzle-nasa.gif|frame|none|Ce simbol urmează în secvența?]] '''Răspuns''': în secvență urmează: [[Image:puzzle-nasa-rezolvare.gif|frame|none|Rezolvare ultima figură din secvență]] Explicaţie: jumătatea din dreapta numără de la 0 la 8 din 2 în 2. Recomandare: instalați '''gbrainy''' pentru mai multe puzzle-uri (căutați pe google).
 
* Sînt 10 oameni numerotați de la 1 la 10. Omul cu numărul 1 spune "fix unul dintre noi minte". Omul cu numărul 2 spune "fix doi dintre noi mințim". Și așa mai departe, al nouălea om spune "fix nouă dintre noi mințim", iar al zecelea susține că "toți mințim". Cine minte și cine spune adevărul?<br/><br/>'''Răspuns''': remarcăm că maxim unul dintre ei spune adevărul, căci dacă ar spune doi cele două afirmaţii ar fi contradictorii. Rămîn două variante: un om spune adevărul, sau nici unul. Dacă nici unul nu ar spune adevărul ar rezulta că omul 10 spune adevărul, deci nu se poate. Dacă unul singur spune adevărul rezultă că omul nouă este singurul care are dreptate. Aceasta este şi soluţia finală.
 
* Puzzle: vine fluxul, urcă trei sferturi de metru pe sfert de oră. Vaporul are 3 metri jumate de la apă pînă sus la buză. În cît timp se va revărsa apa în vapor?<br/><br/>'''Răspuns''': apa nu se va revărsa niciodată în vapor deoarece vaporul se ridică odată cu apa. A fost o întrebare capcană.
 
* Schemă logică: să se spună dacă un număr n are ultimele două cifre consecutive, în ordine crescătoare. Exemple: 312, 4523 și 1 sînt numere care au ultimele două cifre consecutive. 215, 4321 și 7 nu au ultimele două cifre consecutive crescător.<br/><br/>'''Răspuns''': [[Image:cifre-consecutive.gif|frame|none|Să se spună dacă un număr are ultimele două cifre consecutive]]
 
* Schemă logică: să se spună dacă n copii se pot așeza în formă de pătrat plin. Exemple:
 
** Nouă copii se pot așeza în formă de pătrat astfel: [[Image:copii-9-in-patrat.gif|frame|none|Nouă copii așezați în formă de pătrat]]
 
** 14 copii nu se pot așeza în formă de pătrat: [[Image:copii-14-in-patrat.gif|frame|none|14 copii]]<br/><br/>'''Răspuns''': [[Image:copii-in-patrat-2.gif|frame|none|Să se spună dacă n copii se pot așeza în formă de pătrat plin]]
 
  
 
Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_V-a_lec%C8%9Bia_2_-_5_sep_2017]
 
Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_V-a_lec%C8%9Bia_2_-_5_sep_2017]

Latest revision as of 11:56, 13 September 2019

Tema - rezolvări

Rezolvări aici [1]

Lecție

Video al lecției 3.

Exerciții cu structura liniară și alternativă

Strîngeri de mînă

Exercițiu de încălzire: un grup de oameni își strîng mîna fiecare cu fiecare. În total sînt 21 de strîngeri de mînă. Cîţi oameni sînt?

Algoritm: avem n oameni care dau mîna fiecare cu fiecare o singură dată. În total sînt k strîngeri de mînă. Să se scrie o schemă logică care citește k (numărul de strîngeri de mînă), apoi calculează și afișează n (numărul de oameni).

Răspuns: vom folosi matematică (informatica la nivel înalt are nevoie de matematică, aviz amatorilor). Dacă avem n oameni atunci numărul de strîngeri de mînă va fi:

k=n\cdot (n-1):2, adică
2\cdot k=n\cdot (n-1)

Ce valoare va avea {\sqrt  {2\cdot k}}? O valoare cuprinsă între n-1 și n, deoarece:

{\sqrt  {2\cdot k}}\cdot {\sqrt  {2\cdot k}}=n\cdot (n-1)

Dar, deoarece în schemă logică operatorul {\sqrt  {~~}} calculează partea întreagă a radicalului, rezultă că acel radical este chiar egal cu n-1:

{\sqrt  {2\cdot k}}=n-1, adică
n=1+{\sqrt  {2\cdot k}}

Algoritmul care rezultă va fi foarte simplu:

n oameni dau mîna. Sînt k strîngeri de mînă. Dîndu-se k să se calculeze n.

Concluzie: matematica duce la algoritmi mult mai eficienți și mai simpli!

Maximul a trei numere

Se citesc trei numere, a, b și c. Să se afișeze valoarea maximă.

Iată două posibile soluții:

maximul a trei numere, varianta 1
maximul a trei numere, varianta 2

Care din ele este mai bună? Ele sunt aproximativ la fel, cu o diferență: dacă am dori să calculăm maximul a patru sau cinci numere prima schemă logică se dublează pentru fiecare număr în plus. Cea de-a doua adaugă doar o comparație, deci este mai bună.

Cifre impare

Se citește un număr n. Se știe că 1 ≤ n < 100. Să se spună dacă toate cifrele lui n sînt impare.

Iată două posibile soluții:

Toate cifrele lui n sînt impare, varianta 1
Toate cifrele lui n sînt impare, varianta 2

Care din ele este mai bună? Din nou, cele două scheme logice par apropiate, dar atunci cînd n crește (cînd numărul lui de cifre este mai mare), prima schemă logică se dublează cu fiecare cifră în plus, pe cînd cea de-a doua adaugă o singură structură alternativă, deci a doua schemă logică este mai bună.

Divizibilitate

Se citesc trei numere naturale, a, b și k. Să se afișeze numărul de numere divizibile cu k în intervalul [a, b] (inclusiv a și b).

Am putea fi tentați aici să scriem un algoritm rapid:

  • Fie să considerăm că numărul de numere divizibile cu k în intervalul [a, b] este, în principiu, (b - a + 1) / k (deoarece numărul de numere din intervalul [a, b] este b - a + 1). Dar avem excepții, cînd trebuie să adunăm unu, excepții care trebuie tratate cu decizii care nu sînt tocmai simple.
  • Fie să considerăm că numărul de numere este, în principiu, b/k - a/k. Dar atunci cînd a este divizibil cu k trebuie să adunăm unu.

Probabil mai sunt și alte variante. Vom prezenta în continuare o variantă optimă, care nu folosește condiții.

Răspuns: să rezolvăm mai întîi o problemă mai simplă: cîte numere sunt divizibile cu k în intervalul (0, x]? Aici răspunsul este simplu, vom avea exact x/k numere divizibile cu k. Ei bine, numărul de numere divizibile cu k din intervalul [a, b] este totuna cu numărul de numere din intervalul (0, b] din care scădem numărul de numere din intervalul (0, a-1]! Obținem formula:

n = b/k - (a-1)/k

Iar algoritmul devine banal:

Cîte numere divizibile cu k se află în intervalul [a, b]?

Rețineți această tehnică, de a descompune un interval în diferență de două intervale. O vom mai folosi. Această tehnică reduce problema inițială la o subproblemă mai simplă.

Intrebare: Există cazuri cînd algoritmul nu funcționează?

Tema

  • Te afli într-o încăpere goală. Ai în mînă un pahar cilindric și transparent care conține apă. Nu poți să acoperi gura paharului cu mîna, deoarece este prea largă. Cum afli dacă paharul este fix jumate plin?
  • Cîte cubuleţe sînt necesare pentru a construi cubul din figură:
    Cîte cubulețe conține acest cub?
  • Scrieți o schemă logică care să determine dacă un an este bisect. Un an este bisect dacă este divizibil cu 4, cu excepția anilor divizibili cu 100, care nu sînt bisecți, cu excepția anilor divizibili cu 400 care sînt bisecți. Exemple: 2012 este an bisect, 1900 nu a fost an bisect, 2000 a fost an bisect.
  • Se citesc trei numere, a, b și c. Să se afișeze în ordine crescătoare. Exemplu: dacă a = 8, b = 4, c = 12, se va afișa 4 8 12.

Rezolvări aici [2]