2020-11-27 PTA算法_递归部分题目和代码

算法_递归

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型骨牌实现除该特殊点棋盘的全覆盖。(本题要求采用分治算法做)
2020-11-27 PTA算法_递归部分题目和代码
输入格式:
输入三个数,分别是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;
}
上一篇:棋盘覆盖问题(分治法)使用JavaScript可视化!


下一篇:二阶段提交的创新者,阿里私生子seata的公子做派,进来了解一下?(一)