智游城

标题: 筹码的面值怎样设计最好 [打印本页]

作者: 老陈 时间: 2012-12-19 19:58
标题: 筹码的面值怎样设计最好
本帖最后由老陈于 2012-12-19 08:04 编辑

我们玩扑克要用到多种筹码。
在Calgary 经常用到的有0,5$,1$,5$,25$,100$，有时也用500$,但很少使用。在拉斯维加斯，也见过2$、3$和20$的筹码。

下面我出一道题。
我们只考虑整数筹码，1，2，...N
这里N相当大
我们来设计一套筹码，使得
组成各种筹码量使用的筹码个数
的总和（这一行是后加的）
和
筹码的种类
乘积最小。
假设Dealer 都使数学家。

作者: yyy6 时间: 2012-12-19 20:34
是说一套筹码能表示1到N 问这样一套筹码怎么设计个数和种类乘积最小？

作者: dfu2012 时间: 2012-12-19 20:58
可能没打过现场，这题目理解上有点困惑，是否要加一个“之和”？
即“组成各种筹码量使用的筹码个数
和
筹码的种类
乘积之和最小”

比如当N=2时，筹码种类分别是1种（1）和2种（1,2）时. 这个乘积（之和）分别是多少？这个搞清楚了，后面解题就比较顺利点。

我想这类题的基本思路是当N=1，2，3...N-1的时候，找规律，找出N和N-1之间的关系和规律，然后求解。

作者: yyy6 时间: 2012-12-19 21:12
如果是我理解的意思那么是一个在m^k>N的constrain下最小化（m-1）*k^2的问题比如N=4095, m应该是4 k是6。这套筹码就是3个1 3个4 3个16 3个64 3个256 3 个1024

作者: Jsli 时间: 2012-12-19 21:44

yyy6 发表于 2012-12-19 21:12
如果是我理解的意思那么是一个在m^k>N的constrain下最小化（m-1）*k^2的问题比如N=4095, m应该是4 k是6。 ...

晕,没想到yyy6也是数学大家

作者: 伟大的墙 时间: 2012-12-19 21:50

Jsli 发表于 2012-12-19 21:44
晕,没想到yyy6也是数学大家

Jsli你现在在哪呢？我凯撒呢

作者: 老陈 时间: 2012-12-19 21:52
抱歉原题没表达清楚，dfu给我指出了毛病。是应该加一个之和。

我举一个例子：
比如N=100
如果只使用1$的筹码，那么表示1到100，总数就是1+2+....+100=5050
再乘以筹码种类数1=5050

如果使用1$和3$两种筹码
1$用1个筹码
2$用2个筹码
3$用1个筹码
27用9个筹码
表示1到100分别用1,2,1,2,3,2,...,.33,34
加起来为1750
乘以种类数2等于3500

说明使用1$和3$这一方案比只使用1$的方案要好。

作者: 伟大的墙 时间: 2012-12-19 21:53

伟大的墙发表于 2012-12-19 21:50
Jsli你现在在哪呢？我凯撒呢

快散了
我准备转战贝拉胶

作者: 老陈 时间: 2012-12-19 22:06

伟大的墙发表于 2012-12-19 07:53
快散了
我准备转战贝拉胶

这点儿该睡觉了吧？

作者: yyy6 时间: 2012-12-20 09:35

老陈发表于 2012-12-19 21:52
抱歉原题没表达清楚，dfu给我指出了毛病。是应该加一个之和。

我举一个例子：

这样的话，不知道是否我的算法太笨而且很可能是错的：

令m为筹码种类，先假设我们固定m。那么当k=N^1/m正好为整数时，采用1， K, K^2... K^(m-1)的设计，会得到最小和[m/2×N×(k-1)+k], （为什么这么设计和最小是可以递推的，对于ｍ＝２的时候，会等价于一个最小化Ｎ／ｋ＋ｋ的问题，那么ｋ一定是根号Ｎ）

比如N=100，我们要求只用2种筹码即m=2，则最好的选择是1和10（k=10），和为910，积为1820. 所以变为如何选择m最小化[m/2×N×(k-1)+k]×ｍ。因为N很大可以简化为最小化m^2*（N^1/m）. 求导后可以得出m = 0.5×ln（N）

k不正好为整数的时候需要m = ceiling（0.5×ln（N))，比如

N=100的时候m=3，这套筹码为1，5，25，和为554。乘积为1662.
N=1E10的时候m=12，这套筹码为1，7，7^2, 7^3.....7^11, 和约为3.6e11, 乘积约为4.32e12.

作者: cesar 时间: 2012-12-20 10:15
本帖最后由 cesar 于 2012-12-20 10:16 编辑

没看清题

路过

作者: dfu2012 时间: 2012-12-20 11:58
本帖最后由 dfu2012 于 2012-12-20 11:59 编辑

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

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

我的思路如下：

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

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

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

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

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

作者: yyy6 时间: 2012-12-20 12:12

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

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

作者: dfu2012 时间: 2012-12-20 12:19
我的跟帖一向不简洁，所以先请老陈原谅下，下面是我用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

作者: yyy6 时间: 2012-12-20 12:29

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)

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

作者: dfu2012 时间: 2012-12-20 12:37

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

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

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

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

