递归--练习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;
}
查看6道真题和解析