筹码的面值怎样设计最好

没看清题

路过

这道题，采用咱一贯使用的乌龟爬行的方法，非常的笨，一步一步，我相信：野百合也有春天。所以这种方法，最终也能找到答案，而且是最不伤神的方法。

先说说思路：老陈这个题，看起来不露痕迹，真做起来有无从下手的感觉，我只能从实验方法下手。

我的思路如下：

1） 当N越来越大的时候，显然筹码的种类要增多，那么当N大到什么程度的时候需要增多筹码的种类？

2） 首先考虑最简单的情形，当筹码种类 C = 2的时候，当N增加的时候，要求乘积和（与和的乘积等价）最小，有何规律？这个规律的指导意义极大。

3） 当N固定为一个数值的时候，筹码种类C =2 的时候，可以找出这2种筹码里最优的筹码面值，比如N=48的时候，面值（1,7）的这两种筹码满足老陈的要求，那么是否存在C=3的筹码面值比（1,7）的乘积是否更小？

4）当N和C以及相应的筹码面值的规律找出来的时候，那么这个解就找出来了。

个人觉得，不熟悉的话，理论推导的工作量非常的大，实验方法最好，最好的方法就是编程解决，又干净又漂亮，当找到规律后，再反过来理论推导。

dfu2012 发表于 2012-12-20 11:58
这道题，采用咱一贯使用的乌龟爬行的方法，非常的笨，一步一步，我相信：野百合也有春天。所以这种方法，最 ...

按照我的推到N=48, 两种筹码然后用1，7是最优

我的跟帖一向不简洁，所以先请老陈原谅下，下面是我用EXCEL做的当筹码种类固定C=2的时候，不同筹码面值在N不同的时候，乘积和的数值，我试图从中找出规律。

可能下面的数值会乱，先贴出来看看，数值看起来很多，其实就是调整下公式，N=10万也是1秒的事

