In quanti modi diversi si può
dare il resto di
?
esempio:
oppure
CASO FACILE:
SOLO MONETE DA
In quanti modi diversi si può dare il
resto di
0 centesimi
1
centesimo
2 centesimi
3 centesimi
4 centesimi
5 centesimi
CONVENZIONE
2
=
5
=
=
0
In quanti modi diversi si può dare il
resto di
0
0 centesimi
1
1
centesimo
2
2 centesimi
3
3 centesimi
4
4 centesimi
1
+
3
2
+
+
4
+
+
0
....
0
+ 1
A=1
A=
A0
A0
A1
=
A2
A3
A4
=
=
=
1
1
1
1
1
0
+ A1
1
+ 1
1
+ A2
2
+ 1
3
+ 1
2
+ A3
4
+ ....
3
+ A4
4
+ ...
=
A=1
0
+ 1
A=1
0
+
A=
0
+
1
1
+ 1
(1
A
2
+ 1
0
+ 1
3
+ 1
1
+ 1
4
+ ....
2
+ 1
3
+ ..
A=
A0
0
+
1
0
+ A1
A
1
+ A2
2
+ A3
3
+ A4
4
+ ....
11
+ AA12
22
++ A 23
3
+ A 34
4
++ .......
0
1
A0
0
+ A
A 01
3
A0
A1
A2
=
A3
A4
=
=
=
1
1
1
1
1
A0
=
1
An
=
A n-1
=
CASO PIÙ DIFFICILE:
SOLO MONETE DA
(A
(A
(A
0
1
0
+ 1
1
+ 1
2
+ 1
3
+ 1
4
+
1
0
+ 1
1
+ 1
2
+ 1
3
+ 1
4
+
1
2
1
0
+ 1
1
+ 1
2
+ 1
3
+ 1
4
+
)
)
)
0
B=
A+
0
B=
A+
1
A+
(
0
B=
A+
2
B
3
A+
0
A+
A+
1
A+
)
2
(
A A0
0
+ A1
A2
1
+ A2
2
+ A3
3
+
modi di cambiare 4+2 centesimi
con esattamente 2 monete da
)
0
B=
A+
B
B0
0
+ B1
1
+ B2
2
+ B3
3
+ B4
4
+ ....
A0
0
+ A1
1
+ A2
2
+ A3
3
+ A4
4
+ ....
B0
0
+ B1
1
+ B 02
22
+
+ B
B 31
3
3
+
+ BB42
44
++ .... ....
B n = An + Bn-2
Bn= 0
n< 0
Esempio
B n = A n + B n-2
B 5 = A5 + B 3
= 1 + B3
B 3 = A3 + B 1
= 1 + B1
B 1 = A1 + B -1 = 1 + 0
B5 = 3
SOLO MONETE DA
0
C=
1
B+
2
B+
3
B+
B+
0
C=
B+
Cn = Bn + Cn-5
C
Cn= 0
n< 0
0
D=
1
C+
2
C+
3
C+
C+
0
D=
C+
Dn = Cn + Dn-10
D
Dn= 0
n< 0
0
E=
1
D+
2
D+
3
D+
D+
0
E=
D+
E n = D n + En-20
E
En= 0
n< 0
0
F=
1
E+
2
E+
3
E+
E+
0
F=
E+
F n = E n + F n-50
F
F n= 0
n< 0
F 100 = E100 + F 50 =
D100 + E 80 + E50 + F 0 =
C100 + D 90 + D80 + E 60 + D 50 + E 30 + 1 =
...................................
F 100 = 4562