Rekursiv problemlösning
Postat: 25 oktober 2015, 11:50:55
Min son hade en tenta igår med en fråga som gick ut på att bestämma antalet sätt det går att fördela poäng på ett tänkt prov.
Följande villkor gäller:
Det är 5 frågor.
Varje fråga kan ha antingen 1,2,3 eller 4 poäng för fullständigt korrekt svar.
Maxpoängen skall totalt bli 14 poäng.
Vi diskuterade saken efteråt eftersom han var sugen på att veta om han hade gjort rätt. Själv löste han det med kombinatorik på något vis som jag för länge sedan har glömt bort.
Jag gjorde ett rekursivt program i python eftersom jag tycker det är fasligt kul att göra sånt. Så tyckte jag att det blev lite elegant så jag tänkte att jag postar det här.
Programmet returnerar 135 vilket tydligen är rätt svar
Följande villkor gäller:
Det är 5 frågor.
Varje fråga kan ha antingen 1,2,3 eller 4 poäng för fullständigt korrekt svar.
Maxpoängen skall totalt bli 14 poäng.
Vi diskuterade saken efteråt eftersom han var sugen på att veta om han hade gjort rätt. Själv löste han det med kombinatorik på något vis som jag för länge sedan har glömt bort.
Jag gjorde ett rekursivt program i python eftersom jag tycker det är fasligt kul att göra sånt. Så tyckte jag att det blev lite elegant så jag tänkte att jag postar det här.
Kod: Markera allt
maxQuestionPoints = 4
def count_ways(available_points, questions_left):
if questions_left == 0:
# Last question. Count it if available points are exactly 0
return 1 if available_points == 0 else 0
count = 0
# Use 1-4 points on this question and count how many ways the
# rest of the questions can use exactly available points
for used_points in range(1,maxQuestionPoints+1):
count += count_ways(available_points - used_points, questions_left-1)
return count
print(count_ways(14, 5))
Programmet returnerar 135 vilket tydligen är rätt svar