2月3日,立春,多云。“一二三四五六七,万物生芽是今日“。
例12
猜数游戏。计算机随机选择一个0---999之间的整数,然后让人来猜。如果猜测的数字大于实际的数字,就提示说太大了;如果猜测的数字小于实际的数字,就提示说太小了。总共只给十次机会。
提示:1、产生随机数需要头文件 #include
<stdlib.h>;
2、rand()是产生随机数的函数,可产生0至32767的整数;
3、产生随机数需要设置种子:
srand((unsigned)time(NULL));
因为时间是变化的,故产生的随机数也是不同的。
这题目不难,俺老猪是这样做的:
6 srand((unsigned)time(NULL)); 8 int MagicNumber = rand()%1000; 13 printf("输入你的猜测数字(0..999)"); 15 if(Guess==MagicNumber){ 21 printf("十次都没猜中,你玩完了\n");
针对这个问题,大家如何 “又快又稳” 的猜出的呢?如果是一个不懂算法的人,估计就是一个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
大家看看,是不是体现了”递推“的核心思想,代码也很简单。
11 for(int i=2;i<month;i++) 12 fab[i]=fab[i-1]+fab[i-2]; 14 for(int i=0;i<month;i++) 15 cout<<"第"<<i+1<<"个月兔子为:"<<fab[i]<<endl;
结果:
第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;
10 month[i]=month[i+1]/(1+rate/12)+month[48]; 13 cout<<"第"<<i<<"个月末本利合计为:"<<month[i]<<endl;
结果:
第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!
printf("%d的阶乘是:%d\n",n,s);
递推算法是一种用若干步可重复的简运算(规律)来描述复杂问题的方法.
递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项,通常是通过计算机前面的一些项来得出序列中的指定象的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复,该算法利用了计算机速度快和不知疲倦的机器特点。
|