算法设计与分析上机题

1、算法设计与分析上机题第二单元 8594 有重复元素的排列问题；9718 整数因子分解；11088 整数划分的扩展问题；17082 两个有序数序列中找第k小第三单元8596 最长上升子序列；*8601最大长方体问题；10303 数字三角；11077 最长公共子字符串；11078 不能移动的石子合并第四单元8602 区间相交问题；11079 可以移动的石子合并第五单元8600 骑士问题；8603 子集和问题；17085 工作分配问题；11089 多机最佳调度抽选概率： 第二三单元，9选3 第四五单元，6选2机选，这15题必做题中共抽5题，还要从选做题中抽1题，共呈现6题给考生吗？第二单元 8594

2、 有重复元素的排列问题；#include #include #include using namespace std;int total=0;int Findsame(char list,int k,int i) int mark=0; int j; for(j=k; ji; j+) if(listj = listi) mark = 1; break; if(mark=1) return 1; else return 0; /交换元素void Swap(char &a,char &b) char temp; temp=a; a=b; b=temp;/递归全排列void Perm(char li

3、st,int k,int m) /产生listk:m的所有排列 if(k=m) / 开始index = 结束index int i; for(i=0; im; i+) /只剩下1个元素 printf(%c,listi); printf(n); total+; else /还有多个元素带排列，递归产生排列 int i; for(i=k; im; i+) if (Findsame(list,k,i)/判断第i个元素是否在listk,i1中出现过 continue; /*int mark = 0; for(int j = k; j i; j +) if(listj = listi) mark = 1

4、; break; if(1 = mark) continue;*/ Swap(listk,listi); Perm(list,k+1,m); Swap(listk,listi); int main() int n; scanf(%d,&n); char listn; scanf(%s,list); Perm(list,0,n); printf(%d,total); return 0;9718 整数因子分解；#include using namespace std;#include #include int total=0;void count(int n) if(n=1) total+; el

5、se int i; for(i=2;i=n;i+) if(n%i=0) count(n/i); int main() int n; scanf(%d,&n); count(n); printf(%d,total);11088 整数划分的扩展问题；/* 题目求： （1）正整数n划分为若干正整数之和，最大加数不超过m的划分数 （2）正整数n划分为不超过m个正整数之和的划分数 （3）正整数n划分为若干正奇整数之和的划分数 （4）正整数n划分为互不相同正整数之和的划分数 约定： 整数划分无顺序，比如对7划分，认为2 2 3和3 2 2和2 3 2为同一种划分。*/#include #include #

6、include using namespace std;int q1(int n,int m) /问题（1）跟问题（2）的计数是相同的 if(n1)|(m1) return 0; if(n=1)|(m=1) return 1; if(nm) return q1(n,n); if(n=m) return q1(n,m-1)+1; return q1(n,m-1)+q1(n-m,m);int q2(int n,int m) /问题（3）跟问题（4）的计数是相同的 int gn+1n+1, fn+1n+1; / fij表示将i划分为j个奇数的划分数, /gij表示将i划分为j个偶数的划分数 for(

7、int i=0; i=n; i+) /二维数组初始化 for(int j=0; j=n; j+) fij=gij=0; f00=1; g00=1; for(int i=1; i=n; i+) for(int j=1; j=i; j+) gij = fi-jj; fij = gi-jj + fi-1j-1; int res = 0; for(int i=0; i=n; i+) res += fni; return res;int main() int n,m; int temp1,temp2; scanf(%d %d,&n,&m); temp1=q1(n,m); temp2=q2(n,m); p

8、rintf(%d %d %d %d,temp1,temp1,temp2,temp2);17082 两个有序数序列中找第k小#include #include #include using namespace std;#define maxn int amaxn,bmaxn,k;int f(int xbeg,int xend,int ybeg,int yend) int xMid=(xend + xbeg) / 2; /X序列中间位置为 xMid int yMid=(yend + ybeg) / 2;/序列Y中间位置为yMid int halflen= xMid - xbeg + yMid -

9、ybeg + 2; /X左段和Y左段元素个数合计为halfLen if(ybeg yend) return axbeg+k-1;/递归边界,X序列为空时，直接返回Y序列的第k小元素。 if(xbeg xend) return bybeg+k-1;/递归边界,Y序列为空时，直接返回X序列的第k小元素。 if(axMid byMid) if(k halflen) return f(xbeg, xend, ybeg, yMid-1); k = k - (xMid - xbeg + 1); return f(xMid+1, xend, ybeg, yend); else if(k halflen) r

10、eturn f(xbeg, xMid-1, ybeg, yend); k = k - ( yMid - ybeg + 1); return f(xbeg, xend, yMid+1, yend); int main() int m,n,i; scanf(%d%d%d,&m,&n,&k); for(i=0; im; i+) scanf(%d,&ai); for(i=0; in; i+) scanf(%d,&bi); printf(%d,f(0,m-1,0,n-1); return 0;第三单元8596 最长上升子序列；#include #include using namespace std;/

11、 找出数组中最大值int maxL(int f,int n) int temp =0; for(int i = 0; i temp) temp = fi; return temp;/ 求上升子序列长度int LOSubstr(int a, int f, int n) int i,j,k; f0 = 1; for(i = 1; i n; i+) k = 0; for(j = 0; j i; j+) / 与i之前每一个比较 if(aj = ai & k n; if(n = 0) / 退出 break; int an,fn; for(int i = 0; i n; i+) / 读入序列 scanf(

12、%d,&ai); printf(%dn,LOSubstr(a,f,n); printf(n); return 0;8601最大长方体问题；#include #include #include using namespace std;const int N=55;int numNNN;void input(int m,int n,int k) int flag =0;/检测是否全为负数 int i,j,l; for(i=0; im; i+) for(j=0; jn; j+) for(l=0; l=0) flag=1; int check(int m,int n,int k) int flag =

13、0;/检测是否全为负数 int i,j,l; for(i=0; im; i+) for(j=0; jn; j+) for(l=0; l=0) flag=1; return flag;int maxSum(int a,int n) int sum=a0,b=0; for(int i=0; i0) b+=ai; else b=ai; if(sumb) sum=b; return sum;int maxSum2(int aNN,int m,int n) int sum=a00; int bN,i,j,k; for(i=0; im; i+) memset(b,0,sizeof(b); for(j=i;

14、 jm; j+) for(k=0; ksum) sum=max; return sum;int maxSum3(int aNNN,int m,int n,int k) int bNN; int i,j,l; int sum=a000,max=0; for(i=0; im; i+) memset(b,0,sizeof(b); for(j=i; jm; j+) for(l=0; ln; l+) for(int t=0; tsum) sum=max; return sum;int main() int m,n,k; scanf(%d %d %d,&m,&n,&k); if(m=1&m=1&n=1&k

15、=50) input(m,n,k); int sum=maxSum3(num,m,n,k); if(check(m,n,k)=1) printf(%d,sum); else printf(%d,0); return 0;10303 数字三角；#include #include #include #include using namespace std;int main() int n; scanf(%d,&n); int arrn+1n+1; int resn+1n+1; memset(arr, -1, sizeof(int); memset(res, -1, sizeof(int); for

16、 (int i = 1; i = n; i+) for (int j = 1; j = i; j+) scanf(%d,&arrij); / 初始化res结果数组 for (int i = 1; i = 1; i-) for (int j = 1; j = i; j+) / 动规填表 resij = max(resi+1j, resi+1j+1) + arrij; printf(%dn,res11);/最大路径和值 / 找出靠右路径 int y = 1; printf(%d ,arr1y);/顶部最大 for (int i = 2; i = n; i+) / 从上往下找，只需要比较 y 和 y

17、+1，相应输出 “最大值下标对应的” 原值 if (resiy = resiy+1) printf(%d ,arriy+1); y = y+1;/更新y else printf(%d ,arriy); return 0;11077 最长公共子字符串；#include#include#includeusing namespace std;int c1000010000;char str110000;char str210000;void func(int m,int n) if(m0)|(n0) return ; for(int i=0; im; i+) for(int j=0; jn; j+)

18、 cij=0; /c数组初始化 int besti=0,bestj=0; int count=0; for(int i=0; im; i+) for(int j=0; jn; j+) if(str1i=str2j) if(i=0)|(j=0) cij=1; /增加判断是否为第一个，第一个不能再向下 else cij=ci-1j-1 + 1 ; else cij=0; for(int i=0; im; i+) for(int j=0; jcount) count=cij; /查找最长子字符串 besti=i; bestj=j; printf(%dn,count); if(count=0) pri

19、ntf(n);/公共子字符串长度为1，输出空行 else for(int i=besti-count+1; i=besti; i+) printf(%c,str1i);/否则输出靠X左边（如果多个）子字符串int main() int m=0; int n=0; scanf(%s,str1); scanf(%s,str2); m=strlen(str1); n=strlen(str2); func(m,n); return 0;11078 不能移动的石子合并#include#includeusing namespace std;#define x 100int mxx,px,sumx;int

20、n,minnum,maxnum;int maxsxx,minsxx;void MinStone(),MaxStone(),LineStone();int main()int i;cinn;for(i=1;ipi;sum1=p1;for(i=2;i=n;i+)sumi=sumi-1+pi;MinStone();coutm1n ;MaxStone();coutm1nendl; /直线for(i=0;in;i+)pi=pi+1;sum0=p0;for(i=1;in;i+)sumi=sumi-1+pi;LineStone();coutminnum maxnumendl; /环return 0;void

21、 MinStone()int i,j,k,r,t,stonesum;for(i=1;i=n;i+)mii=0;for( r=2;r=n;r+)for(i=1;i1)stonesum=sumj-sumi-1;elsestonesum=sumj;for(k=i;kj;k+)t=mik+mk+1j+stonesum;if(tmij)mij=t;void MaxStone()int i,j,k,r,t,stonesum;for(i=1;i=n;i+)mii=0;for(r=2;r=n;r+)for(i=1;i1)stonesum=sumj-sumi-1;elsestonesum=sumj;for( k

22、=i;kmij)mij=t;int min(int i,int j)if(i=j)return i;elsereturn j;int sums(int i,int j)if(i+j=n)return sums(i,n-i-1)+sums(0,(i+j)%n);elsereturn sumi+j-(i0?sumi-1:0);void LineStone()int i,j,k;for(i=0;in;i+)minsi0=maxsi0=0;for(j=1;jn;j+)for(i=0;in;i+)minsij=;maxsij=0;for(k=0;kj;k+)minsij=min(minsik+mins(

23、i+k+1)%nj-k-1+sums(i,j),minsij);maxsij=max(maxsik+maxs(i+k+1)%nj-k-1+sums(i,j),maxsij);minnum=mins0n-1;maxnum=maxs0n-1;for(i=0;iright - (struct Region *)b)-right;int main() int n; int i,a,b,count=1,begin; scanf(%d,&n); for(i=0; in; i+) scanf(%d%d,&a,&b); Regi.right=b; Regi.left=a; qsort(Reg,n,sizeof

24、(Reg0),cmp); /把区间终点从小到大排序/下面开始统计独立的区间数 begin=Reg0.right; for(i=1; in; i+) if(begin = Regi.left) /注意是 = 因为两个区间的终点和始点在一起是算独立的 begin=Regi.right; count+; printf(%dn,n-count); return 0;11079 可以移动的石子合并#include #include #include using namespace std;/*测试数据：7 345 13 12 16 9 5 226 31 2 3 4 5 6*/int main() int

25、 n,k; cin n k; int stonen+10; for (int i = 0; i stonei; int cur; int minC = 0,maxC = 0; int minTemp, maxTemp; sort(stone, stone + n); cur = n-1; maxTemp = stonecur; while (cur != 0) / 求最大 maxTemp = maxTemp + stonecur - 1; maxC += maxTemp; cur-; /假设石头每堆个数放于stone1stonen,且stonen之后最多k-1个数组单元为可写; while (

26、n % (k - 1) != 1) stonen+ = 0; sort(stone, stone + n); cur = 0; minTemp = stonecur; while (cur = n - k) / 求最小 for (int i = 0; i k - 1; i+) stonecur + k-1 += stonecur + i; minC += stonecur + k-1; cur += k-1; sort(stone, stone + n); cout minC maxC; cout endl; return 0;第五单元8600 骑士问题；#include #include #

27、include #define MAX_N 8 / 棋盘总数（包括添加的边界）#define NBRS 8 / 可达相邻方位数using namespace std;int gridMAX_NMAX_N;/ 棋盘class Position/ 方位类 public : int row; int col;Position offsetNBRS;/ 初始化，移动的相对位移void initOffset() offset0.row = 2;offset0.col = -1;/ 右，上 offset1.row = 2;offset1.col = 1;/ 右，下 offset2.row = 1;offs

28、et2.col = 2;/ 下，右 offset3.row = -1;offset3.col = 2;/ 下，左 offset4.row = -2;offset4.col = 1;/ 左，下 offset5.row = -2;offset5.col = -1;/ 左，上 offset6.row = -1;offset6.col = -2;/ 上，左 offset7.row = 1;offset7.col = -2;/ 上，右/ 返回最短步数，-999则为无法到达int FindPath(Position start, Position finish) if (start.row = finis

29、h.row & start.col = finish.col) return 0; initOffset();/ 初始化相对位移 queue Q;/ 队列 Q.push(start);/ 起点入队列 / 标记可达相邻方格 while (true) if (Q.size() = 0) / 队列空，无解 return -999; Position here = Q.front();/ 取队列首扩展 Q.pop();/ 列首出列 for (int i = 0; i NBRS; i+) / 试探NBRS共8个方位 Position nbr; nbr.row = here.row + offseti.r

30、ow; nbr.col = here.col + offseti.col; if (nbr.row 0 | nbr.col = MAX_N | nbr.col = MAX_N) / 保证nbr合法，省去原代码的初始化围墙工作 continue; if (gridnbr.rownbr.col = 0) / 未标记 gridnbr.rownbr.col = gridhere.rowhere.col + 1;/ 计步 if (nbr.row = finish.row & nbr.col = finish.col) return gridfinish.rowfinish.col;/ 已找到骑士终点位置

31、 /break; Q.push(nbr);/ 邻居入队列 / 将输入的a,b,c,d,e,f,g,h转换成相应数字int getColNum(char c) int row; switch (c) case a: row = 1; break; case b: row = 2; break; case c: row = 3; break; case d: row = 4; break; case e: row = 5; break; case f: row = 6; break; case g: row = 7; break; case h: row = 8; break; default: row = -1; break; return row;int main() int count = 0;/ 计数，当前第几组数据 while (true) count +; int hinder;/ 障碍个数 cin hinder; if (hinder = -1) / -1终止 break; memset(grid, 0, (MAX_N * MAX_N) * sizeof(int);/ 初始化数组 Position start;/ 骑士起点 Position finish;/ 骑士终点 string loc;/ 获取输入字符串