算法实验一实验报告

武汉轻工大学数学与计算机学院算法分析试验汇报指导老师：汤小月专业：信息管理与信息系统班级：信管1201班学号：姓名：试验一分治与递归（2课时）基本题一：基本递归算法一、试验目标与要求熟悉C/C++语言集成开发环境；经过本试验加深对递归过程了解二、试验内容：掌握递归算法概念和基本思想，分析并掌握“整数划分”问题递归算法。三、试验题任意输入一个整数，输出结果能够用递归方法实现整数划分。详细程序代码以下：#include<iostream>usingnamespacestd;intq(intn,intm)//正整数n最大加数m划分数{ if((n<1)||(m<1))return0;//n，m需>1 if((n==1)||(m==1))return1;//正整数或者最大加数=1时，只有一个划分情况 if(n<m)returnq(n,n);//最大加数实际不能大于正整数本身 if(n==m)returnq(n,m-1)+1;//递归，n划分由其q（n，m-1）和n1=n组成 returnq(n,m-1)+q(n-m,m);//正整数n最大加数n1小于m划分由n1=m划分和n1=m-1划分组成}voidmain(){ intn,m; cout<<"请输入一个整数n（-1退出）："<<endl; cin>>n; while(n>=1) { cout<<"请输入一个最大加数m："<<endl; cin>>m; cout<<"正整数n最大加数m划分数为"<<q(n,m)<<endl; cout<<"请输入一个整数n（-1退出）："<<endl; cin>>n; }}进行编译以下：运行结果以下：四、试验步骤了解算法思想和问题要求；编程实现题目要求；上机输入和调试自己所编程序；验证分析试验结果；整理出试验汇报。

基本题二：棋盘覆盖问题一、试验目标与要求1、掌握棋盘覆盖问题算法；2、初步掌握分治算法二、试验题：

盘覆盖问题：在一个2k×2k个方格组成棋盘中，恰有一个方格与其它方格不一样，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示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>usingnamespacestd;intboard[65][65],tile;/*tile为纸片编号*/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);}}//输出最终结果voidresult(intb[][65],intn){inti,j;for(i=1;i<=n;i++) {for(j=1;j<=n;j++) cout<<b[i][j]<<""; cout<<endl;}}intmain(){intsize,dr,dc; cout<<"选择输入4种不一样形态L型骨牌中一个(4/8/16/64):"<<endl; cin>>size; cout<<"请输入特殊块位置(x,y):"<<endl; cin>>dr>>dc; cout<<"结果以下："<<endl;board[dr][dc]=-1;tile++;chessBoard(1,1,dr,dc,size);result(board,size);}运行调试结果以下:试运行结果以下:

提升题一：二分搜索一、试验目标与要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、试验题1、设a[0:n-1]是一个已排好序数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x最大元素位置I和大于x最小元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中位置。2、设有n个不一样整数排好序后存放于t[0:n-1]中，若存在一个下标I，0≤i＜n，使得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;

else

right=mid-1;2

}

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;

else

left=mid+1;

}

return-1;}试验题1代码编写以下:#include<iostream>usingnamespacestd;voidBubbleSort(int*pData,intCount)//冒泡排序函数，pData中从0位置处存了Count个数，该函数将数组中元素排序{intiTemp;for(inti=1;i<Count;i++){for(intj=Count-1;j>=i;j--) {if(pData[j]<pData[j-1]) {iTemp=pData[j-1];pData[j-1]=pData[j];pData[j]=iTemp; } }}}boolBinarySearch(inta[],intn,intx,int&i,int&j)//数组a大小为n，数组中存放了已经排好序（升序）数列{intleft=0;intright=n-1;intmid=0;while(left<right){mid=(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;}intmain(){inta[100];cout<<"请输入数组中数个数，小于100:";intnum=0;cin>>num;cout<<"请输入数组中数："<<endl;for(inti=0;i<num;i++)cin>>a[i];//下面将数组a排成升序BubbleSort(a,num);cout<<"下面输出排序后数组："<<endl;for(i=0;i<num;i++)printf("%4d",a[i]);cout<<endl;cout<<"请输入要查找数:";intx=0;cin>>x;intj=0;if(BinarySearch(a,num,x,i,j))cout<<"找到了，位置为"<<i<<endl;elsecout<<"没找到,小于该数最大元素位置为"<<i<<"大于该数最小元素位置为"<<j<<"（第一个元素位置为0）"<<endl;return0;}试运行调试结果以下:运行结果以下列图所表示:试验题2编写代码以下:#include<iostream>usingnamespacestd;/*依照题目中隐含要求，现在将问题进行简化，假设数组中存放数全部为整数*/voidBubbleSort(int*pData,intCount)//冒泡排序函数，pData中从0位置处存了Count个数，该函数将数组中元素排升序{intiTemp;for(inti=1;i<Count;i++){for(intj=Count-1;j>=i;j--) {if(pData[j]<pData[j-1]) {iTemp=pData[j-1];pData[j-1]=pData[j];pData[j]=iTemp; } }}}boolBinaryFind_iei(inta[],intn,int&i)//数组a大小为n，数组中存放了已经排好序（升序）数列{intleft=0;intright=n-1;intmid=0;while(left<right){mid=(left+right)/2;if(mid==a[mid]){i=mid;returntrue;//找到了}elseif(mid>a[mid])left=mid;elseright=mid;}returnfalse;}intmain(){inta[100];cout<<"请输入数组中数个数，小于100:";intnum=0;cin>>num;cout<<"请输入数组中数："<<endl;for(intii=0;ii<num;ii++)cin>>a[ii];//下面将数组a排成升序BubbleSort(a,num);cout<<"下面输出排序后数组："<<endl;for(inti=0;i<num;i++)printf("%4d",a[i]);cout<<endl;intj=0;if(BinaryFind_iei(a,num,j))cout<<"找到了，位置为"<<j<<endl;elsecout<<"不存在符合第i个位置等于i元素。"<<endl;return0;}试运行调试结果以下:运行结果以下:结果分析：利用分治策略求解时，所需时间取决于分解后子问题个数、子问题规模大小等素，而二分法，因为其划分简单和均匀特点，是经常采取一个有效方法，比如二分法检索。

提升题二：用分治法实现元素选择一、试验要求与目标1、了解分治法基本思想，掌握递归程序编写方法；2、使用分治法编程，求解线形序列中第k小元素。二、试验内容给定线形序列集中n个元素和一个整数k，1≤k≤n，输出这n个元素中第k小元素值及其位置。简述该算法原理、步骤。对该算法与直接排序查找进行比较。编写并调试程序。测试要求：元素个数不少于100；分三种情况：k=1、k=n和k=中位数。编写程序代码以下所表示：#include<stdlib.h>#include<time.h>#include<stdio.h>#include<malloc.h>intpartition(inta[],intp,intr){intz=p,x=r+1;inty=a[p];intt;while(1){while(a[++z]<y&&z<r);//空循环，不符合条件时向下执行while(a[--x]>y);if(z>=x)break;t=a[z];a[z]=a[x];a[x]=t;}a[p]=a[x];a[x]=y;returnx;}voidquicksort(inta[],intp,intr){intq;if(p<r){q=partition(a,p,r);quicksort(a,p,q-1);quicksort(a,q+1,r);}}intmain(){for(;;){intk,*a,*b,n,i,d,s;printf("请输入数组个数:");scanf("%d",&n);printf("\n");a=(int*)malloc(sizeof(int)*n);//给数组a分配空间srand((unsigned)time(NULL));b=(int*)malloc(sizeof(int)*n);//给数组b分配空间srand((