Monthly Archives: November 2009

一个算法设计技巧:递归转化成迭代

 先向师兄道个歉,那么久才写这篇技术文章。

这里我还是把我那天和大家讨论的东西仔细地整理。

一个算法设计技巧:递归转化成迭代。

在某些特定的情况下,递归的效率是非常低的,必须使用迭代来实现。 下面,将通过两个经典的递归例子,来感悟这两种算法设计方法的效率问题。
 
1.计算n的阶乘。 
学过最基本程序设计知识的同学都知道,递归处理。
#include <stdio.h>
#include<stdlib.h>
long fact(int);

int main(void)
{   int n;
    printf(“请输入一个非负整数n:n”);
    scanf(“%d”,&n);
    if(n<0)
       printf(“error:n must>0.”);
       else
    printf(“%d的阶乘为%d.n”,n,fact(n));
    system(“pause”);
    return 0;
}   
   
//计算递归的函数        
long fact(int n)
{
    if(n<=0)
        return -1;
    else
        return n*fact(n-1);
}   

2.计算Fabonacci数列。

基本定义:

f(n)=0,n=0;

f(n)=1,n=1;

f(n)=1,n=2;

f(n)=f(n-1)+f(n-2),(n>2);递归定义。

递归实现:

#include <stdio.h>

//计算数列第n项  
long fib(int n)
{
if (n == 1 || n == 2)  
           return 1;
  return fib(n – 1) + fib(n – 2);
}  

int main()
{  
   int n;
  scanf(“%d”, &n);
  printf(“%ldn”, fib(n));
  return 0;  
}    

一个程序,或者一个算法写好之后,我们自然而然地想到:好有没有更好的实现??这个算法好么??能改进么??

对于这两个程序,效率确实很低下,必须使用更优秀的方式来实现。

一.先分析Fibonacci数列的计算。  
1.感性的认知。  
 
 
  可以看到,f(1)和f(2)被重复计算了很多次,因此效率显得很低下。

  

2.理性分析。     

这里的工作即将集中在程序运行时间的分析上面。

假设,计算第n项需要的时间为T(n)。

由递归关系式知道:T(n) = T(n – 1) + T(n – 2),n >= 3;T(n) = 1。这里的1代表1个CPU单位时间,即CPU计算一个基本语句所需要的时间。 例如,赋值语句,比较大小等等。

先定义一个函数,叫做生成函数,也叫母函数。


 

三.最后,我们来分析计算n的阶乘算法。

 

 


(1)Stirling公式的证明过程如下(来自维基百科):

 

这个公式,以及误差的估计,可以推导如下。我们不直接估计n!,而是考虑它的自然对数

这个方程的右面是积分的近似值(利用梯形法则),而它的误差由欧拉-麦克劳林公式给出:

其中Bk伯努利数Rm,n是欧拉-麦克劳林公式中的余项。取极限,可得:

我们把这个极限记为y。由于欧拉-麦克劳林公式中的余项Rm,n满足:

其中我们用到了大O符号,与以上的方程结合,便得出对数形式的近似公式:

两边取指数,并选择任何正整数m,我们便得到了一个含有未知数ey的公式。当m=1时,公式为:

n趋于无穷大时,两边取极限,并利用沃利斯乘积,便可以得出ey()。因此,我们便得出斯特灵公式:

这个公式也可以反复使用分部积分法来得出,首项可以通过最速下降法得到。把以下的和

用积分近似代替,可以得出不含的因子的斯特灵公式(这个因子通常在实际应用中无关):

[编辑]收敛速率和误差估计

y轴表示截断的斯特灵级数的相对误差,x轴表示所使用的项数。

更加精确的近似公式为:

其中:

斯特灵公式实际上是以下级数(现在称为斯特灵级数)的第一个近似值:

当时,截断级数的误差等于第一个省略掉的项。这是渐近展开式的一个例子。它不是一个收敛级数;对于任何特殊值n,级数的准确性只在取有限个项时达到最大,如果再取更多的项,则准确性将变得越来越差。

阶乘的对数的渐近展开式也称为斯特灵级数:

在这种情况下,级数的误差总是与第一个省略掉的项同号,且最多同大小。