作者: dfu2012 时间: 2012-12-20 12:49
上表中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可以有几个解。即几种筹码方案都满足最小乘积和的要求。

作者: dfu2012 时间: 2012-12-20 13:02

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

作者: yyy6 时间: 2012-12-20 13:04

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.

作者: yyy6 时间: 2012-12-20 13:08

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很大的时候很多东西可以简化。

作者: dfu2012 时间: 2012-12-20 14:04

yyy6 发表于 2012-12-20 13:08
嗯，N^1/C不是整数的时候而且C>3的情况是比较麻烦，C=3的时候我推过是N/K^2+K，后面递推就可以。但是你假 ...

需要推导当N为多少时，C=3的时候，（1，C3，C3^2）优过（1，C3，X）的方案，这里X为任意其它不同于C3^2的值。

但是对一开始并没有想到N为多少时，C3^2是更优解（相对任何非C3^2的X）的人，就需要用试验方法去证实，然后在（1，C3，C3^2）中过滤出最佳解就好。不费脑力的笨办法。

比如当X=C3^2-1的时候，而N=C3^2，以及N=（C3^2+1）的时候，X=C3^2-1显然更优。

这个题从实验方法上，我感觉就是最优解的不断逼近。

总之，这题我是从无从下手处用试验方法步步逼近，能找到点边就满足了。

另外：

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

1-9的时候实际上1种筹码是最小的，不需要2种，即C=1。

我明白你的意识，你计算的结果在这个意义上是正确的，但并不是唯一解。

比如N=8，9的时候，C=1 或者 C=2，而C2=3或者4都是最佳解。图省事的话，你的解能满足要求，严格的话，在某个很小的区段可以有几个解同时存在。 N=48的时候也类似，是否也会出现C=2的最佳解和某个C=3的最佳解在某个N值重合正如C=1和C=2在N=8，9的重合。

那么当C=4,5，...的时候，这个区段是否会扩大等等，未可知，我用的是试验方法，所以我的角度是观察所有变化，你用的是理论推导，所以可以排除一些数据。

我觉得是采用方法不同观察的角度不同，我侧重在临界值的变化发现规律。

作者: dfu2012 时间: 2012-12-20 14:14
本帖最后由 dfu2012 于 2012-12-20 18:13 编辑

再次给老陈道个谦，把这帖子搞的不简洁。

继续我的思路：

从C=2的结果可以看出，当（1，C2）在N=C2^2-2 附近达到最小值，那么类似的，（1，C2，C2^2）也可能会是在N=C2^3附近（或者C^4）达到最佳解，取C2=3，看（1,3,9）（9可以调整为其它大于3的数值）在27附近的值是多少。

依次类推，C2=4，5，6，7，8，9,10的时候，找出规律。

最终找出 C=M时，筹码面值和N的关系，这个数值我回头在EXCEL里试验下。

我的整个思路是：

当N达到多少时，需要用到第3种筹码？
然后是当N到另外一个数值时，需要用到第4种筹码，依次类推，这样就把N的不同区段用到的不同筹码种类和面值的问题都解决了。

N=48时，C=3，面值（1,4,16）的乘积比 C=2时候的所有面值（1，X）的乘积都小。
N=80时，C=3，面值（1,5,25）的乘积比（1,4,16）更优。

YY的公式大致看了下，当N的数值比较小的时候，K和C都会有很细微的偏差，可能和推理时对N的处理方法有关。

如果能确定（1，k,k^2,....k^m）一定是最佳的筹码分配方案，依此方案做求和不会太难，感觉这个方案靠谱，以后找个时间看能否证明下。（这几天颈部附近脊椎不好，睡眠极差，暂不耗神了。）

我不知道这个方案也不确定是否最优，能采用的只能是试验方法，先找规律，我的方法一向比较笨。

作者: 竹林居士 时间: 2012-12-20 20:29
我找到了一个方案：
用3种筹码：1$, 11$ 和 19$
表示1到100筹码的总和为530
再乘以3等于1590
这是我找到的最好的方案。

作者: yyy6 时间: 2012-12-20 21:45
本帖最后由 yyy6 于 2012-12-20 21:52 编辑

竹林居士发表于 2012-12-20 20:29
我找到了一个方案：
用3种筹码：1$, 11$ 和 19$
表示1到100筹码的总和为530

在我的陈述里面有一个地方忽略了我假设第三个筹码是第二个筹码平方地时候最优这在N^（1／m）是整数的时候成立 m是筹码种类
但是不是整数的时候不对准确的数学公式应该是第k个筹码是ceiling(N^(（k-1）／m)), 所以在N=100， m=3的时候第一个筹码是1，第二个筹码是5，第三个是22。这个和是534的样子你的算出来是536好像

作者: yyy6 时间: 2012-12-20 22:16

竹林居士发表于 2012-12-20 20:29
我找到了一个方案：
用3种筹码：1$, 11$ 和 19$
表示1到100筹码的总和为530

又算了一遍 1 11 19应该是536，你可以确认一下

作者: dfu2012 时间: 2012-12-20 22:18
本帖最后由 dfu2012 于 2012-12-20 22:40 编辑

yyy6 发表于 2012-12-20 21:45
在我的陈述里面有一个地方忽略了我假设第三个筹码是第二个筹码平方地时候最优这在N^（1／m）是整数的时 ...

