[已解决]C语言小练习-第3期

KevinHu

~~欢迎来到第四期C语言小练习~~

此处引用简单植物大战僵尸制作（3）的开头（我嗅到了一股广告的气味……）

看到我的昵称

是不是以为这里是盗版的《C语言小练习》

没错，就是盗版（手滑打错了）

看看共同维护人：



没错

从今以后，我就是《C语言小练习》的共同维护人

---

咳咳，进入正题

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

例如：给定一个十进制数 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≤N≤10 或 N=16）进制数 M（100 位之内），求最少经过几步可以得到回文数。如果在 30 步以内（包含 30 步）不可能得到回文数，则输出"Impossible!"。

---

输入输出格式

输入格式

1. 两行，分别是 N，M。

复制代码

输出格式

1. 如果能在 30 步以内得到回文数，输出格式形如 "STEP=ans"，其中 ans 为最少得到回文数的步数。
   
2. 
   
3. 否则输出 "Impossible!"。

复制代码

---

输入输出样例

输入：

1. 10
   
2. 87

复制代码

输出：

1. STEP=4

复制代码

如果喜欢，别忘了评分+订阅哦~ 订阅传送门

（来源：洛谷）

最佳答案

月排行榜 / 总排行榜

Mr、渐行渐远

2020-5-27 20:42:55

这题要模拟高精度加法，先把输入的数字按位正序和逆序存放在两个数组里，然后写一个模拟列竖式的加法函数和一个判断回文的函数，循环下去就行

1. #include <iostream>
   
2. #include <cstring>
   
3. using namespace std;
   
4. int toInt(char s[], int a[], int b[])
   
5. {
   
6.         char *p = s;
   
7.         char *q = s;
   
8.         int i=0;
   
9.         int len;
   
10.         while(*p)
    
11.         {
    
12.                 if(*p>='0'&&*p<='9')
    
13.                 a[i] = *p-'0';
    
14.                 else
    
15.                 a[i] = *p - 'A'+10;
    
16.                 i++;
    
17.                 p++;
    
18.         }
    
19.         len = i;
    
20.         i--;
    
21.         while(*q)
    
22.         {
    
23.                 if(*q>='0'&&*q<='9')
    
24.                 b[i] = *q-'0';
    
25.                 else
    
26.                 b[i] = *q-'A'+10;
    
27.                 i--;
    
28.                 q++;
    
29.         }
    
30.         return len;
    
31. }
    
32. int add(int n, int len, int a[], int b[])
    
33. {
    
34.         int i,temp;
    
35.         for( i=0; i<len; i++)
    
36.         {
    
37.                 temp = (a[i]+b[i])/n;
    
38.                 a[i] = (a[i]+b[i])%n;
    
39.                 a[i+1]+=temp;
    
40.         }
    
41.         if(a[i]==0)
    
42.                 return len;
    
43.         else
    
44.                 return len+1;
    
45. }
    
46. bool judge(int c[], int len)
    
47. {
    
48.         for(int i=0; i<=len/2; i++)
    
49.                 if(c[i]!=c[len-i-1])
    
50.                         return false;
    
51.         return true;
    
52. }
    
53. void reverse(int lenc, int c[], int rc[])
    
54. {
    
55.         for(int i=0; i<lenc; i++)
    
56.                 rc[i] = c[lenc-i-1];
    
57. }
    
58. int main()
    
59. {
    
60.         int a[1000]={0}, b[1000]={0},ra[1000]={0};
    
61.         char s[1000];
    
62.         int n;
    
63.         int step = 1;
    
64.         cin>>n;
    
65.         cin>>s;
    
66.         int lens = toInt(s,a,b);
    
67.         int lena = add(n,lens,a,b);
    
68.         while(!judge(a,lena))
    
69.         {
    
70.                 step ++;
    
71.                 reverse(lena,a,ra);
    
72.                 lena=add(n,lena,a,ra);
    
73.                 if(step>30)
    
74.                         break;
    
75.         }
    
76.         if(step<=30)
    
77.         cout<<"STEP="<<step<<endl;
    
78.         else
    
79.         cout<<"Impossible!"<<endl;
    
80.         return 0;
    
81. }

复制代码

可能有的地方算法不够好，可以再改改

跳转到最佳答案楼层

Mr、渐行渐远

这题要模拟高精度加法，先把输入的数字按位正序和逆序存放在两个数组里，然后写一个模拟列竖式的加法函数和一个判断回文的函数，循环下去就行

1. #include <iostream>
   
2. #include <cstring>
   
3. using namespace std;
   
4. int toInt(char s[], int a[], int b[])
   
5. {
   
6.         char *p = s;
   
7.         char *q = s;
   
8.         int i=0;
   
9.         int len;
   
10.         while(*p)
    
11.         {
    
12.                 if(*p>='0'&&*p<='9')
    
13.                 a[i] = *p-'0';
    
14.                 else
    
15.                 a[i] = *p - 'A'+10;
    
16.                 i++;
    
17.                 p++;
    
18.         }
    
19.         len = i;
    
20.         i--;
    
21.         while(*q)
    
22.         {
    
23.                 if(*q>='0'&&*q<='9')
    
24.                 b[i] = *q-'0';
    
25.                 else
    
26.                 b[i] = *q-'A'+10;
    
27.                 i--;
    
28.                 q++;
    
29.         }
    
30.         return len;
    
31. }
    
32. int add(int n, int len, int a[], int b[])
    
33. {
    
34.         int i,temp;
    
35.         for( i=0; i<len; i++)
    
36.         {
    
37.                 temp = (a[i]+b[i])/n;
    
38.                 a[i] = (a[i]+b[i])%n;
    
39.                 a[i+1]+=temp;
    
40.         }
    
41.         if(a[i]==0)
    
42.                 return len;
    
43.         else
    
44.                 return len+1;
    
45. }
    
46. bool judge(int c[], int len)
    
47. {
    
48.         for(int i=0; i<=len/2; i++)
    
49.                 if(c[i]!=c[len-i-1])
    
50.                         return false;
    
51.         return true;
    
52. }
    
53. void reverse(int lenc, int c[], int rc[])
    
54. {
    
55.         for(int i=0; i<lenc; i++)
    
56.                 rc[i] = c[lenc-i-1];
    
57. }
    
58. int main()
    
59. {
    
60.         int a[1000]={0}, b[1000]={0},ra[1000]={0};
    
61.         char s[1000];
    
62.         int n;
    
63.         int step = 1;
    
64.         cin>>n;
    
65.         cin>>s;
    
66.         int lens = toInt(s,a,b);
    
67.         int lena = add(n,lens,a,b);
    
68.         while(!judge(a,lena))
    
69.         {
    
70.                 step ++;
    
71.                 reverse(lena,a,ra);
    
72.                 lena=add(n,lena,a,ra);
    
73.                 if(step>30)
    
74.                         break;
    
75.         }
    
76.         if(step<=30)
    
77.         cout<<"STEP="<<step<<endl;
    
78.         else
    
79.         cout<<"Impossible!"<<endl;
    
80.         return 0;
    
81. }

复制代码

可能有的地方算法不够好，可以再改改

xiaosi4081

沙发
还有，这应该是4

KevinHu

xiaosi4081 发表于 2020-5-28 07:27
沙发
还有，这应该是4

我改一下……

KevinHu

xiaosi4081 发表于 2020-5-28 07:27
沙发
还有，这应该是4

为什么我改完标题以后还是第3期

405794672

回文数还讲进制。回文数题在C语言经典例题里有。前两天刚做了。就不重复了。

xiaosi4081

没人了？顶