(3)数据分析

至此,数学分析已经臻于完美。

以下是数据:

 

 

 

终于知道,自己为什么学数学了,呵呵 。 微笑  偷笑 大笑   

 

两个算法的迭代版本:
1.斐波那契数列的第n项 

int Fibo(int n){
 
 int a1=1,a2=1; //前两项
 int an ; //第n项 

 if(n==1||n==2)  //n <= 2返回1 
  return 1 ;

 for(int i=3;i<n;i++)
 {
  an=a1+a2;
  a1=a2;
  a2=an;
 }

    return an;
}   

 

2.计算n的阶乘

#include <stdio.h>
int main()
{
 int i,n,s=1;

  scanf(“%d”,&n);
 
  for(i=1;i<=n;i++)
     s*=i;
 
  printf(“%d!=%dn”,n,s);
 
 return 0;
}

    

 
这两个版本都用了一个for循环来实现迭代,只有n次循环就可以完成,效率有了
很大的改善。运行时间都是O(n)。  
 
通过两个例子的分析,递归在某些场合下的效率是很低下的,因此必须使用迭代来实现。
但是,递归并不是不好,关于递归和迭代的转化问题,以下的观点来自这篇博客:
 
 

****不需要消解的递归
那种盲目的消解递归,不惜一切代价躲避递归,认为“递归的速度慢,为了提高速度,必须用栈或者其他的方法来消解”的说法是很片面的。如果一个递归过程用非递归的方法实现后,速度提高了,那只是因为递归做了一些无用功。假使一个递归过程必须要用栈才能消解,那么完全模拟后的结果根本就不会对速度有任何提升,只会减慢;如果你改完后速度提升了,那只证明你的递归函数写的有问题,如多了许多重复操作——打开关闭文件、连接断开数据库,而这些完全可以放到递归外面。可以在本质上是非递归的机器上实现递归过程这一事实本身就证明:为着实际目的,每一个递归程序都可以翻译成纯粹迭代的形式,但这包含着对递归栈的显式处理,而这些运算常常模糊了程序的本质,以致使它非常难以理解。
因此,是递归的而不是迭代的算法应当表述成递归过程。如汉诺塔问题等。汉诺塔问题的递归算法中有两处递归调用,并且其中一处递归调用语句后还有其他语句,因此该递归算法不是尾递归或单向递归。要把这样的递归算法转化为非递归算法,并没有提高程序运行的速度,反而会使程序变得复杂难懂,这是不可取的。也就是说,很多递归算法并不容易改写成迭代程序:它们本质上是递归的,没有简单的迭代形式。这样的递归算法不宜转化为非递归算法。

 

说到底,在我们选择算法时应该全面分析算法的可行性、效率、代码优化。在综合了算法的各个因素后,选择合适的算法来编写程序,这样的程序才会达到优化的效果。

 

四.结束语

数学,是一门艺术,更是一门哲学。

[收藏]世界顶级计算机科学大师 Donald Knuth 的伟大成就

    Donald Knuth自传的开头这样写道:“Donald
Knuth真的只是一个人么?”作为世界顶级计算机科学家之一,Knuth教授已经完成了编译程序、属性文法和运算法则的前沿研究,并编著完成了已在程序设计领域中具有权威标准和参考价值的书目的前三卷。在完成该项工作之余,Knuth还用了十年时间发明了两个数字排版系统,并编写了六本著作对其做了详尽的解释说明,现在,这两个系统已经被广泛地运用于全世界的数学刊物的排版中。随后,Knuth又发明了文件程序设计的两种语言,以及“文章性程式语言”相关的方法论。

   
   
到目前为止,Knuth已经出版发行了17部书籍,一百五十余篇论文,包括了巴比伦算法、圣经、字母“s”的历史等多方面的内容。作为一名数学家,Knuth曾开创了几门新的课程,为纯计算数学做出了很大贡献。他所获得的奖项和荣誉数不胜数,其中最值得注目的有1974年美国计算机协会图灵奖(ACM
Turing Award)(计算机里的诺贝尔奖),1979年美国前总统卡特授予的科学金奖(Medal of
Science)以及1996年11月由于发明先进技术荣获的极受尊重的京都奖(Kyoto
Prize)。在不多的业余时间里,Knuth不仅写小说,还是一个音乐家、作曲家、管风琴设计师。
       