N的值        SUM        sum(3)        sum(4)        sum(5)        SUM(6)        SUM(7)        SUM(8)        SUM(9)        sum(10)        SUM(11)        SUM(12)
1        1        1        1        1        1        1        1        1        1        1        1
2        3        3        3        3        3        3        3        3        3        3        3
3        6        4        6        6        6        6        6        6        6        6        6
4        10        6        7        10        10        10        10        10        10        10        10
5        15        9        9        11        15        15        15        15        15        15        15
6        21        11        12        13        16        21        21        21        21        21        21
7        28        14        16        16        18        22        28        28        28        28        28
8        36        18        18        20        21        24        29        36        36        36        36
9        45        21        21        25        25        27        31        37        45        45        45
10        55        25        25        27        30        31        34        39        46        55        55
11        66        30        30        30        36        36        38        42        48        56        66
12        78        34        33        34        38        42        43        46        51        58        67
13        91        39        37        39        41        49        49        51        55        61        69
14        105        45        42        45        45        51        56        57        60        65        72
15        120        50        48        48        50        54        64        64        66        70        76
16        136        56        52        52        56        58        66        72        73        76        81
17        153        63        57        57        63        63        69        81        81        83        87
18        171        69        63        63        66        69        73        83        90        91        94
19        190        76        70        70        70        76        78        86        100        100        102
20        210        84        75        74        75        84        84        90        102        110        111
21        231        91        81        79        81        87        91        95        105        121        121
22        253        99        88        85        88        91        99        101        109        123        132
23        276        108        96        92        96        96        108        108        114        126        144
24        300        116        102        100        100        102        111        116        120        130        146
25        325        125        109        105        105        109        115        125        127        135        149
26        351        135        117        111        111        117        120        135        135        141        153
27        378        144        126        118        118        126        126        138        144        148        158
28        406        154        133        126        126        130        133        142        154        156        164
29        435        165        141        135        135        135        141        147        165        165        171
30        465        175        150        141        140        141        150        153        168        175        179
31        496        186        160        148        146        148        160        160        172        186        188
32        528        198        168        156        153        156        164        168        177        198        198
33        561        209        177        165        161        165        169        177        183        201        209
34        595        221        187        175        170        175        175        187        190        205        221
35        630        234        198        182        180        180        182        198        198        210        234
36        666        246        207        190        186        186        190        202        207        216        237
37        703        259        217        199        193        193        199        207        217        223        241
38        741        273        228        209        201        201        209        213        228        231        246
39        780        286        240        220        210        210        220        220        240        240        252
40        820        300        250        228        220        220        225        228        244        250        259
41        861        315        261        237        231        231        231        237        249        261        267
42        903        329        273        247        238        237        238        247        255        273        276
43        946        344        286        258        246        244        246        258        262        286        286
44        990        360        297        270        255        252        255        270        270        290        297
45        1035        375        309        279        265        261        265        275        279        295        309
46        1081        391        322        289        276        271        276        281        289        301        322
47        1128        408        336        300        288        282        288        288        300        308        336
48        1176        424        348        312        296        294        294        296        312        316        340
49        1225        441        361        325        305        301        301        305        325        325        345
50        1275        459        375        335        315        309        309        315        330        335        351
51        1326        476        390        346        326        318        318        326        336        346        358
52        1378        494        403        358        338        328        328        338        343        358        366
53        1431        513        417        371        351        339        339        351        351        371        375
54        1485        531        432        385        360        351        351        357        360        385        385
55        1540        550        448        396        370        364        364        364        370        390        396
56        1596        570        462        408        381        372        371        372        381        396        408
57        1653        589        477        421        393        381        379        381        393        403        421
58        1711        609        493        435        406        391        388        391        406        411        435
59        1770        630        510        450        420        402        398        402        420        420        450
60        1830        650        525        462        430        414        409        414        426        430        455
61        1891        671        541        475        441        427        421        427        433        441        461
62        1953        693        558        489        453        441        434        441        441        453        468
63        2016        714        576        504        466        450        448        448        450        466        476
64        2080        736        592        520        480        460        456        456        460        480        485
65        2145        759        609        533        495        471        465        465        471        495        495
66        2211        781        627        547        506        483        475        475        483        501        506
67        2278        804        646        562        518        496        486        486        496        508        518
68        2346        828        663        578        531        510        498        498        510        516        531
69        2415        851        681        595        545        525        511        511        525        525        545
70        2485        875        700        609        560        535        525        525        532        535        560
71        2556        900        720        624        576        546        540        540        540        546        576
72        2628        924        738        640        588        558        549        548        549        558        582
73        2701        949        757        657        601        571        559        557        559        571        589
74        2775        975        777        675        615        585        570        567        570        585        597
75        2850        1000        798        690        630        600        582        578        582        600        606
76        2926        1026        817        706        646        616        595        590        595        616        616
77        3003        1053        837        723        663        627        609        603        609        623        627
78        3081        1079        858        741        676        639        624        617        624        631        639
79        3160        1106        880        760        690        652        640        632        640        640        652
80        3240        1134        900        776        705        666        650        648        648        650        666
81        3321        1161        921        793        721        681        661        657        657        661        681
82        3403        1189        943        811        738        697        673        667        667        673        697
83        3486        1218        966        830        756        714        686        678        678        686        714
84        3570        1246        987        850        770        726        700        690        690        700        721
85        3655        1275        1009        867        785        739        715        703        703        715        729
86        3741        1305        1032        885        801        753        731        717        717        731        738
87        3828        1334        1056        904        818        768        748        732        732        748        748
88        3916        1364        1078        924        836        784        759        748        748        756        759
89        4005        1395        1101        945        855        801        771        765        765        765        771
90        4095        1425        1125        963        870        819        784        775        774        775        784
91        4186        1456        1150        982        886        832        798        786        784        786        798
92        4278        1488        1173        1002        903        846        813        798        795        798        813
93        4371        1519        1197        1023        921        861        829        811        807        811        829
94        4465        1551        1222        1045        940        877        846        825        820        825        846
95        4560        1584        1248        1064        960        894        864        840        834        840        864
96        4656        1616        1272        1084        976        912        876        856        849        856        872
97        4753        1649        1297        1105        993        931        889        873        865        873        881
98        4851        1683        1323        1127        1011        945        903        891        882        891        891
99        4950        1716        1350        1150        1030        960        918        902        900        900        902
100        5050        1750        1375        1170        1050        976        934        914        910        910        914
101        5151        1785        1401        1191        1071        993        951        927        921        921        927
102        5253        1819        1428        1213        1088        1011        969        941        933        933        941
103        5356        1854        1456        1236        1106        1030        988        956        946        946        956
104        5460        1890        1482        1260        1125        1050        1001        972        960        960        972
105        5565        1925        1509        1281        1145        1065        1015        989        975        975        989

dfu2012 发表于 2012-12-20 12:19
我的跟帖一向不简洁，所以先请老陈原谅下，下面是我用EXCEL做的当筹码种类固定C=2的时候，不同筹码面值在N ...

