网站建设多少钱怎么卖,seo网课培训,专业南京网站建设,深圳app开发红孩儿文章目录1. 问题描述2. 解题思路3. 代码实现1. 问题描述
n 个硬币中有1枚是假币#xff0c;真假币唯一的区别是假币重量轻#xff0c;如何快速找出假币
2. 解题思路
暴力做法#xff0c;一个一个的称重#xff0c;O#xff08;n#xff09;复杂度分治思路
将硬币等分…
文章目录1. 问题描述2. 解题思路3. 代码实现1. 问题描述
n 个硬币中有1枚是假币真假币唯一的区别是假币重量轻如何快速找出假币
2. 解题思路
暴力做法一个一个的称重On复杂度分治思路
将硬币等分成两份若为奇数多出一枚放在天平两边轻的一边包含假币若相等则假币是多出的那一枚对轻的一边继续上述操作直到找出假币 复杂度Olog n
3. 代码实现
/*** description: n 个硬币中有1枚是假币假币重量轻如何快速找出假币* author: michael ming* date: 2019/7/6 20:37* modified by: */
#include iostream
#include ctime
#include random
using namespace std;
int findcoin(int *weight, int left, int right, int weightimes)
{if(left1 right)//只有2枚硬币{weightimes;//称重比较一次if(weight[left] weight[right])return left;//返回重量小的位置elsereturn right;}int i, mid, weightsumL, weightsumR;weightsumL weightsumR 0;mid left (right-left)/2;if((right-left1)%2 0)//偶数枚银币{weightimes;for(i left; i mid; i)weightsumL weight[i];//计算左边重量(计算机没有天平只能一个个加)for(i mid1; i right; i)weightsumR weight[i];//右边重量if(weightsumL weightsumR)//左边重假币在右边return findcoin(weight,mid1,right,weightimes);else if(weightsumL weightsumR)//假币在左边return findcoin(weight,left,mid,weightimes);else//假币不在两边偶数枚银币;//什么都不做不必再找了}else//奇数枚硬币{weightimes;for(i left; i mid-1; i)weightsumL weight[i];//计算左边重量for(i mid1; i right; i)weightsumR weight[i];//右边重量if(weightsumL weightsumR)//左边重假币在右边return findcoin(weight,mid1,right,weightimes);else if(weightsumL weightsumR)//假币在左边return findcoin(weight,left,mid-1,weightimes);else//两边相等奇数枚硬币剩余的那个是假币return mid;}
}
int main()
{srand(unsigned(time(0)));int num, i, weightimes 0;cout 请输入硬币总个数:;cin num;const int coinNum num;int *weight new int [coinNum];for(i 0; i coinNum; i){weight[i] 10;}i rand()%num;weight[i] 9; //随机生成假币for(i 0; i coinNum; i)//打印硬币信息{cout i 1 硬币重量: weight[i] endl;}cout 假硬币是第 findcoin(weight,0,coinNum-1,weightimes)1 个。 endl;cout 共称了 weightimes 次找到假币。;delete[]weight;return 0;
}输入 2500枚、5001枚100万枚最多需要 log2n 向上取整次就能找到。