是Knuth独特的审美感决定了他兴趣广泛、富有多方面造诣的特点,Knuth传奇般的生产力也是源于这一点。对于Knuth来说,衡量一个计算机程序是否完整的标准不仅仅在于它是否能够运行,他认为一个计算机程序应该是雅致的、甚至可以说是美的。计算机程序设计应该是一门艺术,一个算法应该像一段音乐,而一个好的程序应该如一部文学作品一般。

早期经历
   
   
Knuth,1938年1月10日生于美国威斯康星州密尔沃基市。他在模式方面辨别和熟练操作的能力在八年级的时候开始显现出来。当时,当地的一家糖果制造商举办了一项比赛,比赛要求选手用其品牌“Ziegler’s
Giant
Bar”中的字母组成新的单词,规定时间内组成单词数量最多者获胜。Knuth参加了比赛,并以单词总数4500余个远远超过了裁判的2500个的标准,轻松赢得头奖。赛后,Knuth说道,如果自己当初想到回答时用些省略符号的话,还能写出更多。这次比赛Knuth为学校赢得了一台电视机,还为每个同学赢得了一根糖果棒。
   
    Knuth多产的出版事业开始于他的高中时代,当时他的科技设计被Westinghouse Science Talent Search
光荣提及。他的“Potzebie System of Weights and
Measures”的基础章节被登在“Mad”杂志第26号,“Power”的基础章节被叫作“whatmeworry”。“Mad”的编辑认识到了年轻的Donald著作的重要性,以25美元买下了他的文章,并刊登在了其1957年6月的期刊上。
   
    高中的时候,Knuth对数学并没多大兴趣,而是把主要精力放在主修的课程:听音乐和作曲上。他在高中的乐队里吹萨克斯、大号时,曾把Dragnet、
Howdy Doody Time
和Brylcream的主题曲联成一段新的音乐。这位著名的科学家在近期评论自己的早期作品时承认:“对于版权,我一无所知。”
       
虽然Knuth的等级平均分是学校历史上最高的,但是他和他的指导老师还是对他能否成功学习大学数学持怀疑态度。Knuth说在他高中阶段和大学早期一直有一种自卑感,这个问题一度是他的一个障碍。作为一个大学新生,Knuth没有对于失败的恐惧,他花了许多时间攻克额外的数学难题,几个月后,他在这方面的能力已经远远超过了其他同学。

高等教育和早期的计算机工作
   
    当Knuth在Case科学院(现在的Case Western
Reserve)获得物理奖学金时,梦想成为一个音乐家的计划改变了。Knuth回去继续研究数学是在大二,当时一个爱出难题的教授提出了一个特殊的问题,并说哪个学生能解决这个问题就立刻记成绩“A”。Knuth跟大多数同学一样,也认为那是道解不出来的题目,直到有一天,他错过了公共汽车,只能步行去看一个演出,Knuth利用路上这点空闲时间决定尝试一下。那阵子他运气真的是非常好,不仅问题很快就解开了,得到了“A”,还成功地经常逃课。虽然Knuth也承认,逃课让他有负罪感,但是很明显,他完全有能力补上落下的功课,接下来的一学年,他的离散数学就又得了个“A”,而且还获得了给自己不能参加的课程评定论文等级的工作机会。
   
    1956年,作为Case的新生,Knuth第一次接触到了计算机,那是一台IBM
650。Knuth说直到一年后,女孩才进入了他的生活。这又是计算机科学界一直以来亏欠科学家们的一个事例之一。

