Skip to content

amani2001/algorithm_study

Repository files navigation

  1. Goldbach's Conjecture, 2000以内大于2的偶数都可以分解成两个素数之各 方法1:以步长2遍历2-2000中的所有偶数,调用isprime方法分别判断分解的两个数是否为素数。若找到这样的两个数,而结束循环 方法2:跟方法1思路基本相同,但在时间复杂度上要少一层循环,该方法设置全局列表变量n_list,对2000以内的所有数进行初始化,数作为列表的下表,列表值用于设置该下标值是否为素数,若为素数设置为1。再以步长2遍历2-2000中的所有偶数,直接读取分解的两个数的下标所对应列表的值是否为1,若同时为1则输出,结束循环 方法3:将n以下所有的素数,保存在列表中,再以步长2遍历2-2000中的所有偶数,直接判断分解的两个数是否在列表中,若同时都在,刚输出结果,结束循环 方法4:与方法3相似,先构造n以下所有素数列表,遍历素数表中的数据,两两相加,若结果在待验证数据列表中,则输出,设置flag用于判断循环是否所有偶数都得到了验证 在四个方法中添加了执行时间监测,从执行时间来看,方法以空间为代价换取了最快的速度,方法4速度最慢。4种方法执行时间如下: method1_time:0.013192176818847656 method2_time:0.0033800601959228516 method3_time:0.03261971473693848 method4_time:0.08139395713806152

  2. 背包装载入门,最优装载问题 问题描述:给定n个物品的重量,设定背包最大的容积,选取尽可能多的物品数装入背包 解决办法::贪心算法,贪心策略,每次选取最小重量的物品放入背包 Knapsack.py:通过随机生成物品重量,采用贪心策略获得放入背包的物品重量和数量 Knapsack_goodsinfo.py:跟Knapsack.py相同,仅增加了显示放入背包的物品具体的对象 Hour_secretary.py:钟点秘书安排会议,采用面向对象方法分别定义秘书类和会议类,按照会议结束时间进行升序排序,每次从余下的会议中选取结束时间最早的会议,且与已安排的会议不冲突,也就是该会议的开始时间需大于上一会议的结束时间。 Shortest_path.py:Dijkstra算法实现。先构造各顶点之间距离的矩阵。指定源点,构建的贪心策略为:先选取源点直接到其他顶点距离的最小值,将该顶点加入到源点集合,再选取到顶点集合距离最小的顶点,依次类推。结果输出时使用了LIFO队列进行操作。

Releases

No releases published

Packages

No packages published

Languages