以下为《算法复习提纲(1)(1)》的无排版文字预览,完整格式请下载
下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。
什么是算法?
算法就是做事的方法或者叫计算机程序中表达的方法。也是一系列解决问题的清晰指令,也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。算法应该具有以下五个重要的特征:有穷性、确切性、输入、输出、可行性
算法的复杂性,时间复杂度的计算方法?
算法的复杂性有时间复杂性和空间复杂性两种。其作用: 时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。
时间复杂度用来表示算法的快慢。时间复杂度的计算方法:先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出T(n)的同数量级(它的同数量级有以下:1,Log2n ,n ,nLog2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n)=该数量级,若T(n)/f(n)求极限可得到一常数c,则时间复杂度T(n)=O(f(n))。
递归算法的优缺点
递归就是让程序调用自身的一种编程技巧。
优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计算法、调试程序带来很大方便。
缺点:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
分治法(二分法):基本思想:指的是每次的查找范围折半。与枚举算法相比,二分查找比较次数少,查找速度快,平均性能好的优点。其缺点是要求待查的数据已被整理为有序列表。
方程求解:P84
在线翻译:P85
动态规划
将一个问题分解为子问题递归求解,并且将中间结果保存以避免重复计算的办法,可以称为‘动态规划’。动态规划通常用来求最优解。能用动态规划解决的求最优解问题,必须满足最优解的每个局部解也都是最优的。P137
解题思路:用动态规划解题,首先要把原问题分解为若干个子问题。
往往将和子问题相关的各个变量的一组取值称为一个”状态”。一个“状态”对应一个或多个子问题。
满足以下两个条件的问题才可以用动态规划的办法求解:问题具有最优子结构性质。无后效性。
贪心算法:贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择。也就是说,不从整体最优上加以考虑,做出的只是在某种意义上的局部最优解 。
斐波那契数列:斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家莱昂纳多·斐 内容过长,仅展示头部和尾部部分文字预览,全文请查看图片预览。 % 3 == 0 && 5 * gj + 3 * mj + xj / 3 == 100) // 总花费为100元。
printf("公鸡为 %d 只,母鸡为 %d 只,小鸡为 %d 只!\n", gj, mj, xj);
}
}
system("pause");
return 0;
}
题目:有5个人坐在一起,问第5个人多少岁?他说比第4个人大2岁。问第4个人岁数,他说比第3个人大2岁。问第3个人,又说比第2人大两岁。问第2个人,说比第1个人大两岁。最后 问第1个人,他说是10岁。请问第5个人多大?(15min)程序分析:利用递归的方法,递归分为回推和递推两个阶段。要想知道第5个人岁数,需知道第4人的岁数,依次类推,推到第1人(10岁),再往回推。
代码:
#include
int age(a)//a为第几人
{
int i;//i用于存放年龄
if(a==1)
{
i=10;
return i;
}
else
{
i=age(a-1)+2;
printf("第%d轮的数是%d\n",a,i);
return i;
}
}
int main()
{
int Age=age(5);
printf("第5个人的年龄是%d岁", Age);
return 0;
}
三hanoi塔(15min)
有三根针a、b、c。a 针上有N个盘子,大的在下,小的在上,要求把这N个盘子从 a 针移到 b 针,在移动过程中可以借助 c 针,每次只允许移动一个盘,且在移动过程中在三根针上都保持大盘在下,小盘在上。解决思路:
当 n=1 时,直接将圆盘从 a 移到 b。
当 n>1 时,需要利用 b,将 n-1 个圆盘移到 c 上,然后将剩下的最大圆盘移到 b
最后利用 a,将 n-1 个较小的圆盘从 c 移到 b 上(递归子问题 n-1)。
我们将n个圆盘的移动问题就分解成了两次 n-1 个圆盘的移动问题。
递归算法:
public static void hanoi(int n,int a,int b,int c){
if(n==1){
move(a,b);
}else{
hanoi(n-1,a,c,b);
move(a,b);
hanoi(n-1,c,b,a);
}
}
[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]
以上为《算法复习提纲(1)(1)》的无排版文字预览,完整格式请下载
下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。