经典算法的简单demo,python版本
目前包括:
(1)给定正整数 n,确定 n 是否是它的所有因子之和。比如 n=6 时,它的所有因子分别为 1,2,3,由于6=1+2+3,所以 6 满足条件.
要求:输入
:正整数 n ;输出
:若 n 是它的所有因子之和,输出 YES ,否则,输出 NO。请给出至少两种方法,并分析对比它们的时间复杂度
(2)编写程序计算斐波那契数列之和:1,2,2,3,5,8,13,21,34
要求:使用递归方法
实现以上算法;对比递归算法的实现过程,从时间复杂度和空间复杂度上考虑
是否可以改进递归算法
给定 n 个元素,这些元素是无序的
,分别使用合并排序
和快速排序
对 n 个元素进行排序。
要求:写出两种排序算法的完整程序, 测试两种算法的时间复杂度,对比它们的优劣
给定 n 个元素,这些元素是有序的
(假定为升序),使用二分查找
特定的元素。
要求:输入
n 个元素,输入某一个特定的值 m ,首先对 n 个元素进行排序(排序算法任选),输出
m 值的位置序号
给定 n 个矩阵{A 0 ,A 1 ,A 2 , …, A n-1 },其中 Ai,i=0, …, n-1 的维数为p i *p i+1 ,并且A i 和A i+1 是可乘的。考察这n个矩阵的连乘积A 0 A 1 A 2 …A n-1 ,由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有多种不同的计算次序。结合动态规划思想,编程确定 n 个矩阵的连乘次序,使得按照这个次数计算矩阵连乘,需要的“数乘”次数最少。
要求:输入
矩阵个数 n ,以及每一个矩阵的尺寸;输出
最佳矩阵连乘次序和数乘次数。
思路:备忘录m,s,分别用于记录相乘次数,标记相乘方式
有 n 个物品和购物车的容量,每个物品的重量为 w[i],价值为v[i],购物车的容量为 W,选若干个物品放入购物车,使它们的总价值最大。结合动态规划思想,编程实现以上 0/1 背包问题
要求:输入
物品的数量n,购物车能承受的重量y,每个物品的重量w,每个物品的价值v; 输出
购物车中所装物品。
思路:物品-容量-价值
表,填充表格用到的递推方程:value[i][j]=max(value[i - 1][j],value[i - 1][j - w[i - 1]] + v[i - 1])
根据贪心算法的思想编程实现背包问题:实现假设山洞中有n种宝物,每种宝物有一定重量w和相应的价值v,毛驴运载能力有限,只能运走m重量的宝物,一种宝物只能拿一样且宝物可以分割,如何使毛驴运走的宝物价值最大化?
要求:输入
毛驴可承载的最大重量m,若干个宝物重量w和它们的价值v; 输出
输出能运走的最大价值。
思路:以单位价值作为依据
编程实现哈夫曼编码过程。
要求:输入
若干字符和对应的权重; 输出
对该字符序列的哈夫曼编码结果使用01序列编码 。
思路:构建树:构造node类,最后输入root;编码:根据树,逐个节点逐层回溯