博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【算法】算法的艺术(二)
阅读量:7241 次
发布时间:2019-06-29

本文共 5282 字,大约阅读时间需要 17 分钟。

国民生产总值多少年翻番?

   假设我国工农业总产值以每年9%的速度增长,问多少年翻一番?
   实例解析:
   翻一番意味着变为原来的两倍,而每年只能增加9%,相当于每年乘上一个1.09。我们可以在程序中不断地乘以1.09,并对此进行计数,若已经达到两倍,则计数器中的值便是需要经过的年数。
   这是一个事先无法确定循环次数的循环。
#include
   int main()   {int n = 0;    float y = 1; //设当年的产值为1,类型不能是int    while( y < 2.0){ //以产值达到2作为结束循环的条件    y *= 1.09;    n++; //每乘一次1.09就意味着过了一年    }    printf(“%d\n”, n);    getch();    return 0;   }   
   这段程序用for循环也能实现:
#include
   int main()   {int n;    float y = 1;    for(n = 0; y < 2.0; n++) //循环条件不是由计数器控制的    y *= 1.09;   printf(“%d\n”, n);   getch();    return 0;   }
 
 

兑换硬币
   一块钱人民币用1分、2分、5分的硬币兑换,共有多少种换法?
   实例解析:
   这其实是第三章中的一个例子,这里我们给出另一种解题思路。
   一块钱若全用5分硬币兑换,则应该换20个;若全用2分硬币,则是50个;若全用1分硬币,则是100个。
   假设我们用m个5分的,n个2分的,则这两个变量的取值范围分别是:0<=m<=20, 0<=n<=50。
   m有21种取值,n有51种取值。
   我们让代表“5分个数”的m和代表“2分个数”的n各自在范围内取一个值,若这两种硬币加起来超过100分(一元钱),则这个m、n的组合是不可用的,若加起来不超过(小于等于)100,不足100的部分可以用1分的硬币补足,因此这个组合应为一种可用的兑换方法。
   让m和n取遍所有可能的组合,便可知道共有多少兑换方法。
   代码如下:
#include 
   int main()   {int n, m, k, count = 0; //count用来计数    for(m = 0; m <= 20; m++)    for(n = 0; n <= 50; n++)    if(m*5 + n*2 <= 100)    count++;    printf(“共有%d种兑换法\n”, count);    getch();    return 0;   }
 
   也是用的穷举法,但仅对m和n的取值穷举,所以较之前少了一层循环,效率更高。
 

 


里程碑上的对称数
   一辆匀速行驶的汽车,清晨,司机看到历程碑上的数是一个对称数:67576,2小时后他才又看到一个对称数,问汽车速度多少?
   实例解析:
   要知道汽车速度,必须知道第二个对称数是多少。我们采用下面的方法找第二个对称数:用循环对67576之后的每一个数都判断一下,看是否对称数,如果是,则停止循环(用break),若不是,则继续下一个数的判断……
   这也是一个事先无法确定循环次数的循环,循环条件的写法有两种:
   (1)循环条件不写或写成1,在循环体中设置退出的条件。
   (2)事先设置一个变量作标志(值为0意味着未找到对称数,为1表示已找到),循环条件是该变量等于0。
   代码如下:
   方法1:
#include
   int main()   {long i; //超过32767, 所以用long    int a,b,c,d,e; //用来存储5个数字    for(i = 67577; ; i++){ //不写循环条件意味着条件始终成立    a = i%10; //个位上的数字    b = i/10%10; //十位上的数字    d = i/1000%10; //千位上的数字    e = i/10000; //万位上的数字     if(a == e && b == d) //遇到对称数则退出循环     break;   }printf(“汽车速度是:%5.2f\n”, (i-67576)/2.); //除以“2.”getch();    return 0;   }
 
   方法2:
#include
   int main()   {long i; //超过32767, 所以用long    int a,b,c,d,e; //用来存储5个数字    int flag = 0; //用作是否找到对称数的标志    for(i = 67577; flag == 0; i++){     a = i%10; //个位上的数字    b = i/10%10; //十位上的数字    d = i/1000%10; //千位上的数字    e = i/10000; //万位上的数字     if(a == e && b == d) //遇到对称数     flag = 1;   }   printf(“汽车速度是:%5.2f\n”, (i-67576-1)/2.);   getch();    return 0;   }
 
   注意:
   方法2计算平均速度时,被除数要多减一个1
 
-------------------------------------------------------------------------
辗转赋值法求表达式的值
   求表达式:前20项的和,保留三位小数。
   实例解析:
   该表达式有两个特点:
   (1) 从第二项开始,每一项的分子等于前一项的分母,而分母等于前一项分子分母之和;
   (2) 一正一负,正负号交错。
   对于第一个特点,我们采用前面介绍的辗转赋值的方法。这个程序需要用循环来求和,我们用变量a、b分别表示第一项的分子分母,可用a/b计算出第一项值,之后,先用b=a+b计算下一项的分母,再用a=b-a使上一项的分母变成下一项分子,然后进入下一次循环计算下一项的值。
   对于第二个特点,我们可以设一个变量sign = 1,每循环一次,给sign乘以-1,这样a/b* sign便是需要合并到sum中的值,其符号恰好一正一负。    
int main()   d{float sum = 0;   int  a = 1, b = 1, sign = 1, i ;    for(i = 1; i <= 20; i++){      sum += ((float)a/b) * sign;      b = a + b;                   //计算下一项的分母      a = b - a;                   //计算下一项的分子      sign *= -1;                  // sign变号    }    printf(“%5.3f\n”, sum);    getch();    return 0;   }
 
   注意:
   程序中sum += ((float)a/b) * sign;一行若不进行强制类型转换,则每一项结果都是0,最终结果也是0。
 

 

 


随机数的生成

   有200人,编号从1到200,从中随机抽取10人获奖,请编程完成抽奖。
  实例解析:
  现实生活中很多时候需要随机生成一些数,比如:随机抽奖,随机生成试卷等。程序中的随机数,需要随机函数来生成,TC中与随机数有关的函数有rand()、srand()、random()、randomize(),他们都是在stdlib.h中定义的,其原型及作用分别是:
int  rand();
  作用:生成一个随机数,范围0~32767。
void srand(unsigned seed);
  作用:用seed做种子初始化随机数发生器,常用系统时间做种子:
srand(time(NULL))。int random(int num);
  作用:生成一个随机数,范围0 ~ num -1。
void randomize();
  作用:用系统时间做种子初始化随机数发生器,需要包含time.h头文件。
 
  本题目要在200人中抽取获奖者,抽取的号码范围是1~200,可以使用rand或random函数,下面两种方法都可以生成一个1~200间的随机数:
rand()%200 + 1;random(200) + 1;
  本例采用后一种方法。
  如果仅仅使用random(200) +1;生成随机数,每次运行程序生成的数都相同(但一次运行中多次调用random()生成的数是不同的)。若要使每次运行生成的随机数不同,必须首先使用一次随机数种子函数:
randomize();    //需要头文件time.h支持
  本题需要生成10个1~200间的号码,循环十次即可:
int i, n[11];randomize();for(i = 1; i <= 10; i++){    n[i] = random(200) + 1;}
  但是这里有一个问题,就是生成的十个数有可能有重复的,如何才能避免重复?
  可以采用这样的方法:循环过程中,每生成一个数,先存起来,然后与前面已经存在的每个数作比较,若有相同的,则重新生成一个新数,覆盖原来的数,直到与前面的数不重复为止。
int i, j, n[11];randomize();for(i = 1; i <= 10; i++){  n[i] = random(200) + 1;  for(j = 1; j < i; j++)     if(n[i] == n[j]){        i--;            break;     }}
  代码中i--的目的是,先使i减1,待执行i++后,i变回原值,这样下一次循环生成的随机数恰可以覆盖原来的数n[i],这便是本算法的巧妙之处。
  为了美观,随机数最好从小到大进行输出,故生成随机数之后,还需要排序。
  本实例完整的程序是:
#include 
  #include
  #include
  int main()  {int i, j, n[11],k,t;   randomize();   for(i = 1; i <= 10; i++){   n[i] = random(200) + 1;   for(j = 1; j < i; j++)   if(n[i] == n[j]){   i--;    break;   }   }   //以下代码是选择法排序   for(i = 1; i <= 9; i++){    k = i;    for(j = i+1; j <= 10; j++)    if(n[j] < n[k])    k = j;    t = n[i];    n[i] = n[k];    n[k] = t;   }   //以下代码输出   for(i = 1; i <= 10; i++)    printf(“%5d”, n[i]); printf(“\n”); getch();   return 0;  }
 

本文出自 “” 博客,请务必保留此出处

转载地址:http://nfybm.baihongyu.com/

你可能感兴趣的文章
ECS应用管理最佳实践
查看>>
12.throw和throws是的区别
查看>>
115.springboot + mybaties
查看>>
福建海峡银行使用ManageEngine统一管控业务应用系统
查看>>
ssh访问与控制
查看>>
java访问数据库
查看>>
皆大欢喜!iPhone不再耗电,续航增加就靠它
查看>>
路由重发布配置代码
查看>>
编写脚本 sumid.sh,计算/etc/passwd文件中的第10个用户和第20用户的 ID之和
查看>>
MYSQL数据库命令
查看>>
C语言win32窗口的俄罗斯方块程序
查看>>
【翻译】Ext JS 5的平板支持
查看>>
工作之餘的保健之法
查看>>
mysql条件字段为空
查看>>
宇宙沸腾SCCM 2012 R2系列(10)OSD操作系统部署(二)- 添加和分发系统映像包
查看>>
win7系统GNS3连接真实网络
查看>>
grub加密
查看>>
gird鼠标移动显示tip
查看>>
Centos 6.2文本模式安装
查看>>
经典日志分析-AWStats
查看>>