一个人民币的等效转换问题!欢迎积极思考发言!

malloc

将一元钱换为等值的1分,2分,5分的硬币,一共有多少种换法?并详细列出每一种方法(即1分,2分,5分硬币的枚数)
共分以下7类情况讨论:
(1)全部换为1分的硬币.
(2)全部换为2分的硬币.
(3)全部换为5分的硬币.
(4)换为1分与2分相组合的硬币.
(5)换为1分与5分相组合的硬币.
(6)换为2分与5分相组合的硬币.
(7)换为1分,2分,5分相组合的硬币.
欢迎大家积极思考!

[ 本帖最后由 malloc 于 07-5-29 13:43 编辑 ]

malloc

对于学理工科的来讲,这个应该不难,仔细考虑!

malloc

one---two---five
0     0     20   
0     5     18   
0     10    16   
0     15    14   
0     20    12   
0     25    10   
0     30    8     
0     35    6     
0     40    4     
0     45    2     
0     50    0     
1     2     19   
1     7     17   
1     12    15   
1     17    13   
1     22    11   
1     27    9     
1     32    7     
1     37    5     
1     42    3     
1     47    1     
2     4     18   
2     9     16   
2     14    14   
2     19    12   
2     24    10   
2     29    8     
2     34    6     
2     39    4     
2     44    2     
2     49    0     
3     1     19   
3     6     17   
3     11    15   
3     16    13   
3     21    11   
3     26    9     
3     31    7     
3     36    5     
3     41    3     
3     46    1     
4     3     18   
4     8     16   
4     13    14   
4     18    12   
4     23    10   
4     28    8     
4     33    6     
4     38    4     
4     43    2     
4     48    0     
5     0     19   
5     5     17   
5     10    15   
5     15    13   
5     20    11   
5     25    9     
5     30    7     
5     35    5     
5     40    3     
5     45    1     
6     2     18   
6     7     16   
6     12    14   
6     17    12   
6     22    10   
6     27    8     
6     32    6     
6     37    4     
6     42    2     
6     47    0     
7     4     17   
7     9     15   
7     14    13   
7     19    11   
7     24    9     
7     29    7     
7     34    5     
7     39    3     
7     44    1     
8     1     18   
8     6     16   
8     11    14   
8     16    12   
8     21    10   
8     26    8     
8     31    6     
8     36    4     
8     41    2     
8     46    0     
9     3     17   
9     8     15   
9     13    13   
9     18    11   
9     23    9     
9     28    7     
9     33    5     
9     38    3     
9     43    1     
10    0     18   
10    5     16   
10    10    14   
10    15    12   
10    20    10   
10    25    8     
10    30    6     
10    35    4     
10    40    2     
10    45    0     
11    2     17   
11    7     15   
11    12    13   
11    17    11   
11    22    9     
11    27    7     
11    32    5     
11    37    3     
11    42    1     
12    4     16   
12    9     14   
12    14    12   
12    19    10   
12    24    8     
12    29    6     
12    34    4     
12    39    2     
12    44    0     
13    1     17   
13    6     15   
13    11    13   
13    16    11   
13    21    9     
13    26    7     
13    31    5     
13    36    3     
13    41    1     
14    3     16   
14    8     14   
14    13    12   
14    18    10   
14    23    8     
14    28    6     
14    33    4     
14    38    2     
14    43    0     
15    0     17   
15    5     15   
15    10    13   
15    15    11   
15    20    9     
15    25    7     
15    30    5     
15    35    3     
15    40    1     
16    2     16   
16    7     14   
16    12    12   
16    17    10   
16    22    8     
16    27    6     
16    32    4     
16    37    2     
16    42    0     
17    4     15   
17    9     13   
17    14    11   
17    19    9     
17    24    7     
17    29    5     
17    34    3     
17    39    1     
18    1     16   
18    6     14   
18    11    12   
18    16    10   
18    21    8     
18    26    6     
18    31    4     
18    36    2     
18    41    0     
19    3     15   
19    8     13   
19    13    11   
19    18    9     
19    23    7     
19    28    5     
19    33    3     
19    38    1     
20    0     16   
20    5     14   
20    10    12   
20    15    10   
20    20    8     
20    25    6     
20    30    4     
20    35    2     
20    40    0     
21    2     15   
21    7     13   
21    12    11   
21    17    9     
21    22    7     
21    27    5     
21    32    3     
21    37    1     
22    4     14   
22    9     12   
22    14    10   
22    19    8     
22    24    6     
22    29    4     
22    34    2     
22    39    0     
23    1     15   
23    6     13   
23    11    11   
23    16    9     
23    21    7     
23    26    5     
23    31    3     
23    36    1     
24    3     14   
24    8     12   
24    13    10   
24    18    8     
24    23    6     
24    28    4     
24    33    2     
24    38    0     
25    0     15   
25    5     13   
25    10    11   
25    15    9     
25    20    7     
25    25    5     
25    30    3     
25    35    1     
26    2     14   
26    7     12   
26    12    10   
26    17    8     
26    22    6     
26    27    4     
26    32    2     
26    37    0     
27    4     13   
27    9     11   
27    14    9     
27    19    7     
27    24    5     
27    29    3     
27    34    1     
28    1     14   
28    6     12   
28    11    10   
28    16    8     
28    21    6     
28    26    4     
28    31    2     
28    36    0     
29    3     13   
29    8     11   
29    13    9     
29    18    7     
29    23    5     
29    28    3     
29    33    1     
30    0     14   
30    5     12   
30    10    10   
30    15    8     
30    20    6     
30    25    4     
30    30    2     
30    35    0     
31    2     13   
31    7     11   
31    12    9     
31    17    7     
31    22    5     
31    27    3     
31    32    1     
32    4     12   
32    9     10   
32    14    8     
32    19    6     
32    24    4     
32    29    2     
32    34    0     
33    1     13   
33    6     11   
33    11    9     
33    16    7     
33    21    5     
33    26    3     
33    31    1     
34    3     12   
34    8     10   
34    13    8     
34    18    6     
34    23    4     
34    28    2     
34    33    0     
35    0     13   
35    5     11   
35    10    9     
35    15    7     
35    20    5     
35    25    3     
35    30    1     
36    2     12   
36    7     10   
36    12    8     
36    17    6     
36    22    4     
36    27    2     
36    32    0     
37    4     11   
37    9     9     
37    14    7     
37    19    5     
37    24    3     
37    29    1     
38    1     12   
38    6     10   
38    11    8     
38    16    6     
38    21    4     
38    26    2     
38    31    0     
39    3     11   
39    8     9     
39    13    7     
39    18    5     
39    23    3     
39    28    1     
40    0     12   
40    5     10   
40    10    8     
40    15    6     
40    20    4     
40    25    2     
40    30    0     
41    2     11   
41    7     9     
41    12    7     
41    17    5     
41    22    3     
41    27    1     
42    4     10   
42    9     8     
42    14    6     
42    19    4     
42    24    2     
42    29    0     
43    1     11   
43    6     9     
43    11    7     
43    16    5     
43    21    3     
43    26    1     
44    3     10   
44    8     8     
44    13    6     
44    18    4     
44    23    2     
44    28    0     
45    0     11   
45    5     9     
45    10    7     
45    15    5     
45    20    3     
45    25    1     
46    2     10   
46    7     8     
46    12    6     
46    17    4     
46    22    2     
46    27    0     
47    4     9     
47    9     7     
47    14    5     
47    19    3     
47    24    1     
48    1     10   
48    6     8     
48    11    6     
48    16    4     
48    21    2     
48    26    0     
49    3     9     
49    8     7     
49    13    5     
49    18    3     
49    23    1     
50    0     10   
50    5     8     
50    10    6     
50    15    4     
50    20    2     
50    25    0     
51    2     9     
51    7     7     
51    12    5     
51    17    3     
51    22    1     
52    4     8     
52    9     6     
52    14    4     
52    19    2     
52    24    0     
53    1     9     
53    6     7     
53    11    5     
53    16    3     
53    21    1     
54    3     8     
54    8     6     
54    13    4     
54    18    2     
54    23    0     
55    0     9     
55    5     7     
55    10    5     
55    15    3     
55    20    1     
56    2     8     
56    7     6     
56    12    4     
56    17    2     
56    22    0     
57    4     7     
57    9     5     
57    14    3     
57    19    1     
58    1     8     
58    6     6     
58    11    4     
58    16    2     
58    21    0     
59    3     7     
59    8     5     
59    13    3     
59    18    1     
60    0     8     
60    5     6     
60    10    4     
60    15    2     
60    20    0     
61    2     7     
61    7     5     
61    12    3     
61    17    1     
62    4     6     
62    9     4     
62    14    2     
62    19    0     
63    1     7     
63    6     5     
63    11    3     
63    16    1     
64    3     6     
64    8     4     
64    13    2     
64    18    0     
65    0     7     
65    5     5     
65    10    3     
65    15    1     
66    2     6     
66    7     4     
66    12    2     
66    17    0     
67    4     5     
67    9     3     
67    14    1     
68    1     6     
68    6     4     
68    11    2     
68    16    0     
69    3     5     
69    8     3     
69    13    1     
70    0     6     
70    5     4     
70    10    2     
70    15    0     
71    2     5     
71    7     3     
71    12    1     
72    4     4     
72    9     2     
72    14    0     
73    1     5     
73    6     3     
73    11    1     
74    3     4     
74    8     2     
74    13    0     
75    0     5     
75    5     3     
75    10    1     
76    2     4     
76    7     2     
76    12    0     
77    4     3     
77    9     1     
78    1     4     
78    6     2     
78    11    0     
79    3     3     
79    8     1     
80    0     4     
80    5     2     
80    10    0     
81    2     3     
81    7     1     
82    4     2     
82    9     0     
83    1     3     
83    6     1     
84    3     2     
84    8     0     
85    0     3     
85    5     1     
86    2     2     
86    7     0     
87    4     1     
88    1     2     
88    6     0     
89    3     1     
90    0     2     
90    5     0     
91    2     1     
92    4     0     
93    1     1     
94    3     0     
95    0     1     
96    2     0     
98    1     0     
100   0     0     
The number of method changing the coinage:541
其实数学上也可以推导的,当然不像计算机这么去一一穷举,那样太费劲了,有兴趣的可以讨论:"如何通过数学推导得出有多少种换法?",快12：00了,我要去吃饭了!