Knuth熬夜读IBM
   
   
650的说明手册,自学基本的程序设计。那时,在高等计算机语言发明之前,程序编写只能用第二代或是汇编语言。这个工作既耗时又困难,因为指令必须根据每台机器特定的构造编写,而实际上指令只须一步就可从二进制0、1系列转存到计算机硬盘上。Knuth说,有了第一次使用650的经历,他便肯定自己能编写出比说明手册上介绍的更好的程序。
   
   
Knuth很快便开始“闲逛”,编写可以执行数学函数的程序。他的第一个程序是把数字转化为素数,第三个是做井字游戏(或者说是让计算机在改正每次输的错误的过程来学会玩井字游戏)。作为学校篮球队的经理,Knuth编写了一个根据不同成绩标准评定每个运动员对球队贡献等级的程序,他的努力赢来了那些认为这样做有助于球队赢得同盟冠军的教练的好评(虽然,无庸质疑,不是每一个运动员都这样认为)。Knuth的成就成了新闻周刊的标志,他和教练、计算机的照片也被刊登在IBM650后来的说明手册上。
   
   
1960年,Knuth从Case毕业时享有着最高荣誉,在由全体教员参加的选举上,他因其公认的出众成就获得了硕士学位。1963年,Knuth回到加利福尼亚理工学院攻取了数学博士学位,之后成为了该院的数学教授。在加利福尼亚理工学院任教期间,Knuth作为Burroughs公司的顾问继续从事软件开发工作。1968年,他加入了斯坦福大学,九年后坐上了该校计算机科学学科的第一把交椅。1993年,Knuth成为斯坦福大学“the
Art of Computer Programming”(计算机程序设计艺术)的荣誉退休教授。

早期成就和计算机程序设计艺术的开端
   
   
1962年,Knuth还是个研究生的时候就开始了他计算机程序的工作。那时,他已经开始了个人咨询,为不同的机器编写编译程序。编译程序是一种翻译原始或高级语言和对象或二进制机器语言的中间语言。在不知道众多软件公司正高额寻求成百上千的编辑者的情况下,Knuth编写了一个程序,赚得5000美元,他的名字立刻响誉了整个行业。世界上一流的出版社Addison-Wesley找到Knuth,请他写一本关于编译程序的书。到1966年,Knuth已经发表了3000页的手写设计草图,并且发明了一种综合方法,用于分析或决定结构翻译所客观需要的文法规则。最近,关于他的那第一部著作,Knuth自己这样评述:“用三年半的时间写第一章可并不是件好事。”
   
   
当Knuth的出版商计算出他的那3000页的笔迹打印成文章大约需要2000页时,大家才发现这实际上是一项多么大的工程。Knuth决定将它详述,成为一部更大的关于程序设计科学的纵览,共分为七个部分。一部巨著就这样——诞生了。《计算机程序设计艺术》,至今仍是各程序类图书书架上标志性的书籍。微软首席执行官比尔?盖茨在1995年接受一次采访时说,“如果你认为你是一名真正优秀的程序员,就去读第一卷,确定可以解决其中所有的问题。”值得注意的是,盖茨本人读这本书时用去了几个月的时间,并同时进行了难以置信的训练。盖茨还说:“如果你能读懂整套书的话,请给我发一份你的简历。
   
   
依Knuth本人所讲,《计算机程序设计艺术》是他毕生最重要的事业,其目的是“组织和总结所知道的计算机方法的相关知识,并打下坚实的数学、历史基础”。Knuth撰写的前三卷被翻译成多种语言,到1976年为止,已卖出超过一百万册。他目前正全神贯注地编写第四卷,他期望第四卷的篇幅约为2000页,并分为三个独立的章节。为了完成丛书的其余部分,Knuth现在进入了一种引退的状态,全身心地投入这项工作。Knuth说,一般说来,他更喜欢在一段时间内集中精神完成一项工作,正像他自己在书中提出的:按“一批”的模式。
   
   
Knuth从他主要的工作计划中拿出了十年,即从1976年起,致力于对数字排版的研究,设计了著名的文件准备TeX系统,字体生成程序METAFONT。这项工作带来的值得注意的副产品是用于结构文件和“文章性程式语言”附随方法论的WEB和CWEB语言。
   
    现在,Knuth和他的妻子Jill,两个孩子John
和Jennifer一起,住在斯坦福大学校园里。他继续着《计算机程序设计艺术》第四卷的编写工作。虽然说Knuth是全身心的投入这一项工作,但他还是能挤出时间研究MMIX的设计,那是一台64位RISC(精简指令集计算机)而他的业余爱好仍然是音乐,还一直邀请那些能够即兴演奏四手联弹钢琴曲的人们给他留下便条,以便安排一些活动。

