埃及分數貪心演算法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；演算法結束；