刚被朋友的电话叫醒，看见你和竹林的解答。

（1,5,22）*3的结果是1578，

即（1,5,22）的乘积和是526. 咱们的答案都不一致啊，这个是可以有标准答案的。

（1,11,19）的结果与我的计算相差较远，回头我再校验下，直觉上类似（1，X,2X）的方案可能不是最佳。

无论如何，可能都能说明，当N的数值不足够大的时候，（1，K,K^2,...K^M）未必是最佳方案，在这个思路上设计的方案对于特定的N会有偏颇。

C=2的时候很容易校验遍历（1,1）-（1，K）即可， C=3的时候校验起来比较麻烦。

基于老陈的题目，现在可以有一个明确答案的子问题：当N=100的时候，最佳方案是什么？

作者: yyy6 时间: 2012-12-20 22:27

dfu2012 发表于 2012-12-20 22:18
刚被朋友的电话叫醒，看见你和竹林的解答。

（1,5,22）*3的结果是1578，

你没算表示100需要的8个筹码吧？
1，5，22应该是最小，和534。方案是我重新列的那个: ceiling(N^((k-1)/m)), where k=1,2,3...m. 1,5,22都是直接代人这个公式算出来的。这个公式当N^(1/m)是整数时与你写那个等价

作者: dfu2012 时间: 2012-12-20 22:47

