分享

计算思维实践之路(七)

 宇哥小屋 2020-01-05

      2月3日,立春,多云。“一二三四五六七,万物生芽是今日“。

      例12 猜数游戏。计算机随机选择一个0---999之间的整数,然后让人来猜。如果猜测的数字大于实际的数字,就提示说太大了;如果猜测的数字小于实际的数字,就提示说太小了。总共只给十次机会。

     提示:1、产生随机数需要头文件 #include <stdlib.h>;

                               2、rand()是产生随机数的函数,可产生0至32767的整数;

                               3、产生随机数需要设置种子:

                                           srand((unsigned)time(NULL));
                                   因为时间是变化的,故产生的随机数也是不同的。
     
这题目不难,俺老猪是这样做的:

  1. 1 #include <stdio.h>
  2. 2 #include <stdlib.h>
  3. 3 #include <time.h>
  4. 4 int main(){
  5. 5 int i,x,Guess;
  6. 6 srand((unsigned)time(NULL));
  7. 7
  8. 8 int MagicNumber = rand()%1000;
  9. 9
  10. 10 int NumGuess = 0;
  11. 11
  12. 12 while(1){
  13. 13 printf("输入你的猜测数字(0..999)");
  14. 14 scanf("%d",&Guess);
  15. 15 if(Guess==MagicNumber){
  16. 16 printf("恭喜你猜对了!\n");
  17. 17 break;
  18. 18 }
  19. 19 else{
  20. 20 if(++NumGuess>=10){
  21. 21 printf("十次都没猜中,你玩完了\n");
  22. 22 break;
  23. 23 }
  24. 24 if(Guess<MagicNumber)
  25. 25 printf("太小了,再大一点\n");
  26. 26 else
  27. 27 printf("太大了,再小一点\n");
  28. 28
  29. 29 }
  30. 30 }
  31. 31
  32. 32 return 0;
  33. 33
  34. 34 }
              针对这个问题,大家如何 “又快又稳” 的猜出的呢?如果是一个不懂算法的人,估计就是一个for循环进行查找,但是这个的复杂度是O(n)。

       那么懂算法的人就会利用数字有序这个特点进行"二分查找“,这个复杂度就是log2N,所以说学算法,懂算法可以给我们实际应用中带来更好的解决方案。

       例13  递推中有两种,“顺推”和“逆推“。顺推的例子:著名的“斐波那契”数列,说的是繁殖兔子的问题,题目如下:

如果1对兔子每月能生1对小兔子,而每对小兔在它出生后的第3个月就可以生1对小兔子,如果从1对初生的小兔子开始,1年后能

繁殖多少兔子?

思路:其实这个问题我们可以将兔子划分为“1月大的兔子“,”2月大的兔子“,”3月大的兔子“。

        ① 初始时:            一对1月大小兔子,总数为1对。

        ② 第一个月:         1月大的小兔子变成2月大的兔子,总数还是1对。

        ③ 第二个月:         2月大的小兔子变成3月大的兔子,繁殖了一对小兔子,总数为2对。

        ④ 第三个月:         3月大的兔子tmd有生了一对小兔子,上个月1月大的小兔子变成了2月大的兔子,总数为3对。

         ......                    ......

        F0=1

        F1=1

        F2=F0+F1

        F3=F1+F2

        ......

        Fn=Fn-2+Fn-1

 大家看看,是不是体现了”递推“的核心思想,代码也很简单。

  1. 1 #include <iostream>
  2. 2 using namespace std;
  3. 3
  4. 4 int main(){
  5. 5 int month =12;
  6. 6 int fab[12];
  7. 7
  8. 8 fab[0]=1;
  9. 9 fab[1]=1;
  10. 10
  11. 11 for(int i=2;i<month;i++)
  12. 12 fab[i]=fab[i-1]+fab[i-2];
  13. 13
  14. 14 for(int i=0;i<month;i++)
  15. 15 cout<<"第"<<i+1<<"个月兔子为:"<<fab[i]<<endl;
  16. 16
  17. 17 return 0;
  18. 18 }
结果:

第1个月兔子为:1
第2个月兔子为:1
第3个月兔子为:2
第4个月兔子为:3
第5个月兔子为:5
第6个月兔子为:8
第7个月兔子为:13
第8个月兔子为:21
第9个月兔子为:34
第10个月兔子为:55
第11个月兔子为:89
第12个月兔子为:144

例14  递推---逆推的例子

        这个一个关于存钱的问题,一个富二代给他儿子的四年大学生活存一笔钱,富三代每月只能取3k作为下个月的生活费,采用的是整存零取的方式,年利率在1.71%,请问富二代需要一次性存入多少钱。

   思路: 这个题目是我们知道了结果,需要逆推条件, 第48月富三代要连本带息的把3k一把取走,那么

         第47月存款应为: 第48个月的存款/(1+0.0171/12(月))+3000

        第46月存款应为: 第47个月的存款/(1+0.0171/12(月))+3000;

         .....                    .....

        第1个月存款应为: 第2个月的存款/(1+0.0171/12(月))+3000;

  1. 1 #include <iostream>
  2. 2 using namespace std;
  3. 3
  4. 4 int main(){
  5. 5 double month[49];
  6. 6 month[48]=3000;
  7. 7 double rate=0.0171;
  8. 8
  9. 9 for(int i=47;i>0;i--)
  10. 10 month[i]=month[i+1]/(1+rate/12)+month[48];
  11. 11
  12. 12 for(int i=48;i>0;i--)
  13. 13 cout<<"第"<<i<<"个月末本利合计为:"<<month[i]<<endl;
  14. 14
  15. 15 return 0;
  16. 16 }
结果:

第48个月末本利合计为:3000
第47个月末本利合计为:5995.73
第46个月末本利合计为:8987.2
第45个月末本利合计为:11974.4
第44个月末本利合计为:14957.4
第43个月末本利合计为:17936.1
第42个月末本利合计为:20910.6
第41个月末本利合计为:23880.8
第40个月末本利合计为:26846.8
第39个月末本利合计为:29808.6
第38个月末本利合计为:32766.2
第37个月末本利合计为:35719.6
第36个月末本利合计为:38668.8
第35个月末本利合计为:41613.7
第34个月末本利合计为:44554.5
第33个月末本利合计为:47491.1
第32个月末本利合计为:50423.5
第31个月末本利合计为:53351.8
第30个月末本利合计为:56275.9
第29个月末本利合计为:59195.8
第28个月末本利合计为:62111.6
第27个月末本利合计为:65023.2
第26个月末本利合计为:67930.6
第25个月末本利合计为:70834
第24个月末本利合计为:73733.2
第23个月末本利合计为:76628.3
第22个月末本利合计为:79519.2
第21个月末本利合计为:82406.1
第20个月末本利合计为:85288.8
第19个月末本利合计为:88167.4
第18个月末本利合计为:91042
第17个月末本利合计为:93912.4
第16个月末本利合计为:96778.8
第15个月末本利合计为:99641.1
第14个月末本利合计为:102499
第13个月末本利合计为:105353
第12个月末本利合计为:108204
第11个月末本利合计为:111050
第10个月末本利合计为:113892
第9个月末本利合计为:116729
第8个月末本利合计为:119563
第7个月末本利合计为:122393
第6个月末本利合计为:125219
第5个月末本利合计为:128041
第4个月末本利合计为:130859
第3个月末本利合计为:133672
第2个月末本利合计为:136482
第1个月末本利合计为:139288
例15  递推---顺推的例子 求n!

  1. #include <stdio.h>
  2. int main()
  3. {
  4. int s,n,i;
  5. printf("请输入所求的阶乘:\n");
  6. scanf("%d",&n);
  7. s=1;
  8. for(i=1;i<=n;i++)
  9. s=s*i;
  10. printf("%d的阶乘是:%d\n",n,s);
  11. return 0;
  12. }
大笑
递推算法是一种用若干步可重复的简运算(规律)来描述复杂问题的方法.
递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项,通常是通过计算机前面的一些项来得出序列中的指定象的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复,该算法利用了计算机速度快和不知疲倦的机器特点。





    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多