貪心演算法的流程圖

A. Python貪心演算法

所謂貪心演算法是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優加以考慮，它所做出的僅僅是在某種意義上的局部最優解。下面讓我們來看一個經典的例題。假設超市的收銀櫃中有1分、2分、5分、1角、2角、5角、1元的硬幣。
顧客結賬如果需要找零錢時，收銀員希望將最少的硬幣數找出給顧客，那麼，給定需要找的零錢數目，如何求得最少的硬幣數呢？這個找零錢的基本思路：每次都選擇面值不超過需要找給顧客的錢最大面值的硬幣。
我們可以從面值最大的硬幣開始，然後依次遞減（圖1）。
首先定義列表d存儲已有幣值。並且定義d_num存儲每種幣值的數量。通過循環遍歷的方法計算出收銀員擁有錢的總金額並保存在變數S中，要找的零錢變數為sum。當找零的金_比收銀員的總金額多時，無法進行找零，提示報錯。要想用的錢幣數量最少，我們從面值最大的幣值開始遍歷。這里也就是我們貪心演算法的核心步驟。計算出每種硬幣所需要的數量，不斷地更新硬幣個數與硬幣面值，最終獲得一個符合要求的組合（圖2）。
貪心演算法在對問題求解時，不是對所有問題都能得到整體最優解，也不是從整體上去考慮，做出的只是在某種意義上的局部最優解。從面值最大的硬幣開始依次遞減，尋找可用的方法。一般貪心演算法並不能保證是最佳的解決方法，這是因為：總是從局部出發沒有從整體考慮，只能確定某些問題是有解的，優點是演算法簡單。常用來解決求最大值或最小值的問題。來源：電腦報

B. 貪心演算法的證明方法

貪心演算法的基本思路如下：
1.建立數學模型來描述問題。
2.把求解的問題分成若干個子問題。
3.對每一子問題求解，得到子問題的局部最優解。
4.把子問題的解局部最優解合成原來解問題的一個解。
----------------------------------------------
其實歸納起來也就一個類。其他的都是分支

C. C語言常用演算法分析的目錄

