貪心算法計(jì)算最優(yōu)分解方案

1、西安郵電大學(xué)（計(jì)算機(jī)學(xué)院）課內(nèi)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：貪心算法計(jì)算最優(yōu)分解方案專業(yè)名稱：班級(jí)：學(xué)生姓名：學(xué)號(hào)（8位）：指導(dǎo)教師：實(shí)驗(yàn)日期：2016年6月1日一.實(shí)驗(yàn)?zāi)康募皩?shí)驗(yàn)環(huán)境實(shí)驗(yàn)?zāi)康模菏煜げ⒄莆肇澬乃惴▽?shí)驗(yàn)環(huán)境：windows7 vc6.0 編譯器實(shí)驗(yàn)內(nèi)容題目描述:設(shè)n是一個(gè)正整數(shù)?，F(xiàn)在要求將n分解成干互不相同的自然數(shù)的和，且使這 些自然數(shù)的成績(jī)最大。算法設(shè)計(jì)：對(duì)于給定的正整數(shù)n，編程計(jì)算最優(yōu)分解方案問(wèn)題分析:若a+b=n,則|a-b|越小，那么,a*b越大。貪心策略:將n分解成從2開(kāi)始的連續(xù)自然數(shù)的和，優(yōu)先的方式下均勻地分給前面各 項(xiàng)。如果最后剩下一個(gè)數(shù)，將此數(shù)加到后項(xiàng)中。例如：對(duì)于8進(jìn)行分解

2、為2和3則剩下一個(gè)3;然后2和3再分別從3中均勻地獲得1最后變成3和4,最后剩下1加給4 上。所以，最終分解成3和5,是8的分解為不相同的自然數(shù)乘機(jī)最大。程序流程圖:開(kāi)始輸入 n,k=l,sum=lk+;ak = ak -1 + 1； n = n - ak;否是結(jié)束四測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果1 正常測(cè)試數(shù)據(jù)（3組）及運(yùn)行結(jié)果;輸入sum /for (i = 0; i < n; j+) ak - i+; for (i = 1; i <- k; i+) sum *= aFJ；五總結(jié)1 實(shí)驗(yàn)過(guò)程中遇到的問(wèn)題及解決辦法；問(wèn)題: 邏輯不清晰。解決辦法 : 畫(huà)出流程圖2對(duì)設(shè)計(jì)及調(diào)試過(guò)程的心得體會(huì)。貪

3、心算法是從問(wèn)題的某個(gè)初始解出發(fā)逐步，逼近給定的目標(biāo)，以盡可能快地 求得更好的解。當(dāng)達(dá)到某一步不能繼續(xù)前進(jìn)時(shí)，算法停止。這時(shí)就得到了問(wèn)題的一 個(gè)解。但不能保證求得的解是最優(yōu)的。貪心算法的優(yōu)點(diǎn)在于時(shí)間復(fù)雜度低。貪心算 法與其他最優(yōu)化算法的區(qū)別在于 : 它具有不可后撤性，可以有后效性，一般情況 下，不能滿足最優(yōu)化原理。貪心算法的特點(diǎn)就決定了它的使用范圍，它一般不適用 于解決可行性問(wèn)題。僅適用于較容易得到可行性解得最優(yōu)性問(wèn)題。 （ 這里較容易得 到可行解得概念 : 當(dāng)前的策略選擇后，不會(huì)或極少出現(xiàn)無(wú)解的情況。交互性題目， 貪心算法是一個(gè)較好的選擇。 ）六附錄：源代碼（電子版）/* 用貪心算法解題 :

4、設(shè) n 是一個(gè)正整數(shù)?，F(xiàn)在要求將 n 分解為若干互不相同的自然數(shù)的和，且使這些自然數(shù)的乘積最 大*/#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>void taixin(int n)int a100;/ 臨時(shí)數(shù)組，保存分解后的數(shù)int k = 1;/a 數(shù)組的索引int sum = 1;/ 最大乘積int i;/ 索引if (n < 5)/如果小于 5，那么都是乘積是1*n ；sum = n;elsea1 = 2;n -= 2;while (n > ak)k+;ak = ak - 1 + 1;n = n - ak;if

5、(n = ak)ak+;n-;/ 讓最后一個(gè)先加 1，其實(shí)算上后面的是加了 2for (i = 0; i < n; i+)ak - i+;for (i = 1; i <= k; i+)sum *= ai;printf(" 分解后的數(shù) :");for (i = 1; i <=k; i+)printf("%d ",ai);printf("n最大的成績(jī) : %d", sum);getchar();void main()int n;char str50;sprintf(str,"%s"," 請(qǐng)輸入一個(gè)正整數(shù) :