加载中…
个人资料
  • 博客等级:
  • 博客积分:
  • 博客访问:
  • 关注人气:
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
正文 字体大小:

算法设计例题2

(2012-11-22 22:56:16)
标签:

杂谈

分类: c语言

有10箱产品每箱有1000件,正品每件100 克。其中的几箱是次品,次品每件比正品轻10 克,问能否用秤只称一次,就找出哪几箱是次品。
问题分析:
1) 假设只有一箱是次品:先将箱子编码1,2,3, 4……10。再从1号箱取1件产品,2号箱取2件产品,3号箱取3件产品……10号箱取10件产品,称它们的重量, 若比标准重量轻10克则1号箱为次品;比标准重量轻20 克,则2号箱为次品;比标准重量轻30克,则3号箱为次 品;……比标准重量轻100克,则10号箱为次品。
设取出产品重量为w,则次品的箱号为((1+2+3+……+10) *100-w)/10。

2) 若不止一箱次品时,以上的方法就行不通了。但以上方法的基本思想还是可利用的,即根据取出每箱产品数量的差异,和取出产 品的总重量与标准重量误差,来分析推算次品的箱号。
数字化过程:先将箱子编码1,2,3,4……10。用枚举方法分析问题,由小到大讨论:
从“1”号箱取1件产品,若最后总重量比标准重量轻10克,则1号箱为次品;
从“2”号箱取2件产品,若最后总重量比标准重量轻20克,则2号箱为次品;

从“3”号箱若取3件产品,若最后总重量比标准重量轻30克,无法识别哪些箱是次品。但从3号箱取4件产品,若最后总重量比标准重量轻40克,肯定3号箱为次品;
再看“4”号箱,
①取5件产品,若最后总重量比标准重量轻50克,无法识别哪些是次品:可能是1、3号箱(分别取1件、4件)或5号箱为次品。
② 取6件产品,若最后总重量比标准重量轻60克,无法识别 哪些是次品:可能是2、3号箱(分别取2件、4件)或5号箱为次 品。

③ 取7件产品,若最后总重量比标准重量轻70克,也无法识别 哪些是次品:可能是1、2、3号箱(分别取1件、2件、4件)或 5号箱为次品。
④ 取8件产品,则最后总重量比标准重量轻80克,则可以肯定 4号箱为次品;无需继续枚举就可看出:1,2,3,4……10号箱取产品的件数分别为20,21,22,23,24,25,26,27, 28,29,即1,2,4,8,16,32,64,128,256,512件。

3)根据以上方法,取出产品称量后:
轻10克1号箱为次品。
轻20克2号箱为次品。
轻30克1、2号箱为次品。
轻40克3号箱为次品。
轻50克1、3号箱为次品。
轻60克2、3号箱为次品。
轻70克1、2、3号箱为次品。
轻80克4号箱为次品。
轻90克1、4号箱为次品。
…………

算法设计:用算式或算法来识别误差与次品箱号.首先是计算标准总重量,存储在变量w1中。输入称取的总重量,存储在变量w2中。然后计算出比标准重量轻多少,仍存储在变量w1中。
1)当w/10=2k 时,则k+1号箱为唯一的一箱次品。
2)当w/10>2k k取最大时记为k1,k1+1号箱为的次品箱;
继续讨论w/10-2 k1 >2 k k取最大时记为k2,k2+1号箱为的次品箱;
…………
直到取等号w/10-2 ki-1 =2 ki ,ki+1号箱为的次品箱;结束。

#include
void main( )
{
 int i,k,n,w1=0,w2=0,t;
    printf("Input the number of boxes:");
    scanf("%d",&n);
    t=1;
    for (i=1;i<=n;i++)
 {
  printf("\n%d box take %d units.\n",i,t);
        w1=w1+t;t=t*2;
 }
    w1=w1*100;
    printf("normal weight %d \n",w1);
    printf("Input reality weight:");
    scanf("%d",&w2);
    w1=(w1-w2)/10;
 while(w1)
 {
  k=0;
        t=1;
        while( w1-t>=0)   //算法说明:算法中的while 循环及其后语句,
  //是用于计算最接近当前重量w1的2 k,则k号箱为次品箱。这个过程也可以通过使用函数来完成。
  {
  t=t*2;
  k=k+1;
  }
        printf("%d is bad\n",k);
        w1=w1-t/2;
 }
}

0

阅读 收藏 喜欢 打印举报/Report
  

新浪BLOG意见反馈留言板 欢迎批评指正

新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 产品答疑

新浪公司 版权所有