注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

xiaochen7777的博客

http://player.youku.com/player.php/sid/X

 
 
 

日志

 
 
关于我

了如指掌,方能规划人生。是说人应该了解一下自己手上的掌纹,它能对你的人生进行导航。(Q号:1583223327),共同学习。

网易考拉推荐
 
 

信息学夏令营的后几天...(3)2008-07-24 06:55 (2009-03-15 21:13:58)  

2014-09-02 10:20:23|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 

9、哈夫曼编码及其译码…?

   1、构造最优二叉树(calc_tree

procedure heap(s,n:longint);

var

i,j:longint;

tempnodetype

begin

j1; tempnode[s];{node[s]的左右儿子的较小者初始化,保持node[s]}

while j<>maxint do

begin

   inode[s].w;jmaxint;{找出node[s]和左右儿子间的最小权值i,其序号为j

   if s*2<=n{顺左孩子方向找}

    then if node[s*2].w<i then begin inode[s*2].w;js*2end;

   if s*2+1<=n{顺右孩子方向找}

    then if node[s*2+1].w<i then begin inode[s*2+1].w;js*2+1end;

if j<>maxint{node[s]的权值和最优二叉树的结点序号调整为左右儿子权值的较小者,继续从node[j]往下调整}

     then begin node[s].wi;node[s].posnode[j].pos;sjend;

node[s]temp;{出发结点调整至s位置}

end{while}

end;{heap}

procedure calc_tree;{构造最优二叉树}

var

i:longint;

t1,t2:nodetype;

begin

for i1 to n do node[i].posi;{每种字符作为最优二叉树的叶结点}

totn;{堆长初始化}

for in div 2 downto 1 do heap(i,tot);{建堆}

fillchar(tree,sizeof(tree),0);{最优二叉树初始化}

for in+1 to n*2-1 do{计算分支结点和根}

begin

   t1node[1];node[1]node[tot]; dec(tot);{取出堆首元素,堆尾元素移至堆首,堆长-1}

   heap(1,tot);{重新调整建堆}

   tree[t1.pos].prti;tree[i].lcht1.pos;{原堆首元素为结点i的左儿子}

   t2node[1];inc(tot);{取出堆首元素,堆长+1}

   node[tot].wt1.w+t2.w; node[tot].posi;{堆尾元素的权值为先前取出的两个堆首元素的权值和,其在最优二叉树的结点序号为i}

   node[1]node[tot];dec(tot);{堆尾元素移至堆首,堆长-1}

   heap(1,tot); {重新调整建堆}

   tree[t2.pos].prti;tree[i].rcht2.pos{原堆首元素为结点i的右儿子}

end{ for }

end;{calc_tree}

2、编码(calc_hcd procedure calc_hcd;{对每个字符进行哈夫曼编码}

var

i,f,c:longint;{fc为父子指针}

cd:string;{当前字符的哈夫曼编码}

begin

for i1 to n do{依次构造每个字符的哈夫曼编码}

begin

   cd''; {字符i的哈夫曼编码初始时为空}

   ftree[i].prt;ci; {从字符i对应的叶结点出发,往根的方向追溯}

   while f<>0 do

    begin

     if tree[f].lch=c{cf的左儿子,则添‘0’;否则添‘1}

      then cd'0'+cd

      else cd'1'+cd;

     cf;ftree[f].prt{追溯f的父结点}

    end; {while}

   hcd[i]cd{记下字符i的哈夫曼编码}

end{for}

for i1 to n Writeln(hcd[i]){依次输出每个字符的哈夫曼编码}

end;{calc_hcd}

3、译码(calc_s1 

procedure calc_s1;{对文章的哈夫曼编码序列进行译码}

var i,l:longint;

begin

s1'';i1; {原文初始时为空,从s的第1个二进制位开始译码}

while s[i]<>'.' do{若译码未结束,则按照遇‘0’左走、遇‘1’右走的走法走一条从根到叶结点的路径}

begin

   l2*n-1;{从根出发向下走至叶结点}

   while tree[l].lch<>0 do

    begin

     if s[i]='0'{遇‘0’左走、遇‘1’右走}

      then ltree[l].lch

      else ltree[l].rch;

     inc(i){译下一个二进制位}

    end; {while}

   s1s1+ch[l] {将叶结点对应的字符加入文章尾}

end{while}

Writeln(s1){输出原文}

end;{calc_s1}

二、            (二叉堆)

1、堆的定义(/大根堆)

2、堆排序(维护堆的性质)

信息学夏令营的后几天...(4)2008-07-24 06:58 P.

 (2009-03-15 21:12:30)
标签: 

杂谈

分类: 2008烟台夏令营

7月20日 8:30~11:30 提高1 DP(1)

主讲:赵宗昌

【引例1】上楼梯

算法:f[1]=1 f[2]=2 f[n]=f[n-1]+f[n-2]

程序:

1) var

n:integer;

function dp(i:integer):longint;

    begin

      if i=1 then exit(1);

      if i=2 then exit(2);

      dp:=dp(i-1)+dp(i-2);

    end;

begin

readln(n);

writeln(dp(n));

end

n=40左右超时,递归过多.

2) const

maxn=90;

var

n:integer;

f:array[1..maxn] of qword;

function dp(i:integer):qword;

    begin

      if i=1 then exit(1);

      if i=2 then exit(2);

      if f[i]>0 then exit(f[i]);

      dp:=dp(i-1)+dp(i-2);

      f[i]:=dp;

    end;

begin

readln(n);

writeln(dp(n));

end.

新开数组,避免重复计算。          

 

【引例2】数字三角形

算法1、f[I,j]=max{f[I+1,j],f[I+1,j+1]}+a[I,j]

程序:

1)朴素DFS

二维数组a[i,j]存储数字三角形。

Procedure dfs(sum,i,j:integer);

{从a[1,1]到走到第i行第j列即a[I,j]时所取得的值为sum}

begin

    if i=n then

       begin if sum>max then max:=sum; exit; end;

    dfs(sum+a[i+1,j],i+1,j);         {向左下方走}

    dfs(sum+a[i+1,j+1],i+1,j+1); {向右下方走}

end;

Begin

Init;

Dfs(a[1,1],1,1);

Writeln(max);

End.

n较大时,纯搜索算法速度较慢

 

信息学夏令营的后几天...(5)2008-07-24 06:58 P.M.

 (2009-03-15 21:11:25)

标签: 

杂谈

分类: 2008烟台夏令营

2) 记忆化搜索