yyy6 发表于 2012-12-20 22:27
你没算表示100需要的8个筹码吧？
1，5，22应该是最小，和534。方案是我重新列的那个: ceiling(N^((k-1)/ ...

我的方法和你的完全不同。

我用的是EXCEL，借用EXCEL的公式和复制功能，把1-100的和严格加一遍，按道理是不会出错的。

（1,5,22）的结果是526.

（1,5,19）的结果是540

（1,11,19）的结果是690，

(1，4，19)的结果是537.

先这些吧。

作者: 竹林居士 时间: 2012-12-20 22:50
(1,11,19) 方案筹码个数如下，SUM=530

1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 1
12 2
13 3
14 4
15 5
16 6
17 7
18 8
19 1
20 2
21 3
22 2
23 3
24 4
25 5
26 6
27 7
28 8
29 9
30 2
31 3
32 4
33 3
34 4
35 5
36 6
37 7
38 2
39 3
40 4
41 3
42 4
43 5
44 4
45 5
46 6
47 7
48 8
49 3
50 4
51 5
52 4
53 5
54 6
55 5
56 6
57 3
58 4
59 5
60 4
61 5
62 6
63 5
64 6
65 7
66 6
67 7
68 4
69 5
70 6
71 5
72 6
73 7
74 6
75 7
76 4
77 5
78 6
79 5
80 6
81 7
82 6
83 7
84 8
85 7
86 8
87 5
88 6
89 7
90 6
91 7
92 8
93 7
94 8
95 5
96 6
97 7
98 6
99 7
100 8

作者: yyy6 时间: 2012-12-20 22:51

dfu2012 发表于 2012-12-20 22:47
我的方法和你的完全不同。

我用的是EXCEL，借用EXCEL的公式和复制功能，把1-100的和严格加一遍，按道理 ...

你的加法有问题1 11 19错太多了。真要用程序实现可以写递归的函数然后穷举。

作者: 竹林居士 时间: 2012-12-20 22:52
(1,5,22)方案筹码个数如下，SUM=534

1 1
2 2
3 3
4 4
5 1
6 2
7 3
8 4
9 5
10 2
11 3
12 4
13 5
14 6
15 3
16 4
17 5
18 6
19 7
20 4
21 5
22 1
23 2
24 3
25 4
26 5
27 2
28 3
29 4
30 5
31 6
32 3
33 4
34 5
35 6
36 7
37 4
38 5
39 6
40 7
41 8
42 5
43 6
44 2
45 3
46 4
47 5
48 6
49 3
50 4
51 5
52 6
53 7
54 4
55 5
56 6
57 7
58 8
59 5
60 6
61 7
62 8
63 9
64 6
65 7
66 3
67 4
68 5
69 6
70 7
71 4
72 5
73 6
74 7
75 8
76 5
77 6
78 7
79 8
80 9
81 6
82 7
83 8
84 9
85 10
86 7
87 8
88 4
89 5
90 6
91 7
92 8
93 5
94 6
95 7
96 8
97 9
98 6
99 7
100 8

作者: 竹林居士 时间: 2012-12-20 22:54
本帖最后由竹林居士于 2012-12-20 09:04 编辑

(1,5,25)方案筹码个数如下，SUM=554

1 1
2 2
3 3
4 4
5 1
6 2
7 3
8 4
9 5
10 2
11 3
12 4
13 5
14 6
15 3
16 4
17 5
18 6
19 7
20 4
21 5
22 6
23 7
24 8
25 1
26 2
27 3
28 4
29 5
30 2
31 3
32 4
33 5
34 6
35 3
36 4
37 5
38 6
39 7
40 4
41 5
42 6
43 7
44 8
45 5
46 6
47 7
48 8
49 9
50 2
51 3
52 4
53 5
54 6
55 3
56 4
57 5
58 6
59 7
60 4
61 5
62 6
63 7
64 8
65 5
66 6
67 7
68 8
69 9
70 6
71 7
72 8
73 9
74 10
75 3
76 4
77 5
78 6
79 7
80 4
81 5
82 6
83 7
84 8
85 5
86 6
87 7
88 8
89 9
90 6
91 7
92 8
93 9
94 10
95 7
96 8
97 9
98 10
99 11
100 4

作者: yyy6 时间: 2012-12-20 22:55

竹林居士发表于 2012-12-20 22:50
(1,11,19) 方案筹码个数如下，SUM=530

1 1

嗯你是对的 530。我在41到43那里算错了

作者: yyy6 时间: 2012-12-20 22:56

竹林居士发表于 2012-12-20 22:54
(1,5,22)方案筹码个数如下，SUM=554

1 1

你这里列的还是1，5，25

作者: 竹林居士 时间: 2012-12-20 22:56
本帖最后由竹林居士于 2012-12-20 09:00 编辑

(1,5,19)方案筹码个数如下，SUM=546

1 1
2 2
3 3
4 4
5 1
6 2
7 3
8 4
9 5
10 2
11 3
12 4
13 5
14 6
15 3
16 4
17 5
18 6
19 1
20 2
21 3
22 4
23 5
24 2
25 3
26 4
27 5
28 6
29 3
30 4
31 5
32 6
33 7
34 4
35 5
36 6
37 7
38 2
39 3
40 4
41 5
42 6
43 3
44 4
45 5
46 6
47 7
48 4
49 5
50 6
51 7
52 8
53 5
54 6
55 7
56 8
57 3
58 4
59 5
60 6
61 7
62 4
63 5
64 6
65 7
66 8
67 5
68 6
69 7
70 8
71 9
72 6
73 7
74 8
75 9
76 4
77 5
78 6
79 7
80 8
81 5
82 6
83 7
84 8
85 9
86 6
87 7
88 8
89 9
90 10
91 7
92 8
93 9
94 10
95 5
96 6
97 7
98 8
99 9
100 6

作者: 竹林居士 时间: 2012-12-20 22:57
(1,4,19)方案筹码个数如下，SUM=544

1 1
2 2
3 3
4 1
5 2
6 3
7 4
8 2
9 3
10 4
11 5
12 3
13 4
14 5
15 6
16 4
17 5
18 6
19 1
20 2
21 3
22 4
23 2
24 3
25 4
26 5
27 3
28 4
29 5
30 6
31 4
32 5
33 6
34 7
35 5
36 6
37 7
38 2
39 3
40 4
41 5
42 3
43 4
44 5
45 6
46 4
47 5
48 6
49 7
50 5
51 6
52 7
53 8
54 6
55 7
56 8
57 3
58 4
59 5
60 6
61 4
62 5
63 6
64 7
65 5
66 6
67 7
68 8
69 6
70 7
71 8
72 9
73 7
74 8
75 9
76 4
77 5
78 6
79 7
80 5
81 6
82 7
83 8
84 6
85 7
86 8
87 9
88 7
89 8
90 9
91 10
92 8
93 9
94 10
95 5
96 6
97 7
98 8
99 6
100 7

作者: dfu2012 时间: 2012-12-20 23:15
本帖最后由 dfu2012 于 2012-12-20 23:27 编辑

yyy6 发表于 2012-12-20 22:51
你的加法有问题1 11 19错太多了。真要用程序实现可以写递归的函数然后穷举。 ...

没错，我的加法出错了，我图省事，直接用EXCEL的功能。

竹林的答案是正确的，估计竹林是用程序写的，对任意N，判断最小路径，比如29=2*11+7.

这个用程序来做，递归调用或者各种手段，比较方便，但用EXCEL做，简单了。

惭愧。

顺便说一下：EXCEL在公式正确的前提下，还是很方便的，但有的时候没办法处理，比如最小路径的判断，这个必须要编程。

作者: dfu2012 时间: 2012-12-21 02:08
刚来了人，他们走后，顺便看了下EXCEL的结果，

（1,5,22）结果是 534，漏加了最后一个8（N=100，实际是漏看成N=99，不是漏加），因为我在第一列下推了一行作为起始行，错把最左当成序列行，即把N=99当100。

（1,5,19）结果是546，（1,5,25）是554.

这几个数值与竹林的答案一致，我的公式很简单：INT（N/C3）+INT((N-C3*INT(N/C3))/C2)+MOD（（N-C3*INT(N/C3))，C2）。

这个公式在（1,5,22）（1,5,19）（1,5,25）的时候似乎不会出错，结果与竹林一致。

但在（1,11,19）公式的计算会出问题，当N=29的时候，S=11*2+7，即乘积和是（2+7）为最短路径，
我的公式是S=1*19+10即（1+10）。判断最短路径只能用编程了，EXCEL还真不知道有什么办法。

从这个意义看，（1，C2，C2^2）似乎不是N的最佳解，即便当N足够大时，这个最佳解也要打个问号。

我几乎觉得YY说的很有道理的时候，竹林的计算似乎又让这个道理充满了疑问。

作者: Jsli 时间: 2012-12-21 09:08

伟大的墙发表于 2012-12-19 21:53
快散了
我准备转战贝拉胶

昨天在威尼斯打的时间太长
有点打伤了
再打接下来就是on tilt了

作者: Jsli 时间: 2012-12-21 09:21

Jsli 发表于 2012-12-21 09:08
昨天在威尼斯打的时间太长
有点打伤了
再打接下来就是on tilt了

最后差不多是送300刀给人家
休息好比啥都重要

作者: 老陈 时间: 2012-12-21 10:01

Jsli 发表于 2012-12-20 19:21
最后差不多是送300刀给人家
休息好比啥都重要

吃饱了
喝足了
睡醒了
歇透了
活蹦乱跳地上战场

作者: Jsli 时间: 2012-12-21 10:06

老陈发表于 2012-12-21 10:01
吃饱了
喝足了
睡醒了

把老陈的贴子弄歪

作者: dfu2012 时间: 2012-12-21 11:25

Jsli 发表于 2012-12-21 10:06
把老陈的贴子弄歪

我觉得，老陈的话就是打德州的笨办法。

太平实了，我来做复杂解读的话，就是这笨办法其实是极难做到的事。

审视内心的变化，当不良情绪出现的时候，引起自己的警觉，能做到吗？

当我控制不住自己，狂躁发脾气的时候，事实上就是我无能软弱自卑的时候，如果意识到这点引起警觉起码不至把事情变得更糟糕。总会想起电影《教父》里的台词：女人和小孩可以粗心，男人不可以。就是说，做事要严谨认真，尤其是重要的事，否则一个差错就会引起很大的困难。

警觉自己的不良情绪，一旦警觉了，放弃不玩就顺理成章了。

作者: dfu2012 时间: 2012-12-21 13:28
本帖最后由 dfu2012 于 2012-12-21 13:32 编辑

按JS说的，当这贴聊天了，说点故事，说一下我对警觉的体会。

本来想跟到JS的一个老贴里，这帖子的主题实在是太遥远了。

我这一年过的很难，预期一再降低，到最后一点办法都没有了（十月是最糟糕的时候），然后转机，好不容易到现在终于熬过来了。

打个比方，1年前，你状态极差下受熟悉的人影响买了个一点都不熟悉的东西，你觉得不对劲，想卖掉，可是没有人买，这个时候你想的是8折，9折能出掉就好了。几个月过去了，你想着7折能卖掉也行。再然后，到了最困难的时候急用钱，你想着3折卖掉都好，熟悉的人已无踪影，所有这一切更像是个陷阱。试想下，1年多前你怎么可能能接受3折出，而3折对于困难时候的你来说也像阳光一样，没办法你需要钱。终于，你筹到一点钱度过难关，事情也逐渐的转好，那个东西也终于能在65折附近卖掉。

熬了一年，很难得的安宁看起来终于能回来了。其实难的时候，差一点钱都可能熬不过去。（你人品差！不会去借吗？说明你人缘不好。可能吧）

先铺垫下我的心理状态所谓前因。

有个朋友，和这事完全无关的朋友，曾经在澳门挥斥千金的人，我也是因为一些机缘认识他，这一认识就是几年，我是这个城市的边缘人物，这个朋友在经济上是我的几十倍甚至更多，但我觉得他也是边缘人物。我基本不主动找他，一般他找我，吃吃饭，聊天。

最近，他找到我，说刚学打德州这几天输了几十万，局是10万的买入，他们自己圈子的人玩，打法也奇特，好像没盲注，一般是1000元起下。让我代他打，为这事吃了几次饭，逐渐知道他们的打法，什么位置筹码量起手牌等完全不会。说明一下，这几十万即便是1年前（已经不景气了），这个朋友眼都不眨一下，也就是这两年，他体会到了巨大的挫折。

这样的局是不是梦寐以求的好局？我刚刚度过难关，仅仅因为需要不多的一些钱，权衡之下，65折出掉那东西。这么个好局，都是有钱的，我替这朋友打，不是很有机会迅速来一票？

一年前的痛还没有完全好，看似安宁的日子还没过两天，我似乎又看到了巨大的机会，是机会吗？当人被欲望蒙蔽的时候，其实很少会注意到警觉。这个朋友确实打的很差，而且输的都是真金白银，或许那些打牌的人也许非常的烂，甚至技术远不如你，但，这样，你就能赢了吗？如果他们“运气”总是那么好的话，总是刚刚好你拿到大牌的时候BB你，你玩什么？会做何感想？你一点不熟悉这个圈子，这个行业。最简单的做法就是：不该你的想都别想。生起这些警觉后，一点都不想参与这个局，无论这是多大的金矿。

他人即是我们的镜子，我的日子过的非常的沉闷，几乎没什么来往的人（在这个社会被彻底的边缘化），这个1年不来往几回的朋友对于现实中的我几乎就算来往比较多了，无论他的经济实力多么的强（其实这几年衰弱的迹象很明显），当一个人内心脆弱无力的时候，那是真正的脆弱无力，比如陷在金钱游戏里成为奴隶拔不出来，而这，对于男人来说或许是真正的悲哀。

啰嗦了很多，平常心最好，共勉吧。

顺祝论坛上各位朋友冬至好。

作者: 竹林居士 时间: 2012-12-21 18:46
又找到一个更好的方案

(1,12,19)方案筹码个数如下，SUM=521

1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 1
13 2
14 3
15 4
16 5
17 6
18 7
19 1
20 2
21 3
22 4
23 5
24 2
25 3
26 4
27 5
28 6
29 7
30 8
31 2
32 3
33 4
34 5
35 6
36 3
37 4
38 2
39 3
40 4
41 5
42 6
43 3
44 4
45 5
46 6
47 7
48 4
49 5
50 3
51 4
52 5
53 6
54 7
55 4
56 5
57 3
58 4
59 5
60 5
61 6
62 4
63 5
64 6
65 7
66 8
67 5
68 6
69 4
70 5
71 6
72 6
73 7
74 5
75 6
76 4
77 5
78 6
79 6
80 7
81 5
82 6
83 7
84 7
85 8
86 6
87 7
88 5
89 6
90 7
91 7
92 8
93 6
94 7
95 5
96 6
97 7
98 7
99 8
100 6

作者: Jsli 时间: 2012-12-21 19:47

dfu2012 发表于 2012-12-21 13:28
按JS说的，当这贴聊天了，说点故事，说一下我对警觉的体会。

本来想跟到JS的一个老贴里，这帖子的主题实在 ...

德夫有QQ没?

我的情况比你差,这个年纪了王小二一年不如一年
我10年回国所有钱做A股(我不做短线)
现在都知道了A股就是被抽弹汁的黑熊
差不多破产了
为此我开微博成了一名愤青

现在打打1-2刀过日子吧
再不行就"贫穷的时候布施你的身体"

作者: Jsli 时间: 2012-12-21 19:53

dfu2012 发表于 2012-12-21 11:25
我觉得，老陈的话就是打德州的笨办法。

太平实了，我来做复杂解读的话，就是这笨办法其实是极难做到的事 ...

虽然老陈总是三言两语
赶脚老陈对扑克的理解是最高境界了

我赌性有点大
不是说赌场烂赌那种
是过日子不安分的一类
性格缺陷

作者: dfu2012 时间: 2012-12-21 20:46

Jsli 发表于 2012-12-21 19:47
德夫有QQ没?

我的情况比你差,这个年纪了王小二一年不如一年

J兄，每个人的经历不同，谈不上谁差还是好，心境不同而已，相由心生，境由心转。

上贴中的那个朋友，曾经很多年前在澳门一夜输掉XXXX万，我初初听人说起的时候，当天人一般的存在，这样的人现实中实在离我太远了。前几年，他一夜玩掉几十万，还能淡定自如。若干年后，他亲口告诉我他以前有多少资金的时候，话语中听出了王小二过年的弦外之音。及至现在，可以连续几天不睡觉不断的玩就因为输了几十万（事实上他现在的实力依然能支撑他这么玩）。我看出了他的无力焦灼和疲惫，他的岁数不小了。就算赢回这几十万，又能怎么样？一个人过的好不好，和他有多少钱真一点关系都没有。

付出了那么大的代价，如果是为了要回曾经失去的，那么人真是很苦，失去的东西就算回来，岁月如何找回？太执着了，执着就是苦。所以怎么找都没用。我一直相信，失去一些东西必然会得到一些东西，所谓等价交换守则。

知足心平常心如果要耗费巨大的代价才能明白，多大的代价才够？有些人一辈子就迷进去了。

你我都比很多人强，有饭吃，有地方住，还能上论坛扯扯淡，很好了，你还能世界到处走走没有签证的麻烦。。。

作者: Jsli 时间: 2012-12-21 21:53

dfu2012 发表于 2012-12-21 20:46
J兄，每个人的经历不同，谈不上谁差还是好，心境不同而已，相由心生，境由心转。

上贴中的那个朋友，曾 ...

德夫无论数学知识还是人生哲学都领会深刻
能在智游城认识真是件开心的事

能到处走?
穷的就只剩下天生的那两个小肉蛋了

作者: 老陈 时间: 2012-12-25 18:16
本帖最后由老陈于 2012-12-25 04:59 编辑

我说一下这道题我的解题思路。
我是用计算机编程序解的，在出题时我高估计算机CPU的计算能力，也就是低估题目的计算复杂性。因此在原题目中写了N是一个很大的数。实际计算中当N＝2000时就很难计算出最优解了。

我是采用逼近的算法解的。
以N＝1000,4种筹码为例。
首先给4种筹码一个初始值：比如（1,5，25,125）
用符合逻辑的初始值就可以，结果与初始值无关，只是稍微影响找到最佳方案的更速度。
1是必须的。
然后在初始值“附近”搜索更好的方案。
“附近”的意思：
5附近为3－8
25附近为18－33
125附近为93－154
这个“附近”不能太大（会使计算复杂），也不能太小（会丢掉更好的方案）。

进行三重循环搜索更好的方案。当找到更好的方案后再在更好的方案“附近”搜索更好的方案。
一直到找不到更好的方案为止。
4种筹码策略用三重循环，5种筹码策略用四重循环，程序是用递归的方法写的，适用于多种筹码策略。

搜索方案也是用递归的方法写的。
Search(CHips,NC)
CHips是筹码数,NC是筹码种类
在使用了1个125的筹码后就
Search(875,3)
当搜索到Search(X,1)就结束了，用X个1$筹码就可以了。把筹码总和记住。所有可能的组合找出筹码最少的。
CHips从1到N搜索，把各个筹码总和加起来，与前一个方案比较，如果这个方案好就在这个方案搜索，否则计算其它方案。

我的计算结果是：
100(1,12,19)=1563
500(1,13,69)=14982
500(1,7,56,95)=13648
500(1,7,17,72,118)=13705
1000(1,18,97)=38955
1000(1,9,89,140)=33996
1000(1,7,52,137,218)=33335
2000(1,22,162)=100488
2000(1,12,138,236)=83884
5000(1,29,300)=349944
10000(1,38,469)=894672

第一个数字为N
括号里的数字个数为筹码种类，单个数字为筹码面值
最后一个数为所有表达1到N的筹码总和乘以筹码种类

N越大，筹码种类越多计算就越复杂。
N＝2000的5种筹码就很难算了，我编的程序只少需要12个小时。

作者: Howard 时间: 2012-12-28 22:14
看到科学松鼠会上有一篇类似文章，转发一下，顺便景仰下老陈强大的编程思路和探求真理的决心：

——————————————————————————————————————————————

本文作者：Albert_JIAO

两个造假币的不小心造出了 33 元的钞票却又不想浪费，他们决定拿到偏远山区花掉。用 33 元的假币买了一串 1 元的糖葫芦后，他们哭了：农民伯伯找给他们两张 16 元！

当然，这只是一个段子。加拿大滑铁卢大学计算机系研究员 Jeffrey Shallit 也很喜欢这个段子，并且他认为，从理论上讲钞票就应该有 16 元和 33 元的。

16元的纸币最方便

以人民币为例，纸币面值在 100 元以下的一共有 1 元、5 元、 10 元、 20 元、 50 元五种。 Jeffrey 认为这 5 种纸币面额数值的组合并不是最科学的，而应该是 1 元、 5 元、 16 元、 23 元、 33 元这五种。

平时我们去超市买东西，每次使用 100 元以下数额的钱（ 1 元到 99 元），需要用 1 元、 5 元、 10 元、 20 元、 50 元五种面额的钱币组合而成，有的时候需要一张，有的时候需要两张或者更多。比如你需要 31 元的零钱，可以用三张 10 元的和一张 1 元，也可以用一张 10 元、一张 20 元和一张 1 元，前一种需要四张纸币，后一种需要三张。在组成 31 元的所有可能方案中， 10+20+1 是最佳的，它最节省钞票张数，也就是说，凑成 31 元最少也需要三张纸币。

我们可以对从 1 到 99 之间的每个数额分别算出来它最少需要的纸币张数，这不难通过编程实现。这样一来就能知道使用这五种面额的人民币组成 99 个数额，在最“环保”的组合方式下，平均需要多少张钞票。

接下来， Jeffrey 在电脑上把参数修改了一下，五种纸币的面额更改为各种其他数值，让电脑程序运行，看一看哪一种货币面额体系在组成99个数额的时候平均最方便、需要的纸币张数最少。最终结果就是前面说过的， 1-5-16-23-33 方案击败了我们现实生活中使用的 1-5-10-20-50 方案，也击败了其他各种方案，组成 99 个数额平均只需要最少的3.29张。

[attach]2411[/attach]
【Jeffrey的货币最佳发行方案。】

值得一提的是，这个研究结果不仅适用于人民币。比如目前美国的流通的硬币主要有 1 美分、 5 美分、 10 美分和 25 美分四种，可是根据 Jeffery 的结果，要想最方便的凑齐 1 美分到 99 美分一共 99 个数额，美联储应该发行 18 美分而不是 10 美分的硬币。

在加拿大，实际流通中的硬币有 6 种： 1 分、 5 分、 10 分、 25 分、100 分和 200 分，而最小的纸币面额是 5 加元。这 6 种硬币的“艰巨任务”是组成 1 到499 的数字。 Jeffery 计算出平均每笔交易会用到 5.9 枚硬币，不过他建议在这个体系中加入一枚面值为 83 分的硬币，这个数值就会降为 4.578 枚。他和他的学生甚至还给 83 分的假想硬币设计了正面和背面图案。不过 Jeffery 的论文在 2003 年就发表了，但到现在 83 分的硬币还没问世。

二进制的面值也好用

当然，最佳货币面额的计算方法也并非完美无瑕，一个漏洞就是 Jeffery 计算平均需要的张数的时候假定 1 到 99 个数额我们平时使用的频率是一样的，可现实交易中往往小的数额出现的机会更大，如果考虑这个因素，恐怕“最佳面额”结果就会有所改变。

另一方面，不只 Jeffery 一个人琢磨过这个问题，有人模仿信息编码方式设计出一套很酷很潇洒的货币面额方案。若纸币面额是按照二进制设置的，1元、2元、4元、8元、16元、32元、64元，虽然未必保证每次付款的时候使用的张数最少，但是神奇之处在于，每次出门的时候只要带齐一套，每样一张，就可以组成1到127的任意数额。

不仅如此，如果考虑了找钱的情况之后，三进制，也就是面值分别为 1 元、 3 元、9元、27元、 81 元……也可以实现“每样一张，找零无忧”的效果，不信你可以随便选个数字试一下。比如你想付款 20 元，需要做的是给收银员一张 27 元、一张 3 元的，收银员找给你一张 1 元的，一张 9 元的，整个交易过程中每张也只出现了一次，唯一的麻烦是三进制的钞票计算起来有点费脑筋。

实际使用不容易

计算机人士提出各种数学游戏式的货币发行方案尽管看起来很酷，真正被掌管货币发行的金融高富帅们采纳的却极少。事实上，银行在考虑发行哪些数额的纸币的时候主要考虑的就是两个实际因素。第一个是货币面额要考虑人们日常的十进制算术习惯，如果又是最优组合，又是二进制、三进制，数学不好的人士必将苦不堪言，街边买菜的大妈恐怕买次东西算钱也要算上几分钟， 5 元、 10 元、 20 元的面额在数学上未必是最佳的，但是起码算数的时候最方便。第二个因素是尽量少发行一些面额种类，如果面值种类很多，尽管组成任意数额都不会出现一大把钞票的情形，但是银行不便于管理，使用者可能自己都搞不清楚到底有哪些面额了。

要说世界上发行钞票面值种类最多的地方当属几年前的非洲国家津巴布韦了。当时津巴布韦国家经济出现了崩溃，恶性通货膨胀愈演愈烈，银行也在滥发纸币。哈佛大学举办的以“乍看之下令人发笑，之后发人深省”为宗旨的搞笑诺贝尔奖 2008 年的数学奖就授予了津巴布韦国家储备银行行长的戈诺，颁奖理由是他居然下令印刷了1分（0.01元）至100万亿面值的钞票，大幅提高了本国国民的数学能力。

现实中的货币面额大多是按照习惯和经验而已，背后并没有涉及到很多数学知识，世界上各国的货币不外乎都是1、2、5、10这类面额，本文有些异想天开的方案恐怕只能停留在数学爱好者自己想象的世界中了。

参考资料

[1] What This Country Needs is an 18 Piece; Jeffrey Shallit

[2] Optimal Denominations for Coins and Bank Notes: In Defense of the Principle of Least Effort; Leo Van Hove

作者: 老陈 时间: 2012-12-29 00:53

Howard 发表于 2012-12-28 08:14
看到科学松鼠会上有一篇类似文章，转发一下，顺便景仰下老陈强大的编程思路和探求真理的决心：

————— ...

筹码面值与种类设计和钞票面值与种类设计在数学上是完全一回事，一点差别也没有！

作者: Jsli 时间: 2012-12-29 01:17
牛人都进圈了
123456...

作者: donot 时间: 2012-12-29 16:22
本帖最后由 donot 于 2012-12-29 16:37 编辑

刚看见这题，还没仔细看回帖。先发个言。
如果“N”足够大，筹码应该是1，5，25，125...5^n.
以下是大概思路：
1）在最佳筹码下，下一个面值都应该是上一个面值的m倍。m是常数。换句话说，筹码面值是等比数列，1，m,m^2,...m^n... (数学可证,但是很繁琐，就不写了）
2）这其实是几进制是最佳进制的问题。大数“N"在m进制下共log(m,N)位（log(m,N)个面值）。m进制下，每位的数字可以是0，1，2……m-1。表示一个[1,N]的数平均每个面值的筹码要用（m-1）/2个。所以
组成各种筹码量使用的筹码个数的总和×筹码的种类= N×（m-1）/2 ×log(m,N)×log(m,N)
3）上面表达式在m比5稍小一点时有极小值。当m为整数时，m=5，上式极小。具体计算就不写了。无非是log换底公式加上对m求导。

注：log(m,N)表示以m为底对N取对数。没法输入公式，只能凑合表示。

作者: donot 时间: 2012-12-29 16:53
看了一下跟帖，大家把N取成小数时，问题反而复杂化了。直接把N想成无穷大更容易看到问题的本质。

作者: dfu2012 时间: 2012-12-29 21:02
本帖最后由 dfu2012 于 2012-12-29 21:04 编辑

我摘抄一段文字：
“
柯尼斯堡七桥问题：
1852年十月，咖色利正在为一副英国地图着色。他思考了要区别各个国家最少需要几种颜色，他得到的结果是四种颜色。1879年给出了这个数确实是4的一个证明。但后来发现这个证明是错误的。几乎一个世纪后，1976年，两个年轻的数学家海肯和爱普尔证明了这个已非常著名的四色地图问题。然而，这个证明认为是值得商榷的，因为他是用计算机得到的，而不是用纯粹的数学逻辑。
”
X^N+Y^N=Z^N,当N大于2时没有整数解。

引
“
后来发现欧拉对于N=3的费马大定理的证明有一个错误，这被高斯改正了。那时候大多数有名望的数学家都是法国人，但毫无疑问那个时代-也可能是所有时代-最伟大的数学家的高斯，却是地道的德国人。
”
“。。。”
《费马大定理》，非常非常好看的一本书，说数学史的，我看的是左平翻译的。原作者是（AMIR D.ACZEL）

数学的魅力在于最难部分的求解，最难部分往往看上去似乎又很简单。

X^N+Y^N=Z^N,当N大于2时没有整数解。

历经数百年（算源头的话可以说数千年），费马大定理到1993年才证明。

欢迎光临智游城 (http://zhiyoucheng.co/)