您还未登陆，请登录后操作！
12枚硬币，有一枚是假的，和真的重量不一样。用天平秤，3次找出假币。并确定假币是重还是轻。
12个硬币用1~12（数字）进行标识，其中已确定是标准硬币的号码加括号注明：
第一次{1+2+3+4}比较{5+6+7+8}
如果相等，第二次{9+10}比较{（1）+11}
如果相等，证明是12硬币不规则，第三次和任意硬币比较，12或者重或者轻两种可能
如果{9+10}>{（1）+11}
第三次9比较10，如果9>10并且{9+10}>{（1）+11}证明是9重
同理如果9 同理如果9=10，证明是11轻
如果{9+10} 第三次9比较10，如果9>10并且{9+10} 如果9 如果9=10，证明是11重
至此刚好8种可能；
如果{1+2+3+4}>{5+6+7+8}
第二次{1+2+5}比较{3+6+（9）}（关键把其中3，5硬币的位置交换）
如果相等，证明1，2，3，5，6为规则硬币，不规则硬币在4，7，8中（见说明2）
第三次7比较8，如果7=8并且{1+2+3+4}>{5+6+7+8}证明是4重
如果7 如果7>8，证明是8轻
如果{1+2+5}>{3+6+（9）}
证明3，5，4，7，8为规则硬币，不规则硬币在1，
12个硬币用1~12（数字）进行标识，其中已确定是标准硬币的号码加括号注明：
第一次{1+2+3+4}比较{5+6+7+8}
如果相等，第二次{9+10}比较{（1）+11}
如果相等，证明是12硬币不规则，第三次和任意硬币比较，12或者重或者轻两种可能
如果{9+10}>{（1）+11}
第三次9比较10，如果9>10并且{9+10}>{（1）+11}证明是9重
同理如果9 同理如果9=10，证明是11轻
如果{9+10} 第三次9比较10，如果9>10并且{9+10} 如果9 如果9=10，证明是11重
至此刚好8种可能；
如果{1+2+3+4}>{5+6+7+8}
第二次{1+2+5}比较{3+6+（9）}（关键把其中3，5硬币的位置交换）
如果相等，证明1，2，3，5，6为规则硬币，不规则硬币在4，7，8中（见说明2）
第三次7比较8，如果7=8并且{1+2+3+4}>{5+6+7+8}证明是4重
如果7 如果7>8，证明是8轻
如果{1+2+5}>{3+6+（9）}
证明3，5，4，7，8为规则硬币，不规则硬币在1，2，6中
第三次1比较2，如果1=2并且{1+2+5}>{3+6+（9）}证明是6轻
如果1>2，证明是1重
如果1 如果{1+2+5} 证明不规则硬币在3，5中（因为位置变化天平变化）
第三次随便比较1与3，如果1=3，证明是5轻
如果1 1>3不可能，因为已经有第一次{1+2+3+4}>{5+6+7+8}
这样刚好也是8种可能。
117.136.9.*
这不是我的吗！！
卡农的天空
说的比较混乱，复制粘贴的吧
回答数：794
卡农的天空
如果你非要说是错的，请具体指出来。我是说前面的。
卡农的天空
不会，前面部分是对的。
他的方法不行，从开始就错了。你别在这上面花时间了。
看清题目，用天平秤，天平是秤不出重量的。
a：AB平衡，则C组中有异常币。
取C1与C2称量，结果：
（1） 平衡，则坏币在C3、C4中，则取C3与C1称量，若平衡，则C4是坏币，
可你不知道C4是重了还是轻了。这里有问题。
当A组和B组相同,那么我们放上C和D，那么CD一定不一样，你能确定假币在C还d吗？
分成4份。第一次相同，第二次相同。这时你只能确定假币在另3个中，不知道轻重。第三秤不管结果是什么你都不能确定。
您的举报已经提交成功，我们将尽快处理，谢谢！扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
硬币翻转问题
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口　　假设我们有8种不同面值的硬币｛1，2，5，10，20，50，100，200｝，用这些硬币组合够成一个给定的数值n。例如n=200，那么一种可能的组合方式为 200 = 3 * 1 + 1＊2 + 1＊5 + 2＊20 + 1 * 50 + 1 * 100. 问总过有多少种可能的组合方式？ (这道题目来自著名编程网站ProjectEuler, 点击查看原题目) 类似的题目还有：
　　[华为面试题] 1分2分5分的硬币三种，组合成1角，共有多少种组合
　　[创新工厂笔试题] 有1分，2分，5分，10分四种硬币，每种硬币数量无限，给定n分钱，有多少中组合可以组成n分钱
　　给定一个数值sum，假设我们有m种不同类型的硬币{V1, V2, ..., Vm}，如果要组合成sum，那么我们有
sum = x1 * V1 + x2 * V2 + ... + xm * Vm&
求所有可能的组合数，就是求满足前面等值的系数{x1, x2, ..., xm}的所有可能个数。
　　[思路1] 当然我们可以采用暴力枚举，各个系数可能的取值无非是x1 = {0, 1, ..., sum / V1}, x2 = {0, 1, ..., sum/ V2}等等。这对于硬币种类数较小的题目还是可以应付的，比如华为和创新工厂的题目，但是复杂度也很高O（sum/V1 * sum/V2 * sum/V3 * ...）
　　[思路2] 从上面的分析中我们也可以这么考虑，我们希望用m种硬币构成sum，根据最后一个硬币Vm的系数的取值为无非有这么几种情况，xm分别取｛0, 1, 2, ..., sum/Vm｝，换句话说，上面分析中的等式和下面的几个等式的联合是等价的。
sum = x1 * V1 + x2 * V2 + ... + 0 * Vm
sum = x1 * V1 + x2 * V2 + ... + 1 * Vm
sum = x1 * V1 + x2 * V2 + ... + 2 * Vm
sum = x1 * V1 + x2 * V2 + ... + K * Vm &
　　其中K是该xm能取的最大数值K = sum / Vm。可是这又有什么用呢？不要急，我们先进行如下变量的定义：
dp[i][sum] = 用前i种硬币构成sum 的所有组合数。
　　那么题目的问题实际上就是求dp[m][sum]，即用前m种硬币（所有硬币）构成sum的所有组合数。在上面的联合等式中：当xn=0时，有多少种组合呢？ 实际上就是前i-1种硬币组合sum，有dp[i-1][sum]种！ xn = 1 时呢，有多少种组合？ 实际上是用前i-1种硬币组合成(sum - Vm)的组合数，有dp[i-1][sum -Vm]种; xn =2呢， dp[i-1][sum - 2 * Vm]种，等等。所有的这些情况加起来就是我们的dp[i][sum]。所以：
dp[i][sum] = dp[i-1][sum - 0*Vm] + dp[i-1][sum - 1*Vm]
+ dp[i-1][sum - 2*Vm] + ... + dp[i-1][sum - K*Vm]; 其中K = sum / Vm
　　换一种更抽象的数学描述就是：
　　通过此公式，我们可以看到问题被一步步缩小，那么初始情况是什么呢？如果sum=0，那么无论有前多少种来组合0，只有一种可能，就是各个系数都等于0；
dp[i][0] = 1 & // i = 0, 1, 2, ... , m
　　如果我们用二位数组表示dp[i][sum], 我们发现第i行的值全部依赖与i-1行的值，所以我们可以逐行求解该数组。如果前0种硬币要组成sum，我们规定为dp[0][sum] = 0.&
　　通过上面的讨论，我们最终可以写出下面的代码来求解该类问题：
* Filename :coins.cpp
* Description: solve coin combinations using dynamic programing
* Complier: g++
* Author: python27
7 #include &iostream&
8 #include &string&
9 #include &cmath&
10 #include &vector&
12 using namespace
14 /****************************************************************
* coin Combinations: using dynamic programming
* Basic idea:
* dp[i][j] = sum(dp[i-1][j-k*coins[i-1]]) for k = 1,2,..., j/coins[i-1]
* dp[0][j] = 1 for j = 0, 1, 2, ..., sum
* coins[] - array store all values of the coins
* coinKinds - how many kinds of coins there are
* sum - the number you want to construct using coins
* the number of combinations using coins construct sum
* c[3] = {1, 2, 5};
* int result = coinCombinations(c, 3, 10);
****************************************************************/
34 int coinCombinations(int coins[], int coinKinds, int sum)
// 2-D array using vector: is equal to: dp[coinKinds+1][sum+1] = {0};
vector&vector&int& & dp(coinKinds + 1);
for (int i = 0; i &= coinK ++i)
dp[i].resize(sum + 1);
for (int i = 0; i &= coinK ++i)
for (int j = 0; j &= ++j)
dp[i][j] = 0;
//init: dp[i][0] = 1; i = 0, 1, 2 ..., coinKinds
//Notice: dp[0][0] must be 1, althongh it make no sense that
//using 0 kinds of coins construct 0 has one way. but it the foundation
//of iteration. without it everything based on it goes wrong
for (int i = 0; i &= coinK ++i)
dp[i][0] = 1;
// iteration: dp[i][j] = sum(dp[i-1][j - k*coins[i-1]])
// k = 0, 1, 2, ... , j / coins[i-1]
for (int i = 1; i &= coinK ++i)
for (int j = 1; j &= ++j)
dp[i][j] = 0;
for (int k = 0; k &= j / coins[i-1]; ++k)
dp[i][j] += dp[i-1][j - k * coins[i-1]];
return dp[coinKinds][sum];
76 int main()
int coins[8] = {1, 2, 5, 10, 20, 50, 100, 200};
int sum = 200;
int result = coinCombinations(coins, 8, 200);
cout && "using 8 kinds of coins construct 200, combinations are: " &&
cout && result &&
　　聪明的读者或许已经发现，在算法的描述中说明用动态规划的方法来求解此问题，什么？动态规划，我们什么时候用动态规划了？哈哈，在我们写出递归公式并且给出初始解的时候，我们就已经在用动态规划了。
　　动态规划的基本思想就是将待求解问题分解为若干子问题，（如本题中我们将dp[i][j]分解为若干dp[i-1][j-x]的问题），先求解这些子问题并将结果保存起来( 我们用dp[][]二维数组保存子结果)，若在求解较大的问题时用到较小子问题的结果，可以直接取用(求dp[i][j]时用dp[i-1][x]的结果)，从而免去重复计算。动态规划是一种非常强大的算法思想，无论做过多少动态规划的题目，下一次依然会被动态规划的强大所震撼。随后的博客中，我们会更多的接触动态规划。你可以在后面的参考文献中找到更多有用的资源。&
[1] ProjectEuler:&
[2] Topcoder Algorithm tutorial:&
[3] Sanjoy Dasgupta. 算法概论. 清华大学出版社， - 193. &
[4] Thomas H. Cormen, et al. 算法导论. 机械工业出版社， - 212.
阅读(...) 评论()用户等级：初中三年级
注册时间：
在线时长：1621 小时
元宝：1005
金币：2428
等级：初中三年级
<em id="authorposton13-10-30 21:48
查看: 785&
本帖最后由 jeokeo 于
21:51 编辑
首先要明白什么是“翻硬币问题”，通常题面形式是这样的：　　M个硬币全部正面朝上，现在要求每次必须同时翻转其中的N个硬币，至少翻转多少次才能使全部硬币反面朝上?　　那么可能出现四种情况：硬币总数（M）每次翻硬币数量（N）备注1奇奇2奇偶不可能完成的任务3偶奇4偶偶　　上面四种情况中，只有当硬币总数是奇数个并且每次翻偶数个硬币时，不能完成要求，其他三种都可以完成翻转。
　　为什么不能完成这种情况呢?根据奇偶的基本性质可以推导出来，每个硬币必须翻转奇数次才能实现反面朝上，现在总数是奇数，那么所有硬币翻转总数就是奇数个奇数，其结果必定是个奇数。但是每次翻转偶数个硬币，那么硬币被翻动的总数为偶数乘以翻动次数，结果必定是偶数。所以这种情况下是不可能完成任务的。　　翻硬币问题形式多样，这里总结出了一个基本的解题步骤。　　第一步：判断总个数是否与每次翻的个数呈倍数关系。如果是倍数关系，翻动次数=M÷N　　第二步：如果没有倍数关系，考虑硬币总数的奇偶情况。　　当总数为偶数　　(1)每次翻的个数是总数减一　　【例1】现有6个一元面值硬币正面朝上放在桌子上，你可以每次翻转5个硬币(必须要翻转5个)，问你最少要经过几次翻转可以使这6个硬币全部反面朝上?　　A.5次 B.6次 C.7次 D.8次　　【解析】本题属于归纳推理问题。一个硬币要翻面，需要翻奇数次，一共有6个硬币，每一次翻转5个，那么必须翻转偶数次才能保证每一枚硬币翻转奇数次，故排除A、C。因为每次翻五个，则有一个没被改变，或者说每次是在原来的基础上变一个，一共有6个硬币，每次变一个，那么需要6次才能全部变完。具体过程如下：　　O O O O O O　　O X X X X X　　X X O O O O　　O O O X X X　　X X X X O O　　O O O O O X　　X X X X X X　　故需要6次，故正确答案为B。　　这类问题的解答公式为：翻动次数=M　　翻动方法：只要按照第一次第一个不翻，第二次第二个不翻，按照此方法进行操作就可以成功。　　(2)除了上述以外情况，要计算翻动次数，我们采用余数分析法。　　首先用总数(M)÷每次翻的个数(N)，表达式为：　　M÷N=a……b　　上面式子中，a为商，b为余数。那么我们把余数分成三种情况：　　①b=1，翻动次数=a+1　　【例2】共有10个硬币正面朝上，每次翻动3个，总共翻动几次才能反面朝上?　　A.3次 B.4次 C.5次 D.6次　　【解析】利用公式：M÷N=10÷3=3……1。余数b=1，翻动次数=3+1=4。　　这个公式在怎么推导出来的呢?　　此题计算为10÷3=3……1，余数为1，我们需要改写余数为10÷3=2……4，相当于翻了2次3个硬币，还剩下4个硬币没有翻过来。　　OOOOOO OOOO　　XXXXXX OOOO　　那么我们将这4个硬币分成两组，每组两个。接下来翻其中的2个硬币和前面已经翻成反面的1个硬币。　　XXXXXO XXOO　　最后把剩下的两个正面硬币和刚才翻成正面的那个硬币一起翻过来。　　XXXXXX XXXX　　只要余数是偶数，都可以采用这样的方法翻转。　　再回过头来看下最初计算式子，10÷3=3……1，我们改写余数为10÷3=2……4，商减少了1，余数变成了1+3=4，余数加除数。根据奇偶基本性质，这里变化的余数一定是个偶数，因为被除数是偶数，被除数=除数×商+1，要使余数为1，除数和商必定也是奇数。所以变化后的余数等于1+除数，结果必定为偶数。偶数就需要2步完成翻转，总体上在原来商的基础上只增加了1，所以余数b=1时，翻动次数=a+1。　　②b=偶数，翻动次数=a+2　　【例3】共有92个杯口朝上的杯子，每次翻动11个杯子，使其杯口朝下，总共翻动几次才能让所有杯子反面朝下?　　A.9次 B.10次 C.11次 D.12次　　【解析】利用公式：M÷N=92÷11=8……4。余数b=偶数，翻动次数=8+2=10。　　翻动方法和上一道例题相同，将最后剩下的4个杯子分成两组，先翻其中的2个和前面已经翻过的2个，然后刚好剩下4个杯口朝上的杯子。总共需要10次。翻动方法如图所示：　　(第8次) XXX …… XXX XXX XXX OOOO　　(第9次) XXX …… OOO OOO OOO XXOO　　(第10次)XXX …… XXX XXX XXX XXXX　　③b=奇数，翻动次数=a+3　　【例4】有18个房间开着灯，如果每次同时拨动5个房间的开关，经过几次拨动，灯全部关上?　　A.3次 B.4次 C.6次 D.几次也不能　　【解析】利用公式：M÷N=18÷5=3……3。余数b=奇数，翻动次数=3+3=6。　　余数是奇数时，为什么要翻3次呢?是如何翻转的呢?下面我们用硬币翻转来代替灯的开关。　　首先完成三次翻转，如图所示：　　OOOOO OOOOO OOOOO OOO　　XXXXX OOOOO OOOOO OOO　　XXXXX XXXXX OOOOO OOO　　XXXXX XXXXX XXXXX OOO　　接下来将剩下的3个全部翻转，并且把前面翻过来的2个再次翻转。　　XXXXX XXXXX XXXOO XXX　　现在就和前面讲的余数是偶数情况相同了。把剩下的分成两组，先翻其中的一组，不够的在前面翻过里面翻转。　　OOOOX XXXXX XXXXO XXX　　最后剩下的刚好翻完。　　XXXXX XXXXX XXXXX XXX　　前面我们讨论的是总数是偶数，总数是奇数时有两种情况：　　(1)每次翻转的个数为奇数，那么按照上面讲的余数分析法解决。　　M÷N=a……b　　①b=1，翻动次数=a+1　　②b=偶数，翻动次数=a+2　　③b=奇数，翻动次数=a+3　　(2)每次翻转的个数为偶数，这种情况下无法完成任务。　　【例5】有7个杯口全部向上的杯子，每次将其中4个同时翻转，经过几次翻转，杯口可以全部向下?【09山西】　　A.3次 B.4次 C.5次 D.几次也不能　　【解析】根据公式，不可能完成任务。所以选D。要想杯子杯口朝下的话，需要翻转奇数次，所以七个杯口要全部向下的话，翻转的总次数为7个奇数的和，必定也是奇数，所以总共也是需要翻转奇数次才行。但是每次翻转其中4个，不论翻多少次总数都是偶数，因此无论翻几次都不行。正确答案为D。
21:47 上传
欧几里德留下了几何原本，传抄在雪白的羊皮纸上，距今已有两千三百多年；阿波罗尼生于帕加，凝视着永恒的圆锥曲线；丢番图却在静静的欣赏不定方程的解，微分、级数、离散、收敛是谁的发现？
喜欢你在连续之中逼近我的极限，经过剑桥三一学院，我以牛顿之名许愿，思念就像傅利叶级数一样蔓延，当空间只剩下拓扑的语言，映射就成了永垂不朽的诗篇，我给你的爱写在Banach空间，深埋在康托尔集合里面，用超越数去超越永远，那一绝对收敛的数列，一万年都不变！
用户等级：初中二年级
注册时间：
在线时长：95 小时
<em id="authorposton13-10-31 09:10
谢谢家长分享，很受用
用户等级：初中一年级
注册时间：
在线时长：63 小时
<em id="authorposton13-10-31 16:03
用户等级：初中三年级
注册时间：
在线时长：784 小时
金币：7217
<em id="authorposton13-10-31 18:48
仔细学习下了，争取类似问题过关
用户等级：小学四年级
注册时间：
在线时长：107 小时
<em id="authorposton13-11-5 22:15
很有启发，学习。
用户等级：初中三年级
注册时间：
在线时长：441 小时
金币：1994
<em id="authorposton13-11-5 23:30
Powered by}