簡單的程序演算法

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

外星人計算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的作用就由讀者自己考慮吧。
--

B. 作為一個程序員，有哪些常用的演算法

常用的演算法有：遞推法、貪心法、列舉法、遞歸法、分治法和模擬法
原則：1. 扎實的基礎。數據結構、離散數學、編譯原理，這些是所有計算機科學的基礎，如果不掌握他們，很難寫出高水平的程序。據我的觀察，學計算機專業的人比學其他專業的人更能寫出高質量的軟體。程序人人都會寫，但當你發現寫到一定程度很難再提高的時候，就應該想想是不是要回過頭來學學這些最基本的理論。不要一開始就去學OOP，即使你再精通OOP，遇到一些基本演算法的時候可能也會束手無策。

2. 豐富的想像力。不要拘泥於固定的思維方式，遇到問題的時候要多想幾種解決問題的方案，試試別人從沒想過的方法。豐富的想像力是建立在豐富的知識的基礎上，除計算機以外，多涉獵其他的學科，比如天文、物理、數學等等。另外，多看科幻電影也是一個很好的途徑。

3. 最簡單的是最好的。這也許是所有科學都遵循的一條准則，如此復雜的質能互換原理在愛因斯坦眼裡不過是一個簡單得不能再簡單的公式：E=mc2。簡單的方法更容易被人理解，更容易實現，也更容易維護。遇到問題時要優先考慮最簡單的方案，只有簡單方案不能滿足要求時再考慮復雜的方案。

4. 不鑽牛角尖。當你遇到障礙的時候，不妨暫時遠離電腦，看看窗外的風景，聽聽輕音樂，和朋友聊聊天。當我遇到難題的時候會去玩游戲，而且是那種極暴力的打鬥類游戲，當負責游戲的那部分大腦細胞極度亢奮的時候，負責編程的那部分大腦細胞就得到了充分的休息。當重新開始工作的時候，我會發現那些難題現在竟然可以迎刃而解。

5. 對答案的渴求。人類自然科學的發展史就是一個渴求得到答案的過程，即使只能知道答案的一小部分也值得我們去付出。只要你堅定信念，一定要找到問題的答案，你才會付出精力去探索，即使最後沒有得到答案，在過程中你也會學到很多東西。

6. 多與別人交流。三人行必有我師，也許在一次和別人不經意的談話中，就可以迸出靈感的火花。多上上網，看看別人對同一問題的看法，會給你很大的啟發。

7. 良好的編程風格。注意養成良好的習慣，代碼的縮進編排，變數的命名規則要始終保持一致。大家都知道如何排除代碼中錯誤，卻往往忽視了對注釋的排錯。注釋是程序的一個重要組成部分，它可以使你的代碼更容易理解，而如果代碼已經清楚地表達了你的思想，就不必再加註釋了，如果注釋和代碼不一致，那就更加糟糕。

8. 韌性和毅力。這也許是"高手"和一般程序員最大的區別。A good programming is 99 weat and 1 ffee。高手們並不是天才，他們是在無數個日日夜夜中磨練出來的。成功能給我們帶來無比的喜悅，但過程卻是無比的枯燥乏味。你不妨做個測試，找個10000以內的素數表，把它們全都抄下來，然後再檢查三遍，如果能夠不間斷地完成這一工作，你就可以滿足這一條。

希望對你有幫助

C. 咨詢一個最簡單的PSO演算法的程序