第1篇演算法基礎篇
第1章程序之魂——演算法
（ 自學視頻、源程序：
配套資源mr1） 2
1.1魂之說 3
1.2演算法的特性 4
1.3演算法的表示方式 5
1.3.1用自然語言描述演算法 5
1.3.2用流程圖描述演算法 5
1.3.3用N-S圖描述演算法 8
1.3.4用計算機語言描述演算法 9
1.4演算法性能分析與度量 10
1.4.1演算法的性能指標 10
1.4.2演算法效率的度量 10
1.4.3演算法的時間復雜度 11
1.4.4演算法的空間復雜度 12
1.5學習演算法的原因 12
第2章數據結構基礎
（ 自學視頻、源程序：
配套資源mr2） 13
2.1數據結構概述 14
2.1.1數據結構的發展 14
2.1.2數據結構的研究對象 14
2.1.3數據結構與演算法的關系 16
2.2數據結構的基本概念 16
2.3C語言常見數據結構 18
2.3.1數組 18
2.3.2結構體 20
2.3.3鏈表 21
2.3.4棧 23
2.3.5隊列 24
第3章查找與排序演算法
（ 自學視頻、源程序：
配套資源mr3） 26
3.1查找演算法 27
3.1.1順序查找 27
3.1.2折半查找 29
3.1.3分塊查找 31
3.1.4哈希查找 33
3.2排序演算法 38
3.2.1選擇排序 38
3.2.2冒泡排序 40
3.2.3直接插入排序 43
3.2.4歸並排序 45
3.2.5希爾排序 48
3.2.6快速排序 49
3.2.7各種排序演算法的比較 52
第4章基本演算法思想
（ 自學視頻、源程序：
配套資源mr4） 54
4.1遞歸的概念和分治法 55
4.1.1遞歸的概念 55
4.1.2遞歸的應用——漢諾塔 55
4.1.3分治法的基本思想 56
4.1.4分治法的應用——棋盤覆蓋
問題 57
4.2動態規劃法 59
4.2.1動態規劃法的基本思想 59
4.2.2動態規劃的應用——最大
子段和 60
4.3貪心演算法 61
4.3.1貪心演算法的基本概念 61
4.3.2貪心演算法的應用——哈夫
曼編碼 62
4.4回溯法 67
4.4.1回溯法的基本思想 67
4.4.2回溯法的應用——連續
郵資問題 68
4.5分支限界法 70
4.5.1分支限界法的基本思想 71
4.5.2分支限界法的應用——旅行
售貨員問題 71
第2篇常用演算法篇
第5章數學演算法
（ 自學視頻、源程序：
配套資源mr5） 76
5.1隨機數求π 77
5.2正態分布的成績 82
5.3繪制最小圓 86
5.4滿意的一元二次方程解 93
5.5計算定積分 101
5.6分解質因數 103
5.7最大公約數和最小公倍數 106
5.8數字的全排列 109
5.9遞推化梯形法求解定積分 111
5.10迭代法開平方運算 115
5.11牛頓切線法解方程 117
5.12改進歐拉方法求解微分方程 119
5.13迭代法求解線性方程組 123
5.14計算貸款利息 127
5.15分數計算器 129
第6章矩陣與數組問題
（ 自學視頻、源程序：
配套資源mr6） 132
6.1「脫殼」組數 133
6.2尋找矩陣中的「鞍點」 135
6.3魔幻方陣 137
6.4矩陣的轉置運算 139
6.5勾股數組 141
6.6百燈判熄 143
6.7巧排螺旋數陣 144
6.8猜數四問 146
第7章經典演算法
（ 自學視頻、源程序：
配套資源mr7） 149
7.1約瑟夫環 150
7.2八皇後問題 152
7.30-1背包問題 156
7.4斐波那契數列 159
7.5尋找水仙花數 161
7.6愛因斯坦階梯問題 162
7.7進制轉換演算法 163
7.8哥德巴赫猜想 165
7.9驗證四方定理 167
7.10尼科徹斯定理 168
7.11角谷猜想 170
7.12prim演算法求最小生成樹 171
7.13迪傑斯特拉演算法 174
第3篇趣味演算法篇
第8章數學趣題
（ 自學視頻、源程序：
配套資源mr8） 178
8.1警察抓犯人 179
8.2舍罕王的失算 181
8.3百錢買百雞問題 183
8.4三色球問題 185
8.5填數字游戲 187
8.6漁夫捕魚問題 190
8.7移數字游戲 191
8.8數字翻譯器 194
8.9猴子吃桃問題 198
8.10馬克思手稿中的數學題 199
8.11判斷迴文式素數 200
8.12完全數 204
8.13自守數 206
8.14一數三平方數 207
8.15古稀數 209
8.16親和數 213
8.17對調數 215
第9章邏輯推理題
（ 自學視頻、源程序：
配套資源mr9） 218
9.1魔術師的秘密 219
9.2婚禮上的謊言 220
9.3誰講了真話 222
9.4白紙與黑紙 223
9.5判斷壞球 224
9.6打漁曬網問題 229
9.7水池注水問題 231
9.8尋找假幣 232
9.9常勝將軍 234
9.10巧算國王分財物 236
9.11商人渡河問題 237
9.12馬踏棋盤 243
9.13猜杏核 246
第4篇演算法競技篇
第10章計算機等級考試演算法實例
（ 自學視頻、源程序：
配套資源mr10） 250
10.1數組的下三角置數 251
10.2查找單鏈表的結點 252
10.3二維數組的元素排序 254
10.4尋找二維數組的最大值 256
第11章程序員考試演算法實例
（ 自學視頻、源程序：
配套資源mr11） 258
11.1電話計費演算法 259
11.2處理鏈表的重復元素 261
11.3劇場方形空位 263
11.4數組的數值操作 265
11.5三位數生成迴文數 267
第12章信息學奧賽演算法實例
（ 自學視頻、源程序：
配套資源mr12） 269
12.1我知你心 270
12.2格雷碼 272
12.3狡猾的狐狸遇上聰明的兔子 275
12.46174問題 276
12.5韓信點兵 279
12.6楊輝三角 281
12.7開關燈問題 284
12.8蛇形方陣 286

D. 高手看過來：C語言的一個小問題

#include<stdio.h>
int main()
{
int s[6]={100,50,20,10,5,1},a[6],i,n,k=0;
scanf("%d",&n);
for(i=0;i<6;++i)
a[i]=n/s[i],n%=s[i],k+=a[i];
for(i=0;i<6;i++)
printf ("%3d元 %d 張\n", s[i],a[i]);
printf("\n總共%d張\n",k);
return 0;
}

E. 畫出演算法的流程圖

對於這種比較高級的演算法代碼直接看程序會比較蒙，你就光看我的演算法流程吧，prim演算法用的是貪心演算法的思想，即每一步都作出局部的最優解，關於prim 演算法為什麼能用貪心演算法的證明，你可以參考《計算機演算法設計與分析》這本書。（我反正不想看那麼無聊的證明，也看不明白，呵呵）。
定義一個集合v 和 a，其中v是全體節點（總節點數為n）的集合，v初始為空。定義一個記錄最小生成數邊數的變數c。
1.在v中任選一個節點，並加入到a中。在v中刪除該節點。

