關鍵路徑演算法c
① pmp如何計算關鍵路徑
pmp計算關鍵路徑的方法如下：
關鍵路徑法（Critical Path Method）是一種用來預測總體項目歷時的項目源網路分析技術。所謂「關鍵路徑」，是指當我們完成了項目進計劃後，在項目的網路圖上，存在著若干條從項目啟動到項目結束之間的路徑，但是對其中一條（嚴格的來說，可能存在一條以上）路徑上來說。
所謂正推法就是從項目的第一個活動到最後一個活動跟蹤全部活動的先後關系，計知算出每個活動的最早開始時間（ES）和最早結束時間（EF）。
所謂倒道推法則是從最後一個活動開始向前追溯到第一個活動，計算出每個活動的最晚開始時間（LS）和最晚結束時間（LF）。
PMP作為項目管理資格認證考試，已在國際上樹立了其權威性：
1、PMP為美國培養了一大批項目管理專業人才，項目管理職業已成為美國的「黃金職業」。在中國許多媒體已把PMP稱為繼MBA，MPA之後的三大金字招牌之一；
2、PMP認證已成為了一個國際性的認證標准，用英語、德語、法語、日語、韓語、西班牙語、葡萄牙語和中文等九種語言進行認證考試；
3、到目前為止，全球有80多萬名PMP，中國大陸地區獲得「PMP」頭銜的已有18萬多人，並逐年增長；
4、各國紛紛效仿美國的項目管理認證制度，推動了世界項目管理的發展。
② 什麼是關鍵路徑
在項目管理中，關鍵路徑是指網路終端元素的元素的序列，該序列具有最長的總工期並決定了整個項目的最短完成時間。
求關鍵路徑的演算法分析
（1） 求關鍵路徑必須在拓撲排序的前提下進行，有環圖不能求關鍵路徑； （2） 只有縮短關鍵活動的工期才有可能縮短工期； （3） 若一個關鍵活動不在所有的關鍵路徑上，減少它並不能減少工期； （4） 只有在不改變關鍵路徑的前提下，縮短關鍵活動才能縮短整個工期。
探尋關鍵路徑
AOE網
用頂點表示事件，弧表示活動，弧上的權值表示活動持續的時間的有向圖叫AOE（Activity On Edge Network）網 。AOE網常用於估算工程完成時間。例如： 圖1
圖1 是一個網。其中有9個事件v1，v2，…，v9；11項活動a1，a2，…，a11。每個事件表示在它之前的活動已經完成，在它之後的活動可以開始。如 v1表示整個工程開始，v9 表示整個工程結束。V5表示活動，a4和a5已經完成，活動a7和a8可以開始。與每個活動相聯系的權表示完成該活動所需的時間。如活動a1需要6天時間可以完成。
AOE 網具有的性質
只有在某頂點所代表的事件發生後，從該頂點出發的各有向邊所代表的活動才能開始。 只有在進入某一頂點的各有向邊所代表的活動都已經結束，該頂點所代表的事件才能發生。 表示實際工程計劃的AOE網應該是無環的，並且存在唯一的入度過為0的開始頂點和唯一的出度為0的完成頂點。 2)
最早發生時間和最晚發生時間的定義
可以採取如下步驟求得關鍵活動： A、從開始頂點 v 1 出發 , 令 ve(1)=0, 按拓樸有序序列求其餘各頂點的可能最早發生時間。 Ve(k)=max{ve(j) t(<j,k>)} （ 1.1 ） j ∈ T 其中T是以頂點vk為尾的所有弧的頭頂點的集合(2 ≤ k ≤ n) 。 如果得到的拓樸有序序列中頂點的個數小於網中頂點個數n，則說明網中有環，不能求出關鍵路徑，演算法結束。 表1
B、從完成頂點 v n 出發，令vl(n)=ve(n)，按逆拓樸有序求其餘各頂點的允許的最晚發生時間: vl(j)=min{vl(k)-t(<j,k>)} k ∈ S 其中 S 是以頂點vj是頭的所有弧的尾頂點集合(1 ≤ j ≤ n-1) 。 C、求每一項活動ai(1 ≤ i ≤ m)的最早開始時間e(i)=ve(j)；最晚開始時間： l(i)=vl(k)-t(<j,k>) 若某條弧滿足 e(i)=l(i) ，則它是關鍵活動。 對於圖1所示的 AOE 網，按以上步驟的計算結果見表1，可得到a1 , a4 , a7 , a8 , a10 , a11 是關鍵活動。
AOE 網的關鍵路徑
圖2
這時從開始頂點到達完成頂點的所有路徑都是關鍵路徑。一個AOE網的關鍵路徑可以不止一條，如圖7.21的AOE網中有二條關鍵路徑，(v1, v2, v5, v7 , v9 ) 和 (v1 , v2 , v5 , v8 , v9 )它們的路徑長度都是16 。如圖2所示：
AOE網研究的問題
（1） 完成整個工程至少需要多少時間； （2） 哪些活動是影響工程的關鍵。 1956年，美國杜邦公司提出關鍵路徑法，並於1957年首先用於1000萬美元化工廠建設，工期比原計劃縮短了4個月。杜邦公司在採用關鍵路徑法的一年中，節省了100萬美元。
關鍵路徑的幾個術語
（1） 關鍵路徑 從源點到匯點的路徑長度最長的路徑叫關鍵路徑。 （2） 活動開始的最早時間e(i) （3） 活動開始的最晚時間l(i) 定義e(i)=l(i)的活動叫關鍵活動。 （4） 事件開始的最早時間ve(i) （5） 事件開始的最晚時間vl(i) 設活動ai由弧<j,k>(即從頂點j到k)表示，其持續時間記為t(<j,k>),則 e(i)=ve(j) l(i)=vl(k)-t(<j,k>) (6_6_1) 求ve(i)和vl(j)分兩步： · 從ve(1)=0開始向前遞推 ve(j)=Max{ ve(i)+t(<i,j>) } (6_6_2) <i,j>T, 2<=j<=n 其中，T是所有以j為弧頭的弧的集合。 · 從vl(n)=ve(n)開始向後遞推 vl(i)=Min{ vl(j)-t(<i,j>) } (6_6_3) <i,j>S, 1<=i<=n-1 其中，S是所有以i為弧尾的弧的集合。 兩個遞推公式是在拓撲有序和逆拓撲有序的前提下進行。 4、 求關鍵路徑的演算法 (1) 輸入e條弧<j,k>，建立AOE網的存儲結構。 (2) 從源點v1出發，令ve(1)=0,求 ve(j) 2<=j<=n。 (3) 從匯點vn出發，令vl(n)=ve(n),求 vl(i) 1<=i<=n-1。 (4) 根據各頂點的ve和vl值，求每條弧s（活動）的最早開始時間e(s)和最晚開始時間l(s)，其中e(s)=l(s)的為關鍵活動。 求關鍵路徑是在拓撲排序的前提下進行的，不能進行拓撲排序，自然也不能求關鍵路徑。 Status ToplogicalSort(ALGraph G,stack &T){ FindInDegree(G,indegree); InitStack(S);count=0; ve[0..G.vexnum-1]=0; while(!StackEmpty(S)) { Pop(S,j);Push(T,j); ++count; for(p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p>adjvex; if(--indegree[k]==0) Push(S,k); if(ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info); } } if(count<G.vexnum) return ERROR; else return OK; } status CriticalPath(ALGraph G){ if(!ToplogicalOrder(G,T)) return ERROR; vl[0..G.vexnum-1]=ve[0..G.vexnum-1]; while(!StackEmpty(T)) for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p>adjvex; t=*(p->info); if(vl[k]-t<vl[j]) vl[j]=vl[k]-t; } for(j=0;j<G.vexnum;++j) for(p=G.vertices[j].firstarc;p;p=p->nextarc) {k=p>adjvex; t=*(p->info); ee=ve[j]; el=vl[k]; tag=(ee==el)?』*』:』』; printf(j,kt,ee,el,tag); } }
③ 給一些程序填空題,PASCAL的
真想要？要有耐心看下去的。。。。
自己挑些題做吧。
2006：
1．（選排列）下面程序的功能是利用遞歸方法生成從 1 到 n(n<10)的 n 個數中取 k(1<=k<=n)個數的 全部可能的排列（不一定按升序輸出）。例如，當 n=3，k=2 時，應該輸出（每行輸出 5 個排列）：
12 13 21 23 32
31
程序：
Program ex501; Var i,n,k:integer;
a:array[1..10] of integer;
count:longint;
Procere perm2(j:integer);
var i,p,t:integer;
begin
if ① then
begin
for i:=k to n do begin inc(count);
t:=a[k]; a[k]:=a[i]; a[i]:=t;
for ② do write(a[p]:1);
write(' ');
t:=a[k];a[k]:=a[i];a[i]:=t;
if (count mod 5=0) then writeln;
end; exit; end;
for i:=j to n do begin
t:=a[j];a[j]:=a[i];a[i]:=t;由OIFans.cn收集
③ ;
t:=a[j]; ④ ;
end end; begin
writeln('Entry n,k (k<=n):'); read(n,k);
count:=0;
for i:=1 to n do a[i]:=i;
⑤ ;
end.
2．（TSP 問題的交叉運算元）TSP 問題(Traveling Salesman Problem)描述如下：給定 n 個城 市，構成一個完全圖，任何兩城市之間都有一個代價（例如路程、旅費等），現要構造遍歷所有城市的環 路，每個城市恰好經過一次，求使總代價達到最小的一條環路。
遺傳演算法是求解該問題的一個很有效的近似演算法。在該演算法中，一個個體為一條環路，其編碼方法 之一是 1 到 n 這 n 個數字的一個排列，每個數字為一個城市的編號。例如當 n=5 時，「3 4 2 1 5」 表示該方案實施的路線為 3->4->2->1->5->3。遺傳演算法的核心是通過兩個個體的交叉操作，產生兩 個新的個體。下面的程序給出了最簡單的一種交叉演算法。具體過程如下：
(1)選定中間一段作為互換段，該段的起止下標為 t1，t2，隨機生成 t1，t2 後，互換兩段。
(2)互換後，在每個新的排列中可能有重復數字，因而不能作為新個體的編碼，一般再做兩步處理：
(2.1) 將兩個互換段中，共同的數字標記為 0，表示已處理完。
(2.2) 將兩個互換段中其餘數字標記為 1，按順序將互換段外重復的數字進行替換。 例如：n=12，兩個個體分別是：
a1: 1 3 5 4 * 2 6 7 9 * 10 12 8 11
a2: 3 2 1 12 * 6 7 10 11 * 8 5 4 9
t1=5，t2=8。上述每一行中，兩個星號間的部分為互換段。假定數組的下標從 1 開始，互換後有：
a1: 1 3 5 4 * 6 7 10 11 * 10 12 8 11
a2: 3 2 1 12 * 2 6 7 9 * 8 5 4 9
然後，將數字 6,7 對應的項標記為 0，星號內數字 2,9,10,11 對應的項標記為 1，並且按順序對 應關系為:10<->2，11<->9。於是，將 a1[9]=10 替換為 a1[9]=2，將 a2[2]=2 替換為 a2[2]=10， 類似再做第 2 組替換。這樣處理後，就得到了兩個新個體：
a1: 1 3 5 4 6 7 10 11 2 12 8 9
a2: 3 10 1 12 2 6 7 9 8 5 4 11
（3）輸出兩個新個體的編碼。 程序：
program ex502;
type arr1=array[1..20] of integer;
var a1,a2,kz1,kz2:arr1; n,k,t1,t2:integer;
function rand1(k:integer):integer;
var t:integer;
begin t:=0;
while (t<2) or(t>k) do t:=random(k+1)-2; rand1:=t;
end;
procere read1(var a:arr1;m:integer);
{讀入數組元素 a[1]至 a[m]，a[0]=0，略。}
procere wrt1(var a:arr1;m:integer);
{輸出數組元素 a[1]至 a[m]，略。}
procere cross(var a1,a2:arr1;t1, t2,n:integer);由OIFans.cn收集
var i,j,t,kj:integer; begin
for i:=t1 to t2 do begin
t:=a1[i]; ① ;
end;
for i:=1 to n do
if (i<t1)or(i>t2) then begin
kz1[i]:=-1;kz2[i]:=-1;
end else
begin ② ; end;
for i:=t1 to t2 do for j:=t1 to t2 do
if(a1[i]=a2[j]) then
begin ③ ; break; end;
for i:=t1 to t2 do if(kz1[i]=1) then begin
for j:=t1 to t2 do if(kz2[j]=1) then
begin kj:=j; break; end;
for j:=1 to n do if ④ then
begin a1[j]:=a2[kj];break; end;
for j:=1 to n do if ⑤ then
begin a2[j]:=a1[i]; break; end;
kz1[i]:=0;kz2[kj]:=0;
end; end; begin
writeln('input (n>5):');
readln(n);
writeln('input array 1:'); read1(a1,n);
writeln('input array 2:'); read1(a2,n);
t1:=rand1(n-1);
repeat
t2:=rand1(n-1); until(t1<>t2); if(t1>t2) then
begin k:=t1; t1:=t2; t2:=k; end;
⑥ ;
wrt1(a1,n); wrt1(a2,n);
end.
2005：
1．木材加工
題目描述:
木材廠有一些原木，現在想把這些木頭切割成一些長度相同的小段木頭（木頭有可能有
剩餘），需要得到的小段的數目是給定的。當然，我們希望得到的小段越長越好，你的任務
是計算能夠得到的小段木頭的最大長度。
木頭長度的單位是cm。原木的長度都是正整數，我們要求切割得到的小段木頭的長度
也是正整數。
輸入:
第一行是兩個正整數N和K(1 ≤ N ≤ 10000，1 ≤ K ≤ 10000)，N是原木的數目，
K是需要得到的小段的數目。
接下來的N行，每行有一個1到10000之間的正整數，表示一根原木的長度。
輸出:
輸出能夠切割得到的小段的最大長度。如果連1cm長的小段都切不出來，輸出」0」。
輸入樣例:
3 7
232
124
456
輸出樣例:
114
程序：
var
n, k : integer;
len : array [1..10000] of integer;
i, left, right, mid : integer;
function isok(t : integer) : boolean;
var
num, i : integer;
begin
num := 0;
for i := 1 to n do begin
if num >= k then break;
num := ① ;
end;
if ② then isok := true
else isok := false;
end;
begin
readln(n, k);
right := 0;
for i := 1 to n do begin
readln(len[i]);
if right < len[i] then right := len[i];
end;
inc(right);
③ ;
while ④ < right do begin
mid := (left + right) div 2;
if ⑤ then right := mid
else left := mid;
end;
writeln(left);
end.
2．N叉樹
題目描述:
我們都了解二叉樹的先根遍歷，中根遍歷和後根遍歷。當知道先根遍歷的結果和中根遍
歷結果的時候，我們可以唯一的確定二叉樹；同樣的，如果知道了後根遍歷的結果和中根遍
歷結果，二叉樹也是唯一確定的。但是如果只知道先根遍歷和後根遍歷的結果，二叉樹就不
是唯一的了。但是我們可以計算滿足條件的不同二叉樹一共有多少個。這不是一個很困難的
問題，稍微復雜一點，我們把這個問題推廣到N叉樹。
我們用小寫英文字母來表示N 叉樹的結點，不同的結點用不同的字母表示。比如，對
於4叉樹，如果先根遍歷的結果是abdefgc，後根遍歷的結果是defgbca，那麼我們可以
得到6個不同的4叉樹（如下圖）。
輸入:
輸入數據包括3行。
第一行是一個正整數N(2 ≤ N ≤ 20)，表示我們要考慮N叉樹。
第二行和第三行分別是兩個字元串序列，分別表示先根遍歷和後根遍歷的結果。
輸出:
輸出不同的N叉樹的數目。題目中給的數據保證得到的結果小於2
31
。
輸入樣例:
4
abdefgc
defgbca
輸出樣例:
6
程序：
var
str1, str2 : string;
N, len : integer;
com : array[0..100, 0..100] of longint;
function getcom(x, y : integer) : longint;
begin
if (y = 0) or (x = y) then ①
else if com[x][y] <> 0 then getcom := com[x][y]
else begin
com[x][y] := getcom(x - 1, y)+ ② ;
getcom := com[x][y];
end;
end;
function count(a, b, c : integer) : longint;
var
sum : longint;
k, s, t, p : integer;
begin
sum := 1; k := 0; s := a + 1; t := c;
if a = b then count := 1
else begin
while s <= b do begin
p := t;
while str1[s] <> str2[t] do inc(t);
sum := sum * count(s, s + t - p, p);
s := ③ ;
④ ; inc(k);
end;
count := ⑤ * getcom(N, k);
end;
end;
begin
readln(N); readln(str1); readln(str2);
len := length(str1);
writeln(count( ⑥ ));
end.
2004：
1．Joseph
題目描述:
原始的Joseph問題的描述如下：有n個人圍坐在一個圓桌周圍，把這n個人依次編號為1，…，n。從編號是1的人開始報數，數到第m個人出列，然後從出列的下一個人重新開始報數，數到第m個人又出列，…，如此反復直到所有的人全部出列為止。比如當n=6，m=5的時候，出列的順序依次是5，4，6，2，3，1。
現在的問題是：假設有k個好人和k個壞人。好人的編號的1到k，壞人的編號是k+1到2k。我們希望求出m的最小值，使得最先出列的k個人都是壞人。
輸入:
僅有的一個數字是k（0 < k <14）。
輸出:
使得最先出列的k個人都是壞人的m的最小值。
輸入樣例:
4
輸出樣例:
30
程序：
program program1;
var
i, k, m, start: longint;
find: boolean;
function check(remain: integer): boolean;
var result: integer;
begin
result:=( ① ) mod remain;
if( ② )then begin
start := result; check := true;
end
else check := false;
end;
begin
find := false;
read(k);
m := k;
while ( ③ ) do begin
find := true; start := 0;
for i := 0 to k-1 do
if( not check( ④ )) then begin
find := false; break;
end;
inc(m);
end;
writeln( ⑤ );
end.
2．邏輯游戲
題目描述:
一個同學給了我一個邏輯游戲。他給了我圖1，在這個圖上，每一段邊界都已經進行了編號。我的任務是在圖中畫一條連續的曲線，使得這條曲線穿過每一個邊界一次且僅穿過一次，而且曲線的起點和終點都在這整個區域的外面。這條曲線是容許自交的。
對於圖1，我的同學告訴我畫出這樣的一條曲線（圖2）是不可能的，但是對於有的圖形（比如圖3），畫出這樣一條曲線是可行的。對於給定的一個圖，我想知道是否可以畫出滿足要求的曲線。
圖1 圖2
圖3 圖4
輸入:
輸入的圖形用一個n×n的矩陣表示的。矩陣的每一個單元里有一個0到255之間（包括0和255）的整數。處於同一個區域的單元里的數相同，相鄰區域的數不同（但是不相鄰的區域里的數可能相同）。
輸入的第一行是n（0<n<100）。以下的n行每行包括n個整數，分別給出對應的單元里的整數（這n個整數之間用空格分開）。圖4給出了輸入樣例對應的圖形。
輸出:
當可以畫出滿足題意的曲線的時候，輸出「YES」；否則，輸出「NO」。
輸入樣例:
3
1 1 2
1 2 2
1 1 2
輸出樣例:
YES
程序：
program program2;
const
d: array[0..7] of integer = (1, 0, -1, 0, 0, 1, ① );
var
orig, n, i, j, ns: integer;
a: array[0..101, 0..101] of integer;
bun: boolean;
procere plimba(x, y: integer);
var i, x1, y1: integer;
begin
a[x, y] := -a[x, y];
if (abs(a[x - 1, y]) <> orig) and (( ② <> a[x - 1, y])
or (abs(a[x, y - 1]) <> orig)) then inc(ns);
if (abs(a[x + 1, y]) <> orig) and ((a[x + 1, y - 1] <> a[x + 1,y])
or (abs(a[x, y - 1]) <> orig)) then inc(ns);
if (abs(a[x, y - 1]) <> orig) and (( ③ <> a[x, y - 1])
or (abs(a[x - 1, y]) <> orig)) then inc(ns);
if (abs(a[x, y + 1]) <> orig) and ((a[x - 1, y + 1] <> a[x,y + 1])
or (abs(a[x - 1, y]) <> orig)) then inc(ns);
for i := 0 to 3 do begin
x1 := x + d[2 * i];y1:=y+ ④ ;
if (x1 >= 1) and (x1 <= n) and (y1 >= 1) and (y1 <= n) and
( ⑤ ) then plimba(x1, y1);
end;
end;
begin
bun := true;
read(n);
for i := 0 to n+1 do
for j := 0 to n+1 do a[i, j] := 0;
a[0, 0] := -1; a[n + 1, 0] := -1;
a[0, n + 1] := -1; a[n + 1, n + 1] := -1;
for i := 1 to n do
for j := 1 to n do read(a[i, j]);
for i := 1 to n do
for j := 1 to n do
if a[i, j] > -1 then begin
ns := 0; ⑥ ;
plimba(i, j);
if ns mod 2 = 1 then bun := false;
end;
if bun then writeln('YES');
if not bun then writeln('NO');
end.
2003：
1. 翻硬幣
題目描述：
一摞硬幣共有m枚，每一枚都是正面朝上。取下最上面的一枚硬幣，將它翻面後放回原處。然後取下最上面的2枚硬幣，將他們一起翻面後放回原處。在取3枚，取4枚……直至m枚。然後在從這摞硬幣最上面的一枚開始，重復剛才的做法。這樣一直做下去，直到這摞硬幣中每一枚又是正面朝上為止。例如，m為1時，翻兩次即可。
輸 入：僅有的一個數字是這摞硬幣的枚數m ，0< m <1000。
輸 出：為了使這摞硬幣中的每一枚都是朝正面朝上所必須翻的次數。
輸入樣例：30
輸出樣例：899
程 序：
program Program1;
var m:integer;
function solve(m: integer):integer;
var i,t,d: integer;
flag: Boolean;
begin
if (m = 1) then
solve := (1)
else begin
d := 2*m+1; t := 2; i := 1; flag := False;
repeat
if (t = 1) then
begin
solve := (2) ; flag := True;
end
else if ( (3) ) then
begin
solve := i*m-1; flag := True;
end
else
t := (4) ;
i:=i+1;
until flag;
end
end;
begin
read(m); if (( (5) ) and (m<1000)) then
writeln( (6) );
end.
2. OIM地形
題目描述：
二維離散世界有一種地形叫OIM(OI Mountain)。這種山的坡度只能上升('/')或下降('\'),而且兩邊的山腳都與地平線等高,山上所有地方都不低於地平線.例如：
/\ /\
/ \/\ 是一座OIM；而 / \ 不是。
\/
這個世界的地理學家們為了方便紀錄，給OIM所有可能的形狀用正整數編好號，而且每個正整數恰好對應一種山形。他們規定，若兩座山的寬度不同，則較寬的編號較大；若寬度相同，則比較從左邊開始第1個坡度不同的地方，坡度上升的編號較大。以下三座OIM的編號有小到大遞增：
/\ /\ /\ /\
/ \/\ / \/\/\ / \/ \。顯然/\的編號為1。但是地理學家在整理紀錄是發覺，查找編號與山形的對應關系不是很方便。他們希望能快速地從編號得到山的形狀。你自告奮勇答應他們寫一個程序，輸入編號，能馬上輸出山形。
輸 入：一個編號（編號大小不超過600,000,000），
輸 出：輸入編號所對應的山形，1座山所佔行數恰為它的高度，即山頂上不能有多餘空行。
輸入樣例：15
輸出樣例： /\ /\
/ \/ \
程 序：
program Program2;
const
L:integer =19; SZ: integer =50;
UP: char = '/'; DN: char = '\';
Var
i,nth,x,y,h,e,f:integer;
m: array[0..1,0..38,0..19] of integer;
pic: array[0..49,0..49] of char;
procere init;
var k,s,a,b,c: integer;
begin
for a:=0 to 1 do
for b:=0 to 2*L do
for c:=0 to L do
m[a,b,c]:=0; m[0,0,0]:=1;
for k:=0 to 2*L-1 do
begin
for s:=1 to L do
begin
m[0,k+1,s] := m[0,k,s+1] + m[1,k,s+1];
m[1,k+1,s]:= (1) ;
end;
m[0,k+1,0] :=m[0,k,1]+m[1,k,1];
end;
end;
procere draw(k,s,nth:integer);
begin
if (k=0) then exit;
if ((nth-m[1,k,s])>=0) then
begin
nth:=nth-m[1,k,s];
if (y>h) then (2) ;
pic[y,x]:=UP; y:=y+1; x:=x+1; draw( (3) );
end
else begin
y:=y - 1; pic[y,x]:=DN; x:=x+1; draw(k-1,s-1,nth);
end;
end;
begin
init;
read(nth);
for e:=0 to SZ-1 do
for f:=0 to SZ-1 do
pic[e,f]:= ' ';
x:=0;
y:=0
h:=0;
i:=0;
while ((nth-m[0,2*i,0])>=0) do
begin
nth:= nth-m[0,2*i,0];
(4) ;
end;
draw( (5) );
for i:=h downto x-1 do
begin
for e:=0 to x-1 do
write(pic[i,e]);
writeln(' ');
end;
end.
2002：
1． 問題描述：工廠在每天的生產中，需要一定數量的零件，同時也可以知道每天生產一個零件的生產單價。在N天的生產中，當天生產的零件可以滿足當天的需要，若當天用不完，可以放到下一天去使用，但要收取每個零件的保管費，不同的天收取的費用也不相同。
問題求解：求得一個N天的生產計劃（即N天中每天應生產零件個數），使總的費用最少。
輸入：N（天數 N<=29）
每天的需求量（N個整數）
每天生產零件的單價（N個整數）
每天保管零件的單價（N個整數）
輸出：每天的生產零件個數（N個整數）
例如：當N=3時，其需要量與費用如下：
第一天 第二天 第三天
需 要 量 25 15 30
生產單價 20 30 32
保管單價 5 10 0
生產計劃的安排可以有許多方案，如下面的三種：
第一天 第二天 第三天 總的費用
25 15 30 25*20+15*30+30*32=1910
40 0 30 40*20+15*5+30*32=1835
70 0 0 70*20+45*5+30*10=1925
程序說明：
b[n]：存放每天的需求量
c[n]：每天生產零件的單價
d[n]：每天保管零件的單價
e[n]：生產計劃
程序：
program exp5;
var
i,j,n,yu,j0,j1,s : integer ;
b,c,d,e : array[0..30] of integer ;
begin
readln(n);
for i:=1 to n do readln(b[i],c[i],d[i]);
for i:=1 to n do e[i]:=0;
①__________:=10000; c[n+2]=0; b[n+1]:=0 j0:=1;
while (j0<=n) do
begin
yu:=c[j0]; j1:=j0; s:=b[j0];
while ②__________ do
begin
③__________ j1:=j1+1; s:=s+b[j1];
end;
④__________ j0:=j1+1;
end;
for i:=1 to n do ⑤__________
readln;
end.
二．問題描述：有n種基本物質（n≤10），分別記為P1，P2，……，Pn，用n種基本物質構造物質，這些物品使用在k個不同地區（k≤20），每個地區對物品提出自己的要求，這些要求用一個n位的數表示：a1a2……a n，其中：
ai = 1表示所需物質中必須有第i種基本物質
= -1表示所需物質中必須不能有第i種基本物質
= 0無所謂
問題求解：當k個不同要求給出之後，給出一種方案，指出哪些物質被使用，哪些物質不被使用。
程序說明：數組 b[1],b[2]……b[n] 表示某種物質
a[1..k,1..n] 記錄k個地區對物品的要求，其中：
a[i,j]=1 表示第i個地區對第j種物品是需要的
a[i,j]=0 表示第i個地區對第j種物品是無所謂的
a[i,j]= -1 表示第i個地區對第j種物品是不需要的
程序：
program gxp2;
var
i,j,k,n : integer ;
p : boolean ;
b : array[0..20] of 0..1 ;
a : array[1..20,1..10] of integer ;
begin
readln(n,k);
for i:=1 to k do
begin
for j:=1 to n do read(a[i,j]);
readln;
end;
for i:=0 to n do b[i]:=0;
p:=true;
while ①__________ do
begin
j:=n;
while b[j]=1 do j:=j-1;
②__________
for i:=j+1 to n do b[i]:=0;
③__________
for i:=1 to k do
for j:=1 to n do
if (a[i,j]=1) and (b[j]=0) or ④__________
then p:=true;
end;
if ⑤__________
then writeln(『找不到！』)
else for i:=1 to n do
if (b[i]=1) then writeln(『物質』,i,』需要』)
else writeln(『物質』,i,』不需要』);
end.
2001：
1.存儲空間的回收演算法。設在內存中已經存放了若干個作業A，B，C，D。其餘的空間為可用的(如圖一中(a))。
此時，可用空間可用一個二維數組dk[1..100，1..2 ]表示，(如下表一中(a))，其中：dk[i，1]對應第i個可用空間首址，dk[i，2]對應第i個可用空間長度如上圖中，dk：
100 50
300 100
50 100
0 0
100 50
300 100
500 100
10000 0
表一(a) 表一(b)
現某個作業釋放一個區域，其首址為d，長度為L，此時將釋放區域加入到可用空間表中。要求在加入時，若可用空間相鄰時，則必須進行合並。因此出現下面的4種情況(如上圖一(b)所示)。
(1)下靠，即回收區域和下面可用空間相鄰，例如，d=80，L=20，此時成為表二中的(a)。
(2)上靠，例如，d=600，L=50，此時表成為表二中的(b)。
(3)上、下靠，例如，d=150，L=150，此時表成為表二中的(c)。
(4)上、下不靠，例如，d=430，L=20，此時表成為表二中的(d)。
80 70
300 100
50 100
100 50
300 100
500 150
100
300
500
100
100 50
300 100
430 20
500 100
表二(a)(下靠) 表二(b)(上靠) 表二(c)(上，下靠) 表二(d)(上，下不靠)
程序說明：對數組dk預置2個標志，即頭和尾標志，成為表二中(b)，這樣可使演算法簡單，sp為dk表末地址。
程序清單：
PROGRAM GAO7_5；
VAR I，J，SP，D，L：INTEGER；
DK ：ARRAY[0..100，1..2]OF INTEGER；
BEGIN
READLN(SP)；
FOR I:=1 TO SP DO
READLN(DK[I，1]，DK[I，2])；
DK[0，1]:=0；DK[0，2]:=0； ① ；
DK[SP，1]:=10000；DK[SP，2]:=0；READLN(D，L)；I:=1；
WHILE DK[I，1]<D DO I:=I+1； ② ；
IF(DK[I，1]+DK[I，2]=D)THEN
IF(D+L=DK[I+1，1])THEN
BEGIN
DK[I，2]:= ③ ；
FOR J:=I+1 TO SP-1 DO
DK[J]:=DK[J+1]；
SP：=SP-1；
END
ELSE DK[I，2]:=DK[I，2]+L
ELSE IF(D+L=DK[I+1，1])THEN
BEGIN
DK[I+1，1]::= ④ ；DK[I+1，2]:=DK[I+1，2]+L
END
ELSE BEGIN
FOR J:=SP DOWNTO I+1 DO DK[J+1]:=DK[J]；
⑤ :=D； DK[I+1，2]:=L；SP:=SP+1；
END；
FOR I:=1 TO SP-1 DO WRITELN(DK[I，1]:4，DK[I，2]:4)；READLN；
END.
2.求關鍵路徑
設有一個工程網路如下圖表示(無環路的有向圖)：
其中，頂點表示活動，①表示工程開始，⑤表示工程結束(可變，用N表示)，邊上的數字表示活動延續的時間。
如上圖中，活動①開始5天後活動②才能開始工作，而活動③則要等①、②完成之後才能開始，即最早也要7天後才能工作。
在工程網路中，延續時間最長的路徑稱為關鍵路徑。上圖中的關鍵路徑為：①—②—③—④—⑤共18天完成。
關鍵路徑的演算法如下：
1.數據結構：
R[1..N，1..N]OF INTEGER； 表示活動的延續時間，若無連線，則用-1表示；
EET[1..N] 表示活動最早可以開始的時間
ET[1..N] 表示活動最遲應該開始的時間
關鍵路徑通過點J，具有如下的性質：EET[J]=ET[J]
2.約定：
結點的排列已經過拓撲排序，即序號前面的結點會影響序號後面結點的活
④ 如何計算關鍵路徑
並行的活動：最早結束時間大者，在關鍵路徑。以網上一圖舉例。
A-->B/C並列，其中C活動最早結束時間（EalyFinish）為第13天，大於7，所以C在關鍵路徑上。
A-->C-->D/E,23>18,同上
A-->C-->D-->G,同上
A-->C-->D-->G-->H，同上
⑤ 求關鍵路徑的程序（最好是C#的，其他的也可以）
usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
namespaceToppath
{
classProgram
{
staticvoidMain(string[]args)
{
node<char>[]Mynode={newnode<char>('A'),newnode<char>('B'),newnode<char>('C'),
newnode<char>('D'),newnode<char>('E'),newnode<char>('F'),
newnode<char>('G'),newnode<char>('H'),newnode<char>('I'),
newnode<char>('J')};
GraphAdjlist<char>xiong=newGraphAdjlist<char>(Mynode);
xiong.SetEdge(Mynode[0],Mynode[1],3);
xiong.SetEdge(Mynode[0],Mynode[2],4);
xiong.SetEdge(Mynode[1],Mynode[3],5);
xiong.SetEdge(Mynode[1],Mynode[4],6);
xiong.SetEdge(Mynode[2],Mynode[3],8);
xiong.SetEdge(Mynode[2],Mynode[5],7);
xiong.SetEdge(Mynode[3],Mynode[4],3);
xiong.SetEdge(Mynode[4],Mynode[7],4);
xiong.SetEdge(Mynode[4],Mynode[6],9);
xiong.SetEdge(Mynode[5],Mynode[7],6);
xiong.SetEdge(Mynode[7],Mynode[8],5);
xiong.SetEdge(Mynode[6],Mynode[9],2);
xiong.SetEdge(Mynode[8],Mynode[9],3);
xiong.toppath();
Console.ReadKey();
}
}
classnode<T>
{
publicTData
{get;set;}
publicnode(Ttemp)
{
Data=temp;
}
}
classvextable<T>
{
publicnode<T>Vex
{get;set;}
publicadjlistnode<T>First
{get;set;}
publicintIn
{get;set;}
publicvextable()
{
Vex=null;
First=null;
}
publicvextable(node<T>p)
{
Vex=p;
First=null;
In=0;
}
}
classadjlistnode<T>
{
publicintIndex
{get;set;}
publicadjlistnode<T>next
{get;set;}
publicintWeight
{get;set;}
publicadjlistnode(intindex)
{
Index=index;
next=null;
Weight=0;
}
publicadjlistnode()
{
Index=-1;
next=null;
Weight=0;
}
}
classGraphAdjlist<T>
{
publicvextable<T>[]vext
{get;set;}
publicint[]Visited
{get;set;}
publicvextable<T>this[intindex]
{
get{returnvext[index];}
set{vext[index]=value;}
}
publicGraphAdjlist(node<T>[]mynode)
{
vext=newvextable<T>[mynode.Length];
Visited=newint[mynode.Length];
for(inti=0;i<mynode.Length;i++)
{
vext[i]=newvextable<T>(mynode[i]);
}
}
publicintIndexofvertex(node<T>x)
{
for(inti=0;i<vext.Length;i++)
{
if(vext[i].Vex.Equals(x))
returni;
}
Console.WriteLine("nothisnode");
return-1;
}
publicvoidSetEdge(node<T>v1,node<T>v2,intv)//這個Top排序要使用的是一個有向鄰接表才對
{
intiv1=Indexofvertex(v1);
intiv2=Indexofvertex(v2);
adjlistnode<T>p1=newadjlistnode<T>(iv1);
adjlistnode<T>p2=newadjlistnode<T>(iv2);
//在v1處添加v2;
p2.next=vext[iv1].First;
vext[iv1].First=p2;
p2.Weight=v;
vext[iv2].In++;//添加入度
}
publicvoidtoppath()
{
Stack<int>temp=newStack<int>();//用什麼都行，但必須保持一致用於存放拓撲坐標
Stack<int>toparray=newStack<int>();//用stack最好，因為正向過去算etv，反向回來算ltv，先入後出最好
Stack<int>path=newStack<int>();//再反一次，存的就是正常的拓撲圖，從頭開始那種
intp=-1;intm=-1;
adjlistnode<T>q=newadjlistnode<T>();
int[]etv=newint[vext.Length];//最早點
int[]ltv=newint[vext.Length];//最晚點
intete=-1;//最早邊，是判斷變數不是數組用來找邊的
intlte=-1;//最晚邊
intk=0;
for(inti=0;i<vext.Length;i++)
{
if(vext[i].In==0)
{
temp.Push(i);//壓入序號
}
}
while(toparray.Count!=vext.Length)
{
p=temp.Pop();
toparray.Push(p);
q=vext[p].First;
while(q!=null)
{
vext[q.Index].In--;//下標就用最原始的值，順序用棧保存好就行
if(vext[q.Index].In==0)
{
temp.Push(q.Index);
}
if(etv[p]+q.Weight>etv[q.Index])//正向過去算etv,etv均初始化為0
{
etv[q.Index]=etv[p]+q.Weight;
}
q=q.next;
}
}//棧就是用來壓和彈的，如果想取完還有，那就在找個棧，邊取邊存，不是給你拿來遍歷用的
for(inti=0;i<vext.Length;i++)//找到etv的最大值拿來賦值給ltv因為這是反向回去，最大值是終點值
{
if(etv[i]>m)
{
m=etv[i];
}
}
while(toparray.Count!=0)
{
k=toparray.Pop();//由於是棧所以彈出的肯定是終點
path.Push(k);//再保存一次
q=vext[k].First;
ltv[k]=m;//將所有最晚頂點置成最大值
while(q!=null)
{
if((ltv[q.Index]-q.Weight)<ltv[k])//算ltv其實是min
{
ltv[k]=ltv[q.Index]-q.Weight;
}
q=q.next;
}
}
while(path.Count!=0)//這邊我感覺還是按拓撲順序得好，因為這樣可以有序的排列頂點，不按也成反正是找邊，邊構成路
{
inti=path.Pop();
q=vext[i].First;
while(q!=null)
{
ete=etv[i];//邊上的值，其實看etv和etl就能看到，只不過用這種方式更加形象的定位到邊，並且給出權值
lte=ltv[q.Index]-q.Weight;
if(ete==lte)
{
Console.WriteLine(vext[i].Vex.Data+""+vext[q.Index].Vex.Data+""+q.Weight);
}
q=q.next;
}
}
Console.ReadKey();
}
}
}
朋友看得懂不，不懂可以加我QQ：1036433209,也許你已成為大神，就當一起學習吧
⑥ 求如下有向圖的關鍵路徑以及任意兩點之間的最短距離
用CPM演算法求有向圖的關鍵路徑和用Dijkstra演算法求有向圖的最短路徑的C語言程序如下
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#define MAX 20
#define INF 32767 // 此處修改最大值
#define nLENGTH(a) (sizeof(a)/sizeof(a[0]))
#define eLENGTH(a) (sizeof(a)/sizeof(char))/(sizeof(a[0])/sizeof(char))
typedef struct _graph{
char vexs[MAX]; // 頂點集合
int vexnum; // 頂點數
int edgnum; // 邊數
int matrix[MAX][MAX]; // 鄰接矩陣
}Graph, *PGraph;
// 邊的結構體
typedef struct _EdgeData{
char start; // 邊的起點
char end; // 邊的終點
int weight; // 邊的權重
}EData;
//指向節點的位置
int point_node(PGraph g,char c){
for(int i=0;i<g->vexnum;i++){
if(g->vexs[i]==c){
return i;
}
}
return -1;
}
PGraph create_graph(int b[][3],char a[],int n,int e){
char c1,c2; //邊的2個頂點
PGraph g; //矩陣
g=(PGraph)malloc(sizeof(Graph));
//memset()第一個參數 是地址，第二個參數是開辟空間的初始值，第三個參數是開辟空間的大小
memset(g, 0, sizeof(Graph));
printf("頂點個數: ");//頂點數
g->vexnum=n;
printf("%d ",g->vexnum);
printf("邊個數: ");//邊數
g->edgnum=e;
printf("%d ",g->edgnum);
//初始化頂點
for(int j=0;j<g->vexnum;j++){
g->vexs[j]=a[j];
}
for(int i=0;i<g->edgnum;i++){
int p1,p2;
c1=char(b[i][0]);
c2=char(b[i][1]);
p1=point_node(g, c1);
p2=point_node(g, c2);
if (p1==-1 || p2==-1){
printf("input error: invalid edge! ");
free(g);
continue;
}
g->matrix[p1][p2]=b[i][2];
}
for(int i=0;i<g->vexnum;i++){
for(int j=0;j<g->vexnum;j++){
if(g->matrix[i][j]==0)
g->matrix[i][j]=INF;
}
}
return g;
}
//關鍵路徑的最短時間
//關鍵路徑法（Critical Path Method，CPM）
void CPM_road(PGraph g){
int i,j;
int a[MAX]={0},b[MAX]={-10};
int max=0;//最長路徑
for( i=0;i<g->vexnum;i++){//列數遍歷
for( j=0;j<g->vexnum;j++){//行數遍歷
//如果g->matrix[j][i]大於0，說明此頂點有前頂點，由前邊的遍歷可知，前頂點的最長路徑a[j]，
//加上g->matrix[j][i]的路徑就是當前a[i]的路徑
if(g->matrix[j][i]!=INF && g->matrix[j][i]+a[j]>max){
max=g->matrix[j][i]+a[j];
a[i]=max;
}
}
max=0;
}
//顯示最長路徑
printf("第一個頂點到每一個頂點的最長路徑:");
printf(" ");
for(i=0;i<g->vexnum;i++){
printf("V%d ",i+1);
}
printf(" ");
for(i=0;i<g->vexnum;i++){
printf("%d ",a[i]);
}
printf(" ");
printf("最後一個頂點到每個頂點的最長路徑:");
for( i=g->vexnum-1;i>=0;i--){ //列數遍歷
for( j=g->vexnum-1;j>=0;j--){ //行數遍歷
//如果g->matrix[j][i]大於0，說明此頂點有前頂點，由前邊的遍歷可知，前頂點的最長路徑a[j]，
//加上g->matrix[j][i]的路徑就是當前a[i]的路徑
if(g->matrix[i][j]!=INF && g->matrix[i][j]+b[j]>max){
max=g->matrix[i][j]+b[j];
b[i]=max;
}
}
max=0;
}
//顯示最長路徑
printf(" ");
for(i=0;i<g->vexnum;i++){
printf("V%d ",i+1);
}
printf(" ");
for(i=0;i<g->vexnum;i++){
printf("%d ",b[i]);
}
printf(" ");
printf("關鍵路徑: ");
for(i=0;i<g->vexnum;i++){
if(a[i]==a[g->vexnum-1]-b[i]){
printf("V%c ",g->vexs[i]);
}
}
printf(" ");
}
void print_shortest_path(PGraph g,int* distance,int* path,int* used,int start,int end){
// 輸出最短距離並列印最短路徑
int i = 0, pre, inverse_path[g->vexnum];
char s1[3],s2[3];
sprintf(s1, "V%d", (start+1));
sprintf(s2, "V%d", (end+1));
printf("從%s頂點到%s頂點的最短距離: %d ", s1, s2, distance[end]);
inverse_path[i] = end;
pre = path[end];
if(pre == -1){
printf("沒有通路! ");
}else{
while(pre != start){
inverse_path[++i] = pre;
pre = path[pre];
}
inverse_path[++i] = start;
printf("從%s頂點到%s頂點的最短路徑: ", s1, s2);
for(; i > 0; i--){
sprintf(s1, "V%d", (inverse_path[i]+1));
printf("%s -> ", s1);
}
sprintf(s1, "V%d", (inverse_path[i]+1));
printf("%s ", s1);
}
return;
}
void shortest_path(PGraph g,int start, int end){ // 基於Dijkstra演算法的最短路徑函數
int distance[g->vexnum]; // 用於存放起始點到其餘各點的最短距離
int path[g->vexnum]; // 用於存放起始點到其餘各點最短路徑的前一個頂點
int used[g->vexnum] = { 0 }; // 用於標記該頂點是否已經找到最短路徑
int i, j, min_node, min_dis, pass_flag = 0;
for(i = 0; i < g->vexnum; i++){
distance[i] = g->matrix[start][i]; // 初始化距離數組
if(g->matrix[start][i] < INF){
path[i] = start; // 初始化路徑數組
}else{
path[i] = -1;
}
}
used[start] = 1;
path[start] = start;
for(i = 0; i < g->vexnum; i++){
min_dis = INF;
for(j = 0; j < g->vexnum; j++){
if(used[j] == 0 && distance[j] < min_dis){
min_node = j;
min_dis = distance[j];
pass_flag++; // 標記是否存在通路
}
}
if(pass_flag != 0){
used[min_node] = 1;
for(j = 0; j < g->vexnum; j++){
if(used[j] == 0){
if(g->matrix[min_node][j] < INF && distance[min_node] + g->matrix[min_node][j] < distance[j]){
distance[j] = distance[min_node] + g->matrix[min_node][j];
path[j] = min_node;
}
}
}
}
}
print_shortest_path(g,distance, path, used, start, end);
return;
}
int main(){
int i,j;
PGraph gp;
char a[]={'1', '2', '3', '4', '5', '6', '7'};
int b[][3]={{'1', '2',3},
{'1', '3',2},
{'1', '4',6},
{'2', '4',2},
{'2', '5',4},
{'3', '4',1},
{'3', '6',3},
{'4', '5',1},
{'5', '7',3},
{'6', '7',4}};
int n=nLENGTH(a);
int e=eLENGTH(b);
gp=create_graph(b,a,n,e);
//列印鄰接矩陣
printf("鄰接矩陣: ");
for (i = 0; i < gp->vexnum; i++){
for (j = 0; j < gp->vexnum; j++)
printf("%d ", gp->matrix[j][i]);
printf(" ");
}
CPM_road(gp);
printf(" ");
for(i=0;i<gp->vexnum;i++){
for(j=0;j<gp->vexnum;j++){
if(i!=j)
shortest_path(gp,i, j);
}
}
return 0;
}
運行結果