【回文数(二)】 （C++代码）

解题思路

用一个数组保存所要算的数的每一位，如10进制87->逆序存储 a 数组={7,8};

 8 7        
+7 8
————
15 15

因为我们是逆序存储的，所以数组从0开始相加，就得到了15 15；又因为87是10进制，所以进位就减去10（n进制就减去n），每大于n，下个下标的数组的值+1，例如(10进制87);

 8 7               8 7            8 7            8 7
+7 8              +7 8           +7 8           +7 8 
-----    --->  ---------  ---> --------- ---> -------
15 15             15 15          15 15          15 15
15+1 15-10        16  5        16-10 5        1  6  5

末位要是大于n,长度要增加。

每做完一次，又重新更新 a 数组，以便判断不是回文时再继续相加.

判断：

for(i=0;i<L/2;i++)

只需做一半，如果是回文，那么前后左右都一样，不是直接标记flag=0，跳出当前循环。

剩下的就是判断了.

注意事项:

参考代码:

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{	
	long long i=0,n,m,L,k=0,a[1000]={0},b[1000]={0};		
	cin>>n; cin>>m;//n进制数m
	while(m)   //存储每一位数字
	{
		a[i]=m%10;	
		m=m/10;
		i++;
	}	
	L=i;		
	while(1)
	{
		for(i=0;i<L;i++)			
			b[i]=a[i]+a[L-i-1];		//首尾相加
		for(i=0;i<L;i++)
		{
			if(b[i]>=n)         //多少进制就大于等于多少，就减去多少进位
			{
				b[i]=b[i]-n;				
				b[i+1]=b[i+1]+1;
				if(i==L-1) L++;    //最后一个要是超出了n，那么再给多一个下标保存，便于判断
			}
			a[i]=b[i];         //循环利用（第一个for）
		}		
		a[i]=b[i]; k++;
		int flag=1;
		for(i=0;i<L/2;i++)
			if(b[i]!=b[L-i-1]) 
			{
				flag=0;break;
			}
		if(flag && k<=30)
		{
			cout<<"STEP="<<k<<endl;break;
		}
		if(k>30)
		{
			cout<<"Impossible!"<<endl;break;
		}
	}
	return 0;
}