算法复习提纲(1)(1)

本文由用户“嘿郎a”分享发布 更新时间:2021-12-27 11:27:49 举报文档

以下为《算法复习提纲(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)》的无排版文字预览,完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的,下载的文档就是什么样的。

图片预览