f:array[0..100,0..100] of integer;

//f[I,j] : (I,j) 到最后一行的最大值

function max(a,b:longint):longint;

begin

    if a>b then exit(a) else exit(b);

end;

Procedure dfs(i,j:integer);

begin

    if i=n then

      begin f[i,j]:=a[i,j]; exit; end;

    if f[i,j]>0 then exit;

    dfs(i+1,j);

    dfs(i+1,j+1);

    f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j];

end;

Begin

   init;

   dfs(1,1);

   writeln(f[1,1]);

End.

设额外数组纪录值,记忆化搜索

3)

1.procedure work{逆推f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j]}

begin

    for i:=1 to n do f[n,i]:=a[n,i];

    for i:=n-1 downto 1 do {枚举行}

      for j:=1 to i do   {枚举每行的元素}

        f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[I,j];{枚举走法}

    writeln(f[1,1]);

end;

2.procedure work2;{顺推f[i,j]=max{f[i-1,j-1],f[i-1,j]}+a[I,j]}

    begin

      f[1,1]:=a[1,1];

      for i:=2 to n do

        for j:=1 to i do

          f[i,j]:=max(f[i-1,j-1],f[i-1,j])+a[i,j];

      ans:=f[n,1];

      for i:=2 to n do if f[n,i]>ans then ans:=f[n,i];

      writeln(ans);

end;

递推实现,速度快。

【引例3】最大连续子序列的和

算法1:枚举任意连续区间

readln(n);

for i:=1 to n do read(a[i]);

ans:=-30000000;

for i:=1 to n do

    for j:=i to n do

      begin

        sum:=0;

        for k:=i to j do sum:=sum+a[k];

        if sum>ans then ans:=sum;

      end;

writeln(ans);

时间复杂度O(n^3)

算法2:算法1优化

readln(n);

for i:=1 to n do read(a[i]);

ans:=-30000000;

for i:=1 to n do

    begin

      sum:=0;

      for j:=i to n do

        begin

           sum:=sum+a[j];

           if sum>ans then ans:=sum;

        end;

    end;

writeln(ans);

时间:O(n2)

算法3:f[I]=max{f[I-1]+a[I],a[I]}//当前的点I要不与之间的构成一串,要么自己单独构成

程序:

procedure dp;

    begin

      f[1]:=a[1];

      for i:=2 to n do

        f[i]:=max(f[i-1]+a[i],a[i]);

      ans:=f[1];

      for i:=2 to n do if f[i]>ans then ans:=f[i];

end;

Begin

Init;

F[1]:=a[I];

Dp;

Writeln(max{f[I]});

End.

算法4:f[i]=max{f[i+1]+a[i],a[i]} //当前的点I要不与之后的构成一串,要么自己单独构成

程序:

procedure dp;

    begin

      f[n]:=a[n];

      for i:=n-1 downto 1 do

        f[i]:=max(a[i]+f[i+1],a[i]);

      ans:=f[1];

      for i:=2 to n do if f[i]>ans then ans:=f[i];

    end;

Begin

Init;

F[n]:=a[n];

Dp;

Writeln(max{f[I]});

End.


  评论这张
 
阅读(20)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017