如何計算一個程序的演算法

1. 怎麼編一個簡單的運算程序

/*簡易計算器.cpp 你自己找個c++編譯器就可以運行*/
#include<iostream>#include<string>using
namespace
std;int
main(){ float
a,b; char
str; cout<<"a="; cin>>a;
//輸入兩個數 cout<<"
b="; cin>>b;

cout<<"請輸入+,-,*,/
其中一個運算符"<<endl;
cout<<"你所選的運算符是:";fflush(stdin);
//清空輸入緩沖區，通常是為了確保不影響後面的數據讀取
str=getchar();
cout<<endl;
switch(str)
{

case
'+':cout<<"a+b="<<a+b;break;

case
'-':cout<<"a-b="<<a-b;break;

case
'*':cout<<"a*b="<<a*b;break; case
'/':cout<<"a/b="<<a/b;break; defaut:cout<<"error";
} return
0; }

2. c語言的一個小程序應該如何計算

遞歸調用函數f，每次加8。y從6到1，共6個8相加，結果是48。

3. 程序中的時間復雜度是怎麼計算的

演算法復雜度的介紹，見網路：
http://ke..com/view/7527.htm

時間復雜度
時間頻度
一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。

計算方法
1. 一般情況下，演算法的基本操作重復執行的次數是模塊n的某一個函數f（n），因此，演算法的時間復雜度記做：T（n）=O（f（n））
分析：隨著模塊n的增大，演算法執行的時間的增長率和f（n）的增長率成正比，所以f（n）越小，演算法的時間復雜度越低，演算法的效率越高。
2. 在計算時間復雜度的時候，先找出演算法的基本操作，然後根據相應的各語句確定它的執行次數，再找出T（n）的同數量級（它的同數量級有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出後，f（n）=該數量級，若T(n)/f(n)求極限可得到一常數c，則時間復雜度T（n）=O（f（n））

例：演算法：
for（i=1;i<=n;++i）
{
for(j=1;j<=n;++j)
{
c[ i ][ j ]=0; //該步驟屬於基本操作 ，執行次數：n的平方 次
for(k=1;k<=n;++k)
c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //該步驟屬於基本操作 ，執行次數：n的三次方 次
}
}
則有 T（n）= n的平方+n的三次方，根據上面括弧里的同數量級，我們可以確定 n的三次方 為T（n）的同數量級
則有f（n）= n的三次方，然後根據T（n）/f（n）求極限可得到常數c
則該演算法的 時間復雜度：T（n）=O（n^3） 註：n^3即是n的3次方。
3.在pascal中比較容易理解，容易計算的方法是：看看有幾重for循環，只有一重則時間復雜度為O（n）,二重則為O（n^2），依此類推，如果有二分則為O(logn)，二分例如快速冪、二分查找，如果一個for循環套一個二分，那麼時間復雜度則為O(nlogn)。

分類
按數量級遞增排列，常見的時間復雜度有：
常數階O(1),對數階O(log2n),線性階O(n),
線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),...，
k次方階O(n^k), 指數階O(2^n) 。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。

關於對其的理解
《數據結構（C語言版）》------嚴蔚敏 吳偉民編著 第15頁有句話"整個演算法的執行時間與基本操作重復執行的次數成正比。"
基本操作重復執行的次數是問題規模n的某個函數f(n)，於是演算法的時間量度可以記為：T(n) = O( f(n) )
如果按照這么推斷，T(n)應該表示的是演算法的時間量度，也就是演算法執行的時間。
而該頁對「語句頻度」也有定義：指的是該語句重復執行的次數。
如果是基本操作所在語句重復執行的次數，那麼就該是f(n)。
上邊的n都表示的問題規模。

以下來自網路知道：

對於這些演算法
(1) for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
s++;

(2) for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
s++;

(3) for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
s++;

(4) i=1;k=0;
while(i<=n-1){
k+=10*i;
i++;
}

(5) for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;

對應的時間復雜度為：

1.時間復雜度O(n^2)
2.時間復雜度O(n^2)
3.時間復雜度O(n^2)
4.時間復雜度O(n)
5.時間復雜度O(n^3)

