假币
八枚硬币
问题描述
1、有八枚外观相同的硬币，其中有一枚是假币
2、不知道假币较重还是较轻
可以用减治法来求解假币问题
算法思想
1、把硬币按照下标(0-2、3-5、6-7)分成三组
2、比较第一组(0-2)与第二组(3-5)的总重量
(1)若前两组重量相等，则假币再第三组中，比较第三组中的两枚硬币找出假币
(2)若前两组重量不相等，则假币在前两组中，跳转到步骤一，继续在前两组中比较，把六枚硬币分成三组，按照上述方法比较，直至找到假币
8枚硬币问题的判定树
算法实现
第一步：产生八枚硬币
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
void produceCoins(int coins[])
{
int i;
srand((unsigned int)time(NULL));
int a = rand() % 9 + 1;//在1~10之间随机产生真币的重量
//先把所有硬币的重量都赋值为真币的质量
for(i = 0; i < 8; i++)
{
coins[i] = a;
}
int b;//假币的重量
do
{
b = rand() % 20 + 1;//在1~20之间随机产生假币的重量
}
while(b == a);//假币的重量不能和真币的重量相同
int c = rand() % 7;//在0~7之间随机产生假币的坐标
coins[c] = b;//把假币添加进去
}第二步：比较硬币找出假币
int compare(int coins[],int i, int j, int k)
{/*i、j、k是硬币的下标，其中i和j待比较的硬币，k是真币的下标*/
int isJiaBi = 1;/*是否有假币的标识，1表示有假币，0表示物价比*/
if(coins[i] > coins[k])//i和k比较
{
printf("第%d个是假币，较重\n", i + 1);
}
else if(coins[i] < coins[k])
{
printf("第%d个是假币，较轻\n", i + 1);
}
else
{
if(coins[j] > coins[k])//j和k比较
{
printf("第%d个是假币，较重\n", j + 1);
}
else if(coins[j] < coins[k])
{
printf("第%d个是假币，较轻\n", j + 1);
}
else
{
isJiaBi = 0;
}
}
return isJiaBi;
}void eightcoins(int coins[])
{
int a = coins[0]+coins[1]+coins[2];
int b = coins[3]+coins[4]+coins[5];
/*若a == b，说明前两组都是真币，假币在第三组中;
否则假币在coins[6]和coins[7]之间*/
if (a == b)
{
compare(coins,6,7,0);
}
else if (a != b)
{
/*若coins[0]+coins[1] == coins[3]+coins[4]，
则假币在coins[2]和coins[5]之间*/
if(coins[0]+coins[1] == coins[3]+coins[4])
compare(coins,2,5,6);
else
{
/*若compare(coins,0,3,2) == 0，说明coins[0]、coins[3]
是真币，则假币在coins[1]和coins[4]之间*/
if(compare(coins,0,3,2) == 0)
{
compare(coins,1,4,2);
}
}
}
}测试上述方法
int main()
{
int i;
int coins[8];
produceCoins(coins);//生成八枚硬币
//输出8枚硬币
for(i = 0; i < 8; i++)
{
printf("%d\t", coins[i]);
}
printf("\n");
eightcoins(coins);//找出假币
return 0;
}测试结果
N枚硬币
问题描述
1、有N枚外观相同的硬币，其中有一枚是假币
2、不知道假币较重还是较轻
n枚硬币求解思想和八枚硬币的求解思想有些相似，也是用减治法求解
算法思想
1、要比较的硬币个数为双数时，一分两半，分别求出两部分的硬币质量之和；若是两部分的硬币质量之和相等，说明两部分都是真币；若是不相等，说明假币在这两部分中，再细分成几个部分，递归调用该方法继续比较，直至找到假币为止
2、要比较的硬币个数为单数时，空出第一个，后面的部分为双数，从中间分成两部分，然后按双数的比较方法继续比较，如果两部分质量之和相等，再判断被空出的第一枚硬币是否是假币，如果两部分质量之和不相等，再细分成几个部分，递归调用该方法继续比较，直至找到假币为止
当然这样分组思想并不是唯一的，也有其他的分组方法
算法实现
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define MAX 10 //MAX是硬币的个数(n)
void produceCoins(int coins[], int n)//n 是硬币个数
{
int i;
srand((unsigned int)time(NULL));
int a = rand() % 10 + 1;//在1~11之间随机产生真币的重量
//先把所有硬币的重量都赋值为真币的质量
for(i = 0; i < n; i++)
{
coins[i] = a;
}
int b;//假币的重量
do
{
b = rand() % 20 + 1;//在1~21之间随机产生假币的重量
}
while(b == a);//假币的重量不能和真币的重量相同
int c = rand() % n;//随机产生假币的坐标
coins[c] = b;//把假币添加进去
}求和函数
//求coins数组下标从from到to的所有硬币的重量的和
int sum_coins(int coins[], int from, int to)
{
int i, sum = 0;
for(i = from; i <= to; i++)
{
sum+=coins[i];
}
return sum;
}通过比较找出假币
int check_coins(int coins[], int from, int to)
{
int n = to - from + 1;//要比较的硬币的个数
int res = 0;//假币的坐标，初始化为0
if(n == 1)
{
/*当只有1枚硬币时，coins[from] == coins[from + 2]或
coins[from] == coins[from - 2]说明该硬币是真币，否则说明
该硬币是假币*/
int a = coins[from] == coins[from + 2];
int b = coins[from] == coins[from - 2];
if (a || b)
{
res = 0;
}
else
{
res = from;
}
}
else
{
/*要比较的硬币个数为双数时，一分两半，分别求出两部分的硬币质量
之和；若是两部分的硬币质量之和相等，说明两部分都是真币；若是不
相等，说明假币在这两部分中，再细分成几个部分，递归调用该方法继
续比较，直至找到假币为止*/
if(n % 2 == 0)//要比较的硬币个数为双数
{
int a = sum_coins(coins, from, from + n/2 -1);
int b = sum_coins(coins, to - n/2 + 1, to);
if(a == b)
{
res = 0;
}
else
{
int res1=check_coins(coins, from, from + n/2 -1);
if(res1 == 0)//两部分质量之和相等
{
//继续比较其他部分
int res2=check_coins(coins, to - n/2 + 1, to);
if(res2 != 0)
res = res2;
else
res = 0;
}
else//两部分质量之和不相等
{
res = res1;
}
}
}
/*要比较的硬币个数为单数时，空出第一个，后面的部分为双数，从
中间分成两部分，然后按双数的比较方法继续比较，如果两部分质量
之和相等，再判断被空出的第一枚硬币是否是假币；如果两部分质量之
和不相等，再细分成几个部分，递归调用该方法继续比较，直至找到
假币为止*/
else//要比较的硬币的个数为单数
{
int res3 = check_coins(coins, from + 1, to);
if(res3 == 0)
{
//判断被空出的第一枚硬币是否是假币
if(coins[from] != coins[from + 1])
{
res = from;
}
}
else
{
res = res3;
}
}
}
return res;//返回假币的下标
}测试上述方法
int main()
{
int coins[MAX];
int i;
produceCoins(coins, MAX);//产生n枚硬币
//输出数组下标
for(i = 0; i < MAX; i++)
{
printf("%d\t", i);
}
printf("\n");
//输出所有硬币
for(i = 0; i < MAX; i++)
{
printf("%d\t", coins[i]);
}
printf("\n");
int end = check_coins(coins, 0, MAX - 1);//找出假币
printf("\nend = %d\n", end);
int a = coins[end] > coins[end + 1];
int b = coins[end] > coins[end - 1];
if (a || b)
{
printf("第%d枚是假币，假币较重", end + 1);
}
else
{
printf("第%d枚是假币，假币较轻", end + 1);
}
return 0;
}测试结果
(程序中是以12个为例的)
8枚硬币
10硬币
相关阅读
电子商务，网络办公，已经变成新时代企事业单位回避不了的问题，新网站上线如何迅速获得流量并且变现，也成了seo工作者绞尽脑汁要搞
网站建设要考虑的问题。在互联网的时代中，网站建设其实是一个非常常见的事情了，几乎每一家企业都希望在互联网上，能够留下属于自己一
当前网络发展迅速的新时代，有许多网站建设公司，因为浏览器的兼容性问题，网站的管理员付出了很多的努力去完善，除了浏览器之外，还
购买授权之前，建议认真阅读下述 “解惑”，以免造成不必要的困惑。另外也可以阅读 《layui 付费产品服务条款》注意：layuiAdmin 受国
我们在利用ftp的storeFile（）上传存储文件的时候，为了让上传速度提升，建议采用添加缓冲区的方式，根据上传文件的大 小，设置