%------基本粒子群優化演算法（Particle Swarm Optimization）-----------
%------作用：求解優化問題
%------初始格式化----------
format long;
c1=1.4962; %學習因子1
c2=1.4962; %學習因子2
w=0.7298; %慣性權重
MaxDT=1000; %最大迭代次數
D=10; %搜索空間維數（未知數個數）
N=40; %初始化群體個體數目
eps=10^(-6); %設置精度(在已知最小值時候用)
%------初始化種群的個體(可以在這里限定位置和速度的范圍)------------
for i=1:N
for j=1:D
x(i,j)=randn; %隨機初始化位置
v(i,j)=randn; %隨機初始化速度
end
end
%------先計算各個粒子的適應度，並初始化Pi和Pg----------------------
for i=1:N
p(i)=fitness(x(i,:),D);
y(i,:)=x(i,:);
end
pg=x(1,:); %Pg為全局最優
for i=2:N
if fitness(x(i,:),D)
pg=x(i,:);
end
end
%------進入主要循環，按照公式依次迭代，直到滿足精度要求------------
for t=1:MaxDT
for i=1:N
v(i,:)=w*v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(pg-x(i,:));
x(i,:)=x(i,:)+v(i,:);
if fitness(x(i,:),D)<p(i)
p(i)=fitness(x(i,:),D);
y(i,:)=x(i,:);
end
if p(i)
pg=y(i,:);
end
end
Pbest(t)=fitness(pg,D);
end
%------最後給出計算結果
disp('*************************************************************')
disp('函數的全局最優位置為：')
Solution=pg
disp('最後得到的優化極值為：')
Result=fitness(pg,D)
disp('*************************************************************')
%------演算法結束---

如果想要適應度函數源程序（fitness.m），可以再聯系

D. 簡單演算法的概念，並舉例說明它在程序中的作用。

1 什麼叫演算法
演算法（Algorithm）是解題的步驟，可以把演算法定義成解一確定類問題的任意一種特殊的方法。在計算機科學中，演算法要用計算機演算法語言描述，演算法代表用計算機解一類問題的精確、有效的方法。演算法+數據結構=程序，求解一個給定的可計算或可解的問題，不同的人可以編寫出不同的程序，來解決同一個問題，這里存在兩個問題：一是與計算方法密切相關的演算法問題；二是程序設計的技術問題。演算法和程序之間存在密切的關系。
演算法是一組有窮的規則，它們規定了解決某一特定類型問題的一系列運算，是對解題方案的准確與完整的描述。制定一個演算法，一般要經過設計、確認、分析、編碼、測試、調試、計時等階段。
對演算法的學習包括五個方面的內容：① 設計演算法。演算法設計工作是不可能完全自動化的，應學習了解已經被實踐證明是有用的一些基本的演算法設計方法，這些基本的設計方法不僅適用於計算機科學，而且適用於電氣工程、運籌學等領域；② 表示演算法。描述演算法的方法有多種形式，例如自然語言和演算法語言，各自有適用的環境和特點；③確認演算法。演算法確認的目的是使人們確信這一演算法能夠正確無誤地工作，即該演算法具有可計算性。正確的演算法用計算機演算法語言描述，構成計算機程序，計算機程序在計算機上運行，得到演算法運算的結果；④ 分析演算法。演算法分析是對一個演算法需要多少計算時間和存儲空間作定量的分析。分析演算法可以預測這一演算法適合在什麼樣的環境中有效地運行，對解決同一問題的不同演算法的有效性作出比較；⑤ 驗證演算法。用計算機語言描述的演算法是否可計算、有效合理，須對程序進行測試，測試程序的工作由調試和作時空分布圖組成。

2、演算法的特性

演算法的特性包括：① 確定性。演算法的每一種運算必須有確定的意義，該種運算應執行何種動作應無二義性，目的明確；② 能行性。要求演算法中有待實現的運算都是基本的，每種運算至少在原理上能由人用紙和筆在有限的時間內完成；③ 輸入。一個演算法有0個或多個輸入，在演算法運算開始之前給出演算法所需數據的初值，這些輸入取自特定的對象集合；④ 輸出。作為演算法運算的結果，一個演算法產生一個或多個輸出，輸出是同輸入有某種特定關系的量；⑤ 有窮性。一個演算法總是在執行了有窮步的運算後終止，即該演算法是可達的。
滿足前四個特性的一組規則不能稱為演算法，只能稱為計算過程，操作系統是計算過程的一個例子，操作系統用來管理計算機資源，控製作業的運行，沒有作業運行時，計算過程並不停止，而是處於等待狀態。

