常用的算法的表示方法(算法的三種表示方法A版)
1.算法的三種表示方法（A版）
去百度文庫(kù)，查看完整內(nèi)容>
內(nèi)容來(lái)自用戶：yicaohan
算法的三種表示方法（A版）
自然語(yǔ)言、程序框圖和程序語(yǔ)句是算法的三種表示方法，是算法的形式化表示，且它們是嚴(yán)格對(duì)應(yīng)的.例如，以下是給出三個(gè)數(shù)求其中的最大數(shù)的自然語(yǔ)言算法、框圖和程序的對(duì)應(yīng)情況，通過(guò)本例體會(huì)其嚴(yán)密的對(duì)應(yīng)關(guān)系.
例 已知，設(shè)計(jì)程序輸入x的值，輸出相應(yīng)的y的值，寫(xiě)出其
算法，畫(huà)出程序框圖并寫(xiě)出其程序.
解：算法步驟為：
第一步：輸入x;
第二步：判斷x是否大于0，若是，y=1；若不是，y=0;
第三步：輸出y.
程序框圖為：
程序?yàn)椋?/p>
INPUT “x=”;x
IF x>0 THEN
y=1
ELSE
y=0
END IF
PRINT y
END
點(diǎn)評(píng)：本題使用了條件語(yǔ)句“IF…THEN…ELSE…ENDIF”
2.算法的三種表示方法（A版）
去百度文庫(kù)，查看完整內(nèi)容>內(nèi)容來(lái)自用戶：yicaohan算法的三種表示方法（A版） 自然語(yǔ)言、程序框圖和程序語(yǔ)句是算法的三種表示方法，是算法的形式化表示，且它們是嚴(yán)格對(duì)應(yīng)的.例如，以下是給出三個(gè)數(shù)求其中的最大數(shù)的自然語(yǔ)言算法、框圖和程序的對(duì)應(yīng)情況，通過(guò)本例體會(huì)其嚴(yán)密的對(duì)應(yīng)關(guān)系.例 已知，設(shè)計(jì)程序輸入x的值，輸出相應(yīng)的y的值，寫(xiě)出其算法，畫(huà)出程序框圖并寫(xiě)出其程序. 解：算法步驟為： 第一步：輸入x； 第二步：判斷x是否大于0，若是，y=1；若不是，y=0； 第三步：輸出y. 程序框圖為： 程序?yàn)椋?INPUT “x=”;x IF x>0 THEN y=1 ELSE y=0 END IF PRINT y END 點(diǎn)評(píng)：本題使用了條件語(yǔ)句“IF…THEN…ELSE…ENDIF”。
3.什么是算法,常用的算法描述有哪些
算法的描述方式主要有自然語(yǔ)言，流程圖，偽代碼等，它們的優(yōu)勢(shì)和不足可以簡(jiǎn)單地歸納如下：1、自然語(yǔ)言優(yōu)勢(shì)：自然語(yǔ)言描述的算法通俗易懂，不用專門的訓(xùn)練不足：a.由于自然語(yǔ)言的歧義性，容易導(dǎo)致算法執(zhí)行的不確定性.b.自然語(yǔ)言的語(yǔ)句一般較長(zhǎng)，導(dǎo)致描述的算法太長(zhǎng).c.當(dāng)一個(gè)算法中循環(huán)和分歧較多時(shí)就很難清晰地表示出來(lái).d.自然語(yǔ)言表示的算法不便翻譯成計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言.2、流程圖優(yōu)勢(shì)：流程圖描述的算法清晰簡(jiǎn)潔，容易表達(dá)選擇結(jié)構(gòu)，它不依賴于任何具體的計(jì)算機(jī)和計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言，從而有利于不同環(huán)境的程序設(shè)計(jì).不足：不易書(shū)寫(xiě)，修改起來(lái)比較費(fèi)事，可以借助于專用的流程圖制作軟件來(lái)提升繪制和修改.3、偽代碼優(yōu)勢(shì)：偽代碼回避了程序設(shè)計(jì)語(yǔ)言的嚴(yán)格、煩瑣的書(shū)寫(xiě)格式，書(shū)寫(xiě)方便，同時(shí)具備格式緊湊，易于理解，便于向計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言過(guò)渡的優(yōu)點(diǎn).不足：由于偽代碼的種類繁多，語(yǔ)句不容易規(guī)范，有時(shí)會(huì)產(chǎn)生誤讀.。
4.簡(jiǎn)述算法的各種表示形式
一、什么是算法 算法是一系列解決問(wèn)題的清晰指令，也就是說(shuō)，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。
算法常常含有重復(fù)的步驟和一些比較或邏輯判斷。如果一個(gè)算法有缺陷，或不適合于某個(gè)問(wèn)題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問(wèn)題。
不同的算法可能用不同的時(shí)間、空間或效率來(lái)完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來(lái)衡量。
算法的時(shí)間復(fù)雜度是指算法需要消耗的時(shí)間資源。一般來(lái)說(shuō)，計(jì)算機(jī)算法是問(wèn)題規(guī)模n 的函數(shù)f(n)，算法執(zhí)行的時(shí)間的增長(zhǎng)率與f(n) 的增長(zhǎng)率正相關(guān)，稱作漸進(jìn)時(shí)間復(fù)雜度（Asymptotic Time Complexity）。
時(shí)間復(fù)雜度用“O（數(shù)量級(jí)）”來(lái)表示，稱為“階”。常見(jiàn)的時(shí)間復(fù)雜度有： O(1)常數(shù)階；O(log2n)對(duì)數(shù)階；O(n)線性階；O(n2)平方階。
算法的空間復(fù)雜度是指算法需要消耗的空間資源。其計(jì)算和表示方法與時(shí)間復(fù)雜度類似，一般都用復(fù)雜度的漸近性來(lái)表示。
同時(shí)間復(fù)雜度相比，空間復(fù)雜度的分析要簡(jiǎn)單得多。 二、算法設(shè)計(jì)的方法 1.遞推法 遞推法是利用問(wèn)題本身所具有的一種遞推關(guān)系求問(wèn)題解的一種方法。
設(shè)要求問(wèn)題規(guī)模為N的解，當(dāng)N=1時(shí)，解或?yàn)橐阎?，或能非常方便地得到解。能采用遞推法構(gòu)造算法的問(wèn)題有重要的遞推性質(zhì)，即當(dāng)?shù)玫絾?wèn)題規(guī)模為i-1的解后，由問(wèn)題的遞推性質(zhì)，能從已求得的規(guī)模為1,2，…，i-1的一系列解，構(gòu)造出問(wèn)題規(guī)模為I的解。
這樣，程序可從i=0或i=1出發(fā)，重復(fù)地，由已知至i-1規(guī)模的解，通過(guò)遞推，獲得規(guī)模為i的解，直至得到規(guī)模為N的解。 【問(wèn)題】 階乘計(jì)算 問(wèn)題描述：編寫(xiě)程序，對(duì)給定的n(n≤100)，計(jì)算并輸出k的階乘k!(k=1,2，…，n)的全部有效數(shù)字。
由于要求的整數(shù)可能大大超出一般整數(shù)的位數(shù)，程序用一維數(shù)組存儲(chǔ)長(zhǎng)整數(shù)，存儲(chǔ)長(zhǎng)整數(shù)數(shù)組的每個(gè)元素只存儲(chǔ)長(zhǎng)整數(shù)的一位數(shù)字。如有m位成整數(shù)N用數(shù)組a[ ]存儲(chǔ)： N=a[m]*10m-1+a[m-1]*10m-2+ … +a[2]*101+a[1]*100 并用a[0]存儲(chǔ)長(zhǎng)整數(shù)N的位數(shù)m，即a[0]=m。
按上述約定，數(shù)組的每個(gè)元素存儲(chǔ)k的階乘k！的一位數(shù)字，并從低位到高位依次存于數(shù)組的第二個(gè)元素、第三個(gè)元素……。例如，5!=120，在數(shù)組中的存儲(chǔ)形式為： 3 0 2 1 …… 首元素3表示長(zhǎng)整數(shù)是一個(gè)3位數(shù)，接著是低位到高位依次是0、2、1，表示成整數(shù)120。
計(jì)算階乘k！可采用對(duì)已求得的階乘（k-1）！連續(xù)累加k-1次后求得。例如，已知4!=24，計(jì)算5！，可對(duì)原來(lái)的24累加4次24后得到120。
細(xì)節(jié)見(jiàn)以下程序。 # include # include # define MAXN 1000 void pnext(int a[ ],int k) { int *b,m=a[0],i,j,r,carry; b=(int * ) malloc(sizeof(int)* (m+1)); for ( i=1;i0;i--) printf(“%d”,a[i]); printf(“\n\n”); } void main() { int a[MAXN],n,k; printf(“Enter the number n: “); scanf(“%d”,&n); a[0]=1; a[1]=1; write(a,1); for (k=2;k1時(shí))。
寫(xiě)成遞歸函數(shù)有： int fib(int n) { if (n==0) return 0; if (n==1) return 1; if (n>1) return fib(n-1)+fib(n-2)； } 遞歸算法的執(zhí)行過(guò)程分遞推和回歸兩個(gè)階段。在遞推階段，把較復(fù)雜的問(wèn)題（規(guī)模為n）的求解推到比原問(wèn)題簡(jiǎn)單一些的問(wèn)題（規(guī)模小于n）的求解。
例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是說(shuō)，為計(jì)算fib(n)，必須先計(jì)算fib(n-1)和fib(n-2)，而計(jì)算fib(n-1)和fib(n-2)，又必須先計(jì)算fib(n-3)和fib(n-4)。
依次類推，直至計(jì)算fib(1)和fib(0)，分別能立即得到結(jié)果1和0。在遞推階段，必須要有終止遞歸的情況。
例如在函數(shù)fib中，當(dāng)n為1和0的情況。 在回歸階段，當(dāng)獲得最簡(jiǎn)單情況的解后，逐級(jí)返回，依次得到稍復(fù)雜問(wèn)題的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的結(jié)果，……，在得到了fib(n-1)和fib(n-2)的結(jié)果后，返回得到fib(n)的結(jié)果。
在編寫(xiě)遞歸函數(shù)時(shí)要注意，函數(shù)中的局部變量和參數(shù)知識(shí)局限于當(dāng)前調(diào)用層，當(dāng)遞推進(jìn)入“簡(jiǎn)單問(wèn)題”層時(shí)，原來(lái)層次上的參數(shù)和局部變量便被隱蔽起來(lái)。在一系列“簡(jiǎn)單問(wèn)題”層，它們各有自己的參數(shù)和局部變量。
由于遞歸引起一系列的函數(shù)調(diào)用，并且可能會(huì)有一系列的重復(fù)計(jì)算，遞歸算法的執(zhí)行效率相對(duì)較低。當(dāng)某個(gè)遞歸算法能較方便地轉(zhuǎn)換成遞推算法時(shí)，通常按遞推算法編寫(xiě)程序。
例如上例計(jì)算斐波那契數(shù)列的第n項(xiàng)的函數(shù)fib(n)應(yīng)采用遞推算法，即從斐波那契數(shù)列的前兩項(xiàng)出發(fā)，逐次由前兩項(xiàng)計(jì)算出下一項(xiàng)，直至計(jì)算出要求的第n項(xiàng)。 【問(wèn)題】 組合問(wèn)題 問(wèn)題描述：找出從自然數(shù)1、2、……、n中任取r個(gè)數(shù)的所有組合。
例如n=5,r=3的所有組合為： （1）5、4、3 (2)5、4、2 (3)5、4、1 (4)5、3、2 (5)5、3、1 (6)5、2、1 (7)4、3、2 (8)4、3、1 (9)4、2、1 (10)3、2、1 分析所列的10個(gè)組合，可以采用這樣的遞歸思想來(lái)考慮求組合函數(shù)的算法。設(shè)函數(shù)為void comb(int m,int k)為找出從自然數(shù)1、2、……、m中任取k個(gè)數(shù)的所有組合。
當(dāng)組合的第一個(gè)數(shù)字選定時(shí)，其后的數(shù)字是從余下的m-1個(gè)數(shù)中取k-1數(shù)的組合。這就將求m個(gè)數(shù)中取k個(gè)數(shù)的組合問(wèn)題轉(zhuǎn)化成求m-1個(gè)數(shù)中取k-1個(gè)數(shù)的組合問(wèn)題。
設(shè)函數(shù)引入工作數(shù)組a[ ]存放求出的組合的數(shù)字，約定函數(shù)將確定的k個(gè)數(shù)字組合的第一個(gè)數(shù)字放在a[k]中，當(dāng)一個(gè)組合求出后，才將a[ ]中的一個(gè)組合輸出。第一個(gè)數(shù)可以是m、m-1、……、k，函數(shù)將確定組合的第一個(gè)數(shù)字。
