递归--练习17（3）

1.素数回文

题目描述

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

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

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

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

输入描述:

输入只有1行。第1行输入一个整数t，保证t为素数。数据保证：9<t<109

输出描述:

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

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
long long huiwen(long long num)
{
  if(num<2)
  {return 0;}
  if(num==2||num==3)
  {return 1;}
  for(long long i=2; i*i<=num;i++)
  {
      if(num%i==0)
      {return 0;}
  }
  return 1;
}
int main()
{
  string s,s1,s2,s3;
  cin>>s1;
  s2=s1;
  reverse(s1.begin(),s1.end());
  s3=s2+s1;
  for(int i=0;i<=s3.size()-1;i++)
  {
	if(i!=s2.size()-1)
	{
	  s+=s3[i];
	}
  }
  long long num=stoll(s);
  if(huiwen(num)==0)
  {cout<<"noprime"<<endl;}
  else
  {cout<<"prime"<<endl;}
}

本题思路：将一个数变成字符串，进行处理后转化回整数，并重新判断其是否为素数

注意：123要变成12321，而不是123321，将s1倒置后要将中间重复部分删去。

2.字母组串

题目描述

由 A,B,C 这3个字母就可以组成许多串。比如：”A”,”AB”,”ABC”,”ABA”,”AACBB” …。现在，小明正在思考一个问题：如果每个字母的个数有限定，能组成多少个已知长度的串呢？

输入描述:

四个整数a，b，c，n（0 ≤ a, b, c, n ≤ 10），空格分隔，分别表示a个A，b个B，c个C 字母，长度为n的串。

输出描述:

一个整数，能组成多少个不同长度为n的串。

#include <iostream>
using namespace std;
int zfc(int a,int b,int c,int n)
{
    if(n==0)
    {
        return 1;
    }
    int sum=0;
    if(a>0)
    {
        sum+=zfc(a-1,b,c,n-1);
    }
        if(b>0)
    {
        sum+=zfc(a,b-1,c,n-1);
    }
        if(c>0)
    {
        sum+=zfc(a,b,c-1,n-1);
    }
    return sum;
}
int main()
{
    int a,b,c,n;
    cin>>a>>b>>c>>n;
    cout<<zfc(a,b,c,n);
}

3.十进制转R进制

题目描述

kiki有一个十进制数，他想转成r进制，请你编程帮他实现。

输入描述:

两个整数，空格间隔，分别表示十进制整数n ( 1 ≤ n ≤ 109 ）和r（1 ≤ r ≤ 16）进制

输出描述:

对应的r进制

#include <iostream>
#include <string>
using namespace std;
string jz(int x,int n)
{
    string std="0123456789ABCDEF";
    string fin=" ";
    while(x>0)
    {
        int re=x%n;
        fin=std[re]+fin;
        x/=n;
    }
    return fin;
}
int main()
{
    int x,n;
    cin>>x>>n;
    string fin=jz(x,n);
    cout<<fin;;
}

4.分解因数

题目描述

给出一个正整数a，要求分解成若干个正整数的乘积，即a = a1 * a2 * a3 * ... * an，并且1 < a1 <= a2 <= a3 <= ... <= an，问这样的分解的种数有多少。注意到a = a也是一种分解。

输入描述:

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a (1 < a < 32768)

输出描述:

输出为n行，每行输出对应一个输入。输出应是一个正整数，指明满足要求的分解的种数。

#include <iostream>
using namespace std;
void find(int star,int m,int &sum)
{
    int i;
    for (i=star; i<=m; i++)
    {
        if(m%i==0 && i<=m/i)
        {
            sum++;
            find(i,m/i,sum);
        }
        if(i>m/i) break;
    }
}
int main()
{
    int m,n,i;
    cin>>n;          //循环n次
    for(i=1;i<=n;i++)
    {
        int sum=1;
        cin>>m;      //输入一个数m
        find(2,m,sum);
        cout<<sum<<endl;
    }
    return 0;
}