Newsgroup: it.scienza.informatica
Titolo: algoritmo per la tombola

Ciao ragazzi, lo so che sono fuori tempo, ma volevo chiedervi se qualcuno
conosce delle informazioni sull'algoritmo per la generazione di cartelle
della tombola. E' gradito qualsiasi tipo di informazione o link! Grazie!


Ecco un programmillo che feci qualche anno fa, scritto in QBASIC.
DECLARE SUB Scegli (n!, q!, a!)
DECLARE SUB Stampa (x!, y!, cartella!, n!)
DECLARE SUB Crea (n!)
DECLARE SUB Stampan (x!, y!, nu!, iniz!, fin!)
CLS
SCREEN 2
RANDOMIZE TIMER
INPUT "Cartelle "; c
DIM SHARED cartella(c, 3, 9) AS STRING
DIM SHARED a(90)
FOR h = 1 TO c
         Crea h
NEXT h
CLS
Stampan 0, 8, 6, 1, c
OPEN "img.txt" FOR OUTPUT AS #1
con = 0
nu = 0
FOR i = 0 TO 639
         FOR j = 0 TO 199
                 IF POINT(i, j) = nu THEN
                         con = con + 1
                         ELSE
                                 PRINT #1, con
                                 nu = 1 - nu
                                 con = 1
                 END IF
         NEXT j
NEXT i
CLOSE
'Disegna.bas serve per ricaricare e visualizzare il file img.txt'
SUB Crea (n)
DIM cl(3)
Scegli 9, 3, a
c1 = a(1)
c2 = a(2)
c3 = a(3)
DO
         cl(1) = 0: cl(2) = 0: cl(3) = 0
         FOR i = 1 TO 3
                 FOR j = 1 TO 9
                         cartella(n, i, j) = ""
                 NEXT j
         NEXT i
         FOR i = 1 TO 9
                 IF i = 1 THEN
                         sot = 0
                         num = 9
                         cif = 1
                         ELSE
                                 IF i = 9 THEN
                                         sot = 1
                                         num = 11
                                         cif = 2
                                 ELSE
                                         sot = 1
                                         num = 10
                                         cif = 2
                                 END IF
                 END IF
                 ag$ = SPACE$(2 - cif)
                 IF (c1 = i) OR (c2 = i) OR (c3 = i) THEN
                         Scegli num, 1, a
                         r = INT(3 * RND) + 1
                         cartella(n, r, i) = ag$ + 
LTRIM$(LTRIM$(RTRIM$(STR$(a(1) - sot + 10 * (i - 1)))))
                         cl(r) = cl(r) + 1
                 ELSE
                         Scegli num, 2, a
                         n1 = a(1)
                         n2 = a(2)
                         IF n1 > n2 THEN
                                 k = n2
                                 n2 = n1
                                 n1 = k
                         END IF
                         Scegli 3, 2, a
                         IF a(1) > a(2) THEN
                                 k = a(2)
                                 a(2) = a(1)
                                 a(1) = k
                         END IF
                         cl(a(1)) = cl(a(1)) + 1
                         cl(a(2)) = cl(a(2)) + 1
                         cartella(n, a(1), i) = ag$ + 
LTRIM$(LTRIM$(RTRIM$(STR$(n1 - sot + 10 * (i - 1)))))
                         cartella(n, a(2), i) = ag$ + 
LTRIM$(LTRIM$(RTRIM$(STR$(n2 - sot + 10 * (i - 1)))))
                 END IF
         NEXT i
LOOP UNTIL (cl(1) = 5) AND (cl(2) = 5) AND (cl(3) = 5)
END SUB
SUB Scegli (n, q, a)
t = n
REDIM vet(n)
FOR i = 1 TO n
         vet(i) = i
NEXT i
a$ = ""
FOR i = 1 TO q
         s = INT(t * RND) + 1
         a$ = a$ + LTRIM$(RTRIM$(STR$(vet(s)))) + " "
         FOR j = s TO t - 1
                 vet(j) = vet(j + 1)
         NEXT j
         t = t - 1
