Newsgroup: it.hobby.enigmi
Titolo: Ricoprire un rettangolo in modo economico

Visto che mi avete risolto prestissimo il problema del ricoprimento
non-banale vi propongo anche questo:
Abbiamo sempre un rettangolo nxm (con n e m interi) da ricoprire di
quadrati.
Ora però possiamo ricoprirlo avendo a disposizione quadrati di tutte le
possibili misure (anche frazioni dell'unità), ma vogliamo farlo in modo da
usare il minor numero di quadrati.
Come lo ricoprireste?
Ciao!!
Marco

 
Essendo un programmatore e non un matematico, ho messo in piedi una 
procedurina ricorsiva, che mi dice anche che quadrati servono.
Spoiler
VV
VV
VV
VV
VV
VV
VV
E' una procedurina in VB, ma penso sia abbastanza comprensibile ed 
adattabile a qualsiasi linguaggio.
' Riceve come parametri di ingresso altezza e lunghezza del rettangolo
Private Sub CalcolaQuadrati(iL, iA)
Dim iMax As Integer
Dim iMin As Integer
    ' Se ho gia' un quadrato, e' inutile che mi sprema...
    If iL = iA Then
        lstQuadrati.AddItem "1 di " & CStr(iL) & "x" & CStr(iL)
        Exit Sub
    End If
 
    ' Cosi' come se uno dei due lati e 1...
    If iL = 1 Then
        lstQuadrati.AddItem CStr(iA) & " di 1x1"
        Exit Sub
    End If
 
    If iA = 1 Then
        lstQuadrati.AddItem CStr(iL) & " di 1x1"
        Exit Sub
    End If
 
    ' Questo mi serve per evidenziare il lato piu' lungo
    If iL > iA Then
        iMax = iL
        iMin = iA
    Else
        iMax = iA
        iMin = iL
    End If
 
    ' L'operatore \\ mi restituisce il risultato intero. 7/2 = 3.5; 7\\2 = 3
    lstQuadrati.AddItem CStr(iMax \\ iMin) & " di " & CStr(iMin) & "x" & 
CStr(iMin)
    ' Chiamata ricorsiva, con un quadrato piu' piccolo
    Call CalcolaQuadrati(iMax - iMin * (iMax \\ iMin), iMin)
End Sub
Le righe con 'lstQuadrati.AddItem...' aggiungono ad un elenco a video i 
quadrati necessari per la ricopertura.
Bye by SixaM 8-]
P.S. Essendo la mia una funzione ricorsiva, c'e' sicuramente un modo piu' 
elegante per scriverla...  
--
Bye by SixaM 8-]
Inviato da 
www.mynewsgate.net

 adattabile a qualsiasi linguaggio.
Ciao, non sono sicuro di aver capito come scegli "geometricamente" i
quadrati da piazzare per ricoprire.
Credo di aver intuito che scegli inizialmente il lato minimo del rettangolo
e piazzi un quadrato con quel lato, poi consideri il sottorettangolo che ti
č rimasto, guardi i lati e piazzi un quadrato di lato uguale al lato minimo.
E cosě via...
Insomma usi un algoritmo "greedy" che fa ogni volta la mossa localmente piů
conveniente.
Ora č vero che cosě finisci sicuramente per ricoprire il rettangolo ma non č
detto che il tuo ricoprimento sia quello piů "economico" (in termini di
quadrati)!!
Prendiamo ad esempio il rettangolo 5x6.
Con il tuo stratagemma lo ricopri con un quadrato 5x5 piů 5 quadrati 1x1: 6
quadrati.
Ma si puň fare di meglio: 3 quadrati 2x2 piů 2 quadrati 3x3: sono 5.
Tra l'altro quest'ultimo tipo di ricoprimento del 5x6 non sembra estendibile
a rettangoli differenti...
Ciao!!
Marco

 
Bye by SixaM 8-]


 
Bye by SixaM 8-]



