Question

Într-un arbore cu rădăcină avem 2021 noduri. Fiecare nivel are un număr pătrat perfect de noduri. Toate frunzele sunt pe același nivel. Care este numărul minim de niveluri pentru a distribui toate cele 2021 de noduri ale arborelui?
Multumesc anticipat!

Answer 1

In arbore avem 3 niveluri:

• Primul nivel contine radacina (1 nod)
• Al doilea nivel contine 256 noduri (16^2)
• Al treilea nivel contine 1764 noduri (42^2)

Pe primul nivel avem radacina, iar pe urmatoarele k-1 niveluri avem un numar patrat perfect de noduri. Deci avem $1 + n_1 +n_2+...+n_k= 2021$, unde $n_k$ reprezinta numarul de noduri de pe nivelul k.

Ar mai trebui ca $n_i \leq n_j, \forall i < j$ (fiecare nivel sa aiba cel putin atatea noduri cate are nivelul anterior, dar acest lucru nu e important).

Putem duce acel 1 in partea cealalta si obtinem:

$\sum_{i=1}^{k}\ n_i =2020$, iar fiecare $n_i$ este un patrat perfect

Pentru ca numarul de niveluri sa fie minim trebuie ca k sa fie cat mai mic. Deci este evident ca putem rezolva o problema echivalenta:

Sa se scrie 2020 ca o suma de patrate perfecte cu un numar minim de termeni.

Putem sa incercam babeste sa ghicim valorile sau putem scrie un program care sa ne ajute.

In programul de mai jos am folosit tehnica programarii dinamice in care am determinat suma de patrate perfecte cu numar de termeni minim pentru i folosindu-ne de rezultatele pentru numerele anterioare memorate in tabela de memoizare listOfSquaresRequired , abordare bottom-up.

Daca $i = j+k$ si putem scrie j si k ca

• $j= a_1 +a_2+...a_n$
• $k = b_1 +b_2+...b_m$

atunci $i = a_1 +a_2+...a_n + b_1 +=b_2+...a_m$.

In cazul nostru $a_i$ si $b_i$ sunt patrate perfecte si incercam sa determinam suma de termeni astfel incat n+m sa aiba cea mai mica valoare posibila.

Este evident faptul ca orice numar n poate fi scris ca 1+1+1+...+1, (iar 1 este patrat perfect) deci orice numar poate fi scris ca suma de n numere patrate perfecte.

Dupa rularea programului de mai jos obtinem rezultatul:

256 1764

Numere care reprezinta numarul de frunze de pe nivelul II si III.

► Rezolvare C++:

#include <iostream>

#include <vector>

//Functie care returneaza un vector ce contine numerele patrate perfecte pana la n

std::vector<int> getPerfectSquaresUpTo(int n)

{

std::vector<int> solution;

for (int i = 0; i<=sqrtl(n); ++i)

 solution.push_back(i * i);

return  solution;

}

std::vector<int> determineSum(int n)

{

//Determina patratele perfecte pana la n

const auto perfectSquares = getPerfectSquaresUpTo(n);

//Creeaza vectorul de patrate perfecte necesare pentru a forma fiecare numar.

std::vector<std::vector<int>> listOfSquaresRequired(n + 1);

//Pentru fiecare patrat perfect numarul de patrate perfecte e 1.

for (const auto& square : perfectSquares)

 listOfSquaresRequired[square] = {square};

for(int i=1; i<=n; i++)

{

 //Daca numarul e patrat perfect treci mai departe

 if (listOfSquaresRequired[i].size() == 1) continue;

 //Orice numar i poate fi scris ca 1+1+1+...+1 de i ori

 int currentMinimum = i;

 //Incercam sa scriem i ca j + k

 for(int j=1; j<i; j++)

 {

  int k = i-j;

  //Daca j poate fi scris ca nj si k poate fi scris ca suma de nk p.p. atunci ni = nj + nk

  int nj = listOfSquaresRequired[j].size();

  int nk = listOfSquaresRequired[k].size();

  int ni = nj + nk;

  //Verificam daca valoarea gasita e minima

  if (currentMinimum > ni) {

   currentMinimum = ni;

   //Salvam valoarea minima gasita

   listOfSquaresRequired[i] = listOfSquaresRequired[j];

   std::copy(listOfSquaresRequired[k].begin(), listOfSquaresRequired[k].end(), std::back_inserter(listOfSquaresRequired[i]));

  }

 }

 //Daca suntem tot la currentMinimum initial introdu i de 1

 if(currentMinimum == i)

  listOfSquaresRequired[i] = std::vector<int>(i, 1);

}

//Returnam numarul de patrate perfecte gasite pentru valoarea ceruta.

return listOfSquaresRequired[n];

}

int main()

{

auto result = determineSum(2020);

//Afiseaza fiecare element din suma

for (auto& element : result)

 std::cout << element << " ";

}