欢迎来到天天文库
浏览记录
ID:40507730
大小:29.37 KB
页数:31页
时间:2019-08-03
《算法设计与分析上机题》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
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#includeusingnamespacestd;inttotal=0;intFindsame(charlist[],intk,inti){intmark=0;intj;for(j=k;j3、voidPerm(charlist[],intk,intm){//产生list[k:m]的所有排列if(k==m)//开始index==结束index{inti;for(i=0;i4、ist[j]==list[i]){mark=1;break;}}if(1==mark)continue;*/Swap(list[k],list[i]);Perm(list,k+1,m);Swap(list[k],list[i]);}}}intmain(){intn;scanf("%d",&n);charlist[n];scanf("%s",list);Perm(list,0,n);printf("%d",total);return0;}9718整数因子分解;#includeusingnamespacestd;#include#inclu5、deinttotal=0;voidcount(intn){if(n==1){total++;}else{inti;for(i=2;i<=n;i++){if(n%i==0){count(n/i);}}}}intmain(){intn;scanf("%d",&n);count(n);printf("%d",total);}11088整数划分的扩展问题;/*题目求:(1)正整数n划分为若干正整数之和,最大加数不超过m的划分数(2)正整数n划分为不超过m个正整数之和的划分数(3)正整数n划分为若干正奇整数之和的划分数(4)正整数n划分为互不相同正整数之和的划分数6、约定:整数划分无顺序,比如对7划分,认为223和322和232为同一种划分。*/#include#include#includeusingnamespacestd;intq1(intn,intm)//问题(1)跟问题(2)的计数是相同的{if((n<1)7、8、(m<1))return0;if((n==1)9、10、(m==1))return1;if(n11、问题(3)跟问题(4)的计数是相同的{intg[n+1][n+1],f[n+1][n+1];//f[i][j]表示将i划分为j个奇数的划分数,//g[i][j]表示将i划分为j个偶数的划分数for(inti=0;i<=n;i++)//二维数组初始化{for(intj=0;j<=n;j++){f[i][j]=g[i][j]=0;}}f[0][0]=1;g[0][0]=1;for(inti=1;i<=n;i++){for(intj=1;j<=i;j++){g[i][j]=f[i-j][j];f[i][j]=g[i-j]
3、voidPerm(charlist[],intk,intm){//产生list[k:m]的所有排列if(k==m)//开始index==结束index{inti;for(i=0;i4、ist[j]==list[i]){mark=1;break;}}if(1==mark)continue;*/Swap(list[k],list[i]);Perm(list,k+1,m);Swap(list[k],list[i]);}}}intmain(){intn;scanf("%d",&n);charlist[n];scanf("%s",list);Perm(list,0,n);printf("%d",total);return0;}9718整数因子分解;#includeusingnamespacestd;#include#inclu5、deinttotal=0;voidcount(intn){if(n==1){total++;}else{inti;for(i=2;i<=n;i++){if(n%i==0){count(n/i);}}}}intmain(){intn;scanf("%d",&n);count(n);printf("%d",total);}11088整数划分的扩展问题;/*题目求:(1)正整数n划分为若干正整数之和,最大加数不超过m的划分数(2)正整数n划分为不超过m个正整数之和的划分数(3)正整数n划分为若干正奇整数之和的划分数(4)正整数n划分为互不相同正整数之和的划分数6、约定:整数划分无顺序,比如对7划分,认为223和322和232为同一种划分。*/#include#include#includeusingnamespacestd;intq1(intn,intm)//问题(1)跟问题(2)的计数是相同的{if((n<1)7、8、(m<1))return0;if((n==1)9、10、(m==1))return1;if(n11、问题(3)跟问题(4)的计数是相同的{intg[n+1][n+1],f[n+1][n+1];//f[i][j]表示将i划分为j个奇数的划分数,//g[i][j]表示将i划分为j个偶数的划分数for(inti=0;i<=n;i++)//二维数组初始化{for(intj=0;j<=n;j++){f[i][j]=g[i][j]=0;}}f[0][0]=1;g[0][0]=1;for(inti=1;i<=n;i++){for(intj=1;j<=i;j++){g[i][j]=f[i-j][j];f[i][j]=g[i-j]
4、ist[j]==list[i]){mark=1;break;}}if(1==mark)continue;*/Swap(list[k],list[i]);Perm(list,k+1,m);Swap(list[k],list[i]);}}}intmain(){intn;scanf("%d",&n);charlist[n];scanf("%s",list);Perm(list,0,n);printf("%d",total);return0;}9718整数因子分解;#includeusingnamespacestd;#include#inclu
5、deinttotal=0;voidcount(intn){if(n==1){total++;}else{inti;for(i=2;i<=n;i++){if(n%i==0){count(n/i);}}}}intmain(){intn;scanf("%d",&n);count(n);printf("%d",total);}11088整数划分的扩展问题;/*题目求:(1)正整数n划分为若干正整数之和,最大加数不超过m的划分数(2)正整数n划分为不超过m个正整数之和的划分数(3)正整数n划分为若干正奇整数之和的划分数(4)正整数n划分为互不相同正整数之和的划分数
6、约定:整数划分无顺序,比如对7划分,认为223和322和232为同一种划分。*/#include#include#includeusingnamespacestd;intq1(intn,intm)//问题(1)跟问题(2)的计数是相同的{if((n<1)
7、
8、(m<1))return0;if((n==1)
9、
10、(m==1))return1;if(n11、问题(3)跟问题(4)的计数是相同的{intg[n+1][n+1],f[n+1][n+1];//f[i][j]表示将i划分为j个奇数的划分数,//g[i][j]表示将i划分为j个偶数的划分数for(inti=0;i<=n;i++)//二维数组初始化{for(intj=0;j<=n;j++){f[i][j]=g[i][j]=0;}}f[0][0]=1;g[0][0]=1;for(inti=1;i<=n;i++){for(intj=1;j<=i;j++){g[i][j]=f[i-j][j];f[i][j]=g[i-j]
11、问题(3)跟问题(4)的计数是相同的{intg[n+1][n+1],f[n+1][n+1];//f[i][j]表示将i划分为j个奇数的划分数,//g[i][j]表示将i划分为j个偶数的划分数for(inti=0;i<=n;i++)//二维数组初始化{for(intj=0;j<=n;j++){f[i][j]=g[i][j]=0;}}f[0][0]=1;g[0][0]=1;for(inti=1;i<=n;i++){for(intj=1;j<=i;j++){g[i][j]=f[i-j][j];f[i][j]=g[i-j]
此文档下载收益归作者所有