1、實驗目的：用動態規劃演算法解決哈弗曼編碼問題。
2、實驗要求：輸入字元的個數和字元的編號及相應頻率,輸出其相應編碼,並寫出其壓縮率。
3、程式清單:
#include
#include<>
#include<>
using namespace std;
int mecou; //定義全域性變數計碼長
class huffman ;
void main( )
cin>>f2;
cout<<"字元數量："< cout<<"字元編號：";
for(int i=1;i<=num;i++)
cout< cout< cout<<"字元頻率：";
for(int i=1;i<=num;i++)
cout< cout< ucnum=unchange(num); //得到定碼長所需的碼數總和
hsort(p,n,1,num); //根據頻率值排序並迴圈新增和，再排序得到最終的序列
renew(p,n把最終序列裡的和結點與加數結點對應便於向後找和結點
cnum=phf(p,n,copy);//輸出哈弗曼編碼後各編號的字首碼，得到哈弗曼編碼所需總碼數
cout<<"壓縮率為"< system("pause");
}void renew(huffman *a,int n)
}void swap(huffman &a,huffman &b)
int partition(huffman *a,int p,int r)
swap(a[p],a[j]);
return j;
}void quicksort(huffman *a,int p,int r)
}void hsort(huffman *a,int n,int nl,int nr) }
void cphf(huffman *a,huffman &b,int i)
}float phf(huffman *a,int n,int (*c)[3])
c[1:w][0]，c[1:w][[1]裡存放1---w編號在a中的編號值和頻率值
for(int i=1;i<=w;i++)
float pp=(float)**e轉換型別
cout<<"使用變長碼編碼需要"< return pp返回總碼數
}float unchange(int n,huffman *a)
4、 執行結果：
執行成功
.5、.實驗體會
我用了老師上課講的演算法，先將序列從小到大排序，拿出最小的兩個相加，他們的和放到陣列的末尾，將首指標向後移動兩個，末尾指標向後移動乙個，繼續排序相加移動指標，如此迴圈，最後輸出編碼。我的程式能執行成功，但是感覺在細節上的實現比較繁瑣,方法不是特別好，有待改進。
動態規劃演算法
首先，我們來觀察一下這個演算法。在求從b1到e的最短距離的時候，先求出從c2到e的最短距離 而在求從b2到e的最短距離的時候，又求了一遍從c2到e的最短距離。也就是說，從c2到e的最短距離我們求了兩遍。同樣可以發現，在求從c1 c2到e的最短距離的過程中，從d1到e的最短距離也被求了兩遍。而在整個程...
5動態規劃演算法習題答案
1 最大子段和問題 給定整數序列，求該序列形如的子段和的最大值 1 已知乙個簡單演算法如下 int maxsum int n,int a,int best i,int bestj return sum 試分析該演算法的時間複雜性。2 試用分治演算法解最大子段和問題，並分析演算法的時間複雜性。3 試說...
揹包問題的動態規劃演算法
1.u1 c 2.m n 1時，fm u 恒為0 3.u 0時，fm u 為0 狀態轉移方程為u k 1 uk xk wk。動態規劃基本方程為 wm u時，fm u f m 1 u 否則fm u 為f m 1 u與f m 1 u wm pm中的較大者。定義 n 1 c矩陣f，其m行u列處為fm u ...