Probleme de Matematica Rezolvate Algoritmic [PDF]

Zitiervorschau

Rezolvăm probleme de matematică... folosind calculatorul Titlul articolului de față poate induce în eroare. Există multe probleme interesante în care calculatorul își dovedește utilitatea. Cele pe care dorim însă să le exemplificăm aici reprezintă situații în care folosirea unui algoritm de rezolvare - și rularea acestuia într-un mediu de dezvoltare (am ales Eclipse și limbajul Java) – se dovedesc imperios necesare (deși la o primă vedere nu s-ar părea). Înainte de toate, enunțurile problemelor. P1. Câte numere naturale de cinci cifre au suma cifrelor cel mult egală cu 10 ? (Culegere pt. clasa a IV-a, Gardin-Berechet, Ed. Paralela 45, 2009, pag. 23) P2. Determinaţi numerele naturale număr natural, astfel încât

a0 , a1 , a2 ,..., a8 , elemente ale mulţimii {0,1, 2,3, 4} şi x

a0 ≠ 0 şi

a0 x8 + a1 x 7 + a2 x 6 + a3 x5 + a4 x 4 + a5 x3 + a6 x 2 + a7 x1 + a8 x 0 = 2012 (Ion Safta, E:14409, G.M.B. 11/2012) P3. Să se determine mulțimile nevide A și B de numere naturale, care satisfac simultan condițiile : i.

A ∩ B = {2}

ii. Cel mai mare element al mulțimii A ∪ B este cel mult egal cu 6; iii. Pentru orice a ∈ A există b ∈ B astfel încât a + b este pătrat perfect; iv. Pentru orice b ∈ B există a ∈ A astfel încât b − a este pătrat perfect. (Adriana și Lucian Dragomir, E:13746, G.M.B. 12/2008; culegere Mate-2000 Consolidare, clasa a V-a, partea I, ediția a II-a, Ed. Paralela 45, 2013, pag. 158) Problema P1 Se observă repede că suma cifrelor unui număr n de cinci cifre ia valori cuprinse între 1 (în cazul singular al numărului 10000) și 45 (pentru n = 99999 ). Căutând o regulă după care să formăm numere de cinci cifre având suma cifrelor 2, 3, 4, ..., ajungem repede la o analiză complicată. Pentru suma cifrelor 2, avem tuplurile

( 2, 0, 0, 0, 0 )

și

(1,1, 0,0, 0 ) .

corespunde doar numărul 20000, cel de-al doilea generează soluțiile

Primului tuplu îi

10001, 10010, 10100 și

11000 . Sunt în total cinci numere de cinci cifre cu suma cifrelor 2. Suma cifrelor 3 este produsă de tuplurile ( 3, 0, 0, 0, 0 ) , ( 2,1, 0, 0, 0 ) și (1,1,1, 0, 0 ) . Primul tuplu corespunde doar lui 30000, al doilea generează 10002, 10020, 10200, 12000, 20001, 20010, 20100 și 21000 , iar al treilea produce soluțiile 10011, 10101, 10110, 11001, 11010 și 11100 . Cu suma cifrelor 3 avem 1 + 8 + 6 = 15 numere de cinci cifre. Tuplurile de 5 cifre cu suma 4 sunt ( 4, 0, 0, 0, 0 ) , ( 3,1, 0, 0, 0 ) , ( 2, 2, 0,0, 0 ) , ( 2,1,1, 0, 0 ) și

(1,1,1,1, 0 ) .

Lor le corespund soluțiile:

40000, 10003, 10030, 10300, 13000, 30001, 30010, 30100, 31000, 20002, 20020, 20200, 22000,10012, 10021, 10102, 10120, 10201, 10210, 11002, 11020, 11200, 12001, 12010, 12100, 20011, 20101, 20110, 21001, 21010, 21100, 10111, 11011, 11101 și 11110 . În total, sunt 1 + 8 + 4 + 18 + 4 = 35 de numere de 5 cifre cu suma cifrelor egală cu 4. Dacă nu v-a ajuns (mie mi-a ajuns cu vârf și îndesat), luați și tuplurile cu sumă 5 :

( 5, 0,0, 0, 0 ) , ( 4,1, 0, 0, 0 ) , ( 3, 2, 0, 0, 0 ) , ( 3,1,1,0, 0 ) , ( 2, 2,1, 0,0 ) , ( 2,1,1,1, 0 )

și

(1,1,1,1,1) .

Acestea trebuie să producă 70 de numere de cinci cifre cu suma egală cu 5. Răbdare și tutun, eu pe prima am isprăvit-o, iar al doilea nu m-a pasionat nicicând. E clar că nu e rezonabil să producem toate numerele de cinci cifre având suma cifrelor cel mult egală cu 10 pentru a le număra ulterior. Posibil să fie vreun algoritm mai ”smart” de numărare, dar cel puțin la o primă vedere un astfel de algoritm nu este la îndemână. În pană de idei, apelăm la prietenul (și totodată inamicul) omului modern, computerul. Presupunem o minimală cunoaștere a unui limbaj de programare; codul Java care urmează (cât și cel de la problema P2) poate fi cu ușurință rescris în C. public class SfCalculator { protected static int sumOfFigures(int n) { int sum = 0, r = 0; do { r = n % 10; sum += r; n = n/10; } while (n != 0); return sum; } public static void main(String[] args) { int ns; for (int k = 1; k