算法设计与分析上机题

《算法设计与分析上机题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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;j

3、voidPerm(charlist[],intk,intm){//产生list[k:m]的所有排列if(k==m)//开始index==结束index{inti;for(i=0;i

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(n

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]