一般來說，時間復雜度是總運算次數表達式中受n的變化影響最大的那一項(不含系數)
比如：一般總運算次數表達式類似於這樣：
a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f
a<>0時，時間復雜度就是O(2^n);
a=0,b<>0 =>O(n^3);
a,b=0,c<>0 =>O(n^2)依此類推

那麼，總運算次數又是如何計算出的呢？
一般來說，我們經常使用for循環，就像剛才五個題，我們就以它們為例
1.循環了n*n次，當然是O(n^2)
2.循環了(n+n-1+n-2+...+1)≈(n^2)/2，因為時間復雜度是不考慮系數的，所以也是O(n^2)
3.循環了(1+2+3+...+n)≈(n^2)/2,當然也是O(n^2)
4.循環了n-1≈n次，所以是O(n)
5.循環了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6(這個公式要記住哦)≈(n^3)/3，不考慮系數，自然是O(n^3)

另外，在時間復雜度中，log(2,n)(以2為底)與lg(n)(以10為底)是等價的，因為對數換底公式：
log(a,b)=log(c,b)/log(c,a)
所以，log(2,n)=log(2,10)*lg(n),忽略掉系數，二者當然是等價的

4. 設計一個計算1×3×5×7×…×99的演算法，並寫出程序。

解：演算法步驟如下： 第一步：S=1； 第二步：i=3； 第三步：S=S×i； 第四步：i=i+2； 第五步：判斷i是否大於99，若是轉到第六步；否則返第三步，繼續執行第三步，第四步，第五步； 第六步：輸出S； 第七步：演算法結束。 相應的程序框圖如圖所示： 。

5. 程序員開發用到的十大基本演算法

演算法一：快速排序演算法
快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο(n log n) 演算法更快，因為它的內部循環（inner loop）可以在大部分的架構上很有效率地被實現出來。

快速排序使用分治法（Divide and conquer）策略來把一個串列（list）分為兩個子串列（sub-lists）。

演算法步驟：
1 從數列中挑出一個元素，稱為 「基準」（pivot），
2 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作。
3 遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個演算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。

演算法二：堆排序演算法
堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序演算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的鍵值或索引總是小於（或者大於）它的父節點。堆排序的平均時間復雜度為Ο(nlogn) 。

演算法步驟：
1.創建一個堆H[0..n-1]
2.把堆首（最大值）和堆尾互換
3.把堆的尺寸縮小1，並調用shift_down(0),目的是把新的數組頂端數據調整到相應位置
4.重復步驟2，直到堆的尺寸為1

演算法三：歸並排序
歸並排序（Merge sort，台灣譯作：合並排序）是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

演算法步驟：

演算法四：二分查找演算法
二分查找演算法是一種在有序數組中查找某一特定元素的搜索演算法。搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜 素過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組 為空，則代表找不到。這種搜索演算法每一次比較都使搜索范圍縮小一半。折半搜索每次把搜索區域減少一半，時間復雜度為Ο(logn) 。

演算法五：BFPRT(線性查找演算法)
BFPRT演算法解決的問題十分經典，即從某n個元素的序列中選出第k大（第k小）的元素，通過巧妙的分 析，BFPRT可以保證在最壞情況下仍為線性時間復雜度。該演算法的思想與快速排序思想相似，當然，為使得演算法在最壞情況下，依然能達到o(n)的時間復雜 度，五位演算法作者做了精妙的處理。

演算法步驟：

終止條件：n=1時，返回的即是i小元素。

演算法六：DFS（深度優先搜索）
深度優先搜索演算法（Depth-First-Search），是搜索演算法的一種。它沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分 支。當節點v的所有邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發 現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止。DFS屬於盲目搜索。

深度優先搜索是圖論中的經典演算法，利用深度優先搜索演算法可以產生目標圖的相應拓撲排序表，利用拓撲排序表可以方便的解決很多相關的圖論問題，如最大路徑問題等等。一般用堆數據結構來輔助實現DFS演算法。

演算法步驟：

