.: Le soluzioni del problema di Marzo 2004 :.

Carlo, ha un amico che lavora in un negozio di edilizia che spesso si trova a dover soddisfare richieste del tipo:" mi prepari n1 pezzi di verga metallica di lunghezza l1, n2 pezzi di verga di lunghezza l2, ...,nk di lunghezza lk". Naturalmente questi pezzi vengono tagliati da verghe di lunghezza standard, diciamo L (ad es. 600 cm) e in generale l1, l2, ...,lk, che sono minori di L, non sono tutti sottomultipli di L e, qualora alcuni di essi lo siano, il numero di pezzi di lunghezza li ricavabili da una verga (L/li) potrebbe non essere sottomultiplo di ni, come pure il numero di pezzi di lunghezza lj ricavabili da una verga potrebbe non esserlo di nj, e così via .
Il suo problema consiste nel trovare quante verghe occorrono per soddisfare le richieste, in modo da ridurre gli scarti al minimo e quindi, ovviamente, i costi.

Pubblico con piacere la soluzione (giunta in ritardo) proposta dal giovane lettore Matteo e invito i fedeli solutori ad esprimere un parere.

Caro sig. Scoleri,

mi chiamo Matteo Monti, ho 12 anni e adoro la matematica. Tempo fa mi sono imbattuto nella vostra rubrica. Così, quando ho trovato il problema proposto per marzo 2004, ho provato a risolverlo.

Sta di fatto che a noi, a scuola (sono in seconda media!), non ci abbiano ancora spiegato tante cose da permetterci di risolvere un problema di quel tipo. Non mi sono lasciato scoraggiare e ci ho ragionato un pò, giungendo ad una soluzione che mi pare possa funzionare.

Ho scritto un "diagramma di flusso". Sicuramente, formalmente la mia soluzione non è corretta, la prego tuttavia di visionarla.

SPIEGAZIONI SU COME INTERPRETARE IL DIAGRAMMA DI FLUSSO:

indica un ciclo. Le operazioni tra i puntini vanno eseguite un numero di volte pari a m - n. Ogni volta che si ricomincia il ciclo, a viene incrementato di 1 (inizialmente, a ha valore pari a m)

vuol dire: se si verifica la condizione cond1 (e, contemporaneamente, la condizione cond2, se specificata e preceduta da &), esegui le operazioni scritte tra parentesi graffe.

3) il punto e virgola (;) che separa due operazioni scritte su di una stessa riga sta a significare che le due operazioni vanno eseguite come se fossero scritte l'una sotto all'altra.

indica di tornare all'istruzione indicata con il numero n)

Detto ciò, le mando per allegato un file .txt con il mio diagramma di flusso. La prego di visionarlo e di scrivermi, se possibile una sua opinione.

SOLUZIONE DEL PROBLEMA DI MARZO 2004

Dati/definizioni:

L = lunghezza standard della verga prodotta
l1, l2,...,lm = lunghezza del pezzo di verga metallica richiesta dal cliente
n1, n2, ... , nm = numero di sbarre per ogni tipo (l)
m = numero di tipi di sbarre (l) richieste dal cliente
sci = scarto corrispondente alla prova i
N = numero di sbarre di verga utilizzate per soddisfare le richieste del cliente
C; SC; G = numeri di passaggio
i; r; j = contatori

-------------------------

DIAGRAMMA DI FLUSSO:

1) Ordino per ordine decrescente gli l: l1 > l2 > l3 > ... > lm
2) i = 1, m
   ( sci = L
     r = i, m
     ( C = nr
       sci - lr >= 0 & C > 0? { C = C - 1; sci = sci - lr}
      )
    )
   C = sc1
   j = 1, m
   ( scj < C? {C = scj; G = j})
   SC = L
   i = G, m
   ( SC - li >= 0 & ni > 0? { ni = ni - 1; SC = SC -li}); N = N + 1
    SC = 0
    i = 1, m
    (ni > 0? { SC = 1})
    SC = 0? {END}
    GOTO 2