一、 数据结构和算法关系 为什么要学数据结构和算法? 通常,计算机解决问题的步骤如下:
二、 两种算法的比较 在此之前大家都已经学过C语言了,不管学的好不好,也可以写点小程序。现在写一个求1+2+3+……+100结果的程序,大多数人会马上写出下面的C语言代码(或者其他语言的代码): inti,sum =0,n =100;for(i =1;i < = n;i++) { sum = sum + i; } printf("%d",sum); 这是最简单的计算机程序之一,它就是一种算法。问题在于,这样是不是真的很好?是不是最高效? 以高斯的童年故事为例,老师要求学生计算1+2+3+……+100的结果,高斯很快就得出了答案,老师非常惊讶,高斯解释道: sum = 1+ 2+ 3+……+ 99+100 sum =100+ 99+ 98+……+ 2+ 1 2*sum =101+101+101+……+101+101 所以sum=5050 用程序来实现如下:s inti,sum =0,n =100; sum = (1+ n ) * n /2; printf("%d",sum); 他用的方法相当于另一种求等差数列的算法,不仅仅可以用于1加到100,就是加到一千,一万,一亿(需要更改整型变量类型为长整型,否则会溢出),也就是瞬间之事。但如果用刚才的程序,显然计算机要循环一千、一万、一亿次的加法运算。如果让计算机按沃斯的算法,那么速度可想而知。 三、 算法定义 算法就是解决问题的方法和步骤。在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。指令可以是计算机指令,也可以是我们平时的语言文字。也就是算法可以通过自然语言描述,也可以通过计算机指令描述。 为了解决某个或某类问题,需要把指令表示成一定的操作序列,操作序列包括一组操作,每一个操作都完成特定的功能,这就是算法了。 如:S1: 使t=1 S2: 使i=2 S3: 使t×i, 乘积仍然放在在变量t中,可表示为t×i→t S4: 使i的值+1,即i+1→i S5: 如果i≤5, 返回重新执行步骤S3以及其后的S4和S5;否则,算法结束。 四、 算法的五大特性 1. 零个输入或多个输入 算法可以具有零个或多个输入。尽管对于绝大多数算法来说,输入参数都是必要的,但对于个别情况,如打印“hello world!”这样的代码,不需要任何输入参数,因此算法的输入可以是零个。 算法至少有一个或多个输出,算法是一定需要输出的,输出的形式可以是打印输出,也可以是返回一个或多个值等。 如: #include"stdio.h"void main() { printf("Hello word!\n");/*没有这一行,程序将没有意义*/} 2. 一个输出或多个输出 算法至少有一个或多个输出,算法是一定需要输出的,输出的形式可以是打印输出,也可以是返回一个或多个值等。 如: #include"stdio.h"void main() { int a,b; scanf(“%d%d”,&a,&b); } 3. 有穷性 有穷性:指算法在执行有限的步骤后自动结束、不会出现无限循环。当然,这里有穷的概念并不是纯数学意义的,而是在实际应用当中合理的、可以接受的“有边界”,即计算机最终一定会结束。 void main() { intsum=0,i=0; while(1) sum+=i; printf(“%d”,sum); } 4. 确定性 确定性:算法的每一步骤都具有确定的含义,不会出现二义性。算法在一定条件下,只有一条执行路径,相同的输入只能有唯一的输出结果。算法的每个步骤被精确定义而无歧义。 void main() { inta=0,b,c; c=a+b; printf(“%d”,c); } 5. 可行性 可行性:算法的每一步都必须是可行的,也就是说,每一步都能够通过执行有限次数完成。可行性意味着算法可以转换为程序上机运行,并得到正确的结果。 求10!程序如下: void main() {ints=1,i;for(i=1;i<=10;i++) s*=i; printf(“10!=%d”,s); } 以上代码可以求出10!=3628800,那么要是求100!呢,只改个i<=100是否可行呢?解决方案又是什么呢?那怎么设计出一个合格的算法呢?请继续参阅第四单元 五、 经典算法 1. 分治算法 有12枚一模一样的硬币,已知其中只有一枚是假币,并且假币和真币的重量不一样(假设已知假币比真币重量轻),方法一: 把12枚硬币分成两等问如何用一个天平把假币从这12枚硬币中找出来,要求只能称3次。 (1)把12枚硬币分成两等份,每份6枚; (2)把有假币的那端的6枚硬币再分成两等份,每份3枚; (3)在有假币的那一端的3枚硬币中任取2个去称重。 方法二: (1)把12枚硬币分成三等份,每份4枚; (2)在有假币的那一端的4枚硬币中,任取两枚放到天平两端去称重; (3)若假币在余下的那两枚中,则把这两枚硬币放到天平两端去称重。 2. 穷举算法 解决百钱买百鸡问题: 某人有100元钱,要买100只鸡。公鸡5元钱一只,母鸡3元钱一只,小鸡一元钱3只。问可买到公鸡,母鸡, 小鸡各为多少只? 根据本问题可以采取逐一列举的方法:不如用x表示公鸡的数量,y表示母鸡的数量 ,z表是小鸡的的数量 x的取值范围1-100 y的取值范围1-100 z的取值范围1-100 满足三个个条件 x+y+z==100 且 5*x+3*y+z/3=100 且z%3==0 则算法简单的写成: void main() {int x,y,z;for(x=1;x<=100;x++) {for(y=1;y<=100;y++) {for(z=1;z<=100;z++) { if(x+y+z==100&&5*x+3*y+z/3=100&& z%3==0) { printf(“公鸡%d只,母鸡%d只,小鸡%d只\n”,x,y,z); } } } } } 当然,本算法也可以改进,比如公鸡数量根据价钱估计明显不能超过20只,母鸡的数量不能超过33只,修改两层循环的条件会使算法更加高效。 void main() {int x,y,z;for(x=1;x<=20;x++) {for(y=1;y<=33;y++) {for(z=1;z<=100;z++) { if(x+y+z==100&&5*x+3*y+z/3=100&& z%3==0) { printf(“公鸡%d只,母鸡%d只,小鸡%d只\n”,x,y,z); } } } } } 3. 递推算法 猴子吃桃子问题: 有数量未知的桃子,猴子第一天吃了总数量的一半又多吃一个,第二天又吃了剩下的一半有多吃一个,依次类推,到第十天桃子的数量仅剩1个,问最初桃子的数量有多少? 使用递推法则有如下计算: 第十天桃子的数量是:1 第九天的数量则是:(1+1)*2=4 第八天的数量则是:(4+1)*2=10 第七天的数量则是:(10+1)*2=22 ...... 直到推到第一天,便计算出桃子的总数量了。 void main() { intday=10,num=1;//day表示天数从第十天逆推 num表示当天桃子的数量while(day>1) { num=(num+1)*2; day--; } printf(“桃子的数量是:%d个\n”,num); } 4. 迭代算法 有一对兔子不吃不喝不会死,第三个月成熟,从成熟开始每月繁殖生下一对兔子,新生的每对兔子仍是第三个月成熟开始每月生一对兔子,那么每个月兔子的对数如何计算。 其实这就是著名数列斐波那契数列如下:1 1 2 3 5 8 13 21 34 ...... 可以采用迭代算法: void main() { inta=1,b=1c,i; printf(“打印前20项的值:\n”); printf(“%d\t%d\t”,a,b); for(i=3;i<=20;i++) { c=a+b; printf(“%d\t”,c); a=b; b=c; } } PS:这里有2048源代码关注私信找我拿! “我告诉你一个秘密,一般人我都不说的,看你与我有缘不妨就告诉你吧,有个特别好的地方,里面好多大佬,说话又好听!” “哪里啊?我也想让别人叫我靓仔!可以吗?” “想知道啊!就在下面自己加!” 某大佬:“我是一名从事了10年开发的老程序员,最近我花了一些时间整理关于C语言、C++,自己有做的材料的整合,一个完整的学习C语言、C++的路线,学习材料和工具。全球最大的C/C++爱好者就在我这里,企鹅裙进(<C语言C++编程学习14>)学习免费送给大家。这里是编程爱好者的聚集地,欢迎初学和进阶中的小伙伴。希望你也能凭自己的努力,成为下一个优秀的程序员。工作需要、感兴趣、为了入行、转行需要学习C/C++的伙伴可以跟我一起学习!” 关注我,带你遨游代码的世界! 最后分享一张C/C++学习路线给爱学习的小伙伴们 |
|