Alan M. Turing: quiz

Visualizzazione post con etichetta quiz. Mostra tutti i post

Tante teste per Tom

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.

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:


#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;
}

Quadrato creativo

Dato n, numero intero positivo, il suo quadrato é uguale alla somma dei primi n numeri dispari.

Usare questa curiosa proprietà per calcolare il quadrato dei primi dieci interi positivi.

In pratica dobbiamo sommare i primi n elementi della progressione aritmetica di ragione 2 con primo termine 1.
Qualcosa come 1 + 3 + 5 + 7 + 9 + ....

Questa l'implementazione che mi é venuta naturale:


    for (int i = 1; i < 11; ++i) {
        int sum = 1;
        for (int j = 1; j < i; ++j) {
            sum += (j*2)+1;
        }

        cout << sum << ' ';
    }
    cout << endl;

L'idea é che il ciclo for esterno reinizializza la sommatoria a 1, il primo elemento della successione, e poi aggiunge gli elementi successivi che possono essere calcolati in funzione dell'indice j in modo immediato. Il primo elemento, 3, é infatti pensabile come 2 + 1, il secondo 2*2 + 1, il terzo 3*2 + 1, eccetera.

Ma, a pensarci un attimo, l'uso del doppio loop for é ridondante. Dopotutto per calcolare il risultato per n basta appoggiarsi a quello per n-1.

Il che porta a questa implementazione:


    vector<int> results;

    results.push_back(1);
    for (int i = 1; i < 10; ++i) {
        results.push_back(results[i-1] + (i*2)+1);
    }

    vector<int>::const_iterator it = results.begin();
    while(it != results.end())
        cout << *it++ << ' ';
    cout << endl;

Il primo elemento é uno, lo mettiamo nel vettore dei risultati. Gli altri li calcoliamo aggiungendo al precedente elemento il successivo numero dispari.

A pensarci meglio, però, nel caso generale l'uso di vector non é che sia una idea geniale. Nel caso corrente non ci sono problemi, dato che sappiamo il nostro vector non cresce più di tanto, ma se pensiamo ad un caso in cui si vogliano trovare i quadrati per centinaia, migliaia o anche più interi conviene usare deque.

Ecco qui la mia implementazione in questo caso:


    deque<int> d;

    d.push_back(1);
    for (int i = 1; i < 10; ++i) {
        d.push_back(d.back() + (i*2)+1);
    }

    deque<int>::const_iterator it = d.begin();
    while(it != d.end())
        cout << *it++ << ' ';
    cout << endl;

Le vocali in una stringa

Scrivere un metodo statico in Java che ritorni il numero di vocali della stringa che gli viene passata come parametro.

Assumiamo che per vocali si intendano solo i caratteri a, e, i, o, u.

A voler fare i precisini bisognerebbe considerare anche i caratteri accentati, per non parlare dei caratteri che rappresentano suoni vocalici specifici di alcune lingue (tedesco, svedese, per dirne un paio). Ma limitiamoci alla soluzione di base.

In una classe creiamo un paio di metodi statici. Il primo, isVowel(), accetta in ingresso un carattere e ritorna true solo se questo é una vocale, secondo la nostra definizione:


    public static final boolean isVowel(char c) {
        switch(c) {
            case 'A':
            case 'a':
            case 'E':
            case 'e':
            case 'I':
            case 'i':
            case 'O':
            case 'o':
            case 'U':
            case 'u':
                return true;
            default:
                return false;
        }
    }

Il secondo metodo é quello richiesto, accetta in input una stringa e fa un loop su di essa al fine di contare tutte le vocali presenti:


    public static int vowels(String input) {
        int value = 0;
        if(input == null)
            return 0;

        for(int i = 0; i < input.length(); ++i)
            if(isVowel(input.charAt(i)))
                ++value;
        return value;
    }

Per testare la funzionalità ho usato questo main:


    public static void main(String[] argv) {
        int value = vowels("ambaradan");
        System.out.println(value);

        value = vowels(null);
        System.out.println(value);

        value = vowels("");
        System.out.println(value);

        value = vowels("aeiou");
        System.out.println(value);

        value = vowels("sfrt");
        System.out.println(value);
    }

Ordinare una matrice

Stiamo lavorando in C++. Ho un array bidimensionale di interi, tipo questo:

Voglio crearne una copia ordinata per colonne, in modo che l'output sia:

come fare?

La mia idea é quella di usare come appoggio un multiset. Approfittando del fatto che l'inserimento in questo container é automaticamente ordinato basta caricare i valori dall'array in input nel multiset e quindi leggerli nell'array di output.

Questo il codice risultante:


#include <iostream>
#include <set>

using namespace std;

namespace {
    const int DIM = 5;

    void mapper(int input[][DIM], int output[][DIM]) {
        multiset<int> temp;

        for (int i = 0; i < DIM; ++i) {
            for (int j = 0; j < DIM; ++j) {
                temp.insert(input[i][j]);
            }
        }

        multiset<int>::const_iterator it = temp.begin();
        for (int i = 0; i < DIM; ++i) {
            for (int j = 0; j < DIM; ++j) {
                // !!! [j][i] !!! ordered by columns
                output[j][i] = *it++;
            }
        }
    }
}

int main() {
    int input[DIM][DIM] = {
        4, 9, 8, 5, 7,
        5, 6, 2, 6, 1,
        9, 7, 8, 3, 2,
        3, 9, 4, 5, 8,
        1, 6, 8, 7, 1
    };

    for (int i = 0; i < DIM; ++i) {
        for (int j = 0; j < DIM; ++j) {
            cout << input[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl;

    int output[DIM][DIM];
    mapper(input, output);

    for (int i = 0; i < DIM; ++i) {
        for (int j = 0; j < DIM; ++j) {
            cout << output[i][j] << ' ';
        }
        cout << endl;
    }
    cout << endl;
}