Tom, rapito da uno scienziato pazzo, si risveglia legato ad una sedia in una stanza completamente oscura.
Gli viene detto che sul tavolo di fronte a lui ci sono cento monete, dieci di queste mostrano la testa, le altre novanta croce.
Per aver salva la vita deve dividere le cento monete in due gruppi, tale che il numero di teste sia uguale.
Gli viene slegato un braccio, in modo da poter riorganizzare a suo piacimento le monete, e gli viene lasciato solo un minuto di tempo, poi verrà accesa la luce e si verificherà il risultato.
Come procedere?
Inutile pensare di contare sul senso del tatto e cercare di distinguere teste da croci, Tom non ha questa capacità e, in ogni caso, il poco tempo a disposizione lo sconsiglia.
Se si potesse solo muovere le monete, senza girarle, Tom sarebbe probabilmente spacciato. Ma c'è una scappatoia: non gli è stato vietato di cambiare la proporzione tra teste e croci.
Dunque è possibile girare le monete. Il problema è che, data l'oscurità, non è possibile sapere che faccia mostrava prima la moneta che giriamo, e nemmeno che faccia ha assunto.
Tom potrebbe magari pensare a varianti creative (tipo ingoiare tutte e cento le monete e dire di averle partizionate in due gruppi di zero monete, ognuno dei quali ha zero teste) ma difficilmente queste soddisferebbero il suo rapitore.
Le cento monete devono restare sul tavolo e, quando la luce verrà accesa, dovranno essere divise in due gruppi che mostrano lo stesso numero di teste.
Notiamo che non ci viene chiesto di dividere le monete in gruppi uguali, e ci viene da pensare che anche questo sia un indizio interessante.
Proviamo a semplificare il problema: diciamo che sulle cento monete ce ne sia solo una che mostra testa e pensiamo di creare un gruppo contenente una sola moneta, lasciandone 99 dall'altra parte. Consideriamo la nostra moneta singola. Se fosse testa, dall'altra parte devono essere tutte croci; se fosse croce, dall'altra parte c'é una testa. Dunque mi basta girarla per ottenere la soluzione. Se era l'unica testa, adesso è croce, e ho diviso i due gruppi in modo che hanno entrambi zero teste; se era croce, adesso è testa, e i due gruppi hanno entrambi una testa.
Se ci fossero due teste, dividerei la popolazione in due gruppi con 2 e 98 monete, e girerei entrambe le monete del primo gruppo. E così via fino ad arrivare alla soluzione per il problema come enunciato.
In pochi secondi, Tom isola dieci monete e le volta. E, qualunque ora sia il numero di teste sul tavolo, lui salva la propria.
Roulette russa
In genere la roulette russa si fa in due, usando un revolver. Si mette uno o più proiettili nel tamburo, lo si fa girare, si punta l'arma alla propria testa e si tira il grilletto.
Si itera finché qualcuno non trova un proiettile.
Consideriamo un revolver che abbia spazio per 6 proiettili, e per il quale ogni foro del tamburo abbia la stessa probabilità di finire in linea con il grilletto, a prescindere dal numero di proiettili che inseriamo.
Il problema è questo: due persone si affrontano alla roulette, il primo è sopravvissuto e, prima di passare l'arma al secondo, gli chiede se vuole girare il tamburo o preferisce tirare direttamente.
Cosa deve fare il secondo per avere le migliori probabilità di non spararsi?
Si analizzi il caso per un proiettile; due proiettili contigui; due proiettili non contigui.
Si tratta di puro calcolo delle probabilità.
Vediamo il primo caso: un unico proiettile nel tamburo.
Se faccio girare il tamburo, ho una probabilità su sei (0,167 circa) di trovare il proiettile.
Se il mio avversario ha appena superato la prova, ho una informazione aggiuntiva: nella camera di scoppio, quando ha tirato il grilletto, non c'era un proiettile. Dunque ora ho una possibilità di trovare un proiettile su cinque (0,2), e non più sei.
Dunque mi conviene far girare il tamburo.
Secondo caso: due proiettili contigui.
Se faccio girare il tamburo, ho due probabilità su sei (0,333) di trovare un proiettile.
Il mio avversario è ancora vivo, dunque non ha trovato il proiettile. Ma allora posso escludere che il grilletto sia sul secondo dei due proiettili contigui (dato che al mio avversario non è capitato il primo) e su uno dei fori non utilizzati (quello che è capitato al mio avversario). Ho dunque 4 possibili posizioni, di cui una occupata da un proiettile, ovvero una possibilità su quattro (0,25) di trovare un proiettile.
Mi conviene non far girare il tamburo.
Terzo caso: due proiettili non contigui.
Se faccio girare il tamburo, come nel caso precedente, ho due probabilità su sei (0,333) di trovare un proiettile.
Uso l'informazione che nel turno precedente il grilletto non era su uno dei due proiettili. Dunque ora è in una tra le quattro posizioni seguenti ai quattro fori non utilizzati. Due di queste sono occupate dai due proiettili, due sono libere. Due probabilità su quattro (0,5) di finire male.
Perciò faccio girare il tamburo.
Si itera finché qualcuno non trova un proiettile.
Consideriamo un revolver che abbia spazio per 6 proiettili, e per il quale ogni foro del tamburo abbia la stessa probabilità di finire in linea con il grilletto, a prescindere dal numero di proiettili che inseriamo.
Il problema è questo: due persone si affrontano alla roulette, il primo è sopravvissuto e, prima di passare l'arma al secondo, gli chiede se vuole girare il tamburo o preferisce tirare direttamente.
Cosa deve fare il secondo per avere le migliori probabilità di non spararsi?
Si analizzi il caso per un proiettile; due proiettili contigui; due proiettili non contigui.
Si tratta di puro calcolo delle probabilità.
Vediamo il primo caso: un unico proiettile nel tamburo.
Se faccio girare il tamburo, ho una probabilità su sei (0,167 circa) di trovare il proiettile.
Se il mio avversario ha appena superato la prova, ho una informazione aggiuntiva: nella camera di scoppio, quando ha tirato il grilletto, non c'era un proiettile. Dunque ora ho una possibilità di trovare un proiettile su cinque (0,2), e non più sei.
Dunque mi conviene far girare il tamburo.
Secondo caso: due proiettili contigui.
Se faccio girare il tamburo, ho due probabilità su sei (0,333) di trovare un proiettile.
Il mio avversario è ancora vivo, dunque non ha trovato il proiettile. Ma allora posso escludere che il grilletto sia sul secondo dei due proiettili contigui (dato che al mio avversario non è capitato il primo) e su uno dei fori non utilizzati (quello che è capitato al mio avversario). Ho dunque 4 possibili posizioni, di cui una occupata da un proiettile, ovvero una possibilità su quattro (0,25) di trovare un proiettile.
Mi conviene non far girare il tamburo.
Terzo caso: due proiettili non contigui.
Se faccio girare il tamburo, come nel caso precedente, ho due probabilità su sei (0,333) di trovare un proiettile.
Uso l'informazione che nel turno precedente il grilletto non era su uno dei due proiettili. Dunque ora è in una tra le quattro posizioni seguenti ai quattro fori non utilizzati. Due di queste sono occupate dai due proiettili, due sono libere. Due probabilità su quattro (0,5) di finire male.
Perciò faccio girare il tamburo.
Grandi attese per un piccolo incremento
Abbiamo ricevuto l'incarico di scrivere una funzione in C++ che deve rispettare le seguenti specifiche:
input: un vettore di interi positivi
output: un long
Il long in output deve essere generato in modo tale che sia pari al valore più elevato ottenibile come produttoria dei valori passati in input, considerando che possiamo incrementare di una unità uno e un solo elemento dell'array.
Ad esempio, se in input ci viene passato {4,3,2} dobbiamo scegliere se tornare (4+1)*3*2 = 30, 4*(3+1)*2 = 32, o 4*3*(2+1) = 36.
Intermezzo fornito da Belle & Sebastian.
In pratica il requisito può essere tradotto come una richiesta di identificare il minore tra i valori passati, incrementarlo, e ritornare la produttoria. Per autoconvincerci di questo fatto pensiamo ad un caso limite, in cui l'input è composto da {1, 100}. Aggiungendo 1 al primo elemento otteniamo il raddoppio del suo valore, e quindi dell'intera produttoria. Se aggiungessimo 1 al secondo, quel valore crescerebbe solo di un centesimo.
Una prima idea potrebbe essere quella di ordinare in modo crescente il vettore, incrementare il primo elemento, eseguire la produttoria sul vettore modificato:
1. Dato che dobbiamo comunque creare una copia del vettore, tanto vale farla implicitamente nell'intestazione della funzione
2. Con for_each scandiamo l'intero vettore, e la funzione lambda si occupa di mettere il risultato della produttoria nella variabile locale res, che poi torneremo al chiamante.
Non è malaccio, come codice. Soprattutto dà una certa soddisfazione scrivere la riga col for_each e la funzione lambda. Ma lascia un po' l'amaro in bocca la copia e il sorting del vettore, entrambe operazioni non necessarie. Infatti, in realtà, a noi interessa trovare e modificare solo un elemento, tutto il resto potremmo risparmiarcelo.
Invece di sort, usiamo allora min_element(), e poi spezziamo il for_each() in due parti, tenendo l'iteratore all'elemento minore del vettore come separatore tra i due tronconi.
Il codice risultante potrebbe dunque essere questo:
input: un vettore di interi positivi
output: un long
Il long in output deve essere generato in modo tale che sia pari al valore più elevato ottenibile come produttoria dei valori passati in input, considerando che possiamo incrementare di una unità uno e un solo elemento dell'array.
Ad esempio, se in input ci viene passato {4,3,2} dobbiamo scegliere se tornare (4+1)*3*2 = 30, 4*(3+1)*2 = 32, o 4*3*(2+1) = 36.
Intermezzo fornito da Belle & Sebastian.
In pratica il requisito può essere tradotto come una richiesta di identificare il minore tra i valori passati, incrementarlo, e ritornare la produttoria. Per autoconvincerci di questo fatto pensiamo ad un caso limite, in cui l'input è composto da {1, 100}. Aggiungendo 1 al primo elemento otteniamo il raddoppio del suo valore, e quindi dell'intera produttoria. Se aggiungessimo 1 al secondo, quel valore crescerebbe solo di un centesimo.
Una prima idea potrebbe essere quella di ordinare in modo crescente il vettore, incrementare il primo elemento, eseguire la produttoria sul vettore modificato:
#include <vector>
#include <algorithm>
long prodPlus1(vector<int> input) // 1.
{
sort(input.begin(), input.end());
++input[0];
long res = 1;
for_each(input.begin(), input.end(), [&res] (int i) {res *= i;}); // 2.
return res;
}
1. Dato che dobbiamo comunque creare una copia del vettore, tanto vale farla implicitamente nell'intestazione della funzione
2. Con for_each scandiamo l'intero vettore, e la funzione lambda si occupa di mettere il risultato della produttoria nella variabile locale res, che poi torneremo al chiamante.
Non è malaccio, come codice. Soprattutto dà una certa soddisfazione scrivere la riga col for_each e la funzione lambda. Ma lascia un po' l'amaro in bocca la copia e il sorting del vettore, entrambe operazioni non necessarie. Infatti, in realtà, a noi interessa trovare e modificare solo un elemento, tutto il resto potremmo risparmiarcelo.
Invece di sort, usiamo allora min_element(), e poi spezziamo il for_each() in due parti, tenendo l'iteratore all'elemento minore del vettore come separatore tra i due tronconi.
Il codice risultante potrebbe dunque essere questo:
#include <vector>
#include <algorithm>
long prodPlus2(const vector<int>& input)
{
vector<int>::const_iterator it = min_element(input.begin(), input.end());
long res = (*it) + 1;
for_each(input.begin(), it, [&res] (int i) {res *= i;});
for_each(it+1, input.end(), [&res] (int i) {res *= i;});
return res;
}
Iscriviti a:
Post (Atom)