69 lines
2.9 KiB
Markdown
69 lines
2.9 KiB
Markdown
---
|
|
id: 5900f5021000cf542c510015
|
|
title: 'Problema 406: gioco degli indovinelli'
|
|
challengeType: 5
|
|
forumTopicId: 302074
|
|
dashedName: problem-406-guessing-game
|
|
---
|
|
|
|
# --description--
|
|
|
|
Stiamo cercando di trovare un numero nascosto selezionato dal set di interi {1, 2, ..., $n$} facendo domande. Per ogni numero (domanda) che chiediamo, otteniamo una di tre possibili risposte:
|
|
|
|
- "Your guess is lower than the hidden number" (il tuo numero è più piccolo del numero nascosto) (e hai una perdita di a), o
|
|
- "Your guess is higher than the hidden number" (Il tuo numero è più alto del numero nascosto) (e hai una perdita di b), o
|
|
- "Yes, that's it!" (Sì, è quello!) (e il gioco conclude).
|
|
|
|
Dati i valori di $n$, $a$, e $b$, una strategia ottimale minimizza la perdita totale per <u>il peggior caso possibile</u>.
|
|
|
|
Per esempio, se $n = 5$, $a = 2$, e $b = 3$, allora potremmo iniziare chiedendo "<strong>2</strong>" come prima domanda.
|
|
|
|
Se ci viene detto che 2 è più grande del numero nascosto, (per una perdita di $b = 3$), allora siamo sicuri che "<strong>1</strong>" è il numero nascosto (per una perdita totale di <strong><span style="color: blue;">3</span></strong>).
|
|
|
|
Se ci viene detto che 2 è più basso del numero nascosto (per un costo di $a = 2$), allora la nostra prossima domanda sarà "<strong>4</strong>".
|
|
|
|
Se ci viene detto che 4 è più alto del numero nascosto (per un costo di $b 0 3$), allora siamo sicuri che "<strong>3</strong>" è il numero nascosto (per un costo totale di $2 + 3 \color{blue}{\mathbf{5}}$).
|
|
|
|
Se ci viene detto che 4 è più basso del numero nascosto (per un costo di $a = 2$), allora siamo sicuri che "<strong>5</strong>" è il numero nascosto (per un costo totale di $2 + 2 = \color{blue}{\mathbf{4}}$).
|
|
|
|
Quindi, per lo scenario peggiore, il costo ottenuto con questa strategia è <strong><span style="color: red">5</span></strong>. Si può anche mostrare che questo è il più basso costo per il peggior scenario ceh può essere ottenuto. Quindi, infatti, abbiamo apena descritto una strategia ottimale per i valori dati di $n$, $a$, e $b$.
|
|
|
|
Sia $C(n, a, b)$ il costo per il peggio scenario ottenuto da una strategia ottimale per i dati valori di $n$, $a$, e $b$.
|
|
|
|
Ecco alcuni esempi:
|
|
|
|
$$\begin{align} & C(5, 2, 3) = 5 \\\\
|
|
& C(500, \sqrt{2}, \sqrt{3}) = 13.220\\,731\\,97\ldots \\\\ & C(20\\,000, 5, 7) = 82 \\\\
|
|
& C(2\\,000\\,000, √5, √7) = 49.637\\,559\\,55\ldots \\\\ \end{align}$$
|
|
|
|
Siano $F_k$ i numeri di Fibonacci: $F_k = F_{k - 1} + F_{k - 2}$ con i casi base $F_1 = F_2 = 1$.
|
|
|
|
Trova $\displaystyle\sum_{k = 1}^{30} C({10}^{12}, \sqrt{k}, \sqrt{F_k})$, e dai la tua risposta arrotondata a 8 decimali dietro il punto.
|
|
|
|
# --hints--
|
|
|
|
`guessingGame()` dovrebbe restituire `36813.12757207`.
|
|
|
|
```js
|
|
assert.strictEqual(guessingGame(), 36813.12757207);
|
|
```
|
|
|
|
# --seed--
|
|
|
|
## --seed-contents--
|
|
|
|
```js
|
|
function guessingGame() {
|
|
|
|
return true;
|
|
}
|
|
|
|
guessingGame();
|
|
```
|
|
|
|
# --solutions--
|
|
|
|
```js
|
|
// solution required
|
|
```
|