回文平方题解
题目来源:
https://www.acwing.com/problem/content/1348/
Lxxx AC源代码:
#include <iostream>
#include <algorithm>
using namespace std;
bool check(string num)
{
for ( int i = 0 , j = num.size() - 1 ; i < j ; i ++, j -- ){
if (num[i] != num[j]) return false;
}
return true;
}
char get(int n)
{
if ( n > 9) return n - 10 + 'A';
else return n + '0';
}
string base( int n , int b)
{
string ans;
while(n)
{
ans += get(n % b);
n /= b;
}
reverse( ans.begin() , ans.end());
return ans;
}
int main()
{
int b ;
cin >> b;
for ( int i = 1 ; i <= 300 ; i ++)
{
string num = base( i * i , b);
if ( check(num) )
{
cout << base( i , b) << " " << num << endl;
}
}
return 0;
}
题目思路:
- 输入n进制
- 将1-300平方之后转化为n进制,记做a
- 如果a是回文数,则输出结果
知识点:
- 将十进制转化为n进制 (短除法,或者叫做 除n反序取余)
- 判断是否为回文数 (双指针算法)
程序编写的过程:
先写main主函数
搭建基本的输入输出的框架
int main()
{
int b ;
cin >> b;
for ( int i = 1 ; i <= 300 ; i ++)
{
string num = base( i * i , b); //base函数用于将当前枚举的数字转化为b进制
if ( check(num) ) //判断num是否为回文数
{
cout << base( i , b) << " " << num << endl;
}
}
return 0;
}
实现base函数
string base( int n , int b)
{
string ans;//ans作为该base函数体的返回值
while(n) //短除法,当n=0的时候结束
{
ans += get(n % b); // 根据题意,A代表10 , B代表11 , 以此类推。
n /= b;
}
reverse( ans.begin() , ans.end()); //由于需要反序取余数,因此使用reverse对字符串进行逆序
return ans;
}
实现get函数
char get(int n)
{
if ( n > 9) return n - 10 + 'A';
else return n + '0';
}
实现check函数
bool check(string num) //传入需要被处理的num字符串
{
/*******************************************************************************
| 双指针算法,i从左开始,j从右开始,如果num[i]和num[j] 不相等,就不是回文数,返回false。 |
********************************************************************************/
for ( int i = 0 , j = num.size() - 1 ; i < j ; i ++, j -- ){
if (num[i] != num[j]) return false;
}
return true;
}