[递归专题打卡]2021 6.30-7.2

2021/6/30

链接：​​https://ac.nowcoder.com/acm/problem/14310​​​
 

★字符串逆序

输入一个字符串，长度在100以内，按相反次序输出其中的所有字符。

输入描述:

输入一个字符串

输出描述:

输出反序的字符串

示例1

输入

tsinghua

输出

auhgnist

解答:

#include<stdio.h>
#include<string.h>
int lenth;
void Output(char* a,int n)
{
  if(n==lenth)
    return;
  Output(a,n+1);
  printf("%c",a[n]);
}
int main()
{
  char a[101];
  scanf("%s",a);
  lenth=strlen(a);
  Output(a,0);
  return 0;
}

链接：​​https://ac.nowcoder.com/acm/problem/14320​​​
 

★杨辉三角

杨辉三角形又称Pascal三角形，它的第i+1行是(a+b)i的展开式的系数。

它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。

下面给出了杨辉三角形的前4行：

   1

  1 1

 1 2 1

1 3 3 1

给出n，输出它的前n行。

输入描述:

输入包含一个数n。

输出描述:

输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次输出，中间使用一个空格分隔。请不要在前面和后面输出多余的空格。

示例1

输入

4

输出

1 1 1 1 2 1 1 3 3 1

说明

1 <= n <= 34。

解答:

#include<iostream>
#define Maxn 100000
using namespace std;

int N;
int a[Maxn];
void Output(int n)
{
  if(n==N+1)
    return ;
  a[n]=1;
//  for(int j=2;j<n;j++){
//    a[j]=a[j-1]+a[j];
//  }//与倒序循环有微妙差距 
  for(int j=n-1;j>=2;j--){
    a[j]=a[j-1]+a[j];
  }
  for(int j=1;j<=n;j++){
    if(j==1){
      cout<<a[j];
    }else{
      cout<<' '<<a[j];
    }
  }
  cout<<endl;
  Output(n+1);  
}
int main()
{
  a[1]=1;
  cin>>N;
  Output(1);
  return 0;
}

链接：​​https://ac.nowcoder.com/acm/problem/14356​​​
 

★s01串

s01串初始为"0"
按以下方式变换
0变1，1变01

输入描述:

1个整数(0~19)

输出描述:

n次变换后s01串

示例1

输入

3

输出

101

说明

初始为0 第一次变化后为 1 第二次变化后为 01 第三次变化后为 101

备注:

数据规模和约定 0~19

解答:

#include<iostream>
using namespace std;

string Output(int n)
{
  if(n==0) return "0";
  if(n==1) return "1";
  return Output(n-2)+Output(n-1);
}
int main()
{
  int N;
  cin>>N;
  cout<<Output(N);
  return 0;
}

2021/7/1

链接：​​https://ac.nowcoder.com/acm/problem/14703​​  

★★素数回文

现在给出一个素数，这个素数满足两点：

1、  只由1-9组成，并且每个数只出现一次，如13,23,1289。

2、  位数从高到低为递减或递增，如2459，87631。

请你判断一下，这个素数的回文数是否为素数（13的回文数是131,127的回文数是12721）。

输入描述:

输入只有1行。

第1行输入一个整数t，保证t为素数。

数据保证：9<t<109

输出描述:

输出一行字符串，如果t的回文数仍是素数，则输出“prime”，否则输出"noprime"。

示例1

输入

13

输出

prime

说明

13的回文数是131，131是素数

示例2

输入

17

输出

noprime

说明

17的回文数是171,171不是素数（因子有3）

备注:

素数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。 素数的回文数为题意中的定义，1331不是素数的回文数。

解答:

#include<iostream>
using namespace std;

bool Isprime(long long number)
{
  if(number<2) return false;
  for(int i=2; i<=number/i; i++)
  {
    if(number%i==0)
      return false;
  }
  return true;
}
int main()
{
  char num[10]; 
  long long a,b,c;
  cin>>a;
  for(c=a/10; c!=0; c/=10)
  {
    a*=10;
    a+=c%10;
  }
  
  if(Isprime(a))
    cout<<"prime";
  else
    cout<<"noprime";
  
  return 0;
}

★★★LP钱不够​[简单DP]LP钱不够(数塔问题)​

链接：​​https://ac.nowcoder.com/acm/problem/14839​​​

★最大公约数

输入两个数，求最大公约数。

输入描述:

输入两个数a,b.

输出描述:

输出a和b的最大公约数

示例1

输入

6 3

输出

3

解答:

#include<iostream>
using namespace std;

int gcd(int a,int b){
  if(b==0) return a;
  return gcd(b,a%b); 
}
int main()
{
  int a,b;
  cin>>a>>b;
  cout<<gcd(a,b);
  return 0;
}

2021/7/2

链接：​​https://ac.nowcoder.com/acm/problem/14359​​​
 

★Fibonacci数列

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

输入描述:

输入包含一个整数n。

输出描述:

输出一行，包含一个整数，表示Fn除以10007的余数。

示例1

输入

10

输出

55

示例2

输入

22

输出

7704

备注:

说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。

数据规模与约定

1 <= n <= 1,000,000。

解答:

#include<iostream>
using namespace std;

int main()
{
  int n;
  int num[3]={1,1,0};
  cin>>n;
  
  if(n==1||n==2){
    cout<<"1"; 
  }else{
    for(int i=3; i<=n; i++)
    {
      num[2]=(num[0]+num[1])%10007;
      num[0]=num[1];
      num[1]=num[2];
    }
    cout<<num[2];
  } 
  return 0;
}

★★​[递归 dfs]枚举全排列和所有组合​