前几天做了个豆瓣笔试题，时间是90分钟，共有6题，要做4道，难度如果没看过类似的着实做起来太慢了。由于豆瓣上面的邮件说不要泄露（还有人会在后期笔试），所以拖到现在才写博客。我先把题目贴出来：将10000块钱兑换成由5000块、2000块、1000块、500块、100块、50块、10块、5块、1块的组成的零钱，问有多少种兑换方式？
这个题，如果朋友们没做过，或许最开始就跟我一样，钱有9种，就做个9重循环，各层累加，当总钱等于10000时就计数器加1，这样是很简单没错，可惜在这数据量的前提下，我用c跑了5、6分钟也没跑出来，于是中止了这种天真的想法。但是还是有必要提下完成这种笨方法时需要用到的基础数据结构，后面我们会对它们进行改进：
一个用于记录各种钱(金额)的数据：y[9]；
一个用于统计各种钱(数量)的数组：x[9]，初始为0；
一个用于标示各种钱(数量上限)的数组：z[9]；
一个用于统计从父循环[i]进入子循环[i+1]时(总金额)的数组：sum[9]，i= 0 to 8；这里我需要重点说明，这个数组是必然需要的，一定得保存上层循环进入下层循环时的初始总金额数，否则当下层循环[i+1]执行完毕返回[i]时就无法知道[i]循环内正确的总金额初值了（除非你把[ 0 ~ i-1 ]层的都算一次加起来）。
接下来，我讲下想到的几个优先考虑的改进：
1、最外层循环应该是最大的数，香港服务器租用，也就是5000块，内层的依次递减。
这种方式可以使步进更大，而且与后面的第3点配合是非常优秀的省时方法，于是令y[] = {5000,2000,1000,500,100,50,10,5,1}，香港虚拟主机，z[] = {3,6,11,21,101,201,1001,2001,10001}；
2、各层循环应该增加临界条件，当发现总数大于或等于时应该返回上层循环。
如果只是按照z[]中的极限临界条件来做循环，明显会有非常多的无用功，所以应该在各层循环内部，判断总钱数是否已经大于、等于10000，如果大于就break到上层循环，如果等于就先计数器加1，再返回上层循环。
3、最底层循环不执行（1块钱）
前面i = 0 to 7层循环分别把5000、2000、1000、500、100、50、10、5块的都算过了，等到了i=8层，也就是算1块钱的数量时就可以直接跳过了，香港服务器，因为反正会有一个数量能满足累加和正好等于10000，所以前面实际上的x[]、y[]、z[]的大小都只要8就行了。这一点可以把循环次数上限最大的（10000次）的那重循环给省略掉，能大大加快计算时间，这时循环由9重循环减到8重。
经过上面3点改进，心想这下应该快了吧，哪知道也花了两分多钟才出结果，仔细思考，觉得最大的问题还是在第2点，临界条件的判断上，使用2中的方法，会导致各层循环都有判断操作（大于、等于、小于），会影响执行效率，这是需要改善的问题，目前来说，第2点的实现方式有三种：
… 3for (x[4]=0;x[4]<z[4];++x[4]) 4 { 5sum[4]=sum[3]+x[4]*y[4]; 6if (sum[4]<10000) ;(sum[4]==10000) { ++count; break; }; 9for (x[5]=0;x[5]<z[5];++x[5])10 {11 …12 }13 }14 ……18for (x[4]=0;x[4]<z[4];++x[4])19 {20sum[4]=sum[3]+x[4]*y[4];21if (sum[4]>10000) break;22for (x[5]=0;x[5]<z[5];++x[5])23 {24 …25 }26 }27 ……31for (x[4]=0;x[4]<z[4];++x[4])32 {33sum[4]=sum[3]+x[4]*y[4];34if (sum[4]==10000) { ++count; break; }(sum[6]>10000) break;36for (x[5]=0;x[5]<z[5];++x[5])37 {38 …39 }40 }41 ……45for (x[7]=0;x[7]<z[7];++x[7])46 {47sum[7]=sum[6]+x[7]*y[7];48if (sum[7]>10000) break;49++count;50 }51 …学习会使你永远立于不败之地。