2.選一個在所有連接v集合和a集合權值最小的邊（即一個節點是v的某一個節點，一個是a中的某一個節點）

3。將兩個節點連接。將c加1

4.將第3步才在v中節點刪除並加入到a中.

5.如果c為n-1則完成最小生成樹，否則回到第2步。

明白了沒？不明白再問我啊，希望對你有所幫助。

F. 貪心演算法的基本思路

1.建立數學模型來描述問題
⒉把求解的問題分成若干個子問題。
⒊對每一子問題求解，得到子問題的局部最優解。
⒋把子問題的解局部最優解合成原來解問題的一個解。
實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步
do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解。
下面是一個可以試用貪心演算法解的題目，貪心解的確不錯，可惜不是最優解。

G. 貪心演算法的本質

1. 貪心法（Greedy Algorithm）定義

求解最優化問題的演算法通常需要經過一系列的步驟，在每個步驟都面臨多種選擇；

貪心法就是這樣的演算法：它在每個決策點作出在當時看來最佳的選擇，即總是遵循某種規則，做出局部最優的選擇，以推導出全局最優解（局部最優解->全局最優解）

2. 對貪心法的深入理解

（1）原理：一種啟發式策略，在每個決策點作出在當時看來最佳的選擇

（2）求解最優化問題的兩個關鍵要素：貪心選擇性質+最優子結構

①貪心選擇性質：進行選擇時，直接做出在當前問題中看來最優的選擇，而不必考慮子問題的解；

②最優子結構：如果一個問題的最優解包含其子問題的最優解，則稱此問題具有最優子結構性質

（3）解題關鍵：貪心策略的選擇

貪心演算法不是對所有問題都能得到整體最優解的，因此選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

（4）一般步驟：

①建立數學模型來描述最優化問題；

②把求解的最優化問題轉化為這樣的形式：對其做出一次選擇後，只剩下一個子問題需要求解；

③證明做出貪心選擇後：

1°原問題總是存在全局最優解，即貪心選擇始終安全；

2°剩餘子問題的局部最優解與貪心選擇組合，即可得到原問題的全局最優解。

並完成2°

3. 貪心法與動態規劃

最優解問題大部分都可以拆分成一個個的子問題，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，大部分情況下這是不可行的。貪心演算法和動態規劃本質上是對子問題樹的一種修剪，兩種演算法要求問題都具有的一個性質就是子問題最優性(組成最優解的每一個子問題的解，對於這個子問題本身肯定也是最優的)。動態規劃方法代表了這一類問題的一般解法，我們自底向上構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，並且以其中的最優值作為自身的值，其它的值舍棄。而貪心演算法是動態規劃方法的一個特例，可以證明每一個子樹的根的值不取決於下面葉子的值，而只取決於當前問題的狀況。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。由於貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優的路，一直走到底就可以了。

H. 學習編程的基礎知識，如何做

編程的基礎知識包括：
小學、初中、高中基礎課程，大學計算機科學專業所有基礎課、專業基礎課和專業課（雜課不用學）。
如果一般摟一下基礎，找些快速入門的書比劃比劃，也能編。但是要想作為職業，繞不開上面那些知識，每門課涉及到的知識在實際工作中只要遇到，都是邁不過去的坎。

I. 貪心演算法的介紹

貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

J. 貪心演算法中的matlab演算法怎麼做

1.數論演算法
求兩數的最大公約數
function gcd(a,b:integer):integer;
begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b);
end ;

求兩數的最小公倍數
function lcm(a,b:integer):integer;
begin
if a< b then swap(a,b);
lcm:=a;
while lcm mod b >0 do inc(lcm,a);
end;

素數的求法
A.小范圍內判斷一個數是否為質數：
function prime (n: integer): Boolean;
var I: integer;
begin
for I:=2 to trunc(sqrt(n)) do
if n mod I=0 then
begin
prime:=false; exit;
end;
prime:=true;
end;

B.判斷longint范圍內的數是否為素數（包含求50000以內的素數表）：
procere getprime;
var
i,j:longint;
p:array[1..50000] of boolean;
begin
fillchar(p,sizeof(p),true);
p[1]:=false;
i:=2;
while i< 50000 do
begin
if p then
begin
j:=i*2;
while j< 50000 do
begin
p[j]:=false;
inc(j,i);
end;
end;
inc(i);
end;
l:=0;
for i:=1 to 50000 do
if p then
begin
inc(l);
pr[l]:=i;
end;
end;{getprime}
function prime(x:longint):integer;
var i:integer;
begin
prime:=false;
for i:=1 to l do
if pr >=x then break
else if x mod pr=0 then exit;
prime:=true;
end;{prime}

