基本题一基本递归算法

基本题一：基本递归算法一、 实验目的与要求1、 熟悉C/C++语言的集成开发环境；2、 通过本实验加深对递归过程的理解二、 实验内容：掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。三、 实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。四、 实验步骤理解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编的程序；验证分析实验结果；整理出实验报告。五、 程序清单#include<iostream>usingnamespacestd;intq(intn,intm){if((n<1)||(m<1))return0;if((n==1)||(m==1))return1;if(n<m)returnq(n,n);if(n==m)returnq(n,m-1)+1;returnq(n,m-1)+q(n-m,m);}intmain(){inta,b;cout<<"请输入整数a:";cin>>a;b=q(a,a);cout<<"整数a的划分多少种:"<<b<<endl;return0;}六、 实验结果监3HC:\Users\Administrator\Desktop\E®\^^l\Debug\l-l.e-xe"罂"少种FPressanykeytocontinue基本题二：棋盘覆盖问题一、 实验目的与要求1、 掌握棋盘覆盖问题的算法；2、 初步掌握分治算法二、 实验题：盘覆盖问题：在一个2kX2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。三、 实验提示voidchessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,//L型骨牌号s=size/2;//分割棋盘//覆盖左上角子棋盘if(dr<tr+s&&dc<tc+s)//特殊方格在此棋盘中chessBoard(tr,tc,dr,dc,s);else{//此棋盘中无特殊方格//用t号L型骨牌覆盖右下角board[tr+s-1][tc+s-1]=t;//覆盖其余方格chessBoard(tr,tc,tr+s-1,tc+s-1,s);}//覆盖右上角子棋盘if(dr<tr+s&&dc>=tc+s)//特殊方格在此棋盘中chessBoard(tr,tc+s,dr,dc,s);else{//此棋盘中无特殊方格//用t号L型骨牌覆盖左下角board[tr+s-1][tc+s]=t;//覆盖其余方格chessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆盖左下角子棋盘if(dr>=tr+s&&dc<tc+s)//特殊方格在此棋盘中chessBoard(tr+s,tc,dr,dc,s);else{//用t号L型骨牌覆盖右上角board[tr+s][tc+s-1]=t;//覆盖其余方格chessBoard(tr+s,tc,tr+s,tc+s-1,s);}//覆盖右下角子棋盘if(dr>=tr+s&&dc>=tc+s)//特殊方格在此棋盘中chessBoard(tr+s,tc+s,dr,dc,s);else{//用t号L型骨牌覆盖左上角board[tr+s][tc+s]=t;//覆盖其余方格chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}四、程序清单#include<iostream>#include<iomanip>usingnamespacestd;inttile=1;intboard[1024][1024];voidChessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,//L型骨牌号s=size/2;//分割棋盘//覆盖左上角子棋盘if(dr<tr+s&&dc<tc+s)//特殊方格在此棋盘中ChessBoard(tr,tc,dr,dc,s);else{//此棋盘中无特殊方格//用t号L型骨牌覆盖右下角board[tr+s-1][tc+s-1]=t;//覆盖其余方格ChessBoard(tr,tc,tr+s-1,tc+s-1,s);}//覆盖右上角子棋盘if(dr<tr+s&&dc>=tc+s)//特殊方格在此棋盘中ChessBoard(tr,tc+s,dr,dc,s);else{//此棋盘中无特殊方格//用t号L型骨牌覆盖左下角board[tr+s-1][tc+s]=t;//覆盖其余方格ChessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆盖左下角子棋盘if(dr>=tr+s&&dc<tc+s)//特殊方格在此棋盘中ChessBoard(tr+s,tc,dr,dc,s);else{//用t号L型骨牌覆盖右上角board[tr+s][tc+s-1]=t;//覆盖其余方格ChessBoard(tr+s,tc,tr+s,tc+s-1,s);}//覆盖右下角子棋盘if(dr>=tr+s&&dc>=tc+s)//特殊方格在此棋盘中ChessBoard(tr+s,tc+s,dr,dc,s);else{//用t号L型骨牌覆盖左上角board[tr+s][tc+s]=t;//覆盖其余方格ChessBoard(tr+s,tc+s,tr+s,tc+s,s);}}voidOutBoard(intsize){inti,j;for(i=0;i<size;i++){for(j=0;j<size;j++){cout<<setw(5)<<board[i][j];}cout<<endl;}}intmain(){intsize,dr,dc;cout<<”请输入棋盘的规格："；cin>>size;cout<<”请输入特殊方格所在的行号和列号：”;cin>>dr>>dc;ChessBoard(0,0,dr,dc,size);OutBoard(size);cout<<"—共有"<<tile<<"个骨牌"<<endl;return0;}五、实验结果提高题一：二分搜索一、 实验目的与要求1、 熟悉二分搜索算法；2、 初步掌握分治算法；二、 实验题1、 设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置I和大于x的最大元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。2、 设有n个不同的整数排好序后存放于t[0:n-1]中，若存在一个下标I,0WiVn，使得t[i]=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O(logn)。三、 实验提示1、用I，j做参数，且采用传递引用或指针的形式带回值。boolBinarySearch(inta[],intn,intx,int&i,int&j){intleft=0;intright=n-1;while(left<right){intmid=(left+right)/2;if(x==a[mid]){i=j=mid;returntrue;}if(x>a[mid])left=mid+1;elseright=mid-1;}i=right;j=left;returnfalse;}intSearchTag(inta[],intn,intx){intleft=0;intright=n-1;while(left<right){intmid=(left+right)/2;if(x==a[mid])returnmid;if(x>a[mid])right=mid-1;elseleft=mid+1;}return-1;}四、程序清单(1)#include<iostream>usingnamespacestd;intb[80],n;boolBinarySearch(inta[],intn,intx);intmain(){cout<<"请问输入多少个元素?"；cin>>n;cout<<"请输入已排好序的元素集合:”;for(intk=0;k<n;k++)cin>>b[k];inty;cout<<"请输入要查找的元素：”；cin>>y;BinarySearch(b,n,y);return0;}boolBinarySearch(inta[],intn,intx){intiJ;intleft=0;intright=n-1;while(left<=right){intmid=(left+right)/2;if(x==a[mid]){i=J=mid;cout<<”你查找的元素序号为："<<i+1<<endl;returntrue;}if(x>a[mid])left=mid+1;elseright=mid-1;｝i=right;j=left;cout<<"你查找的元素不存在，小于它的最大元素和大于它的最小元素分别为:"<<b[i]<<"和"<<bj]<<endl;returnfalse;｝五、实验结果(1)实验二动态规划算法（4学时）基本题一：最长公共子序列问题一、 实验目的与要求1、 熟悉最长公共子序列问题的算法；2、 初步掌握动态规划算法；二、 实验题若给定序列X=｛x1,x2,…,xm｝，则另一序列Z=｛z1,z2,…,zk｝，是X的子序列是指存在一个严格递增下标序列｛i1,i2,…,ik｝使得对于所有j=1,2,…,k有：zj=xij。例如，序列Z=｛B，C，D，B｝是序列X=｛A，B，C，B，D，A，B｝的子序列，相应的递增下标序列为｛2，3，5，7｝。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。给定2个序列X=｛x1,x2,…,xm｝和Y=｛y1,y2,…,yn｝，找出X和Y的最长公共子序列。三、实验提示include"stdlib.h"#include"string.hvoidLCSLength(char*x,char*y,intm,intn,int**c,int**b){inti,j;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{ c[i][j]=c[i][j-1];b[i][j]=3;}}}voidLCS(inti,intj,char*x,int**b){if(i==0||j==0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);printf("%c",x[i]);}elseif(b[i][j]==2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);}四程序清单#include<iostream>#include<stdlib.h>#include<string.h>usingnamespacestd;#defineN20voidLCSLength(charx[N+l],chary[N+l]Jutmjntn,intc[N+l][N+l],intb[N+l][N+l]){intiJ;for(i=1;i<=m;i++)c[i][0]=0;for(i=1;i<=n;i++)c[0][i]=0;for(i=1;i<=m;i++){for(j=l;j<=n;j++){if(x[i]==y[j]){c[i]D]=c[i-l][j-l]+l;b[i]U]=l;}elseif(c[i-l][j]>=c[i]U-l]){c[i]U]=c[i-l]|J];b[i]U]=2;}else{ c[i][j]=c[i]U-l];b[i]U]=3;}}}fbr(ints=l;s<=m;s++){for(intt=l;t<=n;t++){cout«c[s][t];}cout«endl;}coutvv”最长公共子序列长度：“vvc[m][n]vvendl;}voidLCS(intiJntj,charx[N+l],mtb[N+l][N+l])if(i==0IIj==0)return;if(b[i][j]==1){LCS(i-1J-1,x,b);cout<<x[i];}elseif(b[i][j]==2){LCS(i-1j,x,b);}else{LCS(ij-1,x,b);}}intmain(){charx[N+1],y[N+1];intm,n;intb[N+1][N+1];intc[N+1][N+1];cout<<"请输入第一个序列："<<endl;cin>>x+1;cout<<"请输入第二个序列："<<endl;cin>>y+1;m=strlen(x+1);n=strlen(y+1);cout<<"矩阵为："<<endl;LCSLength(x,y,m,n,c,b);cout<<"最长公共子序列为："<<endl;LCS(m,n,x,b);cout<<endl;return0;}五、实验结果基本题二：最大字段和问题一、 实验目的与要求1、 熟悉最长最大字段和问题的算法；2、 进一步掌握动态规划算法；二、 实验题若给定n个整数组成的序列a「a2,a3， an，求该序列形如％+气七+ +an的最大值。 n三、 实验提示intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++)for(intj=i;j<=n;j++){intthissum=0;for(intK=i;k<=j;k++)thissum+=a[k];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}returnsum;}intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++){intthissum=0;for(intj=i;j<=n;j++){thissum+=a[j];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}}returnsum;}四、程序清单#include<iostream>#include<stdlib.h>#include<string.h>usingnamespacestd;intmain(){intMaxSum(intn,int*a,int&besti,int&bestj);int*a=newint[50];intx,n,besti,bestj;cout<<”请输入序列的个数：";cin>>n;cout<<”请输入整数序列：”；for(inti=0;i<n;i++){cin>>a[i];}x=MaxSum(n,a,besti,bestj);cout<<"最大字段和："<<”起始位置："<<besti<<”结束位置："<<bestj<<"最大字段和为："<<x<<endl;;return0;}intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++){intthissum=0;for(intj=i;j<=n;j++){thissum+=a[j];if(thissum>sum){sum=thissum;besti=i;bestj=j;}}}returnsum;}五、实验结果实验三贪心算法（2学时）基本题一：多机调度问题I一、 实验目的与要求1、 熟悉多机调度问题的算法；2、 初步掌握贪心算法；二、 实验题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。三、 实验提示1、 把作业按加工所用的时间从大到小排序2、 如果作业数目比机器的数目少或相等，则直接把作业分配下去3、 如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。typedefstructJob{intID;//作业号inttime;//作业所花费的时间}Job;typedefstructJobNode//作业链表的节点{intID;inttime;JobNode*next;}JobNode,*pJobNode;typedefstructHeader〃链表的表头{ints;pJobNodenext;}Header,pHeader;intSelectMin(Header*M,intm){intk=0;for(inti=1;i<m;i++){if(M[i].s<m[k].s)k=i;}returnk;四、程序清单#include<stdio.h>#defineN10typedefstructnode{intID,time;〃作业所需时间}jobnode;typedefstructNode{intID,avail;//ID机器编号avail每次作业的初始时间}manode;manodemachine[N];jobnodejob[N];/*找出下个作业执行机器*/manode*Find_min(manodea[],intm){manode*temp=&a[0];for(inti=1;i<m;i++)if(a[i].avail<temp->avail)temp=&a[i];}returntemp;}/*对作业时间由大到小进行排序*/voidSort(jobnodet[],intn){jobnodetemp;for(inti=0;i<n-1;i++)for(intj=n-1j>ij--){if(job[j].time>job[j-1].time){temp=job[j];job[j]=job[j-1];job[j-1]=temp;}}}voidmain(){intn,m,temp,i;manode*ma;printf("请问有多少作业需要加工？\n");scanf("%d",&n);printf("请输入各个作业的加工时间：\n");for(i=0;i<n;i++){scanf("%d",&job[i].time);job[i].ID=i+1;}printf("请问有多少台机器可以加工？\n");scanf("%d",&m);for(i=0;i<m;i++)//给机器进行编号并初始化{machine[i].ID=i+1;machine[i].avail=0;}putchar('\n');

