[C] Generare tutte le combinazioni possibili del SuperEnalotto

[MrX87]

Ciao a tutti, parlando con amici ci è sorto un dubbio che riguarda il fantomatico superEnalotto!! pensavamo come generare tutte le combinazioni del superenalotto! calcolandole con qualche formuletta di calcolo combinatorio si ha: 622614630!!

Come primo approccio penso che con un opportuno algoritmo ricorsivo si potrebbe risolvere il problema dal punto di vista concettuale.

Pensando però alla memoria da utilizzare...considerando che si hanno tutte quelle combinazioni e che ogni combinazione è composta da 6 numeri e che ogni intero dichiarando short int in C si occupano 2 byte per intero si ha: 622614630*6*2=7471375560 byte!! che corrispondono a circa 7 Giga byte se non ho fatto errori di calcolo o concettuali!! quindi dopo questi calcoli già si potrebbe riscontrare un problemino sulla memoria se si sviluppa questo problema su un pc normale anche se potrebbe essere risolvibile...

Per quanto riguarda i tempi di calcolo invece non saprei come poterli stimare anche orientativamente...per lo meno sapere se è dell'ordine delle ore...dei giorni....

Se qualcuno sa qualcosa d più...se mi fa sapere lo ringrazio tanto...
ciao a tutti

[Ippo343]

Come primo approccio penso che con un opportuno algoritmo ricorsivo si potrebbe risolvere il problema dal punto di vista concettuale.

1) Un algoritmo ricorsivo è soggetto ad overhead dovuti alla chiamata di funzione che la versione iterativa non ha, ed è per questo che molto spesso la versione iterativa è nettamente più efficiente.

2) Che problema concettuale c'è? Sono solo 7 cicli for annidati... lungo da scrivere, molto facile da capire.

ogni intero dichiarando short int in C si occupano 2 byte

I numeri del superenalotto vanno da 1 a 90 se non sbaglio: in ogni caso sono sotto il 255, e quindi ci stanno in un char. Se usi i char, puoi dimezzare l'utilizzo di memoria, portandolo a "soli" 3,47GB. Su un pc comune è fattibile, dato che ormai molti hanno 4GB di ram (ovviamente verrebbero usati qualche centinaia di mega dallo swap).

Comunque, il punto è... che te ne fai?

P.S: per quanto riguarda i tempi, dovresti fare qualche benchmark al tuo pc e vedere quanti numeri puoi generare al secondo.

[MacApp]

Originariamente inviato da MrX87

Per quanto riguarda i tempi di calcolo invece non saprei come poterli stimare anche orientativamente...per lo meno sapere se è dell'ordine delle ore...dei giorni....

Puoi "maggiorare l'errore": il limite minimo è quello di un ciclo che itera da 1 a 622614630.
;-)

[MdE2005]

Tutte considerazioni giuste quelle riportate fino ad ora, a cui ne aggiungerei un'altra: il multithreading, fermo restando che anche io non vedo l'utilità di tale programma..


Ciao

[MrX87]

bhè si...in realtà non c'è nessuna utilità del programma...era solo a scopo didattico capire un pò come poteva essere risolto concettualmente e se con un pc normale che di adesso si potesse risolvere il problema in tempi ragionevoli...

Puoi "maggiorare l'errore": il limite minimo è quello di un ciclo che itera da 1 a 622614630.

però non ho capito che significa che si può maggiorare il problema in questo modo...perchè provando a farlo sul mio pc...che oltretutto non è un pc modernissimo...è un toshiba del 2006 con una sola cpu...intel centrino 1.73Ghz, e come risultato ho avuto 2.53 secondi. e questo che significa??

[Ippo343]

Significa che il tuo tempo di esecuzione è sempre e sicuramente maggiore di un ciclo vuoto che itera quel numero di volte.

Propongo un ulteriore maggiorazione: un ciclo for che va da 1 a 622614630, con dentro altri 6 for annidati ognuno da 1 a 90 (dato che è questo l'algoritmo che genera tutti le combinazioni).

Tra l'altro, io l'analisi degli algoritmi non l'ho mai studiata, ma ad occhio mi verrebbe da dire che sia un O(n^7) (7 cicli for annidati, ognuno lineare...), sbaglio?

[MrX87]

Tra l'altro, io l'analisi degli algoritmi non l'ho mai studiata, ma ad occhio mi verrebbe da dire che sia un O(n^7) (7 cicli for annidati, ognuno lineare...), sbaglio?

bhè io qualcosina l'ho studiata e se l'algoritmo è costituito da 7 cicli annidati il ragionamento è corretto...basti pensare agli algoritmi di ordinamento tipo bubble sort che è l'esempio classico di ordinamento quadratico appunto perchè costituito da 2 cicli annidati.

mi sorge però un dubbio per quanto riguarda l'algoritmo ricorsivo...

1) Un algoritmo ricorsivo è soggetto ad overhead dovuti alla chiamata di funzione che la versione iterativa non ha, ed è per questo che molto spesso la versione iterativa è nettamente più efficiente.

per quanto riguarda la profondità della ricorsione non sarà più di 6 chiamate per generare una singola combinazione...quindi alla fine tutto questo overhead non lo capisco!!

[Ippo343]

Algoritmo ricorsivo: 622614630 chiamate a funzione.
Algoritmo iterativo: 1 chiamata a funzione.

Se diciamo che l'overhead dovuto alla chiamata ti fa perdere 0.1 millisecondi, l'algoritmo ricorsivo spreca 17.29 ORE solo per le chiamate di funzione, quando quello iterativo impiega 0.1 millisecondi.

Meglio?

[Ippo343]

Dimenticavo: senza contare che l'algoritmo ricorsivo ha un limite tecnologico alle chiamate che può eseguire.

Infatti, ad un certo punto le chiamate dell'algoritmo ricorsivo finiscono lo stack e il programma va in crash.

Prova ad eseguire questo inutilissimo esempio:

#include <iostream>

using namespace std;

void rec_countdown(int n)
{
    cout << n << ' ';

    if (n == 0)
        return;
    else
        rec_countdown(n - 1);
}

void iter_countdown(int n)
{
    for (int i = n; i >= 0; --i)
        cout << i << ' ';
    return;
}

int main()
{
    int n = 1000000;

    //Uncomment the proper lines to run the test you want
    //rec_countdown(n);
    //iter_countdown(n);

    return 0;
}

Vedrai che l'algoritmo ricorsivo non è in grado di contare nemmeno 1 milione di numeri.

[MrX87]

Dimenticavo: senza contare che l'algoritmo ricorsivo ha un limite tecnologico alle chiamate che può eseguire.

Infatti, ad un certo punto le chiamate dell'algoritmo ricorsivo finiscono lo stack e il programma va in crash.

si ma quello che dicevo prima è che usando l'algoritmo ricorsivo non faccio tante chiamate in profondità!! cioè non ricorro più di 6 volte in profondità...quindi il problema che proponi tu non si verifica!!
si dovrebbe piuttosto considerare il problema relativo al tempo necessario a una chiamata a funzione che come dici tu andrebbe a sprecare molto tempo inutile!