NEXT i
in = 0
con = 0
WHILE fi <> LEN(a$)
         con = con + 1
         fi = INSTR(in + 1, a$, " ")
         a(con) = VAL(MID$(a$, in + 1, fi - in))
         in = fi
WEND
END SUB
SUB Stampa (x, y, cartella, n)
lt$ = ""
FOR lt = 1 TO 8
         lt$ = lt$ + "ÄÂÄ"
NEXT lt
LOCATE x, y: PRINT "ÚÄ"; lt$; "Ä¿"
FOR i = 1 TO 3
         LOCATE x + 2 * i - 1, y: PRINT "³";
         LOCATE x + 2 * i - 1, y + 1
         FOR j = 1 TO 9
                 IF cartella(n, i, j) = "" THEN cartella(n, i, j) = "  "
                 PRINT cartella(n, i, j); "³";
         NEXT j
         PRINT
         IF i <> 3 THEN
                 lt$ = ""
                 FOR lt = 1 TO 8
                         lt$ = lt$ + "ÄÅÄ"
                 NEXT lt
                 LOCATE x + 2 * i, y: PRINT "ÃÄ"; lt$; "ÄŽ"
         END IF
NEXT i
lt$ = ""
FOR lt = 1 TO 8
         lt$ = lt$ + "ÄÁÄ"
NEXT lt
LOCATE x + 6, y: PRINT "ÀÄ"; lt$; "ÄÙ"
PRINT
END SUB
SUB Stampan (x, y, n, iniz, fin)
f = 0
FOR h = iniz TO fin
         f = f + 1
         IF (f MOD n = 1) AND f > 1 THEN
                 SLEEP
                 CLS
                 f = 1
         END IF
         Stampa 7 * INT((f - 1) / 2) + 1 + x, 1 + 30 * ((f + 1) MOD 2) + 