if(n<=m){printf("每个作业分配一台机器即可!\n");return;}Sort(job,n);for(i=0;i<n;i++){ma=Find_min(machine,m);printf("机器M%d从%d到%d完成作业％d\n'',ma->ID,ma->avail,ma->avail+job[i].timejob[i]・ID);ma->avail+=job[i].time;}temp=machine[0].avail;for(i=1;i<m;i++){if(machine[i].avail>temp)temp=machine[i].avail;}putchar('\n');printf("完成这批作业的总时间为：%d\n",temp);while(1);}五、实验结果作业数〉机器数£.&£.&£.&£.&£.&Lrf-bLrf-bLrf-tlLrf-tlLrf-tl至至至至至mtrtr成完完道兀完£.&£.&£.&£.&£.&Lrf-bLrf-bLrf-tlLrf-tlLrf-tl至至至至至mtrtr成完完道兀完008761154213总时间为二102.作业数<=机器数请I可有多少作业需要加工？蓄输入各个作业的加工时间:78932请问有多少台机器可以加工?6每个作业分配一台机器即可，Press己nykeytocontinue实验四回溯算法和分支限界法(2学时)基本题一：符号三角形问题一、 实验目的与要求1、 掌握符号三角形问题的算法；2、 初步掌握回溯算法；二、 实验题图“+”，下面都是“-”。下图是由14个“+”和14个“-”组成的符号三角形。2个同号下面都是2个异号下面都是““+”，++-+-+++----+-+++--++--+---+计算在一般情况下，符号三角形的第一行有n个符号。符号三角形问题要求对于给定的n，有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。计算三、 实验提示voidTriangle::Backtrack(intt){if((count>half)ll(t*(t-1)/2-count>half))return;if(t>n)sum++;elsefor(inti=0;i<2;i++){p[1][t]=i;count+=i;for(intj=2;j<=t;j++){p[j][t-j+1]=p[j-1][t-j+1]Ap[j-1][t-j+2];

count+=p[j][t-j+1];}Backtrack(t+1);for(intj=2;j<=t;j++)count-=p[j][t-j+1];count-=i;}}四、程序清单#include<iostream>usingnamespacestd;typedefunsignedcharuchar;〃便于输出//〃便于输出//第一行符号总数//全部符号总数一半//1计数，即"-"号计数//符号存储空间//符合条件的三角形计数uchar**p;longsum;voidBacktrace(intt) 〃t，第一行第t个符号{inti,j;if(t>n){//符号填充完毕sum++;//打印符号cout<<"第"<<sum<<”个:\n";for(i=1;i<=n;++i){for(j=1;j<i;++j){cout<<"";}for(j=1;j<=n-i+1;++j){cout<<cc[p[i][j]]<<"";}cout<<"\n";}}else{for(i=0;i<2;++i)p[1][t]=i; //第一行第t个符号counter+=i; //"-"号统计，因为”+”的值是0for(j=2;j<=t;++j)//当第一行符号>=2时，可以运算出下面行的某些符号，j可代表行号{p[j][t-j+1]=p[j-1][t-j+1]人p[j-1][t-j+2];//通过异或运算下行符号，t-j+1确定的很巧counter+=p[j][t-j+1];}if((counter<=half)&&(t*(t+1)/2-counter<=half)){//若符号统计未超过半数，并且另一种符号也未超过半数，同时隐含两者必须相等才能结束Backtrace(t+1); //在第一行增加下一个符号}〃回溯，判断另一种符号情况 像是出栈一样，恢复所有对counter的操作for(j=2;j<=t;++j){counter-=p[j][t-j+1];}counter-=i;}intmain(){cout<<”请输入第一行符号个数n：";cin>>n;counter=0;sum=0;half=n*(n+1)/2;inti=0;if(half%2==0){〃总数必须为偶数，若为奇数则无解half/=2;p=newuchar*[n+1];for(i=0;i<=n;++i){p[i]=newuchar[n+1];memset(p[i],0,sizeof(uchar)*(n+1));Backtrace(l);for(i=0;i<=n;++i) 〃删除二维动态数组的方法{delete[]p[i];}delete[]p;}cout<<"\n总共"<<sum<<"个”<<endl;return0;}五、实验结果董船弟一仃符号个魏n：3++—+—第2个：+—+第;个：—++—+第牝+++总共4个Pressanpkeytocontinue基本题二：0—1背包问题|一、 实验目的与要求1、 掌握0—1背包问题的回溯算法；2、 进一步掌握回溯算法；二、 实验题：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大？三、 实验提示template<classTypew,classTypep>TypepKnap<Typew,Typep>::Bound(inti){//计算上界Typewcleft=c-cw;//剩余容量Typepb=cp;//以物品单位重量价值递减序装入物品while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//装满背包if(i<=n)b+=p[i]/w[i]*cleft;returnb;}四、程序清单#include<iostream>usingnamespacestd;classKnap{friendintKnapsack(intp[],intw[],intc,intn);public:voidprint(){for(intm=1;m<=n;m++){cout<<bestx[m]<<"";}cout<<endl;};private:intBound(inti);voidBacktrack(inti);intc;//背包容量intn;//物品数int*w;//物品重量数组int*p;//物品价值数组intcw;//当前重量intcp;//当前价值intbestp;//当前最优值int*bestx;//当前最优解int*x;//当前解};intKnap::Bound(inti){〃计算上界intcleft=c-cw;//剩余容量intb=cp;〃以物品单位重量价值递减序装入物品while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++；}//装满背包if(i<=n)b+=p[i]/w[i]*cleft;returnb;}voidKnap::Backtrack(inti){if(i>n){if(bestp<cp){for(intj=