Selezione Scolastica – 23 febbraio 2021

Aiuto
1

Qualcuno riesce a spiegare il procedimento per arrivare alla soluzione di questo esercizio della scorsa selezione scolastica 2021?

Date le seguenti funzioni:

1:  function f(x: integer) -> integer
2:      if x mod 2 = 0 then
3:          return 0
4:      else
5:          return 1 + f((x − 1) / 2)
6:      end if
7:  end function
8:  function g(x: integer) -> integer
9:      if x > 250 or x <= 0 then
10:         return 0
11:     else
12:         return max(f(x), g(x / 2))
13:     end if
14: end function

Tenendo conto che la divisione restituisce un risultato intero (quindi, ad esempio, sia 4/2 che 5/2 restituiscono 2), qual è il massimo x tale per cui g(x) = 1?

2

Innanzitutto possiamo assumere che il valore x sia compreso tra 1 e 250, altrimenti g(x) = 0.

Osserviamo che g(x) \ge 1 per ogni x, infatti g(x) chiama ricorsivamente g\left(\left\lfloor\frac{x}{2}\right\rfloor\right) fino a quando x = 1 e possiamo verificare facilmente che g(1) = f(1) = 1.

Ne consegue quindi che g(x) è uguale a 1 quando f(x) \le 1 e g\left(\left\lfloor\frac{x}{2}\right\rfloor\right) = 1, cerchiamo dunque un valore x tale che \max \left\{f(x), f\left(\left\lfloor\frac{x}{2}\right\rfloor\right), f\left(\left\lfloor\frac{x}{4}\right\rfloor\right), \ldots, f\left(1\right)\right\} = 1.

Notiamo che f(x)\le 1 se è solo se:

  • x è pari e quindi il bit meno significativo di x è 0; oppure
  • x è dispari e \left\lfloor\frac{x - 1}{2}\right\rfloor è pari.

Analizziamo la seconda condizione:

  • \left\lfloor\frac{x - 1}{2}\right\rfloor è pari se e solo se il secondo bit meno significativo di x - 1 è 0;
  • il secondo bit di x - 1 è 0 se e solo se gli ultimi due bit di x sono 10 oppure 01.

Ne deduciamo quindi che se g(x) = 1 allora x non può avere due bit consecutivi uguali a 1, il valore massimo di x è perciò 10101010_2 = 170_{10}.

2 Mi Piace