Solutii Grigore Moisil 2008

• Lista de probleme
• Joc8
• Patrat
• Fibo

Joc8

Din descrierea jocului se desprinde algoritmul cautarii binare, algoritm care nu trebuia sa fie cunoscut de concurenti, deoarece este descris in enunt. Singurele dificultati constau in intelegerea si implementarea modelului descris.

Citeste x,y
  gasit = fals
  cat timp nu gasit si (x <= y) executa:
    z = (x + y) div 2
    Citeste: raspuns
    Daca raspuns = 1 atunci
      gasit = adevarat
    altfel
      Citeste: raspuns
      Daca raspuns = 1 atunci
        y = z - 1
      altfel
        x = z + 1
      Sfarsit(Daca)
    Sfarsit(Daca)
  Sfarsit(Cat timp)
  Daca gasit atunci
    Scrie: z
  altfel
    Scrie: 0
  Sfarsit(Daca)
Sfarsit(Algoritm)

Patrat

Problema se rezolva simplu daca construim vectorul ok, unde ok_i va fi true daca si numai daca i respecta proprietatile din enunt. Pentru a construi acest vector putem proceda astfel:

pentru i = 1, 20000
     ok[i] = false
pentru i = 1, [radical(20000)]
    pentru j = i+1, [radical(20000)]
        daca i * i + j * j <= 20000
            ok[i * i + j * j] = true

Pentru a afisa toate numerele intre x si y ce se pot scrie ca suma de patrate este suficient sa iteram un i intre cele doua margini si sa afisam acele valori care indeplinesc ok_i = true.

Fibo

Problema poate fi abordata in mai multe feluri:

• Luam in considerare pe rand toate numerele mai mici sau egale cu numarul dat N si generam reprezentarea lor in sistemul Fibonacci. Apoi verificam sirul de caractere pentru a stabili daca este sau nu palindrom.
• Este posibil sa abordam problema si invers, adica sa generam sirul de caractere palindrom formate din cifre 1 si 0. Lungimea sirului de caractere va fi egala cu lungimea sirului Fibonacci continand numere mai mici sau egale cu n. Cum al 30-lea termen fibonacci depaseste 10⁶ avem cel mult 2¹⁶ posibilitati de a genera palindroame.