y, cartella, h
NEXT h
SLEEP
END SUB
Se dovesse risultarti oscuro scrivimi.
Ciao
-- 
_-==.==-_*_-==.==-_
   _    _   __    _   " Ogni sistema ha le sue leggi :
  |_)_ |_) (_  _ |_)     alcune possono essere eluse
  | (_|| \o__)(/_| \    altre...infrante " (Morpheus)
  (Giacomo Bellucci)
 
PaR._IL_BIAN...@libero.it
      _________
     /ficm code\          Per rispondermi togliete
     \ [Hx23B] /        _IL_BIANCONIGLIO_ dall'email
      ¯¯¯¯¯¯¯¯¯

"Capitan Harlock" ha scritto:

Una dozzina di anni fa, un amico mi chiese un programma per generare
le cartelle per una tombola di beneficenza. Ho ripescato il sorgente
e, visto che č corto, lo inserisco al fondo del messaggio.
Il programma scrive semplici righe di testo: questo era sufficiente
per il mio amico che, se ben ricordo, usň un programmino in BASIC per
la stampa delle cartelle.
Riguardando il programma, ho notato che un numero puň comparire piů
di una volta in una cartella. Non saprei dire se questo sia dovuto ad
una svista oppure si tratti di qualcosa di normale nelle cartelle
della tombola (sono molti anni che non ne vedo una!). In ogni caso,
non č difficile modificare il programma per evitare doppioni.
-- 
   Gianfranco Boggio-Togna
   Milano 
=== INIZIO PROGRAMMA ===
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define TRUE 1
#define FALSE 0
typedef int schema_di_riga [5] ;
typedef int schema_di_cartella [3] ;
int
rand10 ()
{
    double r ;
    r = ((double) rand()) / ((double) RAND_MAX) ;
    return ((int) (r * 10.0)) ;
}
long
numero_di_combinazioni (int N, int R)
{
    long    n ;
    int r ;
    n = (long) N ;
    r = R - 1 ;
    while (r--) 
        n *= --N ;
    r = R ;
    while (r) 
        n /= r-- ;
    return n ;
}
int
genera_combinazione (int  combinazione[], 
                     int  N,
                     int  R,
                     int  passo,
                     int  prima_combinazione)
{
    int i, j ;
/*
    Algoritmo COMB_LEX, da:
    Page & Wilson: An introduction to Computational Combinatorics 
    Cambridge University Press
*/
start:
    if (prima_combinazione) {
        for (i = 0 ; i < R ; i++)
            combinazione[i] = i ;
        return TRUE ;
    }
 
    for (i = R-1 ; i >= 0 ; i --) 
        if (combinazione[i] < N-R+i) {
            combinazione[i] ++ ;
            for (j = i+1 ; j < R ; j ++)
                combinazione[j] = combinazione[j-1] + 1 ;
            if (--passo == 0)
                return TRUE ;
            else
                goto start ;
        }
    return FALSE ;
}
int
schema_ok (schema_di_riga  schema, int max_adiacenti) 
{
    int i, j , adiacenti ;
    for (i = 0 ; i < 4 ; i++) {
        adiacenti = 0 ;
        for (j = i+1 ; j < 5; j ++) {
            if ( schema [j] == (schema[j-1] +1) )  {
                if (++adiacenti == max_adiacenti)
                    return FALSE ;
            } else
                break ;
        }
    }           
    return TRUE ;
}
schema_di_riga  * tabella_schemi [126] ;
genera_riga ( int indice_schema )
{
    int riga [9] ;
    int i, c ;
    schema_di_riga  * s ;
    int random[10] ;
    s = tabella_schemi [indice_schema] ;
    for (i = 0 ; i < 9 ; i++)
        riga [i] = 0 ;
    for (i = 0 ; i < 5 ; i++) {
        c = (*s)[i] ;
        riga [c] = c * 10 + rand10() + 1;   
    }
    for (i = 0 ; i < 9 ; i++)
        printf ("%02d ", riga [i]) ; 
    printf ("\n") ;
}
main () 
{
    schema_di_riga    s ;
    schema_di_riga  * schemi ;
    int       numero_schemi ;
    int       max_adiacenti ;
    long      max_cartelle ;
    int       numero_cartelle ;
    schema_di_cartella cartella ;
    int       intervallo ;
 
    int i, j, k ;
    numero_cartelle = 3000 ;
    max_adiacenti = 3 ;  
    fprintf (stderr, "Cartelle da generare: ") ;
    scanf  ("%d", &numero_cartelle) ; 
    fprintf (stderr, "\nMassima sequenza di numeri adiacenti: ") ;
    scanf  ("%d", &max_adiacenti) ;
    schemi = (schema_di_riga *) calloc (126, sizeof(schema_di_riga)) ;
    numero_schemi = 0 ;
    genera_combinazione (s, 9, 5, 1, TRUE) ;
    if ( schema_ok (s, max_adiacenti) ) {
        tabella_schemi [numero_schemi++] = schemi ;
        for (i = 0 ; i < 5 ; i++)
            (* schemi)[i] = s[i] ;
        schemi ++ ;
    }
    while ( genera_combinazione (s, 9, 5, 1, FALSE) )
        if ( schema_ok (s, max_adiacenti) ) {
            tabella_schemi [numero_schemi++] = schemi ;
            for (i = 0 ; i < 5 ; i++)
                (* schemi)[i] = s[i] ;
            schemi ++ ;
        }
    for (i = 0 ; i < 10 ; i++) 
        for (j = 0 ; j < numero_schemi ; j++) {
            k = rand() % numero_schemi ;
            schemi = tabella_schemi[k] ;
            tabella_schemi[k] = tabella_schemi[j] ;
            tabella_schemi[j] = schemi ;
        }
    max_cartelle = (long) numero_di_combinazioni (numero_schemi, 3) ;
    intervallo = max_cartelle / numero_cartelle ;
    genera_combinazione (cartella, numero_schemi, 3, 1, TRUE) ;
    while ( numero_cartelle &&
            genera_combinazione (cartella,
                                 numero_schemi,
                                 3,
                                 intervallo,
                                 FALSE) )
    {
        for (i = 0 ; i < 3 ; i ++)
            genera_riga (cartella[i]) ;
        printf ("\n") ;
        numero_cartelle -- ;
    }   
}
=== FINE PROGRAMMA ===