Clasa a V-a lecția 3 - 8 sep 2017

From Algopedia
Jump to navigationJump to search

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:

, adică

Ce valoare va avea ? O valoare cuprinsă între și , deoarece:

Dar, deoarece în schemă logică operatorul calculează partea întreagă a radicalului, rezultă că acel radical este chiar egal cu :

, adică

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]