算法_递归
1 递归实现逆序输出整数
1.本题目要求读入1个正整数n,然后编写递归函数reverse(int n)实现将该正整数逆序输出。
输入格式:
输入在一行中给出1个正整数n。
输出格式:
对每一组输入,在一行中输出n的逆序数。
输入样例:
12345
输出样例:
54321
源代码:
#include <iostream>
using namespace std;
int s=0;
void reverse(int n)
{
if(n>0)
{
s=n%10;
n=n/10;
cout<<s;
reverse(n);
}
}
int main()
{
int n;
cin>>n;
reverse(n);
cout<<endl;
return 0;
}
2 二分查找
2.输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x,使用二分查找算法查找x,输出x所在的下标(0~n-1)及比较次数。若x不存在,输出-1和比较次数。
输入格式:
输入共三行:
第一行是n值;
第二行是n个整数;
第三行是x值。
输出格式:
输出x所在的下标(0~n-1)及比较次数。若x不存在,输出-1和比较次数。
输入样例:
4
1 2 3 4
1
输出样例:
0
2
源代码:
#include <iostream>
#include <algorithm>
using namespace std;
void erfen(int n,int *a,int m)
{
int front=0;
int end=n-1;
int mid;
int i=0;
mid=(front+end)/2;
while(front<end||front==end)
{
++i;
if(a[mid]<m)
front=mid+1;
if(a[mid]>m)
end=mid-1;
if(a[mid]==m)
break;
mid=(front+end)/2;
}
if(a[mid]!=m)
{
cout<<-1<<endl;
cout<<i<<endl;
}
else
{
cout<<mid<<endl;
cout<<i<<endl;
}
}
int main()
{
int n,m;
int a[1000];
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
cin>>m;
erfen(n,a,m);
return 0;
}
3 改写二分搜索算法
3.题目来源:《计算机算法设计与分析》,王晓东
设a[0:n-1]是已排好序的数组,请改写二分搜索算法,使得当x不在数组中时,返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时,i和j相同,均为x在数组中的位置。
输入格式:
输入有两行:
第一行是n值和x值;
第二行是n个不相同的整数组成的非降序序列,每个整数之间以空格分隔。
输出格式:
输出小于x的最大元素的最大下标i和大于x的最小元素的最小下标j。当搜索元素在数组中时,i和j相同。
提示:若x小于全部数值,则输出:-1 0
若x大于全部数值,则输出:n-1的值 n的值
输入样例:
在这里给出一组输入。例如:
6 5
2 4 6 8 10 12
输出样例:
在这里给出相应的输出。例如:
1 2
源代码:
#include <iostream>
using namespace std;
int B(int* a,int x,int low,int heigh,int n)
{
int mid;
while(low<=heigh)
{
mid=(low+heigh)/2;
if(a[mid]==x)
{
cout<<mid<<" "<<mid<<endl;
return 0;
}
else if(a[mid]<x)
{
low=mid+1;
}
else
{
heigh=mid-1;
}
}
if(x<a[0])
{
cout<<-1<<" "<<0<<endl;
return 0;
}
if(x>a[n-1])
{
cout<<n-1<<" "<<n<<endl;
return 0;
}
if(x>a[mid]&&x<a[n-1])
{
cout<<mid<<" "<<mid+1<<endl;
return 0;
}
if(a[0]<x&&x<a[mid])
{
cout<<mid-1<<" "<<mid<<endl;
return 0;
}
return 0;
}
int main()
{
int n,a[1000],x;
cin>>n;
cin>>x;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
B(a,x,0,n-1,n);
return 0;
}
4 分形的递归输出
分形,具有以非整数维形式充填空间的形态特征。通常被定义为“一个粗糙或零碎的几何形状,可以分成数个部分,且每一部分都(至少近似地)是整体缩小后的形状”,即具有自相似的性质。
一个盒状分形定义如下:
度为1的盒分形为:
X
度为2的盒分形为:
X X
X
X X
依次类推,如果B(n-1)表示n-1度的盒分形,则n度的盒分形递归定义如下:
B(n - 1) B(n - 1)
B(n - 1)
B(n - 1) B(n - 1)
请画出度为n的盒分形的图形
输入格式:
输入一系列度,每行给出一个不大于7的正整数。输入的最后一行以-1表示输入结束
输出格式:
对于每个用例,输出用’X’标记的盒状分形。在每个测试用例后输出包含一个短划线“-”的一行。
输入样例:
1
2
3
4
-1
输出样例:
注意:每行的空格请输出完整。
X
X X
X
X X
X X X X
X X
X X X X
X X
X
X X
X X X X
X X
X X X X
X X X X X X X X
X X X X
X X X X X X X X
X X X X
X X
X X X X
X X X X X X X X
X X X X
X X X X X X X X
X X X X
X X
X X X X
X X
X
X X
X X X X
X X
X X X X
X X X X X X X X
X X X X
X X X X X X X X
X X X X
X X
X X X X
X X X X X X X X
X X X X
X X X X X X X X
源代码:
#include <iostream>
#include <cmath>
using namespace std;
char maps[999][999];
void print(int n, int x, int y)
{
//递归边界
if (n == 1){
maps[x][y] = 'X';
}
else{
//n-1的宽m
int m = pow(3, n-2);
//左上方的n-1度盒分形
print(n-1, x, y);
//右上方
print(n-1, x+2*m, y);
//中间
print(n-1, x , y + 2 * m);
//左下方
print(n-1, x + m, y + m);
//右下方
print(n-1,x+2*m,y+2*m);
}
}
int main()
{
int n;
cin >> n;
int i,j;
while (n != -1){
int size = pow(3, n - 1);
for ( i = 0; i < size; i++){
for ( j = 0; j < size; j++){
maps[i][j] = ' ';
maps[i][size] = '\0';
}
}
print(n, 0, 0);
for ( i = 0; i < size; i++)
cout<<maps[i]<<endl;
cout << "-"<<endl;
cin >> n;
}
return 0;
}
5 棋盘覆盖
在一个2^k * 2k(k为正整数,k<=10,length=2k)个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格(其坐标为aa,bb,分别代表行坐标号和列坐标号),以及有四种L型骨牌(如下图)。求用若干块这种L型骨牌实现除该特殊点棋盘的全覆盖。(本题要求采用分治算法做)
输入格式:
输入三个数,分别是aa,bb,length.
输出格式:
输出整个棋盘。其中特殊方格填为0,然后铺棋盘的顺序为:先铺四个子棋盘交界的部分,然后递归的对每个子棋盘按照左上,右上,右下,左下的顺时针顺序铺满棋盘。每一块骨牌中三个方格数字相同,按照顺序标号,即第一块骨牌全标为1,第二块骨牌全标为2,…,以此类推。输出的每个数占4个场宽,右对齐。
输入样例:
1 1 4
表示:特殊格子为(1,1),棋盘有4行4列。
输出样例:
0 2 3 3
2 2 1 3
5 1 1 4
5 5 4 4
源代码:
#include <iostream>
using namespace std;
#define N 90
int Board[N][N];
int tile = 1;
void ChessBoard(int tr,int tc,int dr,int dc,int size)
{
if(size == 1)
{
return;
}
int t = tile++;
int s = size/2;
if(dr<tr+s && dc<tc+s)
{
ChessBoard(tr,tc,dr,dc,s);
}
else
{
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
{
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+s,dr,dc,s);
}
else
{
Board[tr+s][tc+s] = t;
ChessBoard(tr+s,tc+s,tr+s,tc+s,s);
}
if(dr>=tr+s && dc<tc+s)
{
ChessBoard(tr+s,tc,dr,dc,s);
}
else
{
Board[tr+s][tc+s-1] = t;
ChessBoard(tr+s,tc,tr+s,tc+s-1,s);
}
}
int main()
{
int x,y,size;
cin>>x>>y>>size;
for(int i=0; i<90; i++)
{
for(int j=0; j<90; j++)
{
Board[i][j] = 0;
}
}
ChessBoard(0,0,x-1,y-1,size);
for(int i=0; i<size; i++)
{
for(int j=0; j<size; j++)
printf("%4d",Board[i][j]);
cout<<endl;
}
return 0;
}