算法分析實驗題集

http://blog.csdn.net/mzx0821

      雨紛紛、舊故裡草木深、我聽聞、你始終一個人、斑駁的城門、盤踞着老樹根、石闆上回蕩的是再等、

                                                                      —— 永不放棄的Mzx0821

希望全部的同學算法分析都都不會挂科、

注：題庫包含卓越班實驗題和非卓越班實驗題、由于不知道老師會不會考超範圍的、

由于OJ資料弱的原因、不保證下面解法的正确性、特别感謝small rabbit貢獻的部分答案、

實驗一：

249  凸包面積

303  取模

352   合并果子

493   PostOffice

794   近期對問題

實驗二：

76   數字模式的識别

254   翻煎餅

342   變位詞

445   選擇問題

541   排列的字典序問題

642   俄式乘法

實驗三：

注：和上面反複的題我就不再寫了、

640   Binary search

956   約瑟夫問題的實作

005   Euclid's Game

405   Fibonacci number

413   Quick Sort

414   The Next Permutation

425   Polynomial calculate

446    合并排序

480   Locker doors

641  The Dutch flag problem

411  售貨員的難題

a:b;

}

int solve()

{

int i,j,k;

int st=1<<(n+1);

for(i=0;i<=n;++i)

for(j=0;j<st;++j)

dp[i][j]=inf;

dp[0][1]=0;

for(i=1;i<st;++i)

for(j=0;j<=n;++j)

if((i&(1<<j)) == 0)

continue;

for(k=0;k<=n;++k)

if((i&(1<<k)) == 0)

dp[k][i|(1<<k)]=min(dp[k][i|(1<<k)],dp[j][i]+map[j][k]);

return dp[n][st-1];

int main()

while(scanf("%d",&n) != EOF)

int i,j;

for(i=0;i<n;++i)

for(j=0;j<n;++j)

scanf("%d",&map[i][j]);

map[i][n]=map[i][0];

int ans=solve();

printf("%d\n",ans);

return 0;

572   Boyer–Moore–Horspool algorithm

649   NBA Finals

680   Jack Straws

這标簽給的也是醉了、就是一個并查集、無語、、

(x) : (y))

#define MINV(x, y) ((x) <= (y) ? (x) : (y))

using namespace std;

int num;

struct node

int x1, y1, x2, y2;

}data[MAX_N + 1];

int set[MAX_N + 1];

int rank[MAX_N + 1];

//推斷第3個點在1,2點構成的線短的哪個方向, -1: 逆時針方向, 1: 順時針方向

int direct(int x1, int y1, int x2, int y2, int x3, int y3)

return (x3 - x1) * (y2 - y1) - (x2 - x1) * (y3 - y1);

//推斷第3個點是否在1,2點構成的線短上

bool onLine(int x1, int y1, int x2, int y2, int x3, int y3)

return (MINV(x1, x2) <= x3 && x3 <= MAXV(x1, x2) && MINV(y1, y2) <= y3 && y3 <= MAXV(y1, y2));

//推斷點1,2構成的線短與點3,4構成的線短是否相交

bool intersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4)

int d1 = direct(x3, y3, x4, y4, x1, y1);

int d2 = direct(x3, y3, x4, y4, x2, y2);

int d3 = direct(x1, y1, x2, y2, x3, y3);

int d4 = direct(x1, y1, x2, y2, x4, y4);

if(((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) && ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0)))

return true;

if(d1 == 0 && onLine(x3, y3, x4, y4, x1, y1))

else if(d2 == 0 && onLine(x3, y3, x4, y4, x2, y2))

else if(d3 == 0 && onLine(x1, y1, x2, y2, x3, y3))

else if(d4 == 0 && onLine(x1, y1, x2, y2, x4, y4))

else

return false;

int find(int pos)

if(pos != set[pos])

set[pos] = find(set[pos]);

return set[pos];

void joinSet(int pos1, int pos2)

if(pos1 == pos2)

return;

int pre1 = find(pos1);

int pre2 = find(pos2);

if(pre1 == pre2)

int rank1 = rank[pre1];

int rank2 = rank[pre2];

if(rank1 < rank2)

set[pre1] = pre2;

else if(rank1 > rank2)

set[pre2] = pre1;

rank[pre1]++;

void init()

int i;

for(i = 1; i <= num; i++)

set[i] = i;

rank[i] = 0;

int i, n1, n2, pre1, pre2;

while(cin>>num && num != 0)

cin>>data[i].x1>>data[i].y1>>data[i].x2>>data[i].y2;

init();

for(n1 = 1; n1 <= num; n1++)

for(n2 = n1; n2 <= num; n2++)

pre1 = find(n1);

pre2 = find(n2);

if(intersect(data[n1].x1, data[n1].y1, data[n1].x2, data[n1].y2,

data[n2].x1, data[n2].y1, data[n2].x2, data[n2].y2))

joinSet(n1, n2);

while(cin>>n1>>n2 && !(n1 == 0 && n2 == 0))

cout<<"CONNECTED"<<endl;

cout<<"NOT CONNECTED"<<endl;

410   尼克的任務

544   跑跑卡丁車

679    Secret Code

698   Independent Task Scheduling

1080    單純行法

明明叫做單純形法好麼。

。

。數學渣、不會做、等有空問下理學院的同學怎麼搞、

本文轉自mfrbuaa部落格園部落格，原文連結：http://www.cnblogs.com/mfrbuaa/p/5175271.html，如需轉載請自行聯系原作者