信息學之數(shù)學基礎

1、第一章 有關數(shù)論的算法1.1 最大公約數(shù)與最小公倍數(shù)1.2 有關素數(shù)的算法1.3 方程ax+by=c的整數(shù)解及應用1.4 求ab mod n1.1最大公約數(shù)與最小公倍數(shù) 1.算法1: 歐幾里德算法求a，b的最大公約數(shù) function gcd(a,b:longint):longint; begin if b=0 then gcdd:=a else gcd:=gcd(b,a mod b); end;2.算法2:最小公倍數(shù)acm=a*b div gcd(a,b);3.算法3:擴展的歐幾里德算法，求出gcd(a,b)和滿足gcd(a,b)=ax+by

2、的整數(shù)x和y function exgcd(a,b:longint;var x,y:longint):longint;vart:longint;beginif b=0 then  begin  result:=a;  x:=1;  y:=0; endelse begin result:=exgcd(b,a mod b,x,y); t:=x; x:=y; y:=t-(a div b)*y; end;end;（理論依據(jù)：gcd(a,b)=ax+by=bx1+(a mod

3、 b)y1=bx1+(a-(a div b)*b)y1=ay1+b(x1-(a div b)*y1)1. 2有關素數(shù)的算法1.算法4:求前n個素數(shù):program BasicMath_Prime;constmaxn=1000;varpnum,n:longint; p:array1.maxn of longint;function IsPrime(x:longint):boolean;var i:integer;beginfor i:=1 to pnum do if sqr(pi)<=x then  begin   if x mod pi=

4、0 then     begin      IsPrime:=false;       exit;     end; end  else  begin   IsPrime:=true;   exit; end;IsPrime:=true;end;procedure main;var x:longint;beginpnu

5、m:=0;x:=1;while(pnum<n) dobegin inc(x); if IsPrime(x) then  begin   inc(pnum);   ppnum:=x;  end;end;end;procedure out;var i,t:integer;beginfor i:=1 to n do begin write(pi:5);t:=t+1; if t mod 10=0 then writeln; end;end;beginreadln(n);main

6、;out;end.2.算法5:求不大于n的所有素數(shù)program sushu3;const maxn=10000;vari,k,n:integer;a:array1.maxn of integer;beginreadln(n);for i:=1 to n do ai:=i;a1:=0;i:=2;while i<n dobegin k:=2*i; while k<=n do  begin  ak:=0;  k:=k+i;  end; i:=i+1; while (ai=0) and (i<n) do

7、 i:=i+1;end;k:=0;for i:=1 to n do if ai<>0  then       begin       write(ai:5); k:=k+1;       if k mod 10 =0 then writeln;       endend.3.算法6:將整數(shù)分解質因數(shù)的積program Basi

8、cMath_PolynomialFactors;constmaxp=1000;varpnum,n:longint;num,p:array1.maxp of longint;procedure main;var x:longint;begin fillchar(num,sizeof(num),0); fillchar(p,sizeof(p),0); pnum:=0; x:=1; while(n>1) do  begin  inc(x);  if n mod x=0 then   

9、begin     inc(pnum);     ppnum:=x;     while(n mod x=0) do       begin        n:=n div x;        inc(numpnum);     

10、 end;   end; end;end;procedure out;var j,i:integer;beginfor i:=1 to pnum dofor j:=1 to numi dowrite(pi:5);writeln;end;beginmain;out;end.1.3方程ax+by=c的整數(shù)解及應用 1.算法7：求方程ax+by=c的整數(shù)解 procedure equation(a,b,c:longint;var x0,y0:longint);var d,x,y:longint;begin d:=exgcd(a,b,x,y); if

11、c mod d>0 then begin  writeln('no answer');  halt; end else begin  x0:=x*(c div d);  y0:=y*(c div d); end;end; 2.方程ax+by=c整數(shù)解的應用 例1：有三個分別裝有a升水、b升水和c升水的量筒(gcd(a，b)1，c>b>a>0),現(xiàn)c筒裝滿水，問能否在c筒個量出d升水(c>d>0)。若能，請列出一種方案。算法分析： 量水過程實際上就是倒來倒

