贪心算法的流程图

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;