FreeBASIC – esercizi

Permutazioni semplici e soluzione esercizio Bocconi

Eccomi di nuovo a voi con un programmino in FreeBASIC. L’occasione per scriverlo è capitata ieri, quando mi è stato presentato un problema di “allenamento” per le gare internazionali di matematica organizzate dall’università Bocconi. Questi “allenamenti” sono basati su esercizi dati in passato per altre gare dello stesso tipo; in particolare, questo che vi propongo si trovava in una gara del 2006. Potete prelevare il file PDF da questo link che ho trovato su internet. Nel documento PDF ci sono diversi esercizi, ma quello che mi è stato proposto è il numero 10, denominato CONNESSIONE. Devo dire che la parte più difficile della soluzione è stata quella di interpretrare la traccia che, francamente, era parecchio oscura e talvolta rasentava la mancanza di senso, come nella frase “la somma, magari costituita da un unico addendo”, ma una volta capito quello che veniva inteso, il resto è stato facile.
Con un po’ di ragionamenti (partendo dalle somme 1 e 2) si trova facilmente la soluzione, anzi una delle soluzioni possibili. E questo basta per dire di aver risolto il problema. Ok. Dopo un po’ ho pensato di realizzare un programma che trovasse, matematicamente, tutte le possibili soluzioni. Ho impostato la traccia in un modo diverso, che a me è sembrato più chiaro. Ho immaginato sette villette disposte in un certo territorio. Ogni villetta ha il proprio numero civico, da 1 a 7. Da ogni villetta si scorgono una o più delle altre (alcune non sono reciprocamente visibili) e le persone che vivono in ognuna di esse, decidono di calcolare la somma dei numeri civici delle villette che riescono a vedere. I risultati di 6 di questi personaggi sono noti (1, 2, 3, 5, 8, 13), si chiede quale sia la somma calcolata dal settimo. Ho realizzato uno schemino per spiegare queste relazioni:

casette

Sa = B
Sb = A + C + F
Sc = B + D
Sd = C + E + F + G
Se = D
Sf = B + D + G
Sg = D + F

Per ‘Sa’ si intende la somma dei numeri civici delle villette viste dall’abitazione [ a ], per ‘Sb’ quelli visti dalla villetta [ b ] e così via. In pratica le linee che collegano le casette indicano la possibilità di “vedere” le altre. Il programma, quindi, agisce così: genera tutte le possibili PERMUTAZIONI SEMPLICI di 7 elementi, calcola le equazioni per ognuna delle permutazioni e verifica nei risultati se 6 di essi corrispondono a quelli dati nella traccia ; in quel caso, rivela il settimo che è la soluzione. Le permutazioni di 7 elementi sono 5040 (corrispondenti a 7 fattoriale), ma le soluzioni sono solo 8, delle quali 4 non valide perché alcune delle somme si ripetono. Le restanti 4 danno come totale 22, 21 o 19 (quest’ultimo in due permutazioni), che sono quelle indicate come risultato dalla Bocconi.
Le permutazioni vengono tutte salvate sul file di uscita risultati.txt e dopo ogni riga valida, cioè che risponde ai requisiti, viene stampato un ‘*** Ok’ seguito dalle somma calcolate da tutti gli “abitanti” delle villette, da ‘Sa’ a ‘Sg’. Di sotto, il listato del programma :

Dim Shared As Integer contatore(7) ' array usato come contatore a 7 digit
Dim Shared As Integer civici(7) ' array dei numeri civici
Dim Shared As Integer somme(6) ' array delle somme gia' note
Dim Shared As Integer nrow ' numero riga per stampa
Dim Shared As Integer finito ' segnalatore di iterazioni finite

' subroutine per creazione nuova permutazione semplice
'-----------------------------------------------------
Sub Newrow()
Dim As Integer x,y