12、去，每次倒的時候總有如下幾個持點： 1.總有一個筒中的水沒有變動； 2不是一個筒被倒?jié)M就是另一個筒被倒光； 3c筒僅起中轉作用，而本身容積除了必須足夠裝下a簡和b簡的全部水外，別無其   它限制。 程序如下: program mw;typenode=array0.1 of longint;vara,b,c:node;d,step,x,y:longint;function exgcd(a,b:longint;var x,y:longint):longint;var t:longint;begin if b=0 then  be

13、gin   exgcd:=a;x:=1;y:=0;  end  else  begin   exgcd:=exgcd(b,a mod b,x,y);   t:=x;x:=y;y:=t-(a div b)*y  end;end;procedure equation(a,b,c:longint;var x0,y0:longint);var d,x,y:longint;begin d:=exgcd(a,b,x,y); if c mod d>0 then begin&

14、#160; writeln('no answer');  halt; end else begin  x0:=x*(c div d);  y0:=y*(c div d); end;end;procedure fill(var a,b:node);var t:longint;begin if a1<b0-b1 then t:=a1               

15、;    else t:=b0-b1; a1:=a1-t; b1:=b1+tend;begin write('a,b,c,d='); readln(a0,b0,c0,d); equation(a0,b0,d,x,y); step:=0; a1:=0;b1:=0;c1:=c0; writeln(step:5,':',a1:5,b1:5,c1:5); if x>0 then  repeat   if a1=0 t

16、hen fill(c,a) else                if b1=b0 then fill(b,c) else fill(a,b);   inc(step);   writeln(step:5,':',a1:5,b1:5,c1:5);  until c1=d  else   repeat    if b1=0

17、 then fill(c,b) else              if a1=a0 then fill(a,c) else fill(b,a);    inc(step);   writeln(step:5,':',a1:5,b1:5,c1:5);   until c1=d;end.1.4 求ab mod n 1.算法8:直接疊代法求ab mod n function f(a,b

18、,n:longint): longint; var d,i:longint; begin  d:=a;  for i:=2 to b do d:=d mod n*a;  d:=d mod n;  f:=d; end; 2.算法9:加速疊代法 function f(a,b,n:longint):longint; var d,t:longint; begin  d:=1;t:=a;  while b>0 do   begin if t=1 then begin f:=d;exit end   ; if

19、b mod 2 =1 then d:=d*t mod n;    b:=b div 2;     t:=t*t mod n;   end;  f:=d end; 練習： 1.熟記并默寫以上算法.第三章 排列與組合3.1 加法原理與乘法原理3.2 排列與組合概念與計算公式3.3 排列與組合的產(chǎn)生算法3.1加法原理與乘法原理 1.加法原理： 做一件事情，完成它可以有n類辦法，在第一類辦法中有m1 種不同的方法，在第二類辦法中有 m2種不同的方法，在第n類辦法中有 mn種不同的方法。那么完成這件事共有 N= m1+m2+.+mn

20、種不同的方法。 2.乘法原理： 做一件事情，完成它需要分成n個步驟，做第一步有m1 種不同的方法，做第二步有 m2種不同的方法，做第n步有 種mn不同的方法，那么完成這件事有 N=m1*m2*.*mn 種不同的方法。 3.兩個原理的區(qū)別：一個與分類有關，一個與分步有關；加法原理是“分類完成”，乘法原理是“分步完成”。 練習： 1.由數(shù)字1，2，3，4，5可以組成多少個三位數(shù)（各位上的數(shù)字允許重復）？      2.由數(shù)字0、1，2，3，4，5可以組成多少個三位數(shù)（各位上的數(shù)字允許重復）？      3.由數(shù)字0，1

21、，2，3，4，5可以組成多少個十位數(shù)字大于個位數(shù)字的兩位數(shù)？ 例  4. 一個三位密碼鎖,各位上數(shù)字由0,1,2,3,4,5,6,7,8,9十個數(shù)字組成,可以設置多少種三位數(shù)的密碼(各位上的數(shù)字允許重復)？首位數(shù)字不為0的密碼數(shù)是多少種？首位數(shù)字是0的密碼數(shù)又是多少種？ 5.如圖，要給地圖A、B、C、D四個區(qū)域分別涂上3種不同顏色中的某一種，允許同一種顏色使用多次，但相鄰區(qū)域必須涂不同的顏色，不同的涂色方案有多少種？ 6.某班有22名女生，23名男生.      選一位學生代表班級去領獎，有幾種不同選法？    &

