【算法】算法的艺术(二)

  1. 云栖社区>
  2. 博客>
  3. 正文

【算法】算法的艺术(二)

科技小能手 2017-11-08 18:23:00 浏览502
展开阅读全文

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

   假设我国工农业总产值以每年9%的速度增长,问多少年翻一番?
   实例解析:
   翻一番意味着变为原来的两倍,而每年只能增加9%,相当于每年乘上一个1.09。我们可以在程序中不断地乘以1.09,并对此进行计数,若已经达到两倍,则计数器中的值便是需要经过的年数。
   这是一个事先无法确定循环次数的循环。
1
2
3
4
5
6
7
8
9
10
11
12
#include<stdio.h>
   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循环也能实现:
1
2
3
4
5
6
7
8
9
10
#include<stdio.h>
   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取遍所有可能的组合,便可知道共有多少兑换方法。
   代码如下:
1
2
3
4
5
6
7
8
9
10
11
#include <stdio.h>
   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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<stdio.h>
   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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<stdio.h>
   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中的值,其符号恰好一正一负。    
1
2
3
4
5
6
7
8
9
10
11
12
13
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中定义的,其原型及作用分别是:
1
int  rand();
  作用:生成一个随机数,范围0~32767。
1
void srand(unsigned seed);
  作用:用seed做种子初始化随机数发生器,常用系统时间做种子:
1
2
srand(time(NULL))。
int random(int num);
  作用:生成一个随机数,范围0 ~ num -1。
1
void randomize();
  作用:用系统时间做种子初始化随机数发生器,需要包含time.h头文件。
  本题目要在200人中抽取获奖者,抽取的号码范围是1~200,可以使用rand或random函数,下面两种方法都可以生成一个1~200间的随机数:
1
2
rand()%200 + 1;
random(200) + 1;
  本例采用后一种方法。
  如果仅仅使用random(200) +1;生成随机数,每次运行程序生成的数都相同(但一次运行中多次调用random()生成的数是不同的)。若要使每次运行生成的随机数不同,必须首先使用一次随机数种子函数:
1
randomize();    //需要头文件time.h支持
  本题需要生成10个1~200间的号码,循环十次即可:
1
2
3
4
5
6
int i, n[11];
randomize();
for(i = 1; i <= 10; i++)
{
    n[i] = random(200) + 1;
}
  但是这里有一个问题,就是生成的十个数有可能有重复的,如何才能避免重复?
  可以采用这样的方法:循环过程中,每生成一个数,先存起来,然后与前面已经存在的每个数作比较,若有相同的,则重新生成一个新数,覆盖原来的数,直到与前面的数不重复为止。
1
2
3
4
5
6
7
8
9
10
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],这便是本算法的巧妙之处。
  为了美观,随机数最好从小到大进行输出,故生成随机数之后,还需要排序。
  本实例完整的程序是:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
  #include <stdlib.h>
  #include <time.h>
  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;
  }


本文转自infohacker 51CTO博客,原文链接:http://blog.51cto.com/liucw/1171337

网友评论

登录后评论
0/500
评论
科技小能手
+ 关注