埃及分数贪心算法python

❶ 贪心算法的数学应用

如把3/7和13/23分别化为三个单位分数的和
【贪心算法】
设a、b为互质正整数，a<b 分数a/b 可用以下的步骤分解成若干个单位分数之和：
步骤一： 用b 除以a，得商数q1 及余数r1。（r1=b - a*q1）
步骤二：把a/b 记作：a/b=1/(q1+1）+(a-r1)/b(q1+1）
步骤三：重复步骤2，直到分解完毕
3/7=1/3+2/21=1/3+1/11+1/231
13/23=1/2+3/46=1/2+1/16+1/368
以上其实是数学家斐波那契提出的一种求解埃及分数的贪心算法，准确的算法表述应该是这样的：
设某个真分数的分子为a，分母为b;
把b除以a的商部分加1后的值作为埃及分数的某一个分母c；
将a乘以c再减去b，作为新的a；
将b乘以c，得到新的b；
如果a大于1且能整除b，则最后一个分母为b/a；算法结束；
或者，如果a等于1，则，最后一个分母为b；算法结束；
否则重复上面的步骤。
备注：事实上，后面判断a是否大于1和a是否等于1的两个判断可以合在一起，及判断b%a是否等于0，最后一个分母为b/a，显然是正确的。
PHP代码： classtanxin{public$weight;public$price;publicfunction__construct($weight=0,$price=0){$this->weight=$weight;$this->price=$price;}}//生成数据$n=10;for($i=1;$i<=$n;$i++){$weight=rand(1,20);$price=rand(1,10);$x[$i]=newtanxin($weight,$price);}//输出结果functiondisplay($x){$len=count($x);foreach($xas$val){echo$val->weight,'',$val->price;echo'<br>';}}//按照价格和重量比排序functiontsort(&$x){$len=count($x);for($i=1;$i<=$len;$i++){for($j=1;$j<=$len-$i;$j++){$temp=$x[$j];$res=$x[$j+1]->price/$x[$j+1]->weight;$temres=$temp->price/$temp->weight;if($res>$temres){$x[$j]=$x[$j+1];$x[$j+1]=$temp;}}}}//贪心算法functiontanxin($x,$totalweight=50){$len=count($x);$allprice=0;for($i=1;$i<=$len;$i++){if($x[$i]->weight>$totalweight)break;else{$allprice+=$x[$i]->price;$totalweight=$totalweight-$x[$i]->weight;}}if($i<$len)$allprice+=$x[$i]->price*($totalweight/$x[$i]->weight);return$allprice;}tsort($x);//按非递增次序排序display($x);//显示echo'0-1背包最优解为:';echotanxin($x);java源代码 packagemain;importjava.util.ArrayList;importjava.util.Collections;importjava.util.Comparator;importjava.util.List;importjava.util.Random;publicclassMain{/***测试*/publicstaticvoidmain(String[]args){//1.随机构造一批任务List<Pair<Integer>>inputList=newArrayList<Pair<Integer>>();Randomrand=newRandom();for(intn=0;n<20;++n){Integerleft=rand.nextInt(100);Integerright=left+rand.nextInt(100)+1;Pair<Integer>pair=newPair<Integer>(left,right);inputList.add(pair);}//将任务列表按结束时间排序（也就是根据right字段进行排序）sortByRight(inputList);printPairList(inputList);//执行算法List<Pair<Integer>>outputList=algorithm(inputList);System.out.println();printPairList(outputList);}/***贪心算法**@paraminputList*@return使数量最多的任务方案*/publicstatic<TextendsComparable<T>>List<Pair<T>>algorithm(List<Pair<T>>inputList){if(null==inputList||inputList.size()==0||inputList.size()==1){returninputList;}sortByRight(inputList);List<Pair<T>>outputList=newArrayList<Pair<T>>();intlast=0;outputList.add(inputList.get(last));intintputSize=inputList.size();for(intm=1;m<intputSize;++m){Pair<T>nextPair=inputList.get(m);TnextLeft=nextPair.getLeft();Pair<T>lastOutPair=inputList.get(last);TlastRight=lastOutPair.getRight();intflag=nextLeft.compareTo(lastRight);if(flag>=0){outputList.add(nextPair);last=m;}}returnoutputList;}/***对传入的List<Pair<T>>对象进行排序，使Pair根据right从小到大排序。**@paraminputList*/privatestatic<TextendsComparable<T>>voidsortByRight(List<Pair<T>>inputList){CompareByRight<T>comparator=newCompareByRight<T>();Collections.sort(inputList,comparator);}/***打印一个List<Pair<T>>对象。**@paraminputList*/privatestatic<TextendsComparable<T>>voidprintPairList(List<Pair<T>>inputList){for(Pair<T>pair:inputList){System.out.println(pair.toString());}}}/***根据Pair.right比较两个Pair。用于Conlections.sort()方法。**@param<T>*/classCompareByRight<TextendsComparable<T>>implementsComparator<Pair<T>>{/*@Override*/publicintcompare(Pair<T>o1,Pair<T>o2){Tr1=o1.getRight();Tr2=o2.getRight();intflag=r1.compareTo(r2);returnflag;}}/***代表一个任务对象。有点装逼用模板来写了。left表示开始时间，right表示结束时间。**@param<T>*/classPair<TextendsComparable<T>>{privateTleft;privateTright;publicPair(Tleft,Tright){this.left=left;this.right=right;}@OverridepublicStringtoString(){return[left=+left.toString()+','+right=+right.toString()+']';}publicTgetLeft(){returnleft;}publicvoidsetLeft(Tleft){this.left=left;}publicTgetRight(){returnright;}publicvoidsetRight(Tright){this.right=right;}}

❷ 贪心算法

埃及分数的算法叫做“迭代加深搜索”

那个问题用贪心我认为是不能的。

贪心一般是一种显而易见的算法应用在问题当中而得到最优解或较优解。（我的理解）
是否可以解决您的问题？

❸ 贪心算法

#include <stdio.h>

#define M 100

void main()

{

int i,j,k,temp,m,n;

int t[M]={2,14,4,16,6,5,3},p[M]={1,2,3,4,5,6,7},s[M],d[M]={0};

m=3;n=7;

for(i=0;i<7;i++)

for(j=0;j<7-i;j++)

if(t[j]<t[j+1])

{

temp=t[j];

t[j]=t[j+1];

t[j+1]=temp;

temp=p[j];

p[j]=p[j+1];

p[j+1]=temp;

}

for(i=0;i<m;i++) //求时间。

{

s[i]=p[i];

d[i]=t[i];

}

for(k=0;k<m;k++)

printf(" %d",d[k]);

printf("\n");

for(i=m;i<n;i++)

{

for(k=0;k<m-1;k++) //求最小。

{

temp=d[k];

if(temp>d[k+1])

{temp=d[k+1];j=k+1;}

}

printf("这是最小下标的： %d\n",j);

printf("最小的值： %d\n",temp);

for(k=0;k<m;k++)

printf(" %d",d[k]);

printf("\n");

//j=temp;

s[j]=s[j]+p[i];

d[j]=d[j]+t[i];

}

printf("\n");

for(k=0;k<7;k++)

printf(" %d",t[k]);

printf("\n");

for(k=0;k<7;k++)

printf(" %d",p[k]);

printf("\n");

for(k=0;k<m;k++)

printf(" %d",s[k]);

printf("\n");

for(k=0;k<m;k++)

printf(" %d",d[k]);

printf("\n");

}

❹ 求python用贪心算法实现01背包问题代码

numpy是科学计算用的。主要是那个array，比较节约内存，而且矩阵运算方便。成为python科学计算的利器。matplotlib是用于可视化的。只先学会XY的散点图，再加一个柱状图就可以了。其它的都可以暂时不学。几句话就成了。不用找本书。找个例子代码看完就会了。这两个只是计算用的。与机器学习有点儿关联。但还不是机器学习。 机器学习算法你可以使用R project，那个函数库更多些。 你要肯下功夫啃代码，最慢1小时就能掌握 numpy和matplotlib。如果你觉着难，总是想绕圈圈，想容易些，就很难弄会它。也许几天才会。

❺ 贪心算法

平面点集三角剖分的贪心算法要求三角剖分后边的总长度尽可能小。算法的基本思想是将所有的两点间距离从小到大排序，依次序每次取一条三角剖分的边，直至达到要求的边数。以下是两种贪心算法的主要步骤。

3.2.2.1 贪心算法1

第一步:设置一个记录三角剖分中边的数组T。

第二步:计算点集S中所有点对之间的距离d(p_i，p_j)，1≤i，j≤n，i≠j，并且对距离从小到大进行排序，设为d₁，d₂，…，d_n(n-1)/2，相应的线段记为e₁，e₂，…，e_n(n-1)/2，将这些线段存储在数组E中。

第三步:从线段集E中取出长度最短的边e₁存到T中作为三角剖分的第一条边，此时k=1。

第四步:依次从E中取出长度最短的边e_k，与T中已有的边进行求交运算，如果不相交则存到T中，并从E中删除e_k。这一步运行到S中没有边为止，即至k=n(n-1)/2。

第五步:输出T。

该算法中，第二步需要计算n(n-1)/2次距离，另外距离排序需要O(n²lgn)次比较。T中元素随第四步循环次数的增加而增加，因此向T中加入一条新边所需要的判定两条线段是否相交的次数也随之增加。如果第四步的前3n-6次循环后已经构成点集的三角剖分，那么第四步循环所需要的判定两条线段是否相交的次数为

1+2+…+3n-7+(3n-6)×(n(n-1)/2-(3n-6))=O(n³)

在常数时间内可以判定两条线段是否相交，因此该算法的时间复杂性为O(n³)。

3.2.2.2 贪心算法2

第一步:求点集的凸壳，设凸壳顶点为p₁，p₂，…，p_m，凸壳的边为e₁，e₂，…，e_m。并将凸壳顶点按顺序连接成边的e_i加入T(三角剖分的边集合)，并且e_i的权值被赋为1。凸壳内点的集合为S₁={p_m+1，p_m+2，…，p_n}。

第二步:从内部点S₁中任取一点p_i，求与p_i距离最近的点p_j，将线段 存入T。

第三步:求与p_j距离最近的点(除点p_i外)，设为p_k，并将线段 加入T，并将这些边的权值设为1，而w_ij、w_jk和w_ki的值加1，即为2。边的权值为2则表示该边为两个三角形共有。

第五步:对权值为1的边(除e₁，e₂，…，e_m外)的两个端点分别求与其距离最近的点，并将其连线(得到新的三角形)加入T，新三角形边的权值加1。

第六步:对权值为1的边重复上一步，当一条边被使用一次其权值增加1，直到所有边的权值均为2为止(除e₁，e₂，…，e_m外)。

贪心算法2中，第一步耗费O(nlgn);第二步需要计算n-1次距离与n-2次比较;第三步求p_k要计算n-2次的距离与n-3次比较;第四步要进行(n-3)×3次的距离计算及(n-4)×3次比较;第五步至多进行n-6次的距离计算与n-7次比较;第六步到第五步的循环次数不超过3n-9;因此整个贪心算法2的时间复杂性为

O(nlgn)+O(n)+O(n)+O(n)+(n-6)×(3n-9)=O(n²)

❻ 使用python贪心算法和蛮力算法解决问题~~

# coding:utf-8 """定义一个函数，名字为sameSums(aList)，alist是一个整形list(限定重复元素不超过2个,排2f0e除这样的list，元素前后差为1，[4,5,6,7,8])，函数作用是判断能分成两组，使得两组数字的和相等。若可以择返回值是true，若不可以返回值是false。如下例：sameSums([4, 7, 6, 3]) --> True //4+6 = 10 and 7 + 3 = 10sameSums([3, 3]) --> TruesameSums([4, 12, 16]) --> True //4+12= 16 and 16sameSums([5, 1]) --> False 特别提示：这个题目，贪心算法只能计算上面这样的情况。这个题目，对初学者来说，有点难度，但稍微有点算法基础，编程思路，就不难。先讲一个故事：二个小孩儿时从树上采板栗，最后合并一堆，分板栗，采集一人选一个的分。假定人性是贪婪的，第一个先选的人，选最大的，第二个选的人，选次大的，一直循环下去。贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。这个题目：先将list从大到小排序，中间设置2个空的list，从大的开始选，下一次选的时候，需要比较一下和，如果谁的和小，再添加一个，直到最后一个元素。 """ def sameSums(int_list): """ www.iplaypy.com python教程 """ >>> sameSums([4, 7, 6, 3]) True >>> sameSums([3, 3]) True >>> sameSums([4, 12, 16]) True >>> sameSums([5, 1]) False """ new_lst = sorted(int_list, reverse=True) list1 = list() list2 = list() for n in new_lst: if sum(list1) < sum(list2): list1.append(n) else: list2.append(n) return sum(list1) == sum(list2) if __name__ == "__main__": import doctest doctest.testmod() lst = [3, 9, 10, 30, 8] print sameSums(lst)

❼ Python贪心算法

所谓贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优加以考虑，它所做出的仅仅是在某种意义上的局部最优解。下面让我们来看一个经典的例题。假设超市的收银柜中有1分、2分、5分、1角、2角、5角、1元的硬币。
顾客结账如果需要找零钱时，收银员希望将最少的硬币数找出给顾客，那么，给定需要找的零钱数目，如何求得最少的硬币数呢？这个找零钱的基本思路：每次都选择面值不超过需要找给顾客的钱最大面值的硬币。
我们可以从面值最大的硬币开始，然后依次递减（图1）。
首先定义列表d存储已有币值。并且定义d_num存储每种币值的数量。通过循环遍历的方法计算出收银员拥有钱的总金额并保存在变量S中，要找的零钱变量为sum。当找零的金_比收银员的总金额多时，无法进行找零，提示报错。要想用的钱币数量最少，我们从面值最大的币值开始遍历。这里也就是我们贪心算法的核心步骤。计算出每种硬币所需要的数量，不断地更新硬币个数与硬币面值，最终获得一个符合要求的组合（图2）。
贪心算法在对问题求解时，不是对所有问题都能得到整体最优解，也不是从整体上去考虑，做出的只是在某种意义上的局部最优解。从面值最大的硬币开始依次递减，寻找可用的方法。一般贪心算法并不能保证是最佳的解决方法，这是因为：总是从局部出发没有从整体考虑，只能确定某些问题是有解的，优点是算法简单。常用来解决求最大值或最小值的问题。来源：电脑报

❽ 贪心算法

埃及分数的算法叫做“迭代加深搜索”

那个问题用贪心我认为是不能的。

贪心一般是一种显而易见的算法应用在问题当中而得到最优解或较优解。（我的理解）

❾ 埃及分数的拆分法

所谓埃及分数分解就是将一个分数分解成若干个分子为1的分数之和.如“在114=1()+1()+1()+1()①的()内填入互不相同的自然数,使等式成立”.对埃及分数分解的研究很多[1,2],一种通行的解法是:将114的分子分母同乘14的四个约数1、2、7、14的和并加以展开.例如,114=1×2414×24=114×24+214×24+714×24+1414×24=1336+1118+148+124.这种方法称为约数和分解法.我们知道,按约数和分解法上例的答案就只有一个.但在学生的答案中,出现了数十个不同的正确答案.这些答案不同于上面的解法,而且找不到共性,这是否是约数和分解法呢?本文就以这个题目为例加以探究把真分数表示为埃及分数之和的形式，所谓的埃及分数是指分子为1的分数
例如：7/8=1/2+1/3+1/24；要求用最少的埃及分数来表示

解析：设a、b为互质正整数，a<b 分数a/b 可用以下的步骤分解成若干个单位分数之和：
步骤一： 用b 除以a，得商数q1 及余数r1。（r1=b - a*q1）
步骤二：把a/b 记作：a/b=1/(q1+1）+(a-r)/b(q1+1）
步骤三：重复步骤2，直到分解完毕
以上其实是 数学家 斐波那契提出的一种求解 埃及分数 的贪心算法，准确的算法表述应该是这样的：
设某个真分数的分子为a，分母为b;
把b除以a的商部分加1后的值作为埃及分数的某一个分母c；
将a乘以c再减去b，作为新的a；
将b乘以c，得到新的b；
如果a大于1且能整除b，则最后一个分母为b/a；算法结束；
或者，如果a等于1，则，最后一个分母为b；算法结束；