Diciamo che mi sono limitato alle misure intere.
Non saprei dire se le misure frazionarie (razionali)
possono aiutare e in ogni caso invece che decomporre un rettangolo
CxR proverei a decomporre rettangoli (CK)x(RK) per vedere se
il numero di quadrati cala. Chiaramente, lavorando a brute-force,
un fattore anche piccolo K da abbastanza noia...
Chiamiamo Greedy(R,C) il numero di quadrati nel ricoprimento di un
rettangolo RxC che ha  proposto SixaM.
Questo costituisce un limite superiore al numero minimo
di quadrati e i casi interessanti sono quelli (come 5x6) in cui si
puo' andare sotto.
Sotto, salvo errori et omissioni,
ho listato tutte le soluzioni per rettangoli con
lato maggiore <=31 per cui la soluzione migliore e'
minore del valore dato da Greedy. (G sta per greedy, B per best).
Tutte le soluzioni hanno preso circa 30 secondi di tempo di calcolo
(piu' una mezzora di prezioso tempo-uomo per il programma).
La lista di numeri tra parentesi rappresenta la soluzione.
Come ricostruire il ricoprimento a partire dalla lista di numeri
l'ho scritto in fondo alla lista, cosi' se uno vuole puo'
cimentarsi. Mi accorgo ora che i rettangoli sono ordinati
in modo un po' bislacco, ma penso che lo capiate.
Tra i problemi "piccoli" il primo interessante direi che
e'  11x13.
ciao,
g.
---------------------------------------------------------------------------
  5 x  6 : G= 6, B= 5 (3 2 2 3 2)
  6 x  7 : G= 7, B= 5 (4 2 2 3 3)
  7 x  8 : G= 8, B= 7 (4 3 3 4 2 1 1)
  8 x  9 : G= 9, B= 7 (5 3 2 1 1 4 4)
  9 x 10 : G=10, B= 6 (5 4 4 5 2 2)
  5 x 11 : G= 7, B= 6 (5 3 2 2 3 2)
  6 x 11 : G= 7, B= 6 (6 3 3 2 2 2)
10 x 11 : G=11, B= 6 (6 4 2 2 5 5)
10 x 12 : G= 6, B= 5 (6 4 4 6 4)
11 x 12 : G=12, B= 7 (8 3 3 3 4 4 3)
  6 x 13 : G= 8, B= 6 (6 4 2 2 3 3)
  7 x 13 : G= 8, B= 6 (7 4 3 3 2 2)
11 x 13 : G= 8, B= 6 (7 4 4 6 1 5)
12 x 13 : G=13, B= 7 (9 3 3 3 4 4 4)
12 x 14 : G= 7, B= 5 (8 4 4 6 6)
13 x 14 : G=14, B= 7 (7 6 6 7 2 2 2)
  7 x 15 : G= 9, B= 8 (7 4 3 3 4 2 1 1)
  8 x 15 : G= 9, B= 8 (8 4 4 3 3 2 1 1)
13 x 15 : G= 9, B= 8 (10 3 3 3 3 5 5 3)
14 x 15 : G=15, B= 7 (9 5 5 6 3 5 3)
  5 x 16 : G= 8, B= 7 (5 5 3 2 2 3 2)
11 x 16 : G= 8, B= 7 (11 5 3 3 2 2 2)
14 x 16 : G= 8, B= 7 (8 6 6 8 4 2 2)
15 x 16 : G=16, B= 7 (10 5 5 6 6 3 3)
  6 x 17 : G= 8, B= 7 (6 6 3 3 2 2 2)
  8 x 17 : G=10, B= 8 (8 5 3 2 1 1 4 4)
  9 x 17 : G=10, B= 8 (9 5 4 4 3 2 1 1)
11 x 17 : G= 8, B= 7 (11 6 3 2 2 3 2)
14 x 17 : G= 8, B= 7 (10 4 4 2 2 7 7)
15 x 17 : G=10, B= 8 (12 3 3 3 3 5 5 5)
16 x 17 : G=17, B= 8 (10 6 6 7 3 1 5 4)
15 x 18 : G= 6, B= 5 (9 6 6 9 6)
16 x 18 : G= 9, B= 7 (10 6 4 2 2 8 8)
17 x 18 : G=18, B= 8 (9 8 8 9 2 2 2 2)
  6 x 19 : G= 9, B= 7 (6 6 4 2 2 3 3)
  9 x 19 : G=11, B= 7 (9 5 4 4 5 2 2)
10 x 19 : G=11, B= 7 (10 5 5 4 4 2 2)
13 x 19 : G= 9, B= 7 (13 6 4 3 3 2 2)
14 x 19 : G= 8, B= 7 (8 6 6 4 4 7 7)
15 x 19 : G= 8, B= 7 (10 5 5 9 6 3 3)
16 x 19 : G= 9, B= 7 (10 6 6 9 1 1 7)
17 x 19 : G=11, B= 9 (12 5 5 2 3 7 7 3 3)
18 x 19 : G=19, B= 7 (11 7 7 8 3 5 5)
  7 x 20 : G= 9, B= 7 (7 7 4 3 3 2 2)
13 x 20 : G= 9, B= 7 (13 7 4 2 2 3 3)
17 x 20 : G= 9, B= 7 (11 6 6 9 1 1 8)
18 x 20 : G=10, B= 6 (10 8 8 10 4 4)
19 x 20 : G=20, B= 9 (15 4 4 4 4 5 5 5 4)
  5 x 21 : G= 9, B= 8 (5 5 5 3 2 2 3 2)
10 x 21 : G=12, B= 7 (10 6 4 2 2 5 5)
11 x 21 : G=12, B= 7 (11 6 5 5 4 2 2)
16 x 21 : G= 9, B= 8 (16 5 5 3 3 2 2 2)
18 x 21 : G= 7, B= 5 (12 6 6 9 9)
19 x 21 : G=12, B= 7 (11 8 4 4 10 1 9)
20 x 21 : G=21, B= 8 (14 6 6 6 7 7 3 3)
  7 x 22 : G=10, B= 9 (7 7 4 3 3 4 2 1 1)
10 x 22 : G= 7, B= 6 (10 6 4 4 6 4)
12 x 22 : G= 7, B= 6 (12 6 6 4 4 4)
15 x 22 : G=10, B= 8 (12 3 3 3 3 10 5 5)
19 x 22 : G=10, B= 8 (11 8 8 11 6 2 2 2)
20 x 22 : G=11, B= 6 (12 8 4 4 10 10)
21 x 22 : G=22, B= 8 (15 6 6 3 3 7 7 7)
  6 x 23 : G= 9, B= 8 (6 6 6 3 3 2 2 2)
  8 x 23 : G=10, B= 9 (8 8 4 4 3 3 2 1 1)
11 x 23 : G=13, B= 8 (11 8 3 3 3 4 4 3)
12 x 23 : G=13, B= 8 (12 8 4 4 3 3 3 3)
15 x 23 : G=10, B= 8 (9 6 6 9 6 5 5 5)
17 x 23 : G= 9, B= 8 (17 6 6 3 2 2 3 2)
20 x 23 : G=10, B= 8 (15 5 5 5 8 8 4 4)
21 x 23 : G=13, B= 8 (14 7 7 9 9 3 3 3)
22 x 23 : G=23, B= 8 (12 6 4 4 6 4 11 11)
11 x 24 : G= 9, B= 7 (11 7 4 4 6 1 5)
13 x 24 : G= 9, B= 7 (13 7 6 1 5 4 4)
20 x 24 : G= 6, B= 5 (12 8 8 12 8)
21 x 24 : G= 8, B= 7 (12 9 9 12 6 3 3)
22 x 24 : G=12, B= 7 (16 6 6 6 8 8 6)
23 x 24 : G=24, B= 8 (15 8 8 9 6 8 3 3)
  6 x 25 : G=10, B= 8 (6 6 6 4 2 2 3 3)
  8 x 25 : G=11, B= 9 (8 8 5 3 2 1 1 4 4)
12 x 25 : G=14, B= 8 (12 9 3 3 3 4 4 4)
13 x 25 : G=14, B= 8 (13 9 4 4 4 3 3 3)
17 x 25 : G=11, B= 9 (17 8 5 4 4 3 2 1 1)
19 x 25 : G=10, B= 8 (19 6 6 4 3 3 2 2)
21 x 25 : G=10, B= 8 (13 8 8 12 1 1 1 9)
22 x 25 : G=11, B= 8 (14 8 6 2 2 2 11 11)
23 x 25 : G=14, B= 8 (17 6 6 6 8 8 1 7)
24 x 25 : G=25, B= 8 (16 8 8 9 9 6 3 3)
  5 x 26 : G=10, B= 9 (5 5 5 5 3 2 2 3 2)
  9 x 26 : G=11, B= 9 (9 9 5 4 4 3 2 1 1)
12 x 26 : G= 8, B= 6 (12 8 4 4 6 6)
14 x 26 : G= 8, B= 6 (14 8 6 6 4 4)
17 x 26 : G=11, B= 9 (17 9 5 3 2 1 1 4 4)
21 x 26 : G=10, B= 8 (14 7 7 12 9 3 3 3)
22 x 26 : G= 8, B= 6 (14 8 8 12 2 10)
23 x 26 : G=11, B= 8 (13 10 10 13 6 4 2 2)
24 x 26 : G=13, B= 7 (18 6 6 6 8 8 8)
25 x 26 : G=26, B= 8 (13 12 8 4 13 4 6 6)
  7 x 27 : G=10, B= 8 (7 7 7 4 3 3 2 2)
11 x 27 : G= 9, B= 8 (11 11 5 3 3 2 2 2)
13 x 27 : G=15, B= 8 (13 7 6 6 7 2 2 2)
14 x 27 : G=15, B= 8 (14 7 7 6 6 2 2 2)
16 x 27 : G= 9, B= 8 (16 11 5 3 2 2 3 2)
20 x 27 : G=10, B= 8 (20 7 7 4 2 2 3 3)
22 x 27 : G= 9, B= 8 (16 6 6 4 2 2 11 11)
23 x 27 : G=10, B= 8 (16 7 7 7 11 5 6 6)
24 x 27 : G= 9, B= 7 (15 9 6 3 3 12 12)
25 x 27 : G=15, B=10 (14 11 3 3 5 13 7 5 6 6)
26 x 27 : G=27, B= 8 (14 8 4 4 6 6 13 13)
  9 x 28 : G=12, B= 8 (9 9 5 4 4 5 2 2)
11 x 28 : G= 9, B= 8 (11 11 6 3 2 2 3 2)
13 x 28 : G=10, B= 9 (13 10 3 3 3 3 5 5 3)
15 x 28 : G=10, B= 8 (10 5 5 9 6 6 9 6)
17 x 28 : G= 9, B= 8 (17 11 6 3 3 2 2 2)
19 x 28 : G=12, B= 8 (19 9 5 5 4 4 2 2)
24 x 28 : G= 7, B= 5 (16 8 8 12 12)
25 x 28 : G=12, B=10 (16 9 9 12 4 2 2 5 8 5)
26 x 28 : G=14, B= 7 (14 12 12 14 4 4 4)
27 x 28 : G=28, B= 8 (17 10 10 11 3 3 8 8)
  6 x 29 : G=10, B= 9 (6 6 6 6 3 3 2 2 2)
  7 x 29 : G=11, B=10 (7 7 7 4 3 3 4 2 1 1)
10 x 29 : G=12, B= 8 (10 10 5 5 4 4 2 2)
14 x 29 : G=16, B= 8 (14 9 5 5 6 3 5 3)
15 x 29 : G=16, B= 8 (15 9 6 3 3 5 5 5)
19 x 29 : G=12, B= 8 (19 10 5 4 4 5 2 2)
22 x 29 : G=11, B= 9 (18 4 4 4 4 2 2 11 11)
23 x 29 : G=10, B= 9 (23 6 6 6 3 2 2 3 2)
25 x 29 : G=11, B=10 (15 10 2 8 2 1 1 14 3 11)
26 x 29 : G=12, B= 8 (16 10 6 4 2 2 13 13)
27 x 29 : G=16, B= 8 (16 11 11 13 3 3 7 7)
28 x 29 : G=29, B= 9 (21 7 7 7 8 8 8 4 4)
14 x 30 : G= 9, B= 8 (14 8 6 6 8 4 2 2)
16 x 30 : G= 9, B= 8 (16 8 8 6 6 4 2 2)
25 x 30 : G= 6, B= 5 (15 10 10 15 10)
26 x 30 : G= 9, B= 8 (20 6 6 6 6 10 10 6)
27 x 30 : G=10, B= 6 (15 12 12 15 6 6)
28 x 30 : G=15, B= 7 (18 10 10 12 6 10 6)
29 x 30 : G=30, B= 9 (20 9 9 9 10 10 3 3 3)
  5 x 31 : G=11, B=10 (5 5 5 5 5 3 2 2 3 2)
  6 x 31 : G=11, B= 9 (6 6 6 6 4 2 2 3 3)
  8 x 31 : G=11, B=10 (8 8 8 4 4 3 3 2 1 1)
10 x 31 : G=13, B= 8 (10 10 6 4 2 2 5 5)
14 x 31 : G= 9, B= 8 (14 10 4 4 2 2 7 7)
15 x 31 : G=17, B= 8 (15 10 5 5 6 6 3 3)
16 x 31 : G=17, B= 8 (16 10 6 6 5 5 3 3)
17 x 31 : G= 9, B= 8 (17 10 7 7 4 4 2 2)
21 x 31 : G=13, B= 8 (21 10 6 5 5 4 2 2)
22 x 31 : G= 9, B= 8 (12 10 10 8 4 4 11 11)
23 x 31 : G=11, B= 8 (12 11 11 12 2 9 7 7)
24 x 31 : G= 9, B= 8 (16 8 8 15 9 6 3 3)
25 x 31 : G=11, B= 8 (17 8 8 4 4 14 3 11)
26 x 31 : G=11, B= 8 (15 11 11 8 7 9 9 8)
27 x 31 : G=11, B=10 (16 11 3 8 3 15 1 2 2 12)
28 x 31 : G=13, B= 8 (16 12 6 6 15 1 1 13)
29 x 31 : G=17, B= 8 (19 10 10 12 6 1 11 6)
30 x 31 : G=31, B= 8 (17 13 4 9 14 7 9 7)
---------------------------------------------------------------------------
Data una riga ad esempio 17 x 20 : G = 9, B = 7 ( 11 6 6 9 1 1 8 )
consideriamo una griglia di quadratini di 17 righe e 20 colonne.
Stabiliamo un ordinameto dei quadratini per cui se due quadratini
stanno in due colonne diverse viene prima quello con la colonna
minore. Se stanno nella stessa colonna viene prima quello con la
riga minore.
La lista di numeri fra parentesi rappresenta i lati dei quadrati
che compongono il ricoprimento. Vanno inseriti nella griglia nell'ordine
in cui compaiono, ogni volta mettendo l'angolo in alto a sinistra del
quadrato nel primo (rispetto all'ordinamento di cui sopra) quadratino
libero della griglia.
ciao,
g.

 a rettangoli differenti...
E' estensibile per esempio al rettangolo 8*15 , con tre quadrati 5*5 e
cinque quadrati 3*3; quindi otto quadrati complessivamente contro i nove che
si avrebbero con il sistema "greedy".
In genere direi che questo tipo di ricoprimento si può applicare quando il
lato minore è somma di due (o più) divisori del lato maggiore.
Notare che i "divisori" non devono necessariamente essere interi. Per
esempio nel rettango 4*15, il lato minore è somma di 2.5+1.5, entrambi
divisori di 15; potremmo usare dieci quadrati da 1.5*1.5 e sei quadrati
2.5*2.5.
In questo caso però il ricoprimento non è economico.
ciao
paolo

 procedurina ricorsiva, che mi dice anche che quadrati servono.
L'algoritmo "greedy" funziona sempre, ma non è detto che dia il numero
minore di quadrati. Già con un rettangolo 5x6 il tuo procedimento
termina con 6 quadrati (uno 5x5 e cinque 1x1) mentre se ne usano di meno
ricoprendo con due quadrati 3x3 e tre quadrati 2x2.
Maurizio

 28 x 30 : G=15, B= 7 (18 10 10 12 6 10 6)
E quanto detto è chiaramente vero anche quando i ricoprimenti "best"
coincidono con quelli "greedy".
Tuttavia dimostrare che ciò avviene sempre per i ricoprimenti "best" mi pare
che non sia facilissimo...
Ciao!!
Marco

 non-banale vi propongo anche questo:
Ma l'abbiamo risolto? Non me n'ero accorto.  :o)
Tu scrivevi:
"Abbiamo un rettangolo di lati mxn (interi) e vogliamo ricoprirlo con
quadrati.
Diciamo che il ricoprimento è "non-banale" se i quadrati che usiamo
hanno tutti il lato maggiore del massimo comun divisore tra m e n
(perchè se potessimo usare quadrati di quella dimensione sarebbe
banale ricoprire il rettangolo)."
E noi si e' cominciato a fare ipotesi del genere:
"Mi restringo al caso in cui m e n sono primi tra loro.
Ovvero voglio trovare una ricopertura che non usi il quadratino 1x1."
[Giovanni Resta e anch'io]
Ora, se prendiamo uno di questi rettangoli minimali banali e lo
moltiplichiamo per k, chi mi dice che resta banale?
Casi semplici e piccoli che ho provato sono restati banali, ma
per k grande e' probabile che le sommatorie di molti quadrati
diano soluzioni non-banali.
O no?
Ciao!!!  ((^__^))'
Livio

 O no?
Hai ragione !!
Per esempio 7x8 e' banale ma 14x16 direi che si puo'
fare con 11 quadrati di lato maggiore o uguale a 3.
Se a qualcuno interessa oggi pomeriggio metto in linea
(non li posto qui)
i risultati fino a rettangoli 63x63 e il codice
in C commentato per trovare i due tipi di coperture
(minimali di quadrati qualsiasi, e nonbanali)
che abbiamo trattato in questo thread.
ciao.
g.

 che abbiamo trattato in questo thread.
Mi interessa!
Ciao!!!  ((^__^))'
Livio

 (con il vecchio solver di Gerard Putter)
Interessante... Come mi posso procurare questo solver?
Grazie!
Ciao!!
Marco

Ho messo in linea all'indirizzo
http://www.imc.pi.cnr.it/resta/rettangoli/
i seguenti file che mi dispiace sono solo testuali,
(quindi non sono belli come quelli del (per me mitico) Livio Zucca.
Per le coperture minime:-----------------------------------------------
108k ricoperture.html      file con le coperture minime fino a 49x50
7.0k ricoperture.html.zip  lo stesso file zippato
  23k ricopri.c.html        il file C commentato (commenti a colori)
2.2k ricopri.c.zip         il file C zippato (file di testo EOL linux)
Per le coperture non banali:------------------------------------------
142k nonbanale.html        coperture non banali minime a 39x40
7.9k nonbanale.html.zip    lo stesso file zippato
  36k nonbana.c.html        il file C commentato (commenti a colori)
2.8k nonbana.c.zip         il file C zippato (file di testo EOL linux)
-----------------------------------------------------------------------
Volevo arrivare a dimensioni maggiori ma ho avuto qualche
contrattempo (e in ogni caso il programma ricopri andrebbe
leggermento modificato come indico in cima al programma),
magari successivamente....
ciao,
g.

 i seguenti file che mi dispiace sono solo testuali,
Volevo segnalare un errore (penso solo nella versione html)
del file nonbana.c (nonbana.c.html).
La riga che contiene l'istruzione
usati--;
va cancellata.
ciao.
g

 Grazie!
Puoi tirarlo giu' dal mio sito a questa pagina:
http://www.geocities.com/liviozuc/pmf4.html
insieme ad un mio piccolo aiuto Windows, approvato da
Gerard, che rende meno ostico l'uso del suo applet Java
del 1998.
Devo pero' avvertirti che nel frattempo ne han fatti di piu'
potenti. Qualcuno del ng potra' esserti piu' preciso di me,
perche' io mi sono caparbiamente ed irrazionalmente
affezionato a questo.
Ciao Lord!!!  ((^__^))'
Livio