用减治法解决假币问题的解决
发布时间
阅读量：
阅读量
减治法求解假币问题
减治法：将原始问题划分为多个子问题，且原问题的解与这些子问题的解之间具有明确的关联性，这种关联通常体现为以下两种形式：
1）原问题的解仅存在于某个较小规模的子问题之中；
2）原问题的解与某个较小规模子问题的解之间存在某种对应关系。
假币问题：在n个硬币中存在一枚假币，但无法确定其具体归属哪一组？已知假币的质量小于真币，通过称重操作确定假币的位置。
设N枚硬币的质量信息保存在数组coin[N]中，函数Falsecoin用于解决该假币定位问题。
测试用例：coin[]={2,2,1,2,2,2,2,2}
#include<stdio.h>
int coin[]={2,2,1,2,2,2,2,2};
int Falsecoin(int high,int low,int n)//判断假币在哪一组
{
int num1,num2,num3;
int sum1=0,sum2=0;
if(n==1)//递归结束条件
return low+1;
if(n%3==0)//3组硬币的个数相同
num1=num2=n/3;
else
num1=num2=n/3+1;
num3=n-num1-num2;全部评论 (0)
还没有任何评论哟~