上述描述可能比較抽象，舉個實例：
DFS 在訪問圖中某一起始頂點 v 後，由 v 出發，訪問它的任一鄰接頂點 w1；再從 w1 出發，訪問與 w1鄰 接但還沒有訪問過的頂點 w2；然後再從 w2 出發，進行類似的訪問，… 如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。

接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之後再從此頂點出發，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復上述過程，直到連通圖中所有頂點都被訪問過為止。

演算法七：BFS(廣度優先搜索)
廣度優先搜索演算法（Breadth-First-Search），是一種圖形搜索演算法。簡單的說，BFS是從根節點開始，沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問，則演算法中止。BFS同樣屬於盲目搜索。一般用隊列數據結構來輔助實現BFS演算法。

演算法步驟：

演算法八：Dijkstra演算法
戴克斯特拉演算法（Dijkstra』s algorithm）是由荷蘭計算機科學家艾茲赫爾·戴克斯特拉提出。迪科斯徹演算法使用了廣度優先搜索解決非負權有向圖的單源最短路徑問題，演算法最終得到一個最短路徑樹。該演算法常用於路由演算法或者作為其他圖演算法的一個子模塊。

該演算法的輸入包含了一個有權重的有向圖 G，以及G中的一個來源頂點 S。我們以 V 表示 G 中所有頂點的集合。每一個圖中的邊，都是兩個頂點所形成的有序元素對。(u, v) 表示從頂點 u 到 v 有路徑相連。我們以 E 表示G中所有邊的集合，而邊的權重則由權重函數 w: E → [0, ∞] 定義。因此，w(u, v) 就是從頂點 u 到頂點 v 的非負權重（weight）。邊的權重可以想像成兩個頂點之間的距離。任兩點間路徑的權重，就是該路徑上所有邊的權重總和。已知有 V 中有頂點 s 及 t，Dijkstra 演算法可以找到 s 到 t的最低權重路徑(例如，最短路徑)。這個演算法也可以在一個圖中，找到從一個頂點 s 到任何其他頂點的最短路徑。對於不含負權的有向圖，Dijkstra演算法是目前已知的最快的單源最短路徑演算法。

演算法步驟：

重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止

演算法九：動態規劃演算法
動態規劃（Dynamic programming）是一種在數學、計算機科學和經濟學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。 動態規劃常常適用於有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少於樸素解法。

動態規劃背後的基本思想非常簡單。大致上，若要解一個給定問題，我們需要解其不同部分（即子問題），再合並子問題的解以得出原問題的解。 通常許多 子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，從而減少計算量： 一旦某個給定子問題的解已經算出，則將其記憶化存儲，以便下次需要同一個 子問題解之時直接查表。 這種做法在重復子問題的數目關於輸入的規模呈指數增長時特別有用。

關於動態規劃最經典的問題當屬背包問題。

演算法步驟：

演算法十：樸素貝葉斯分類演算法
樸素貝葉斯分類演算法是一種基於貝葉斯定理的簡單概率分類演算法。貝葉斯分類的基礎是概率推理，就是在各種條件的存在不確定，僅知其出現概率的情況下， 如何完成推理和決策任務。概率推理是與確定性推理相對應的。而樸素貝葉斯分類器是基於獨立假設的，即假設樣本每個特徵與其他特徵都不相關。

樸素貝葉斯分類器依靠精確的自然概率模型，在有監督學習的樣本集中能獲取得非常好的分類效果。在許多實際應用中，樸素貝葉斯模型參數估計使用最大似然估計方法，換言之樸素貝葉斯模型能工作並沒有用到貝葉斯概率或者任何貝葉斯模型。

盡管是帶著這些樸素思想和過於簡單化的假設，但樸素貝葉斯分類器在很多復雜的現實情形中仍能夠取得相當好的效果。

6. 如何查看一個程序的演算法請詳細介紹。

這是看不出來的，只能靠你自己去分析程序… 如果程序的演算法你不會當然是看不懂的了…如果程序有注釋，那程序的可讀性就強了…

7. 怒了，求高人解釋程序演算法，很簡短的一個程序

外星人計算Pi的程序

