NOIP普及组教学1-回文数

Posted on Edited on In

P1015 [NOIP 1999 普及组] 回文数

题目描述

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。

例如：给定一个十进制数 $56$，将 $56$ 加 $65$（即把 $56$ 从右向左读），得到 $121$ 是一个回文数。

又如：对于十进制数 $87$：

STEP1：$87+78=165$
STEP2：$165+561=726$
STEP3：$726+627=1353$
STEP4：$1353+3531=4884$

在这里的一步是指进行了一次 $N$ 进制的加法，上例最少用了 $4$ 步得到回文数 $4884$。

写一个程序，给定一个 $N$（$2 \le N \le 10$ 或 $N=16$）进制数 $M$（$100$ 位之内），求最少经过几步可以得到回文数。如果在 $30$ 步以内（包含 $30$ 步）不可能得到回文数，则输出 Impossible!。

输入格式

两行，分别是 $N$，$M$。

输出格式

如果能在 $30$ 步以内得到回文数，输出格式形如 STEP=ans，其中 $\text{ans}$ 为最少得到回文数的步数。

否则输出 Impossible!。

输入输出样例 #1

输入 #1

1
2
3
10
87

输出 #1

1
2
STEP=4

处理思路

读入

首先，我们使用cin去将输入数据储存到int N和string M中，

之所以使用string M是因为M.size()可以很方便的获取字符长度

以便后续转移到数组中

转移

得到字符串之后，我们还需要补位，

即最终结果可能有110位，输入的有3位，

我们也要把有效数字前的107位补上

（虽然后续操作也要逆过来找有效数字，但是这样做可以避免进位操作时未指定元素初始值而导致的错误）

while(M.size() < 110)M = '0' + M;

之后使用

1
2
3
4
5
6
for(int i = 0;i<110;i++){
	if(M[i] >= '0' && M[i] <= '9')
		arr[i] = M[i] - '0';
	else 
		arr[i] = M[i] - 'A' + 10;
}

将字符串转移到int arr[110]中

其中对Ascii码值操作可以将字符转为对应数组

判断

这个功能是核心，用来判断每一步之后的数字是不是回文数

1
2
3
4
5
6
7
8
9
10
11
12
13
bool check(){
    //由于补有0，所以要寻找有效数字
	int f = -1;
	for(int i = 0;i<110;i++){
		if(arr[i] != 0 && f == -1)f = i;
		if(f != -1 && arr[109 - (i-f)] != arr[i]){//直接对ascill进行比较
			return false;
            //找到不对称的马上给出否定结果并跳出
		}
	}
    return true;
    //没有找到不对称的给出肯定结果
}

模拟计算捕捉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void _step(){//step与万能头里的函数重名了
	int brr[110];
	for(int i = 0;i<110;i++){
		brr[i] = arr[i];
	}
    //先记录初始的值
	int f = -1;//找有效数字
	for(int j = 0;j<110;j++){
		if(brr[j] != 0 && f == -1)f = j;
		if(f != -1){
			arr[109 - (j-f)] += brr[j];
            //逐位运算
		}
	}
	for(int k = 109;k>0;k--){
		arr[k-1] += arr[k] / N;
		arr[k] = arr[k] % N;
        //根据N进行进位
//		cout << arr[k] << endl;
	}
	res++;
    //步骤数+1
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
int arr[110],N,res = 0,step = 0;
string M;
bool check(){
	int f = -1;
	for(int i = 0;i<110;i++){
		if(arr[i] != 0 && f == -1)f = i;
		if(f != -1 && arr[109 - (i-f)] != arr[i]){
			return false;
		}
	}
	return true;
}
void _step(){
	int brr[110];
	for(int i = 0;i<110;i++){
		brr[i] = arr[i];
	}
	int f = -1;
	for(int j = 0;j<110;j++){
		if(brr[j] != 0 && f == -1)f = j;
		if(f != -1){
			arr[109 - (j-f)] += brr[j];
		}
	}
	for(int k = 109;k>0;k--){
		arr[k-1] += arr[k] / N;
		arr[k] = arr[k] % N;
//		cout << arr[k] << endl;
	}
	res++;
}
int main(){
	cin >> N >> M;
	while(M.size() < 110)M = '0' + M;
//	cout << M;
	for(int i = 0;i<110;i++){
		if(M[i] >= '0' && M[i] <= '9')
			arr[i] = M[i] - '0';
		else 
			arr[i] = M[i] - 'A' + 10;
	}
	for(int j = 0;j<30;j++){
		_step();
		if(check() == true){
			cout << "STEP=" << res;
			return 0;
		}
	}
	cout << "Impossible!";
	return 0;
}