22、#160; 選出男學生與女學生各一名去參加智力競賽，有幾種不同的選法？    7.105有多少個約數(shù)？并將這些約數(shù)寫出來.    8.從5幅不同的國畫、2幅不同的油畫、7幅不同的水彩畫中選不同畫種的兩幅畫布置房間，有幾種選法？    9.若x、y可以取1，2，3，4，5中的任一個，則點(x,y)的不同個數(shù)有多少？    10.一個口袋內(nèi)裝有5個小球另一個口袋內(nèi)裝有4個小球，所有這些小球的顏色各不相同 從兩個口袋內(nèi)任取一個小球，有 種不同的取法； 11.從兩個口袋內(nèi)各取一個小球，有 種不同的取法. 12.乘積（a1+

23、a2+a3）(b1+b2+b3+b4)(c1+c2+c3+c4+c5)展開共有 個項。 13.有四位考生安排在5個考場參加考試.有 種不同的安排方法。 (答案:125；180；15；1000，900，100；6；45，506；8；59；25；9；20；60；625） 3. 2 排列與組合的概念與計算公式 1排列及計算公式 從n個不同元素中，任取m(mn)個元素按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的一個排列；從n個不同元素中取出m(mn)個元素的所有排列的個數(shù)，叫做從n個不同元素中取出m個元素的排列數(shù)，用符號 p(n,m)表示. p(n,m)=n(n-1)(n-2)(n-m+

24、1)= n!/(n-m)!(規(guī)定0!=1). 2組合及計算公式 從n個不同元素中，任取m(mn)個元素并成一組，叫做從n個不同元素中取出m個元素的一個組合；從n個不同元素中取出m(mn)個元素的所有組合的個數(shù)，叫做從n個不同元素中取出m個元素的組合數(shù).用符號 c(n,m) 表示. c(n,m)=p(n,m)/m!=n!/(n-m)!*m!)；c(n,m)=c(n,n-m); 其他排列與組合公式 從n個元素中取出r個元素的循環(huán)排列數(shù)p(n,r)/r=n!/r(n-r)!. n個元素被分成k類，每類的個數(shù)分別是n1,n2,.nk這n個元素的全排列數(shù)為 n!/(n1!*n2!*.*nk!). k類元

25、素,每類的個數(shù)無限,從中取出m個元素的組合數(shù)為c(m+k-1,m). 練習： 1（1）用0，1，2，3，4組合多少無重復數(shù)字的四位數(shù)？（96） （2）這四位數(shù)中能被4整除的數(shù)有多少個？（30） （3）這四位數(shù)中能被3整除的數(shù)有多少個？（36） 2用0，1，2，3，4五個數(shù)字組成無重復數(shù)字的五位數(shù)從小到大依次排列. （1）       第49個數(shù)是多少？（30124） （2）       23140是第幾個數(shù)？（40） 求下列不同的排法種數(shù)：（1）  

