算法分析实验题集

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，如需转载请自行联系原作者