3、演算法的描述

演算法的描述方法可以歸納為以下幾種：
(1) 自然語言；
(2) 圖形，如N�S圖、流程圖，圖的描述與演算法語言的描述對應；
(3) 演算法語言，即計算機語言、程序設計語言、偽代碼；
(4) 形式語言，用數學的方法，可以避免自然語言的二義性。
用各種演算法描述方法所描述的同一演算法，該演算法的功用是一樣的，允許在演算法的描述和實現方法上有所不同。
人們的生產活動和日常生活離不開演算法，都在自覺不自覺地使用演算法，例如人們到商店購買物品，會首先確定購買哪些物品，准備好所需的錢，然後確定到哪些商場選購、怎樣去商場、行走的路線，若物品的質量好如何處理，對物品不滿意又怎樣處理，購買物品後做什麼等。以上購物的演算法是用自然語言描述的，也可以用其他描述方法描述該演算法。

E. 用c語言寫一個簡單的程序，就是在鍵盤上輸入10個數，然後求平均數

代碼如下：

#include<stdio.h>


intmain(void)
{
inta[10],sum=0;
for(inti=0;i<10;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
printf("%f",sum/10.);

return0;
}

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

演算法一：快速排序演算法
快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序 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）是一種在數學、計算機科學和經濟學中使用的，通過把原問題分解為相對簡單的子問題的方式求解復雜問題的方法。 動態規劃常常適用於有重疊子問題和最優子結構性質的問題，動態規劃方法所耗時間往往遠少於樸素解法。

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

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

演算法步驟：

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

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

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

G. 用C語言編寫一段簡單的程序，作業調度和低級調度演算法

真不容易啊，怕是沒人弄了!
優先順序調度演算法程序:
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef struct node
{
char name[10]; /*進程標識符*/
int prio; /*進程優先數*/
int round; /*進程時間輪轉時間片*/
int cputime; /*進程佔用CPU時間*/
int needtime; /*進程到完成還要的時間*/
int count; /*計數器*/
char state; /*進程的狀態*/
struct node *next; /*鏈指針*/
}PCB;
PCB *finish,*ready,*tail,*run; /*隊列指針*/
int N; /*進程數*/
/*將就緒隊列中的第一個進程投入運行*/
firstin()
{
run=ready; /*就緒隊列頭指針賦值給運行頭指針*/
run->state='R'; /*進程狀態變為運行態*/
ready=ready->next; /*就緒對列頭指針後移到下一進程*/
}
/*標題輸出函數*/
void prt1(char a)
{
if(toupper(a)=='P') /*優先數法*/
printf(" name cputime needtime priority state\n");
else
printf(" name cputime needtime count round state\n");
}
/*進程PCB輸出*/
void prt2(char a,PCB *q)
{
if(toupper(a)=='P') /*優先數法的輸出*/
printf(" %-10s%-10d%-10d%-10d %c\n",q->name,
q->cputime,q->needtime,q->prio,q->state);
else/*輪轉法的輸出*/
printf(" %-10s%-10d%-10d%-10d%-10d %-c\n",q->name,
q->cputime,q->needtime,q->count,q->round,q->state);
}
/*輸出函數*/
void prt(char algo)
{
PCB *p;
prt1(algo); /*輸出標題*/
if(run!=NULL) /*如果運行指針不空*/
prt2(algo,run); /*輸出當前正在運行的PCB*/
p=ready; /*輸出就緒隊列PCB*/
while(p!=NULL)
{
prt2(algo,p);
p=p->next;
}
p=finish; /*輸出完成隊列的PCB*/
while(p!=NULL)
{
prt2(algo,p);
p=p->next;
}
getch(); /*壓任意鍵繼續*/
}
/*優先數的插入演算法*/
insert1(PCB *q)
{
PCB *p1,*s,*r;
int b;
s=q; /*待插入的PCB指針*/
p1=ready; /*就緒隊列頭指針*/
r=p1; /*r做p1的前驅指針*/
b=1;
while((p1!=NULL)&&b) /*根據優先數確定插入位置*/
if(p1->prio>=s->prio)
{
r=p1;
p1=p1->next;
}
else
b=0;
if(r!=p1) /*如果條件成立說明插入在r與p1之間*/
{
r->next=s;
s->next=p1;
}
else
{
s->next=p1; /*否則插入在就緒隊列的頭*/
ready=s;
}
}
/*輪轉法插入函數*/
insert2(PCB *p2)
{
tail->next=p2; /*將新的PCB插入在當前就緒隊列的尾*/
tail=p2;
p2->next=NULL;
}
/*優先數創建初始PCB信息*/
void create1(char alg)
{
PCB *p;
int i,time;
char na[10];
ready=NULL; /*就緒隊列頭指針*/
finish=NULL; /*完成隊列頭指針*/
run=NULL; /*運行隊列指針*/
printf("Enter name and time of process\n"); /*輸入進程標識和所需時間創建PCB*/
for(i=1;i<=N;i++)
{
p=malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
p->state='w';
p->prio=50-time;
if(ready!=NULL) /*就緒隊列不空調用插入函數插入*/
insert1(p);
else
{
p->next=ready; /*創建就緒隊列的第一個PCB*/
ready=p;
}
}
clrscr();
printf(" output of priority:\n");
printf("************************************************\n");
prt(alg); /*輸出進程PCB信息*/
run=ready; /*將就緒隊列的第一個進程投入運行*/
ready=ready->next;
run->state='R';
}
/*輪轉法創建進程PCB*/
void create2(char alg)
{
PCB *p;
int i,time;
char na[10];
ready=NULL;
finish=NULL;
run=NULL;
printf("Enter name and time of round process\n");
for(i=1;i<=N;i++)
{
p=malloc(sizeof(PCB));
scanf("%s",na);
scanf("%d",&time);
strcpy(p->name,na);
p->cputime=0;
p->needtime=time;
p->count=0; /*計數器*/
p->state='w';
p->round=2; /*時間片*/
if(ready!=NULL)
insert2(p);
else
{
p->next=ready;
ready=p;
tail=p;
}
}
clrscr();
printf(" output of round\n");
printf("************************************************\n");
prt(alg); /*輸出進程PCB信息*/
run=ready; /*將就緒隊列的第一個進程投入運行*/
ready=ready->next;
run->state='R';
}
/*優先數調度演算法*/
priority(char alg)
{
while(run!=NULL) /*當運行隊列不空時，有進程正在運行*/
{
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
run->prio=run->prio-3; /*每運行一次優先數降低3個單位*/
if(run->needtime==0) /*如所需時間為0將其插入完成隊列*/
{
run->next=finish;
finish=run;
run->state='F'; /*置狀態為完成態*/
run=NULL; /*運行隊列頭指針為空*/
if(ready!=NULL) /*如就緒隊列不空*/
firstin(); /*將就緒對列的第一個進程投入運行*/
}
else /*沒有運行完同時優先數不是最大，則將其變為就緒態插入到就緒隊列*/
if((ready!=NULL)&&(run->prio<ready->prio))
{
run->state='W';
insert1(run);
firstin(); /*將就緒隊列的第一個進程投入運行*/
}
prt(alg); /*輸出進程PCB信息*/
}
}
/*時間片輪轉法*/
roundrun(char alg)
{
while(run!=NULL)
{
run->cputime=run->cputime+1;
run->needtime=run->needtime-1;
run->count=run->count+1;
if(run->needtime==0)/*運行完將其變為完成態，插入完成隊列*/
{
run->next=finish;
finish=run;
run->state='F';
run=NULL;
if(ready!=NULL)
firstin(); /*就緒對列不空，將第一個進程投入運行*/
}
else
if(run->count==run->round) /*如果時間片到*/
{
run->count=0; /*計數器置0*/
if(ready!=NULL) /*如就緒隊列不空*/
{
run->state='W'; /*將進程插入到就緒隊列中等待輪轉*/
insert2(run);
firstin(); /*將就緒對列的第一個進程投入運行*/
}
}
prt(alg); /*輸出進程信息*/
}
}
/*主函數*/
main()
{
char algo; /*演算法標記*/
clrscr();
printf("type the algorithm:P/R(priority/roundrobin)\n");
scanf("%c",&algo); /*輸入字元確定演算法*/
printf("Enter process number\n");
scanf("%d",&N); /*輸入進程數*/
if(algo=='P'||algo=='p')
{
create1(algo); /*優先數法*/
priority(algo);
}
else
if(algo=='R'||algo=='r')
{
create2(algo); /*輪轉法*/
roundrun(algo);
}
}

H. 程序員必須掌握哪些演算法

一.基本演算法:

枚舉. (poj1753,poj2965)

貪心(poj1328,poj2109,poj2586)

遞歸和分治法.

遞推.

構造法.(poj3295)

模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.圖演算法:

圖的深度優先遍歷和廣度優先遍歷.

最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓撲排序 (poj1094)

二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)