一、源程序
本文分析下面這個很流行的計算PI的小程序。下面這個程序初看起來似乎摸不到頭腦，
不過不用擔心，當你讀完本文的時候就能夠基本讀懂它了。
程序一：很牛的計算Pi的程序
int a=10000,b,c=2800,d,e,f[2801],g;
main() {
for(;b-c;)
f[b++]=a/5;
for(;d=0,g=c*2;c -=14,printf("%.4d",e+d/a),e=d%a)
for(b=c; d+=f[b]*a,f[b]=d%--g,d/=g--,--b; d*=b);
}
二、數學公式
數學家們研究了數不清的方法來計算PI,這個程序所用的公式如下：
1 2 3 k
pi = 2 + --- * (2 + --- * (2 + --- * (2 + ... (2 + ---- * (2 + ... ))...)))

3 5 7 2k+1
至於這個公式為什麼能夠計算出PI，已經超出了本文的能力范圍。
下面要做的事情就是要分析清楚程序是如何實現這個公式的。
我們先來驗證一下這個公式：
程序二：Pi公式驗證程序
#include "stdio.h"
void main()
{
float pi=2;
int i;
for(i=100;i>=1;i--)
pi=pi*(float)i/(2*i+1)+2;
printf("%f\n",pi);
getchar();
}
上面這個程序的結果是3.141593。
三、程序展開
在正式分析程序之前，我們需要對程序一進行一下展開。我們可以看出程序一都是使用
for循環來完成計算的，這樣做雖然可以使得程序短小，但是卻很難讀懂。根據for循環
的運行順序，我們可以把它展開為如下while循環的程序：
程序三：for轉換為while之後的程序
int a=10000,b,c=2800,d,e,f[2801],g;
main() {
int i;
for(i=0;i<c;i++)
f[i]=a/5;
while(c!=0)
{
d=0;
g=c*2;
b=c;
while(1)
{
d=d+f[b]*a;
g--;
f[b]=d%g;
d=d/g;
g--;
b--;
if(b==0) break;
d=d*b;
}
c=c-14;
printf("%.4d",e+d/a);
e=d%a;
}
}
註：
for([1];[2];[3]) {[4];}
的運行順序是[1],[2],[4],[3]。如果有逗號操作符，例如：d=0,g=c*2，則先運行d=0,
然後運行g=c*2,並且最終的結果是最後一個表達式的值，也就是這里的c*2。
下面我們就針對展開後的程序來分析。
四、程序分析
要想計算出無限精度的PI，我們需要上述的迭代公式運行無數次，並且其中每個分數也
是完全精確的，這在計算機中自然是無法實現的。那麼基本實現思想就是迭代足夠多次
，並且每個分數也足夠精確，這樣就能夠計算出PI的前n位來。上面這個程序計算800位
，迭代公式一共迭代2800次。
int a=10000,b,c=2800,d,e,f[2801],g;
這句話中的2800就是迭代次數。
由於float或者double的精度遠遠不夠，因此程序中使用整數類型（實際是長整型），分
段運算（每次計算4位）。我們可以看到輸出語句 printf("%.4d",e+d/a); 其中%.4就是
把計算出來的4位輸出，我們看到c每次減少14（ c=c-14;），而c的初始大小為2800，因
此一共就分了200段運算，並且每次輸出4位，所以一共輸出了800位。
由於使用整型數運算，因此有必要乘上一個系數，在這個程序中系數為1000，也就是說
，公式如下：
1 2 3 k
1000*pi = 2k+ --- * (2k+ --- * (2k+ --- * (2k+ ... (2k+ ---- * (2k+ ... )).
..)))
3 5 7 2k+1
這里的2k表示2000，也就是f[2801]數組初始化以後的數據,a=10000,a/5=2000,所以下面
的程序把f中的每個元素都賦值為2000：
for(i=0;i<c;i++)
f[i]=a/5;
你可能會覺得奇怪，為什麼這里要把一個常數儲存到數組中去，請繼續往下看。
我們先來跟蹤一下程序的運行：
while(c!=0) 假設這是第一次運行，c=2800，為迭代次數
{
d=0;
g=c*2; 這里的g是用來做k/(2k+1)中的分子
b=c; 這里的b是用來做k/(2k+1)中的分子
while(1)
{
d=d+f[b]*a; f中的所有的值都為2000，這里在計算時又把系數擴大了
a=10000倍。

這樣做的目的稍候介紹，你可以看到
輸出的時候是d/a,所以這不影
計算
g--;
f[b]=d%g; 先不管這一行
d=d/g; 第一次運行的g為2*2799+1，你可以看到g做了分母
g--;
b--;
if(b==0) break;
d=d*b; 這里的b為2799，可以看到d做了分子。
}
c=c-14;
printf("%.4d",e+d/a);
e=d%a;
}
只需要粗略的看看上面的程序，我們就大概知道它的確是使用的那個迭代公式來計算Pi
的了，不過不知道到現在為止你是否明白了f數組的用處。如果沒有明白，請繼續閱讀。