Knuth成就简要回顾

编译程序
       
编译程序能够实现高级语言和二进制机器语言之间的翻译。二十世纪六十年代初期,Knuth教授致力于这方面的研究,虽然现代的软件已经可以使其变的简单一些,但编写编译程序仍被认为是一项极为困难的工作。Knuth教授在这方面最著名的成就是LR(k)分析的研究,那是一个能使确定一串字符文法规则的过程更加顺畅的值得注目的方法。

属性文法
   
   
在编译程序的工作之后,Knuth教授走上了形式上定义程序语言意义、语义的研究道路。他建立起一个更加经济的方法去通译联合规则,他把这种方法称作“属性规则”。该方法创立的同时,计算机科学的子域被称作“属性文法”。

算法
   
   
也许Knuth教授在计算机科学领域最原创的贡献就是他对于算法的分析。算法是编写一个程序,使之能去完成一项任务的基础,例如搜索或分类等。在加利福尼亚理工学院时,Knuth教授在一个毕业生的协作下,开发了用来探究数学公理推论的Knuth-Bendix算法。1968年,Knuth教授在斯坦福,和他的一个学生开发了Knuth-Morris-Pratt算法,该法则使计算机在文章中搜索一串字符的过程更加连贯。他所著的《计算机程序设计艺术》是一个详尽的算法实践和科学的概观。

数字化排版
   
   
“数学书籍和杂志已经不像从前那样漂亮了。”Knuth教授在一篇早期关于数学排版的文章中这样写道。由于对计算机排版的校样的低质量感到无法忍受,Knuth教授从他史诗性的七卷集巨著的编写过程中拿出了十年时间,来开发一个高质量的计算机排版系统。其间,Knuth开发了两个用于文件排版和字体生成的软件系统,这两个系统现在已被世界大多数出版社运用。它们分别是TeX,用于出版业的科学排版,和“优美文章”的产品METAFONT,一个字体生成程序。

结构化文件和文章性程式语言
   
   
Knuth教授的排版研究,引领他发明了文件构造的两种语言和一个方法论,叫作“文章性程式语言”。语言分别是WEB和CWEB,它们促进了程序编写向“文学作品,是用来阅读的”这个方向发展。这两种语言的结合,一种是文件格式化,另一种是程序设计,这就使程序员能够同时创建两个不同的系统程序,一个面向人,另一个面向机器。当一条过程清楚地描述程序并促进其维护时,另外一个则产生一个机器可执行的程序。这些工作就是Knuth教授在实现其使程序设计为读者易懂、甚至感觉漂亮的目标的过程中,在计算机领域里所做出的巨大贡献。

Forever Young

    

     

Forever Young 
          by Alphaville

 

let’s dance in style, lets dance for a while 
heaven can wait we’re only watching the skies 
hoping for the best but expecting the worst 
are you going to drop the bomb or not? 
let us die young or let us live forever 
we don’t have the power but we never say never 
sitting in a sandpit, life is a short trip 
the music’s for the sad men 
can you imagine when this race is won 
turn our golden faces into the sun 
praising our leaders we’re getting in tune 
the music’s played by the madmen 
forever young, i want to be forever young 
do you really want to live forever, forever and ever 
some are like water, some are like the heat 
some are a melody and some are the beat 
sooner or later they all will be gone 
why don’t they stay young 
it’s so hard to get old without a cause 
i don’t want to perish like a fading horse 
youth is like diamonds in the sun 
and dimonds are forever 
so many adventures couldn’t happen today 
so many songs we forgot to play 
so many dreams are swinging out of the blue 
we let them come true

 


 

I want to be forever young.

Suddently,This song recalled some memories of my childhood.

That is my happiest time during my life because of my relatives,my brother,those cattles,those pools,those fishes.

My uncle,my aunty,my grandma.

I did not to care for what I should to eat today,I did not to a lot work because my aunty had tackled it perfectly.

What I should care about is:try to enjoy myself,to get pure delight from those funny things.

I want to be forever young.