最大流的增廣路演算法(KM演算法). (poj1459,poj3436)

三.數據結構.

串 (poj1035,poj3080,poj1936)

排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)

簡單並查集的應用.

哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼樹(poj3253)

堆

trie樹(靜態建樹、動態建樹) (poj2513)

四.簡單搜索

深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.動態規劃

背包問題. (poj1837,poj1276)

型如下表的簡單DP(可參考lrj的書 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學

組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.

幾何公式.

叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)

多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)

中級（校賽壓軸及省賽中等難度）:
一.基本演算法:

C++的標准模版庫的應用. (poj3096,poj3007)

較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)

二.圖演算法:

差分約束系統的建立和求解. (poj1201,poj2983)

最小費用最大流(poj2516,poj2516,poj2195)

雙連通分量(poj2942)

強連通分支及其縮點.(poj2186)

圖的割邊和割點(poj3352)

最小割模型、網路流規約(poj3308)

三.數據結構.

線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)

靜態二叉檢索樹. (poj2482,poj2352)

樹狀樹組(poj1195,poj3321)

RMQ. (poj3264,poj3368)

並查集的高級應用. (poj1703,2492)

KMP演算法. (poj1961,poj2406)

四.搜索

最優化剪枝和可行性剪枝

搜索的技巧和優化 (poj3411,poj1724)