d=d/g,這一行的目的是除以2k+1，我們知道之所以程序無法精確計算的原因就是這個除
法。即使用浮點數，答案也是不夠精確的，因此直接用來計算800位的Pi是不可能的。那
么不精確的成分在哪裡？很明顯：就是那個余數d%g。程序用f數組把這個誤差儲存起來
，再下次計算的時候使用。現在你也應該知道為什麼d=d+f[b]*a;中間需要乘上a了吧。
把分子擴大之後，才好把誤差精確的算出來。
d如果不乘10000這個系數，則其值為2000，那麼運行d=d/g；則是2000/(2*2799+1)，這
種整數的除法答案為0，根本無法迭代下去了。
現在我們知道程序就是把余數儲存起來，作為下次迭代的時候的參數，那麼為什麼這么
做就可以使得下次迭代出來的結果為
接下來的4位數呢？
這實際上和我們在紙上作除法很類似：
0142
/——------
7 / 1
10
7
---------------
30
28
---------------
20
14
---------------
60
.....
我們可以發現，在做除法的時候，我們通常把余數擴大之後再來計算，f中既然儲存的是
余數，而f[b]*a;則正好把這個余數擴大了a倍，然後如此循環下去，可以計算到任意精
度。
這里要說明的是，事實上每次計算出來的d並不一定只有4位數，例如第一次計算的時候
，d的值為31415926，輸出4位時候，把低四位的值儲存在e中間，e=d%a，也就是5926。

最後，這個c=c-14不太好理解。事實上沒有這條語句，程序計算出來的仍然正確。只是
因為如果迭代2800次，無論分數如何精確，最後Pi的精度只能夠達到800。
你可以把程序改為如下形式嘗試一下：
for(i=0;i<800;i++)
{
d=0;
g=c*2;
b=c;
while(1)
{
d=d+f[b]*a;
g--;
f[b]=d%g;
d=d/g;
g--;
b--;
if(b==0) break;
d=d*b;
}
// c=c-14; 不要這句話。
printf("%.4d",e+d/a);
e=d%a;
}
最後的答案仍然正確。
不過我們可以看到內循環的次數是c次，也就是說每次迭代計算c次。而每次計算後續位
數的時候，迭代次數減少14，而不影響精度。為什麼會這樣，我沒有研究。另外最後的
e+d/a,和e=d/a的作用就由讀者自己考慮吧。
--

8. 設計一個演算法計算1×2×3×…×100，畫出程序框圖．

第一步：設i的值為1；
第二步：設S的值為1；×
第三步：如果i≤100執行第四步，
否則轉去執行第七步；
第四步：計算S×i並將結果代替S；
第五步：計算i+1並將結果代替i；
第六步：轉去執行第三步；
第七步：輸出S的值並結束演算法．

9. 設計一個計算 的演算法，並畫出它的程序流程圖.

程序流程圖是程序分析中最基本、最重要的分析技術，它是進行程序流程分析過程中最基本的工具。它運用工序圖示符號對生產現場的整個製造過程做詳細的記錄，以便對零部件、產品在整個製造過程中的生產、加工、檢驗、儲存等環節待作詳細的研究與分析，特別適用於分析生產過程中的成本浪費，提高經濟效益。