retry:
    x = 7 ' posiziona su elemento piu' a destra del contatore
    Do
        contatore(x) = contatore(x) +1 ' passa a nuovo digit
        If contatore(x) <= 7 Then Exit Do ' termina se non li hai usati tutti
        contatore(x) = 1 ' altrimenti ricomincia dal primo digit
        x = x -1 ' passa al digit immediatamente a sinistra
    Loop Until x = 0 ' esegui per tutti i digits
    If x = 0 Then ' se il conteggio è finito (tutti i digits usati)
        finito = 1 ' attiva segnale di conteggio terminato
        Exit Sub ' termina la subroutine
    Endif 

    ' vogliamo le permutazioni semplici, quindi saltiamo
    '  le combinazioni con elementi ripetuti
    For x = 1 to 6
        For y = x+1 to 7
            If contatore(x) = contatore(y) Then Goto retry
        Next y
    Next x
End Sub

' subroutine per la stampa della attuale permutazione
'----------------------------------------------------
Sub Outrow()
Dim As Integer x

    Print #1,nrow, ' scrivi nuova riga permutazione semplice
    nrow = nrow +1
    For x = 1 to 7
        Print #1, civici(contatore(x));" ";
    Next x
    Print #1, ' fine linea

End Sub

' subroutine per il calcolo del problema
'---------------------------------------
Sub Calcola()
Dim As Integer S(7)
Dim As Integer x, y, num

    ' calcolo somme numeri civici visibili da ogni villetta
    S(1) = civici(contatore(2)) ' Sa = b
    S(2) = civici(contatore(1)) + civici(contatore(3)) + civici(contatore(6)) ' Sb = a+c+f
    S(3) = civici(contatore(2)) + civici(contatore(4)) ' Sc = b+d
    S(4) = civici(contatore(3)) + civici(contatore(5)) + civici(contatore(6)) + civici(contatore(7)) ' Sd = c+e+f+g
    S(5) = civici(contatore(4)) ' Se = d
    S(6) = civici(contatore(2)) + civici(contatore(4)) + civici(contatore(7)) ' Sf = b+d+g
    S(7) = civici(contatore(4)) + civici(contatore(6)) ' Sg = d+f

    num = 0 ' azzera numero di somme valide
    For x = 1 to 7 ' per tutte le somme calcolate
        For y = 1 to 6 ' per tutte le somme gia' note
            If S(x) = somme(y) then
                num = num +1
                y = 6 ' termina il for interno
            Endif
        Next y
    Next x
    If num = 6 Then ' tutti le somme valide
        Print #1,"*** ok ";
        For x = 1 to 7
            Print #1, "[";S(x);"] ";
        Next x
        Print #1,
    Endif
End Sub

' programma principale
'---------------------

    Print " **********************************************************"
    Print " ** Programma per il calcolo della soluzione al problema **"
    Print " **  delle sette casette con numeri civici da 1 a 7, che **"
    Print " **  si vedono nella mappa allegata al problema.         **"
    Print " ** Compilato con FreeBasic, opzione QB - E.Ficara 2011  **"
    Print " **********************************************************"

    civici(1) = 1: civici(2) = 2: civici(3) = 3: civici(4) = 4 ' assegna numeri civici alle casette
    civici(5) = 5: civici(6) = 6: civici(7) = 7

    somme(1) = 1: somme(2) = 2: somme(3) = 3 ' assegna le somme gia' note
    somme(4) = 5: somme(5) = 8: somme(6) = 13

    For i = 1 to 6 ' inizializza contatore 7 digit
        contatore(i) = 1
    Next i
    contatore(i) = 0 ' combinazione -1 (per successivo incremento con Newrow)

    nrow = 1 ' inizializza numero linea per stampa
    finito = 0 ' inizializza il segnalatore di iterazioni complete

    Open "risultati.txt" For Output As #1 ' prepara file di uscita
    Print #1,"Permutazioni semplici:" & Chr$(13) & Chr$(10)
    Do ' inizia loop combinazioni
        Newrow ' calcola nuova permutazione semplice
        If finito > 0 then Exit Do ' esci se segnale di conteggio finito 
        Outrow ' altrimenti stampa linea
        Calcola ' esegui calcolo del problema
    Loop
    Close #1

    Print "Programma terminato. E' stato creato il file risultati.txt"
    Print "Premere un tasto qualsiasi per terminare..."
    Do
        If Inkey$ <> "" then Exit Do
    Loop
End