26、60;    6男女排成一排，2女相鄰；(p(7,7)*p(2,2)（2）       6男女排成一排，2女不能相鄰；(p(6,6)*p(7,2)（3）       5男3女排成一排，3女都不能相鄰;(p(5.5)*p(6,3)（4）       4男4女排成一排，同性者相鄰；(p(4,4)*p(4,4)*p(2,2)（5）     &#

27、160; 4男4女排成一排，同性者不能相鄰。(p(4,4)*p(4,4)*p(2,2)有四位醫(yī)生、六位護士、五所學校。(1)            若要選派三位醫(yī)生到五所學校之中的三所學校舉辦健康教育講座，每所學校去一位醫(yī)生有多少種不同的選派方法？(c(5,3)*p(4,3)(2)            在醫(yī)生或護士中任選五人，派到五所學校進行健康情況調(diào)查，每校去且僅去一人，有

28、多少種不同的選派方法？(p(10,5)(3)            組成三個體檢小組，每組一名醫(yī)生、兩名護士，到五所學校中的三所學校為老師體檢，有多少種不同的選派方法？(c(5,3)*p(4,3)*c(6,2)*c(4,2)*c(2,2)平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同一條直線上。問用這些點為頂點，能組成多少個不同四邊形？(2250) 平面上有三條平行直線，每條直線上分別有7，5，6個點，且不同直線上三個點都不在同一條直線上。問用這些點為

29、頂點，能組成多少個不同三角形？(751) 將N個紅球和M個黃球排成一行。例如:N=2,M=2可得到以下6種排法:紅紅黃黃 紅黃紅黃 紅黃黃紅 黃紅紅黃 黃紅黃紅 黃黃紅紅問題:當N=4,M=3時有多少種不同排法?(不用列出每種排法)(35)8.用20個不同顏色的念珠穿成一條項鏈,能做多少個不同的項鏈.(20!/20)9在單詞MISSISSIPPI 中字母的排列數(shù)是(11!/(1!*4!*4!*2!)10求取自1,2,.k的長為r的非減序列的個數(shù)為(c(r+k-1,r) 3.排列與組合的產(chǎn)生算法1排列的產(chǎn)生方法：（遞歸，深度優(yōu)先產(chǎn)生）程序如下：program pailei;const

30、m=4;var a:array1.m of integer ;    b:array1.m of boolean;procedure print;var i:integer;begin for i:=1 to m do  write(ai); writeln;end;procedure try(dep:integer);var i:integer;begin for i:=1 to m do  if  bi then   begin   adep:=i; bi:=f

31、alse;   if dep=m then print else try(dep+1);   bi:=true;   end;end;beginfillchar(b,sizeof(b),true);try(1);end.方法根據(jù)上一個排列產(chǎn)生下一個排列程序如下：program pailei;const m=5;var a:array1.m of integer ;i,j,temp,k,l:integer;procedure print;var i:integer;begin for i:=1 to m do  wr

32、ite(ai); writeln;end;beginfor i:=1 to m do ai:=i;repeat print; i:=m-1; while (i>0) and (ai>ai+1) do i:=i-1; if i>0 then begin  j:=m;  while  aj<ai do j:=j-1;  temp:=ai;ai:=aj;aj:=temp;  k:=i+1;l:=m;  while k<l do  &

33、#160; begin    temp:=ak;ak:=al;al:=temp;     k:=k+1;l:=l-1    end; end;until i=0;end.組合的產(chǎn)生算法算法：（遞歸，深度優(yōu)先產(chǎn)生）程序如下：program zuhe;const n=6;m=4;var a:array0.m of integer; i,j:integer;procedure print;var i:integer;begin for i:=1 to m do write

34、(ai); writeln;end;procedure try(dep:integer);var i:integer;begin for i:=adep-1+1  to n-(m-dep) do  begin  adep:=i;  if dep=m then print else try(dep+1);  endend;begina0:=0;try(1);end.算法：根據(jù)前一個組合產(chǎn)生下一個組合程序如下：program zuhe;const n=6;m=4;var a:array1.m of integer; i

35、,j:integer;procedure print;var i:integer;begin for i:=1 to m do write(ai); writeln;end;begin for i:=1 to m do  ai:=i; repeat  print;  i:=m;  while (i>0) and (ai=n-(m-i) do dec(i);  if i>0 then   begin    ai:=ai+1;  

36、;  for j:=i+1 to m do aj:=aj-1+1;  end; until i=0;end.練習：已知n（1<=n<=20）個整數(shù)x1,x2,xn（1<=xi<=5000000），以及一個整數(shù)k（k<n）。從n個整數(shù)中任選k個整數(shù)相加，可分別得到一系列的和?，F(xiàn)在，要求你計算出和為素數(shù)共有多少種。n個部件,每個部件必須經(jīng)過先A后B兩道工序。       以知部件i在A,B 機器上的時間分別為ai，bi。如何安排加工順序，總加工時間最短？ 輸入： 5 部件1234

37、5ai358710bi6 2149輸出：341 5  4  2  3第四章 計算幾何4.1 基礎知識4.2 線段相交判斷4.3 尋找凸包算法4.1 基礎知識 1.兩點間的距離公式：  已知：平面上的兩點的直角坐標分別為P1(x1,y1)，P2(x2,y2)，則P1和P2兩點間的距離為       d=sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) 2.線段的中點坐標公式：  已知：平面上的兩點的直角坐標分別為P1(x1,y1)，P2(x2,y2)，則線段P1P2

38、的中點坐標為       x=(x1+x2)/2     y=(y1+y2)/2  3.直線的斜率公式：   已知：平面上的兩點的直角坐標分別為P1(x1,y1)，P2(x2,y2),則線段P1P2所在的直線的斜率為      k=（y2-y1)/(x2-x1) 4.直線的點斜式方程:   已知：直線過點P0(x0,y0)，斜率為k,則該直線所在的方程為        y=k(

39、x-x0)+y0=kx+y0-kx0=kx+b(與y軸交點的縱坐標:縱截距) 練習 1.已知:矩形上三點的坐標p1(x1,y1),p2(x2,y2),p3(x3,y3)   (1)求矩形另外一點的坐標p4(x4,y4)。   (2)判斷點p(x,y)是在矩形內(nèi)、矩形外還是在矩形的邊上。    4. 2 線段的相交判斷 1.叉積 已知：平面上的兩點的直角坐標分別為p1(x1,y1)，p2(x2,y2)則 （1）該兩點相對坐標原點(0,0)的叉積為m=x1*y2-x2*y1    若m>0 則相對坐標原點,點p1

40、在點p2的順時針方向    若m<0 則相對坐標原點,點p1在點p2的逆時針方向    若m=0 則原點和p1、p2在一條直線上（2）該兩點相對點p0(x0,y0)的叉積為m=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0)    若m>0 則相對p0點,點p1在點p2的順時針方向    若m<0 則相對p0點,點p1在點p2的逆時針方向    若m=0 則p0和p1、p2在一條直線上2.確定兩條連續(xù)的有向線段p0

41、p1和p1p2在pl點是向左轉還是向右轉    (1)計算叉積m=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0) （2）判斷m     若m>0 則p1點向左拐     若m<0 則p1點向右拐     若m=0 則點p0、p1、p2在一條直線上 3.確定兩條線段p1p2、p3p4是否相交  程序如下：program xdxj;type p=record   

42、  x, y:realend;var p1,p2,p3,p4:p;function m(p1,p2,p0:p):real;begin m:=(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);end;function max(a,b:real):real;begin if a>b then max:=a else max:=b;end;function min(a,b:real):real;begin if a<b then min:=a else min:=b;end;function acros

43、s(p1,p2,p3,p4:p):boolean;begin if (max(p1.x,p2.x)>=min(p3.x,p4.x) and    (max(p3.x,p4.x)>=min(p1.x,p2.x) and    (max(p1.y,p2.y)>=min(p3.y,p4.y) and    (max(p3.y, p4.y)>=min(p1.y,p2.y) and    (m(p2,p3,p1)*m(p2,p4,p1)<0) a

44、nd (m(p4,p1,p3)*m(p4,p2,p3)<0)   then across:=true else across:=false;end;begin readln(p1.x,p1.y,p2.x,p2.y); readln(p3.x,p3.y,p4.x,p4.y); if across(p1,p2,p3,p4) then writeln('yes') else writeln('no');end.4.尋找凸包算法1.凸包的概念一個點集Q（p0,p1,p2.pn-1)，它的凸包是一個最小的凸多邊形P，

45、且滿足Q中的每個點或者在P的邊界上，或者在P的內(nèi)部。在直觀上，我們可以把Q中的每個點看作露在板外的鐵釘那么凸包就是包含所有鐵釘?shù)囊粋€拉緊的橡皮繩所構成的形狀如圖：2.尋找凸包算法算法如下(Graham算法):1)求q中y坐標最小的點p0,若具有最小坐標的點有多個,則取最左邊的點作為po.2)對q中剩余的點按逆時針相對p0的極角排序,若有數(shù)個保留其中距p0最遠的點 得到序列(p1,p2,.pn-1);3)p0,p1,p2相繼入棧4)for i=3 to n-1 do    1) while 由次棧頂元素、棧頂元素和Pi所形成角不是向左轉do棧頂元素出棧s；

46、    2)pi入棧5)打印按逆時針排列的棧中的各頂點程序如下:program tubao;const maxn=500;type p=record     x,y:real;     end;var n,top:integer;list:array0.maxnof p;s:array1.maxn of integer;f:text;procedure swap(var a,b:p);var t:p;begin t:=a;a:=b;b:=t end;function m(p1,p2,p

47、0:p):real;begin m:=(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);end;function comp(p1,p2:p):boolean;var t:real;begin t:=m(p1,p2,list0); if (t>0) or (t=0) and (sqr(p1.x-list0.x)+sqr(p1.y-list0.y)<  sqr(p2.x-list0.x)+sqr(p2.y-list0.y)   then comp:=true else 

48、comp:=false;end;procedure sort(l,r:integer);var i,j:integer;x:p;begin if r-l+1<=5 then begin  for j:=l+1 to  r do   begin    i:=j;    while (i>1) and comp(listi,listi-1) do     begin  swap(listi,listi-1); dec(i) en

49、d   end;  end else   begin    x:=listl+random(r-l+1);    i:=l;j:=r;    repeat     while comp(listi,x) do inc(j);     while comp(x,listj) do dec(j);     if i<j then swa

50、p(listi,listj)    until i>=j;    sort(l,j);    sort(j+1,r);    endend;procedure init;var i:integer;begin assign(f,'input.txt'); reset(f); readln(f,n); for i:=0 to n-1 do  begin   readln(f,listi.

51、x,listi.y);   if (listi.y<list0.y) or    (listi.y=list0.y) and (listi.x<list0.x)    then swap(list0,listi);   end ; sort(1,n-1) end; procedure graham; var i:integer; begin  for i:=1 to 3 do si:=i-1;  top:=3;&#

52、160; for i:=3 to n-1 do   begin    while m(listi,liststop,liststop-1)>=0 do dec(top);    inc(top);    stop:=i;   end;  for i:=1 to top do   write('(',listsi.x:7:2,',',listsi.y:7:2,')');  w

53、riteln end; begin init; graham; readln end.練習:1.巳知:平面上有n個點(n<=10000)，用Graham算法找出彼此間最遠的兩個點.第五章 其它數(shù)學知識及算法5.1 鴿巢原理5.2 容斥原理5.3 常見遞推關系及應用5.1 鴿巢原理 1.簡單形式 如果n+1個物體被放進n個盒子，那么至少有一個盒子包含兩個或更多的物體。 例1：在13個人中存在兩個人，他們的生日在同一月份里。 例2：設有n對已婚夫婦。為保證有一對夫婦被選出，至少要從這2n個人中選出多少人？（n+1） 2.加強形式 令

54、q1,q2,.qn為正整數(shù)。如果將  q1+q2+.+qn-n+1個物體放入n個盒子內(nèi),那么或者第一個盒子至少含有q1個物體,或者第二個盒子 至少含有q2個物體,.,或者第n個盒子含有qn個物體. 例3:一籃子水果裝有蘋果、香蕉、和橘子。為了保證籃子內(nèi)或者至少8個蘋果或者至少6個香蕉或者至少9 個橘子，則放入籃子中的水果的最小件數(shù)是多少？（21件） 5. 2   容斥原理及應用    原理：集S的不具有性質P1,P2,.，Pm的物體的個數(shù)由下式給出： |A1A2.Am|=|S|-|Ai|+|AiAj|-|AiAjAk|+.+(-1)m

55、|A1A2.Am| 如:m=3,時上式為： |A1A2A3|=|S|-(|A1|+|A2|+|A3|)+(|A1A2|+|A1A3|+|A2A3|)|A1A2A3| 推論:至少具有性質P1,P2,.Pm之一的集合S的物體的個數(shù)有： | A1A2.Am|=|S|A1A2.Am|= |Ai|-|AiAj|+|AiAjAk|+.+(-1)m+1|A1A2.Am| 例4：求從1到1000不能被5，6，和8整除的整數(shù)的個數(shù)？  （1000-（200+166+125）+（33+25+41）-8=600） 5. 常見遞推關系及應用1.算術序列 每一項比前一項大一個常數(shù)d； 若初始項為h0：則遞推關

56、系為 hn=hn-1+d=h0+nd； 對應的各項為：h0，h0+d，h0+2d，.,h0+nd; 前n項的和為(n+1)h0+dn(n+1)/2 例5: 1,2,3,. 例6: 1,3,5,7.等都是算術序列。 2.幾何序列 每一項是前面一項的常數(shù)q倍 若初始項為h0：則遞推關系為 hn=h0qn-1q=h0qn； 對應的各項為: h0，h0q1，h0q2，.,h0qn例7: 1,2,4,8,16,. 例8: 5,15,45,135,.等都是幾何序列; 前n項和為(qn+1-1)/(q-1) )h0 3.Fibonacci序列 除第一、第二項外每一項是它前兩項的和； 若首項為f0為0,則序列為0，1，1，2，3，5，8.遞推關系為(n>=2)fn=fn-1+fn-2    前n項的和Sn=f0+f1+f2+.+fn=fn+2-1 例9:以下是Fibonacci的示例:       1.樓梯有n階臺階,上樓可以一步上1階,也可以一步上2階,編一程序計算共有多少種不同的走法?       2.有一對雌雄兔,每兩個月就繁殖雌雄各一對