下载文档原格式
10算法策略之贪婪法贪婪算法贪婪法⼜叫登⼭法, 它的根本思想是逐步到达⼭顶,即逐步获得最优解。
贪婪算法没有固定的算法框架，算法设计的关键是贪婪策略的选择。
⼀定要注意，选择的贪婪策略要具有⽆后向性。
某状态以后的过程和不会影响以前的状态,只与当前状态或以前的状态有关,称这种特性为⽆后效性。
可绝对贪婪问题【例1】键盘输⼊⼀个⾼精度的正整数N，去掉其中任意S个数字后剩下的数字按原左右次序将组成⼀个新的正整数。
编程对给定的N和S，寻找⼀种⽅案使得剩下的数字组成的新数最⼩。
输⼊数据均不需判错。
输出应包括所去掉的数字的位置和组成的新的正整数（N不超过240位）。
数据结构设计：对⾼精度正整数的运算在上⼀节我们刚刚接触过，和那⾥⼀样，将输⼊的⾼精度数存储为字符串格式。
根据输出要求设置数组，在删除数字时记录其位置。
我们采⽤⽅法1）。
⼀种简单的控制相邻数字⽐较的⽅法是每次从头开始，最多删除s次，也就从头⽐较s次。
按题⽬要求设置数组data记录删除的数字所在位置。
较s次。
按题⽬要求设置数组data记录删除的数字所在位置delete(char n[],int b,int k){int i;for(i=b;i<= length(n)-k;i=i+1) n[i]=n[i+k];}main（）{char n[100]; int s,i,j,j1,c,data[100],len;input(n); input(s); len=length(n);if(s>len){print(“data error”); return;}j1=0;for (i=1;i<=s ;i=i+1){for (j=1;j<length(n);j=j+1)if (n[j]>n[j+1]) //贪婪选择{delete(n,j,1);if (j>j1) data[i]=j+i; //记录删除数字位置else //实例2向前删除的情况实例data[i]=data[i-1]-1;j1=j; break; }if( j>length(n)) break;}for (i=i;i<=s;i=i+1){ j=len-i+1;delete(n,j,1); data[i]=j;}while (n[1]='0' and length(n) >1)delete(n,1,1); //将字符串⾸的若⼲个“0”去掉 print(n);for (i=1;i<=s;i=i+1)print(data[i],' ');}算法说明1：注意记录删除位置不⼀定是要删除数字d的下标，因为有可能d的前或后有可能已经有字符被删除，d的前⾯已经有元素删除容易想到，但⼀定不要忽略了其后也有可能已删除了字符，实例2中删除1时，其后的2已被删除。
贪婪取走启发式算法摘要：1.启发式算法的定义和特点2.贪婪算法的基本思想和应用实例3.启发式算法在解决问题时的优势和局限性4.贪婪算法的改进方向和未来发展正文：一、启发式算法的定义和特点启发式算法（Heuristic Algorithm）是一种根据问题特点进行近似求解的方法。
与精确算法相比，启发式算法通常能够在较短的时间内找到一个可行解或次优解，但可能无法保证解的最优性。
启发式算法的特点如下：1.利用问题的局部结构和特征进行推理和求解。
2.通常采用贪心策略，即在每一步决策中都选择当前看起来最优的解。
3.算法的复杂度和计算时间相对较低。
二、贪婪算法的基本思想和应用实例贪婪算法（Greedy Algorithm）是一种典型的启发式算法，其基本思想是在问题的每一步决策中都选择当前最优的解，期望最终得到全局最优解。
贪婪算法应用广泛，下面举两个实例：1.最小生成树问题：在构建一棵最小生成树时，可以从任意一个顶点开始，每次选择连接已选择顶点的边中权值最小的边，直到所有顶点都被连接。
2.旅行商问题：在给定若干城市和它们之间的距离矩阵时，贪婪算法可以在每一步选择距离当前城市最近的下一个城市，最终得到一条最短路径。
三、启发式算法在解决问题时的优势和局限性启发式算法在解决复杂问题时具有明显优势：1.算法简单，易于理解和实现。
2.计算速度快，能够在较短时间内得到一个可行解或次优解。
然而，启发式算法也存在局限性：1.得到的解不一定是最优解，可能受到算法的初始状态和搜索策略的影响。
2.算法的性能可能受到问题规模和实例特征的影响。
四、贪婪算法的改进方向和未来发展为了提高贪婪算法的性能，可以从以下几个方面进行改进：1.改进贪婪策略，如引入局部搜索、模拟退火等技术，以降低算法陷入局部最优的可能性。
2.结合问题特点，设计更具针对性的启发式函数和搜索算法。
3.利用机器学习、人工智能等技术，对算法的初始状态和搜索策略进行优化。
学习理论中的贪婪算法探讨一、引言贪婪算法是一种常见的算法思想，它通过贪心策略，每次选择局部最优解，最终能得到全局最优解。
贪婪算法广泛应用于各个领域，例如数据压缩、图形图像处理、排队论、优化问题等。
本文将学习理论中的贪婪算法进行探讨，包括贪婪算法的原理、应用场景、实现方式及优缺点等。
二、贪婪算法的原理贪婪算法是一种基于局部最优解的算法思想。
它的核心思想是每次选择当前情况下的最优解，然后进行下一步操作，直到得到全局最优解。
具体来说，贪婪算法可以分为以下几个步骤：1. 确定解空间和约束条件。
2. 确定度量标准，以便进行局部最优解的评估。
3. 通过贪心策略选择当前最优解，并对问题进行局部优化。
4. 判断是否得到全局最优解，如果没有则回到步骤3，继续进行贪心策略选择。
三、贪婪算法的应用场景贪婪算法是一种高效的算法思想，广泛应用于各个领域，例如：1. 数据压缩在数据压缩中，贪婪算法可以通过对频率排序，选择编码字母，从而实现数据压缩。
2. 图形图像处理在图形图像处理中，贪婪算法可以通过匹配算法，实现图形图像的匹配与识别。
3. 排队论在排队论中，贪婪算法可以通过选择最短的队列，进行任务分配与处理。
4. 优化问题在优化问题中，贪婪算法可以通过快速求解局部最优解，进而实现全局最优解的求解。
四、贪婪算法的实现方式贪婪算法的实现方式较为灵活，可以根据实际需要进行选择。
通常情况下，贪婪算法的实现方式可以分为以下几类：1. 贪心算法贪心算法是贪婪算法中最常见的实现方式之一。
它通过从问题的局部最优解出发，逐步构建整个问题的最优解。
例如，在任务调度中，可以通过选择最近截止时间的任务，进行调度与处理。
2. 堆排序堆排序是贪婪算法中一种高效的实现方式。
它通过使用堆结构，从中选择最大或最小的元素，并进行排序。
在数据压缩中，堆排序可以通过选择频率最小的元素，进行字母的编码，从而实现数据压缩。
3. 贪心分数背包问题贪心分数背包问题是贪婪算法中一种重要的应用场景。
np难问题常用算法NP难问题是计算机科学中一个重要的概念，指的是一类问题，其解决方案的验证可以在多项式时间内完成，但要找到解决方案却需要非多项式时间。
NP难问题常常需要借助一些特定的算法来解决，这些算法在计算复杂度上可能并不高，但在实际应用中却起到了至关重要的作用。
下面将介绍一些常用的算法，用于解决NP难问题。
1. 贪婪算法（Greedy Algorithm）贪婪算法是一种常用的近似算法，用于解决优化问题。
它的基本思想是每一步都选择当前最优的解决方案，希望最终得到全局最优解。
虽然贪婪算法不能保证得到最优解，但在一些问题中却表现良好，比如最小生成树问题、背包问题等。
2. 动态规划算法（Dynamic Programming）动态规划算法通常用于解决具有重叠子问题和最优子结构性质的问题。
其基本思想是将原问题分解为若干个子问题，先求解子问题，再利用子问题的解逐步推导出原问题的解。
动态规划算法在解决NP难问题中有着重要的应用，比如最长公共子序列问题、背包问题等。
3. 分支定界算法（Branch and Bound Algorithm）分支定界算法是一种用于解决组合优化问题的算法。
它通过逐步分解问题，将问题空间划分为若干个子问题，再利用上下界信息剪枝，最终找到最优解。
分支定界算法在解决NP难问题中有着广泛的应用，比如旅行商问题、背包问题等。
4. 遗传算法（Genetic Algorithm）遗传算法是一种模拟生物进化过程的优化算法，用于解决复杂的组合优化问题。
它通过模拟遗传、突变、选择等过程，逐步优化问题的解。
遗传算法在解决NP难问题中有着独特的优势，比如图着色问题、旅行商问题等。
5. 模拟退火算法（Simulated Annealing Algorithm）模拟退火算法是一种基于统计力学原理的全局优化算法，用于解决组合优化问题。
它通过模拟固体退火过程，逐步降低系统能量，最终找到全局最优解。
模拟退火算法在解决NP难问题中表现优异，比如图着色问题、背包问题等。
贪婪算法的基本原理贪婪算法（Greedy Algorithm）是一种常见的算法设计思想，它在每一步选择中都采取当前状态下最优的选择，以期望达到全局最优解。
贪婪算法的基本原理可以概括为“局部最优选择，期望全局最优解”。
在每个步骤中做出局部最优选择是贪婪算法的关键特点。
贪婪算法通常适用于满足贪婪选择性质（Greedy Choice Property）和最优子结构（Optimal Substructure）的问题。
贪婪选择性质意味着通过做出局部最优选择，可以得到全局最优解。
最优子结构意味着一个问题的最优解可以通过一系列子问题的最优解来表示。
当一个问题具有最优子结构性质时，我们可以通过贪婪算法来求解问题。
1.定义问题的优化目标。
2.将问题分解为若干子问题，子问题必须满足最优子结构性质。
3.设计一个贪婪策略，通过局部最优选择来做出决策。
4.解决每个子问题，得到局部最优解。
5.将各个子问题的解合并，得到原问题的解。
不过，贪婪算法不一定能得到全局最优解，因为它只关注局部最优选择，并没有进行全局。
有时，贪婪算法会陷入局部最优解而无法达到全局最优解。
因此，在使用贪婪算法求解问题时，必须确保问题满足贪心选择性质和最优子结构性质。
贪婪算法在许多问题中都有广泛的应用。
以下是几个常见问题的例子：1.最小生成树问题：通过选择边的方式，连接图中的所有顶点，并使得选择的边权和最小。
2.背包问题：在给定的背包容量下，选择一些物品放入背包中，使得物品的总价值最大。
3.哈夫曼编码：通过贪心选择思想构建最优的可变长度编码，以实现数据的高效压缩。
4.集合覆盖问题：从一组集合中选择最少的集合，覆盖全集的元素。
总结起来，贪婪算法是一种简单有效的算法设计思想，它通过局部最优选择来逐步求解问题，并期望达到全局最优解。
贪婪算法适用于满足贪心选择性质和最优子结构性质的问题，但不保证一定能得到全局最优解。
在实际应用中，我们需要理解问题的特点和约束条件，并根据问题的性质选择适合的算法来解决问题。
c语言算法--贪婪算法---0/1背包问题在0 / 1背包问题中，需对容量为c 的背包进行装载。
从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。
对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高，即n ?i=1pi xi 取得最大值。
约束条件为n ?i =1wi xi≤c 和xi?[ 0 , 1 ] ( 1≤i≤n)。
在这个表达式中，需求出xt 的值。
xi = 1表示物品i 装入背包中，xi =0 表示物品i 不装入背包。
0 / 1背包问题是一个一般化的货箱装载问题，即每个货箱所获得的价值不同。
货箱装载问题转化为背包问题的形式为：船作为背包，货箱作为可装入背包的物品。
例1-8 在杂货店比赛中你获得了第一名，奖品是一车免费杂货。
店中有n 种不同的货物。
规则规定从每种货物中最多只能拿一件，车子的容量为c，物品i 需占用wi 的空间，价值为pi 。
你的目标是使车中装载的物品价值最大。
当然，所装货物不能超过车的容量，且同一种物品不得拿走多件。
这个问题可仿照0 / 1背包问题进行建模，其中车对应于背包，货物对应于物品。
0 / 1背包问题有好几种贪婪策略，每个贪婪策略都采用多步过程来完成背包的装入。
在每一步过程中利用贪婪准则选择一个物品装入背包。
一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。
这种策略不能保证得到最优解。
例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 1 0 5。
当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。
而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。
另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。
Greedy Algorithm：贪心算法算法思想在贪婪算法中采用逐步构造最优解的方法。
在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。
决策一旦作出，就不可再更改。
作出贪婪决策的依据称为贪婪准则（greedy criterion），也就是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。
当达到某算法中的某一步不能再继续前进时，算法停止。
虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。
一般情况下，为了获得较好的性能，必须对算法进行细致的调整。
但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。
Greedy Algorithm在设计方面不能保证求得的最后解是最佳的和不能用来求最大或最小解问题，只能求满足某些约束条件的可行解的范围。
Example1例1-4 [找零钱] 一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。
售货员希望用数目最少的硬币找给小孩。
假设提供了数目不限的面值为2 5美分、1 0美分、5美分、及1美分的硬币。
售货员分步骤组成要找的零钱数，每次加入一个硬币。
选择硬币时所采用的贪婪准则如下：每一次选择应使零钱数尽量增大。
为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。
假设需要找给小孩6 7美分，首先入选的是两枚2 5美分的硬币，第三枚入选的不能是2 5美分的硬币，否则硬币的选择将不可行（零钱总数超过6 7美分），第三枚应选择1 0美分的硬币，然后是5美分的，最后加入两个1美分的硬币。
贪婪算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）。
可以证明采用上述贪婪算法找零钱时所用的硬币数目的确最少（见练习1）。
贪婪算法的基本思路贪婪算法的基本思路贪婪算法是一种常见的算法，它在许多问题中都有广泛的应用。
其基本思路是每次选择当前最优解，然后继续寻找下一个最优解，直到找到整个问题的最优解。
下面将详细介绍贪婪算法的基本思路。
一、什么是贪婪算法贪婪算法（Greedy Algorithm）是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。
简单来说，就是把问题分成若干个阶段，在每个阶段都选择当前状态下最优解，从而得到全局最优解。
二、贪婪算法的特点1. 贪心策略：每次选择当前状态下最优解，并认为这样做可以得到全局最优解。
2. 简单易实现：相较于其他复杂度较高的算法，如动态规划等，贪婪算法实现起来相对简单。
3. 适用范围广：贪婪算法可以用于许多问题中，在某些情况下可以得到很好的效果。
三、贪婪算法的应用1. 最小生成树：Kruskal算法和Prim算法都是贪婪算法的应用。
2. 背包问题：贪心策略可以用于解决一些特殊的背包问题，如分数背包问题。
3. 最短路径问题：Dijkstra算法也是贪婪算法的一种。
4. 集合覆盖问题：集合覆盖问题是指在给定的集合中，选择最少的子集，使得这些子集的并集可以完全覆盖原始集合。
贪心策略可以用于解决这个问题。
四、贪婪算法的实现步骤1. 确定贪心策略：在每个阶段选择当前状态下最优解。
2. 构造可行解：根据贪心策略构造可行解。
3. 证明最优性：证明所构造出来的可行解具有全局最优性。
五、贪婪算法与动态规划的比较与动态规划相比，贪婪算法更加简单易实现，但是其求得结果不一定是全局最优解。
而动态规划虽然复杂度较高，但求得结果一定是全局最优解。
因此，在具体应用中需要根据具体情况选择使用哪种算法。
六、贪婪算法的优缺点1. 优点：实现简单，速度快，适用范围广。
2. 缺点：可能无法得到全局最优解，只能得到一个近似最优解。
七、贪婪算法的应用举例1. 分数背包问题：假设有一个背包可以容纳W重量的物品，现在有n 件物品，每件物品的重量为wi，价值为vi。
貪婪策略貪婪策略（Greedy Method）常用來解決最佳化問題（Optimization Problem） 貪婪法是最直接的解法， 。
每次的決策都是朝向目前“最好” 的方向前進，而且不回頭。
舉例來說，某一個銀行出納櫃檯要服務 n 個 顧客，銀行的目標是希望顧客在櫃檯等待的平均時間要最少。
解決之道 是每次都從尚未服務的顧客中，選擇需要服務時間最短的顧客來服務， 如此就可達到預期目標。
像這樣每次都選擇最小服務時間的策略就是一 種貪婪策略。
現在以實例說明此演算法。
假設有 5 個顧客 A，B，C，D，E 幾乎同時到 達銀行櫃檯，其所需服務時間如下表：顧客服務時 間A B C D E5 1 4 2 3根據貪婪演算法，銀行櫃檯將依序服務 B，D，E，C，A。
顧客在櫃檯等 待的平均時間為[1 + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3 + 4) + (1 + 2 + 3 + 4 + 5) ] / 5 = 7。
再介紹一個可用貪婪策略解決的背包問題（Knapsack Problem）。
假設 有多個可分解的物件和一只限重 W 的背包， 每件物件有其重量及其被選 取放入背包內的利益。
請問要如何將物件放進背包內而使得獲得的利益 最大？解決的方法是每次在限重的情形下， 選取尚未放入的物件中擁有 最大的利益與重量的比值之物件放入背包內。
設背包限重 100，有 A，B，C，D，E 共五個物件，其資料如下表：物件 A B C D E重量 10 20 30 40 50利益 20 30 66 40 60利益/重量 2.0 1.5 2.2 1.0 1.2因為物件 C 的利益/重量最高，所以將物件 C 放入背包內，此時背包的 重量為 30。
接著從物件 A，B，D，E 中挑出其利益/重量最高的物件 A 放入背包內，這時背包的重量為 30＋10＝40。
接下來，從物件 B，D，E 中挑出其利益/重量最高的物件 B 裝入背包內，之後背包的重量為 40+20=60。
再從剩下的物件 D 和 E 中選出其利益/重量最高的物件 E。
由 於物件 E 整個放入背包內會超過重量 100﹐所以物件 E 只能放入 0.8 個。
最後得到的利益為 66+20+30+60 放入以後得總重量為 60+50 0.8=100。
0.8=164。
物件裝入背包的情形整理於下表﹕物件個數 累計利益 累計重量C A B E1 1 1 0.866 86 116 16430 40 60 100接著介紹最小擴展樹（Minimum Spanning Tree）問題。
圖 22.5 是由頂 點（Vertex）及邊（Edge）構成的圖形，其中圓圈代表頂點，連接兩頂 點的線為邊，而且每個邊都有非負的加權（Weight）（例如頂點 V3 與頂 點 V5 間的邊之加權為 5）。
由於圖 22.5 的邊都無方向，稱圖 22.5 的圖 形為無向圖（Undirected Graph）。
定義無向圖的路徑（Path）為頂點 的序列，其中序列裏每個頂點與其後一個頂點之間必有邊相連。
例如圖 1 中[V1, V5, V2]是一條從頂點 V1 到頂點 V2 的路徑。
圖1 若無向圖的任兩頂點都存在一條路徑，則稱此圖為聯通圖（Connected Graph）。
例如圖 1 就是聯通圖。
從某頂點出發回到該頂點的路徑稱為 迴圈（Cycle）。
例如圖 1 的[V1, V5, V2, V1]路徑就是迴圈。
一個沒有迴 圈的圖形稱為無迴圈圖（Acyclic Graph）。
定義樹（Tree）為聯通的 無迴圈圖。
若圖形 G 的頂點所成的集合為 V， 邊所成的集合為 E， G=(V, 以 E)表示圖形 G。
定義圖形 G=(V, E)的擴展樹 T=(V, E’)是包括所有 G的頂點的樹，其中 E’是 E 的子集合。
例如圖 2(a)及(b)都是圖 1 的擴 展樹。
圖2 定義擴展樹 T=(V, E)的加權為集合 E’中所有的邊的加權的總和。
例如 圖 2 (a)的擴展樹加權為 1+3+5+7=16，而 2 (b) 的擴展樹加權為 1+2+3+6=12。
圖形 G 的最小擴展樹就是擁有最小加權的擴展樹。
如圖 2 (b) 的擴展樹是圖 1 的最小擴展樹。
最小擴展樹問題就是去求出給定的聯通 且加權的無向圖之最小擴展樹。
接著介紹以貪婪策略設計的 Kruskal 演算法。
假設要求圖形 G=(V, E) 的最小擴展樹。
此演算法依據邊的加權由小到大的順序考慮該邊是否為 最小擴展樹的邊。
若邊 e 加入後不會產生迴圈，則邊 e 為最小擴展樹的 一員；反之，邊 e 就不是最小擴展樹的一員。
如此重複直到建構出最小 擴展樹。
詳細的步驟分述於下：步驟 1： 將圖形 G=(V, E)所有的邊依其加權由小到大排好， 依序為 e1, e2, e3, …, em。
步驟 2：建立圖形 T=(V, E’)，其中 E’ = 。
設 i = 1。
步驟 3： ei 加入圖形 T 中不產生迴圈， 若 則將 ei 加入圖形 T， E’= E’ 即 ? { ei }；否則，i = i + 1。
步驟 4：若圖形 T 不是圖形 G 的擴展樹，則重複步驟 3；否則，圖形 T 是圖形 G 的最小擴展樹，結束演算法執行。
圖3 用(a, b)表示頂點 a 與頂點 b 的邊。
以找圖 1 的最小擴展樹為例，將圖 1 的邊依加權排序後得 e1 =(V1, V5), e2 =(V2, V3), e3 =(V2, V5), e4 =(V1, V2), e5 =(V3, V5), e6 =(V1, V4), e7 =(V4, V5), e8 =(V3, V4)。
一開始 圖形 T 只有頂點但沒有邊（圖 3 (a)）。
考慮 e1 =(V1, V5)，因不產生 迴圈，就將(V1, V5)加入 T 內（圖 3 (b)）。
同樣的， e2 =(V2, V3)及 e3 =(V2, V5)也依序加入 T 內（圖 3(c)和(d)）。
當考慮 e4 =(V1, V2)時， 因加入後會產生[V1, V5, V2, V1]的迴圈，所以拒絕(V1, V2)的加入（圖 3 (e)）。
同樣的理由，也拒絕 e5 =(V3, V5)的加入（圖 3(f)）。
而後 因 e6 =(V1, V4)加入 T 後不產生迴圈， 所以將(V1, V4)加入 T 中 （圖 3(g)） 。
此時 T 為 G 的擴展樹， 停止演算法。
最後得到的圖 3(g)就是圖 1 的最小 擴展樹。
最後介紹最短路徑問題（Shortest Path Problem）。
下圖是 S、A、B、 T 四個地點的交通路線，各路線分別標上距離：假設要求從 S 到 T 的最短路徑長度。
D(a,b)表示從 a 到 b 的最短路徑 令 長度。
從上圖﹐可知 D(S,T)=D(S,A)+D(A,B)+D(B,T)=10+15+20=45。
如此只要利用貪婪策略就能得到答案。
但是此貪婪策略並不適用於所有的 最短路徑問題，例如要找下圖的 D(S,T)，則 D(S,T)=24+20=44，此結果 不等於 D(S,A)+D(A,B)+D(B,T)=45。
郵票問題如何買到最少的郵票數 1.計算 99 元可買幾張 50 元最貴的郵票 (1 張) , 然後剩下多少 錢. (餘 49 元)2.計算 49 元可買幾張 25 元次貴的郵票 (1 張) , 然後剩下多少錢. (餘 24 元) 3.計算 24 元可買幾張 10 元再次貴的郵票 (2 張) , 然後剩下多少錢. (餘 4 元) 4.計算 4 元可買幾張 5 元再次貴的郵票 (0 張) , 然後剩下多少錢. (餘 4 元)5.計算 4 元可買幾張 1 元再次貴的郵票 (4 張) , 然後剩下多少錢. (餘 0 元) 附註:1.由最貴的郵票先買 2.當錢數為 0 整時停止 動畫:The Stamp ProblemPrim用 Prim's 的方法找到最小擴展樹 1.由 A 點為起點 , v 為所有點的集合 , x={A} ; y= v-x={B,C,D,E,F}2.找出以 A 點為起點而相鄰的最短路徑 (18--D 點) , 連接 A 點 D 點 , 將 D 點放入 x 中 , y={B,C,E,F} 3.以 D 點為起點找出相鄰的最短路徑 (6--E 點) ,連接 D 點 E 點 , E 點放入 x 中 , y={B,C,F} 4.以 E 點為起點找出相鄰的最短路徑 (5--F 點) ,連接 E 點 F 點 , F 點放入 x 中 , y={B,C} 5.以 F 點為起點找出相鄰的最短路徑 (10--D 點) , 但 D 點 E 點 F 點 形 成一個迴圈, 故退回到 E 點 6.以 E 點為起點找出相鄰的最短路徑 (11--C 點) ,連接 E 點 C 點 , C 點放入 x 中 , y={B} 7.以 C 點為起點找出相鄰的最短路徑 (14--D 點) , 但 C 點 D 點 E 點 形 成一個迴圈, 故退回到 E 點 8.以 E 點為起點找出相鄰的最短路徑 (16--B 點) , 連接 E 點 B 點 , 將 B 點放入 x 中 , y={} 9.當 y 為空集合時, 此圖為最小擴展樹 將 將 將動畫:The Prim's Method to Find a Minimal Spanning TreeKruskal用 Kruskal's 的方法找到最小擴展樹 1.找出所有邊的最小值 (5) , 並連接兩點 (E 點 F 點) 2.找出所有邊的次小值 (6) ,並連接兩點 (D 點 E 點) 3.找出所有邊的再次小值 (10) , 但 D 點 E 點 F 點為一個迴圈 , 故此 邊線不連接 4.找出所有邊的次小值 (11) ,並連接兩點 (C 點 E 點) 5.找出所有邊的再次小值 (14) , 但 C 點 D 點 E 點為一個迴圈 , 故此 邊線不連接6.找出所有邊的次小值 (16) ,並連接兩點 (B點 E點)7.找出所有邊的次小值 (18) ,並連接兩點 (A點 D點)8.當所有的點都有連線 , 則此圖為最小擴展樹動畫:The Kruskal's Method to Find a Minimal Spanning Tree。