{:soso_e110:} 无视我{:soso_e101:}  在我前面回复说了，c=2的时候最好推导，最后和是可以简化为最小化N/k+k，k是筹码面值。所以k=根号N。c=3的时候最后会简化为N/k^2+k, 这样k=N^1/3. 数学归纳法递推下去是k=N^1/c. 这样代入得到我写的和的公式，再求C去最小化这个和×C. 简化求导后C = CEILING(0.5*ln（N)). ln是自然对数。K=CEILING(N^1/C)

我很好奇这里是不是有很简单的解法，如果我做的即使是对的也确实比较复杂。

yyy6 发表于 2012-12-20 12:12
按照我的推到N=48, 两种筹码然后用1，7是最优

不急，我先验证完，我用的是笨办法。

似乎你的答案和我的计算有很细微的差别，我刚才好像也看错了。

（1,7）对应的N临界值似乎是47.其他类似，我再校验下。

上表中SUM是筹码面值=1的乘积和。

SUM(3)指筹码面值为1和3的时候的乘积和。这里令3为当C=2即种类为2的时候筹码面值C2=3 (C1=1)

很明显，当N=7,14,23,34,47,62,79,98的时候，对应的乘积和最小的C2=3,4,5,6,7,8,9,10.


这是非常有意识的结论，每一种筹码值都有自己的适应范围，
比如，当筹码面值是（1,3）的时候 N的临界值= C2^2-2=9-2=7，
当筹码面值是（1,4）的时候N的临界值=C2^2-2=16-2=14
其他类似，这是一个非常有规律的现象。

在C=2时候可以找到N值的最佳解，但还没有考虑C=3的情况，比如N=47的时候，当C=2的时候，显然（1,7）是最佳解，那么再找找C=3的时候的最佳解，

比较C=3和C=2的最佳解的乘积和大小，找出规律，通而广之，最后找到通解。找到通解后，再反过来理论推导。

我原来以为是N和N-1的关系，其实是筹码面值种类变化从2到3到4的规律变化，复杂不知道多少倍。

YY的解答太早了，没细看，如果要严谨推导的话，这个工作量可能非常的大，所以一开始就没有想着走这条路，当然，我感觉YY的答案可能是接近真相的解（没验证也没推导，只是感觉）。

仔细观察N值C=2的时候C2的变化，会发现，当N=特定值的时候，C2可以有几个解。即几种筹码方案都满足最小乘积和的要求。

yyy6 发表于 2012-12-20 12:29
无视我  在我前面回复说了，c=2的时候最好推导，最后和是可以简化为最小化N/ ...

C=2的时候比较好推导，我偷懒，所以用EXCEL。

C=3的时候，比如N=100，要严格证明（1，5,25）是C=3的时候的最优解，得证明它比（1,4,16）或者（1,5,10）等任意其它组合都好才行，要有严格的证明才行，我觉得麻烦。

然后要严格证明 C=3的时候的最优解比C=2的时候的最优解要好。

诸如此类的工作量实在繁杂，所以采用了实验的笨方法。

这也是我说的“野百合也有春天”的含义。

严格证明消耗的时间会非常的多，即便是EXCEL，黏贴写帖子等也非常的繁杂。

YY兄直指要害的方法实在让人佩服，这题初始我以为可以试试，老陈说清后仔细想才发现大汗淋漓，再然后用这笨方法，用笨方法找到规律然后找到通解，再从理论上慢慢证明，这样弯路会少很多。

dfu2012 发表于 2012-12-20 12:49
上表中SUM是筹码面值=1的乘积和。

SUM(3)指筹码面值为1和3的时候的乘积和。这里令3为当C=2即种类为2的时候 ...

你这个数据总结有问题，其实1-9的时候SUM(3)是最小的，10-16SUM(4)是最小的，17-25SUM(5)是最小的，这就是我说的根号N. N = K^2-2到K^2的时候会出现两种方案一样的情况，你归类到下一种去了。

不过这只是推导的第一步。理论不复杂，你知道C1是1，给定C2，列出对N的求和公式就完了，就是几个等差数列。简化后会看到N/C2+C2.

dfu2012 发表于 2012-12-20 13:02
C=2的时候比较好推导，我偷懒，所以用EXCEL。

C=3的时候，比如N=100，要严格证明（1，5,25）是C=3的时候 ...

嗯，N^1/C不是整数的时候而且C>3的情况是比较麻烦，C=3的时候我推过是N/K^2+K，后面递推就可以。但是你假设N很大的时候很多东西可以简化。