Tävlingsprogrammering/Uppgifter/Bokhyllor
Bokhyllor
Du ska köpa bokhyllor för att få plats med alla dina böcker. Du vet från början vilka
böcker du har och behöver räkna ut antalet bokhyllor som krävs. Böckerna har tre olika
storlekar: en liten bok tar 1 platsenhet, en mellanstor 2 och en stor bok tar 3 platsenheter.
Varje hylla rymmer ett visst antal platsenheter. Givet hur många böcker du har av
varje sort, skriv ett program som beräknar hur många hyllor du behöver om du vill ha
så få hyllor som möjligt. Antalet böcker av varje sort kommer vara högst 20.
Körningsexempel 1
Antal små ? 30 Antal mellan ? 0 Antal stora ? 0 Hyllstorlek ? 10 Antal hyllor: 3
Du sätter 10 små böcker på varje hylla.
Körningsexempel 2
Antal små ? 0 Antal mellan ? 0 Antal stora ? 10 Hyllstorlek ? 10 Antal hyllor: 4
Du sätter 3 stora böcker på 3 hyllor, och får tyvärr en hylla till med bara en bok i.
Körningsexempel 3
Antal små ? 8 Antal mellan ? 7 Antal stora ? 5 Hyllstorlek ? 15 Antal hyllor: 3
Körningsexempel 4
Antal små ? 1 Antal mellan ? 4 Antal stora ? 13 Hyllstorlek ? 7 Antal hyllor: 8
Lösning
redigeraProblemet blir enklare om man inser några fakta:
- Om du har tvåor kvar och det finns plats för en tvåa är det alltid bättre att sätta en tvåa än två ettor.
- Om du har ettor kvar och det finns plats för en etta är det alltid bättre att sätta en etta än att lämna tomt.
Däremot är det inte lika självklart om man ska sätta en tvåa eller en trea när det finns plats för vilket som. Man kan klura ut fler regler men man måste nog ändå testa några olika sätt.
Problemet kan lösas genom att man testar varje möjligt antal treor på en hylla (minst en trea måste man ta om man har kvar, för någon gång måste de ju sättas in). För varje val proppar man in övriga böcker enligt reglerna ovan, och sedan står man inför samma problem igen fast med färre antal böcker. Detta är alltså perfekt för en rekursiv funktion som anropar sig själv.
Exempellösning i C:
#include <stdio.h> int MIN(int p, int q) {return p<q?p:q;} int N; int antalhyllor(int n1, int n2, int n3) { //Hur många hyllor behövs om vi har n1 ettor, n2 tvåor och n3 treor kvar? int best=100000, i3,i2,i1,g1,g2; if(n1==0 && n2==0 && n3==0) return 0; //För 0 böcker behövs 0 hyllor g1=(n3>0)?1:0; //Minsta antalet treor att testa: 1 om vi har några kvar g2=MIN(n3,N/3); //Största antalet treor att testa for(i3=g1;i3<=g2;i3++) { //Loopa över antalet treor vi sätter in i2=MIN((N-i3*3)/2,n2); //Kläm in så många tvåor det går i1=MIN(N-i3*3-i2*2,n1); //Kläm in så många ettor det går best=MIN(best,1+antalhyllor(n1-i1,n2-i2,n3-i3)); //Rekursera. Om detta är det minsta antalet hittills så spara det i best } return best; } int main() { int ett,tva,tre; scanf("%d %d %d %d", &ett,&tva,&tre,&N); printf("%d\n",antalhyllor(ett,tva,tre)); return 0; }
Och som vi alla vet, är det Haskell som är kung på rekursiva funktioner.
-- Bokhyllor
module Main where
getInt = fmap read getLine :: IO Int
main = putStr "Antal sma ? " >> getInt >>= \low ->
putStr "Antal mellan ? " >> getInt >>= \mid ->
putStr "Antal stora ? " >> getInt >>= \big ->
putStr "Hyllstorlek ? " >> getInt >>= \hylla ->
putStrLn.("Antal hyllor: "++).show $ rek hylla low mid big
rek _ 0 0 0 = 0
rek n l m b = 1 + minimum [rek n (l-z) (m-y) (b-x) | x <- [s..min (div n 3) b], let (y,z) = (min m $ div (n-x*3) 2, min l $ n-x*3-y*2)]
where s = if b>0 then 1 else 0