starlamb

哇！青松。。你发的帖子还真不“轻松”。哈
还需要绞尽脑汁才能想。。。。
我虽然很喜欢数学，不过，看见你的帖子的号码。。。让我懒得动脑筋了。。。

malloc

确实不“轻松“，就写了那么一小段程序。
我之所以要拿出来讨论，就是想寻求更好的数学方法，想在程序中发挥数学的威力，提高程序运行效率。毕竟穷举对于计算机来说是比较耗时的！
如果想好了都可以把方法说出来讨论！数学推导过程与不涉及具体写代码，不是编程的也欢迎思考发言，参与的人能更多,多人的智慧往往强于独自一个人，我就想知道较好的数学方法。

[ 本帖最后由 malloc 于 07-6-8 09:07 编辑 ]

malloc

有好的算法,欢迎指点!

[ 本帖最后由 malloc 于 07-6-8 09:12 编辑 ]

malloc

从表面上看似乎要用到组合(Combine),但仔细观察会发现情况太多，运用组合来求解将会很费力。因此我采用数学推导:
设1分，2分，5分的硬币枚数各为X,Y,Z,将得出公式:
  X+2*Y+5*Z=100
(1)当Y,Z为0时，X=100,所以X的取值范围：[0,100]
(2)当X,Z为0时,Y=50,所以Y的取值范围：[0,50]
(3)当X,Y为0时,Z＝20,所以Z的取值范围:[0,20]
并且X,Y,Z均为整数。
由于Z最小,因此我就以Z来枚举观察其规律:
(1)当Z=0时,X+2*Y=100---->Y=(100-X)/2
要使Y为整数,100-X必须为偶数,即X必须为偶数,0--100之间的偶数有:100/2+1=51个
(2)当Z=1时,X+2*Y=95---->Y=(95-X)/2:
要使Y为整数,95-X必须为偶数,即X必须为奇数,0---95之间的奇数有:94/2+1=48个
(3)当Z=2时,X+2*Y=90--->Y=(90-X)/2
要使Y为整数,90-X必须为偶数,即X必须为偶数,0--90之间的偶数有:90/2+1=46个(比(1)少了5个)
(4)当Z=3时,X+2*Y=85---->Y=(85-X)/2
要使Y为整数,85-X必须为偶数,即X必须为奇数,0---85之间的奇数有:84/2+1=43个(比(2)少了5个)
......
此时我们可以得出规律:
(1)当Z为偶数时，X必然为偶数.当Z为奇数时,X必然为奇数
(2)当Z从0--20递增时,偶数和奇数间隔出现,每当Z增加2时,X的偶数或奇数个数比上次减少了5
根据这一规律我们可以得出两组等差数列:
51,46,41,36,31,26,21,16,11,6,1
48,43,38,33,28,23,18,13,8,3
将其求和可以得出Z从0--20递增时,X的奇数及偶数的总和,该值即为换法的总数:
(51+46+....6+1)+(48+43+...+8+3)
=11*(51+1)/2+10*(48+3)/2
=541
这是我目前的思路.
有好的想法欢迎发言!

散打

这还叫简单!我头都看大了!
楼主太假打了!

碧草青青

都是数学牛人。

malnu

嗯～哼～我还是撤吧。