記憶化搜索(poj3373,poj1691)

五.動態規劃

較為復雜的動態規劃(如動態規劃解特別的旅行商TSP問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)

樹型動態規劃(poj2057,poj1947,poj2486,poj3140)

六.數學

組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.
數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩餘定理) (poj3101)
計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
隨機化演算法(poj3318,poj2454)
雜題(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.

坐標離散化.

掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多邊形的內核(半平面交)(poj3130,poj3335)

幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高級（regional中等難度）:
一.基本演算法要求:

代碼快速寫成,精簡但不失風格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

保證正確性和高效性. poj3434

二.圖演算法:

度限制最小生成樹和第K最短路. (poj1639)

最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最優比率生成樹. (poj2728)

最小樹形圖(poj3164)

次小生成樹.

無向圖、有向圖的最小環

三.數據結構.

trie圖的建立和應用. (poj2778)

LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 在線演算法(RMQ+dfs)).(poj1330)
雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的目的). (poj2823)
左偏樹(可合並堆).

後綴樹(非常有用的數據結構,也是賽區考題的熱點).(poj3415,poj3294)
四.搜索

較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*演算法. (poj3131,poj2870,poj2286)

五.動態規劃

需要用數據結構優化的動態規劃.(poj2754,poj3378,poj3017)
四邊形不等式理論.

較難的狀態DP(poj3133)

六.數學

組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.

半平面求交(poj3384,poj2540)

可視圖的建立(poj2966)

點集最小圓覆蓋.

對踵點(poj2079)