2．

3．

4.求最小生成樹
A.Prim演算法：
procere prim(v0:integer);
var
lowcost,closest:array[1..maxn] of integer;
i,j,k,min:integer;
begin
for i:=1 to n do
begin
lowcost:=cost[v0,i];
closest:=v0;
end;
for i:=1 to n-1 do
begin
{尋找離生成樹最近的未加入頂點k}
min:=maxlongint;
for j:=1 to n do
if (lowcost[j]< min) and (lowcost[j]< >0) then
begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=0; {將頂點k加入生成樹}
{生成樹中增加一條新的邊k到closest[k]}
{修正各點的lowcost和closest值}
for j:=1 to n do
if cost[k,j]< lwocost[j] then
begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;
end;{prim}
B.Kruskal演算法：(貪心)
按權值遞增順序刪去圖中的邊，若不形成迴路則將此邊加入最小生成樹。
function find(v:integer):integer; {返回頂點v所在的集合}
var i:integer;
begin
i:=1;
while (i< =n) and (not v in vset) do inc(i);
if i< =n then find:=i
else find:=0;
end;
procere kruskal;
var
tot,i,j:integer;
begin
for i:=1 to n do vset:=;{初始化定義n個集合，第I個集合包含一個元素I}
p:=n-1; q:=1; tot:=0; {p為尚待加入的邊數，q為邊集指針}
sort;
{對所有邊按權值遞增排序，存於e[I]中，e[I].v1與e[I].v2為邊I所連接的兩個頂點的序號，e[I].len為第I條邊的長度}
while p >0 do
begin
i:=find(e[q].v1);j:=find(e[q].v2);
if i< >j then
begin
inc(tot,e[q].len);
vset:=vset+vset[j];vset[j]:=[];
dec(p);
end;
inc(q);
end;
writeln(tot);
end;

5.最短路徑
A.標號法求解單源點最短路徑：
var
a:array[1..maxn,1..maxn] of integer;
b:array[1..maxn] of integer; {b指頂點i到源點的最短路徑}
mark:array[1..maxn] of boolean;

procere bhf;
var
best,best_j:integer;
begin
fillchar(mark,sizeof(mark),false);
mark[1]:=true; b[1]:=0;{1為源點}
repeat
best:=0;
for i:=1 to n do
If mark then {對每一個已計算出最短路徑的點}
for j:=1 to n do
if (not mark[j]) and (a[i,j] >0) then
if (best=0) or (b+a[i,j]< best) then
begin
best:=b+a[i,j]; best_j:=j;
end;
if best >0 then
begin
b[best_j]:=best；mark[best_j]:=true;
end;
until best=0;
end;{bhf}

B.Floyed演算法求解所有頂點對之間的最短路徑：
procere floyed;
begin
for I:=1 to n do
for j:=1 to n do
if a[I,j] >0 then p[I,j]:=I else p[I,j]:=0;
{p[I,j]表示I到j的最短路徑上j的前驅結點}
for k:=1 to n do {枚舉中間結點}
for i:=1 to n do
for j:=1 to n do
if a[i,k]+a[j,k]< a[i,j] then
begin
a[i,j]:=a[i,k]+a[k,j];
p[I,j]:=p[k,j];
end;
end;
C. Dijkstra 演算法：
類似標號法，本質為貪心演算法。
var
a:array[1..maxn,1..maxn] of integer;
b,pre:array[1..maxn] of integer; {pre指最短路徑上I的前驅結點}
mark:array[1..maxn] of boolean;
procere dijkstra(v0:integer);
begin
fillchar(mark,sizeof(mark),false);
for i:=1 to n do
begin
d:=a[v0,i];
if d< >0 then pre:=v0 else pre:=0;
end;
mark[v0]:=true;
repeat {每循環一次加入一個離1集合最近的結點並調整其他結點的參數}
min:=maxint; u:=0; {u記錄離1集合最近的結點}
for i:=1 to n do
if (not mark) and (d< min) then
begin
u:=i; min:=d;
end;
if u< >0 then
begin
mark:=true;
for i:=1 to n do
if (not mark) and (a[u,i]+d< d) then
begin
d:=a[u,i]+d;
pre:=u;
end;
end;
until u=0;
end;
D.計算圖的傳遞閉包
Procere Longlink;
Var
T:array[1..maxn,1..maxn] of boolean;
Begin
Fillchar(t,sizeof(t),false);
For k:=1 to n do
For I:=1 to n do
For j:=1 to n do
T[I,j]:=t[I,j] or (t[I,k] and t[k,j]);
End;