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