1 一筆畫問題
2 迷宮問題
3 最短路徑問題(就是給出一個交通示意圖,邊上的數字為路的長度,求每個結點到某個固定點的最短路程)
4 N個球稱重問題吧
荷蘭國旗問題????四色定理
3種顏色(0,1,2)在一個數組里,每次只可交換一次,掃描一邊后,三種顏色自然分開,應為顏色為:紅,白,藍,(荷蘭國旗的顏色)所以叫它荷蘭國旗問題(也是他老人家的國籍)!
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#define N 15
int main(int argc, char* argv[])
{
char array[N];
char t,*p_red_end,*p_write_end,*p_blue_head; //分別為紅色的尾指針、白色的尾指
針、藍色的首指針
int i;
srand( (unsigned)time( NULL ) );
for(i=0;i<N;i++)
{
switch (rand()%3)
{
case 0:
array=’r’;
break;
case 1:
array=’w’;
break;
default:
array=’b’;
}
printf("%c ",array);
}
printf("\n";
for(p_red_end=p_write_end=array,p_blue_head=array+14;p_write_end<=p_blue_head
switch (*p_write_end)
{
case ’r’:
t=*p_red_end;
*p_red_end=*p_write_end;
*p_write_end=t;
p_red_end++;
p_write_end++;
break;
case ’b’:
t=*p_write_end;
*p_write_end=*p_blue_head;
*p_blue_head=t;
p_blue_head--;
break;
default:
p_write_end++;
}
for(i=0;i<N;i++)
printf("%c ",array);
}
運行結果是:
rrrwwrwwrwbbbbb
這個結果是荷蘭國旗算法的結果嗎?(我不清楚荷蘭國旗算法)
題目最終要求的結果應該是:紅,白,蘭,紅,白,蘭,紅,白,蘭……還是:紅,紅,紅,紅,紅,白,白,白,白,藍,藍,藍,藍,藍……?
#include "stdio.h"
#define k 15 /*假定數組有15個數*/
char a[k]={’r’,’w’,’b’,’r’,’r’,’b’,’w’,’w’,’b’,’b’,’b’,’w’,’r’,’r’,’w’}; /*r,b,w代表紅,
藍,白*/
main()
{int i,ii;
char t;
int m,n,p;
m=0; /*m為紅色末尾指針*/
n=0; /*n為白色末尾指針*/
p=14;/*p為藍紅色頭指針*/
for (ii=0;ii<15;ii++)
printf("%c",a[ii]);
while(n<=p)
{
if (a[n]==’r’) {t=a[n];a[n]=a[m];a[m]=t;m++;n++;}
else if (a[n]==’w’) n++;
else {
t=a[n];a[n]=a[p];a[p]=t;p--;n++;
if (a[n-1]==’r’) {t=a[n-1];a[n-1]=a[m];a[m]=t;m++;}
}
for (i=0;i<15;i++)
prinrf("%s",a[n]);
}
貨郎問題????
一筆畫問題
const max=6;{頂點數為6}
type shuzu=array[1..max,1..max]of 0..max;
const a:shuzu {圖的描述與定義 1:連通;0:不通}
=((0,1,0,1,1,1),
(1,0,1,0,1,0),
(0,1,0,1,1,1),
(1,0,1,0,1,1),
(1,1,1,1,0,0),
(1,0,1,1,0,0));
var
bianshu:array[1..max]of 0..max; {與每一條邊相連的邊數}
path:array[0..1000]of integer; {記錄畫法,只記錄頂點}
zongbianshu,ii,first,i,total:integer;
procedure output(dep:integer); {輸出各個頂點的畫法順序}
var sum,i,j:integer;
begin
inc(total);
writeln(’total:’,total);
for i:=0 to dep do write(Path);writeln;
end;
function ok(now,i:integer;var next:integer):boolean;{判斷第I條連接邊是否已行過}
var j,jj:integer;
begin
j:=0; jj:=0;
while jj<>i do begin inc(j);if a[now,j]<>0 then inc(jj);end;
next:=j;
{判斷當前頂點的第I條連接邊的另一端是哪個頂點,找出后賦給NEXT傳回}
ok:=true;
if (a[now,j]<>1) then ok:=false; {A[I,J]=0:原本不通}
end; { =2:曾走過}
procedure init; {初始化}
var i,j :integer;
begin
total:=0; {方案總數}
zongbianshu:=0; {總邊數}
for i:=1 to max do
for j:=1 to max do
if a[i,j]<>0 then begin inc(bianshu);inc(zongbianshu);end;
{求與每一邊連接的邊數bianshu}
zongbianshu:=zongbianshu div 2; {圖中的總邊數}
end;
procedure find(dep,nowpoint:integer); {dep:畫第幾條邊;nowpoint:現在所處的頂點}
var i,next,j:integer;
begin
for i:=1 to bianshu[nowpoint] do {與當前頂點有多少條相接,則有多少種走法}
if ok(nowpoint,i,next) then begin {與當前頂點相接的第I條邊可行嗎?}
{如果可行,其求出另一端點是NEXT}
a[nowpoint,next]:=2; a[next,nowpoint]:=2; {置成已走過標志}
path[dep]:=next; {記錄頂點,方便輸出}
if dep < zongbianshu then find(dep+1,next) {未搜索完每一條邊}
else output(dep);
path[dep]:=0; {回溯}
a[nowpoint,next]:=1; a[next,nowpoint]:=1;
end;
begin
init; {初始化,求邊數等}
for first:=1 to max do {分別從各個頂點出發,嘗試一筆畫}
fillchar(path,sizeof(path),0);
path[0]:=first; {記錄其起始的頂點}
writeln(’from point ’,first,’:’);readln;
find(1,first); {從起始點first,一條邊一條邊地畫下去}
end.
銀行家算法其實是很普通的但是比較經典的算法,每本OS的書上都講的,主要用來防止產生死鎖的,
形象的講:銀行發放貸款(對不同的客戶,有分期貸的)不能使有限可用資金匱乏而導致整個銀行無法運轉,也就是說每次請求貸款時,銀行要考慮他能否憑著貸款完成項目還清貸款使銀行運轉正常,
(借用flyingcoolhwak寫的步驟)
令Request(i)是進程P(i)請求向量,如果Request(i)[j]=k,則進程P(i)希望請求j類資源k個。
算法步驟如下:
1、如果Request(i)>Need(i)則出錯(請求量超過申報的最大量),否則轉2、
2、如果Requdst(i)>Available則P(i)等待,否則轉3、
3、系統對P(i)所請求的資源實施試探分配,更改數據結構中的數值
4、Available<-Available-Request(i)
Allocation(i)<-Allocation(i)+Request(i)
Need(i)<-Need(i)-Request(i)
5、執行安全性算法(如下),如果是安全的則承認試分配,否則廢除試分配,讓進程P(i)等待
貨郎擔問題
問題描述
歐幾里德貨郎擔問題是對平面給定的n個點確定一條連結各點的、閉合的游歷路線問題。圖1(a)給出了七個點問題的解。Bitonic旅行路線問題是歐幾里德貨郎擔問題的簡化,這種旅行路線先從最左邊開始,嚴格地由左至右到最右邊的點,然后再嚴格地由右至左到出發點,求路程最短的路徑長度。圖1(b)給出了七個點問題的解。
請設計一種多項式時間的算法,解決Bitonic旅行路線問題
2 迷宮問題
3 最短路徑問題(就是給出一個交通示意圖,邊上的數字為路的長度,求每個結點到某個固定點的最短路程)
4 N個球稱重問題吧
荷蘭國旗問題????四色定理
3種顏色(0,1,2)在一個數組里,每次只可交換一次,掃描一邊后,三種顏色自然分開,應為顏色為:紅,白,藍,(荷蘭國旗的顏色)所以叫它荷蘭國旗問題(也是他老人家的國籍)!
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#define N 15
int main(int argc, char* argv[])
{
char array[N];
char t,*p_red_end,*p_write_end,*p_blue_head; //分別為紅色的尾指針、白色的尾指
針、藍色的首指針
int i;
srand( (unsigned)time( NULL ) );
for(i=0;i<N;i++)
{
switch (rand()%3)
{
case 0:
array=’r’;
break;
case 1:
array=’w’;
break;
default:
array=’b’;
}
printf("%c ",array);
}
printf("\n";
for(p_red_end=p_write_end=array,p_blue_head=array+14;p_write_end<=p_blue_head
switch (*p_write_end)
{
case ’r’:
t=*p_red_end;
*p_red_end=*p_write_end;
*p_write_end=t;
p_red_end++;
p_write_end++;
break;
case ’b’:
t=*p_write_end;
*p_write_end=*p_blue_head;
*p_blue_head=t;
p_blue_head--;
break;
default:
p_write_end++;
}
for(i=0;i<N;i++)
printf("%c ",array);
}
運行結果是:
rrrwwrwwrwbbbbb
這個結果是荷蘭國旗算法的結果嗎?(我不清楚荷蘭國旗算法)
題目最終要求的結果應該是:紅,白,蘭,紅,白,蘭,紅,白,蘭……還是:紅,紅,紅,紅,紅,白,白,白,白,藍,藍,藍,藍,藍……?
#include "stdio.h"
#define k 15 /*假定數組有15個數*/
char a[k]={’r’,’w’,’b’,’r’,’r’,’b’,’w’,’w’,’b’,’b’,’b’,’w’,’r’,’r’,’w’}; /*r,b,w代表紅,
藍,白*/
main()
{int i,ii;
char t;
int m,n,p;
m=0; /*m為紅色末尾指針*/
n=0; /*n為白色末尾指針*/
p=14;/*p為藍紅色頭指針*/
for (ii=0;ii<15;ii++)
printf("%c",a[ii]);
while(n<=p)
{
if (a[n]==’r’) {t=a[n];a[n]=a[m];a[m]=t;m++;n++;}
else if (a[n]==’w’) n++;
else {
t=a[n];a[n]=a[p];a[p]=t;p--;n++;
if (a[n-1]==’r’) {t=a[n-1];a[n-1]=a[m];a[m]=t;m++;}
}
for (i=0;i<15;i++)
prinrf("%s",a[n]);
}
貨郎問題????
一筆畫問題
const max=6;{頂點數為6}
type shuzu=array[1..max,1..max]of 0..max;
const a:shuzu {圖的描述與定義 1:連通;0:不通}
=((0,1,0,1,1,1),
(1,0,1,0,1,0),
(0,1,0,1,1,1),
(1,0,1,0,1,1),
(1,1,1,1,0,0),
(1,0,1,1,0,0));
var
bianshu:array[1..max]of 0..max; {與每一條邊相連的邊數}
path:array[0..1000]of integer; {記錄畫法,只記錄頂點}
zongbianshu,ii,first,i,total:integer;
procedure output(dep:integer); {輸出各個頂點的畫法順序}
var sum,i,j:integer;
begin
inc(total);
writeln(’total:’,total);
for i:=0 to dep do write(Path);writeln;
end;
function ok(now,i:integer;var next:integer):boolean;{判斷第I條連接邊是否已行過}
var j,jj:integer;
begin
j:=0; jj:=0;
while jj<>i do begin inc(j);if a[now,j]<>0 then inc(jj);end;
next:=j;
{判斷當前頂點的第I條連接邊的另一端是哪個頂點,找出后賦給NEXT傳回}
ok:=true;
if (a[now,j]<>1) then ok:=false; {A[I,J]=0:原本不通}
end; { =2:曾走過}
procedure init; {初始化}
var i,j :integer;
begin
total:=0; {方案總數}
zongbianshu:=0; {總邊數}
for i:=1 to max do
for j:=1 to max do
if a[i,j]<>0 then begin inc(bianshu);inc(zongbianshu);end;
{求與每一邊連接的邊數bianshu}
zongbianshu:=zongbianshu div 2; {圖中的總邊數}
end;
procedure find(dep,nowpoint:integer); {dep:畫第幾條邊;nowpoint:現在所處的頂點}
var i,next,j:integer;
begin
for i:=1 to bianshu[nowpoint] do {與當前頂點有多少條相接,則有多少種走法}
if ok(nowpoint,i,next) then begin {與當前頂點相接的第I條邊可行嗎?}
{如果可行,其求出另一端點是NEXT}
a[nowpoint,next]:=2; a[next,nowpoint]:=2; {置成已走過標志}
path[dep]:=next; {記錄頂點,方便輸出}
if dep < zongbianshu then find(dep+1,next) {未搜索完每一條邊}
else output(dep);
path[dep]:=0; {回溯}
a[nowpoint,next]:=1; a[next,nowpoint]:=1;
end;
begin
init; {初始化,求邊數等}
for first:=1 to max do {分別從各個頂點出發,嘗試一筆畫}
fillchar(path,sizeof(path),0);
path[0]:=first; {記錄其起始的頂點}
writeln(’from point ’,first,’:’);readln;
find(1,first); {從起始點first,一條邊一條邊地畫下去}
end.
銀行家算法其實是很普通的但是比較經典的算法,每本OS的書上都講的,主要用來防止產生死鎖的,
形象的講:銀行發放貸款(對不同的客戶,有分期貸的)不能使有限可用資金匱乏而導致整個銀行無法運轉,也就是說每次請求貸款時,銀行要考慮他能否憑著貸款完成項目還清貸款使銀行運轉正常,
(借用flyingcoolhwak寫的步驟)
令Request(i)是進程P(i)請求向量,如果Request(i)[j]=k,則進程P(i)希望請求j類資源k個。
算法步驟如下:
1、如果Request(i)>Need(i)則出錯(請求量超過申報的最大量),否則轉2、
2、如果Requdst(i)>Available則P(i)等待,否則轉3、
3、系統對P(i)所請求的資源實施試探分配,更改數據結構中的數值
4、Available<-Available-Request(i)
Allocation(i)<-Allocation(i)+Request(i)
Need(i)<-Need(i)-Request(i)
5、執行安全性算法(如下),如果是安全的則承認試分配,否則廢除試分配,讓進程P(i)等待
貨郎擔問題
問題描述
歐幾里德貨郎擔問題是對平面給定的n個點確定一條連結各點的、閉合的游歷路線問題。圖1(a)給出了七個點問題的解。Bitonic旅行路線問題是歐幾里德貨郎擔問題的簡化,這種旅行路線先從最左邊開始,嚴格地由左至右到最右邊的點,然后再嚴格地由右至左到出發點,求路程最短的路徑長度。圖1(b)給出了七個點問題的解。
請設計一種多項式時間的算法,解決Bitonic旅行路線問題