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