Thoughts on Palindromic Numbers in Beijing University of Music (with code)

Tip: After the article is written, the table of contents can be automatically generated. How to generate it can refer to the help document on the right

Title

If a number (with a non-zero first digit) reads the same from left to right as from right to left, we call it a palindromic number.

For example: Given a decimal number 56, add 56 to 65 (that is, read 56 from right to left), and get 121, which is a palindrome.

Another example: For the decimal number 87, STEP1: 87 + 78 = 165 STEP2: 165 + 561 = 726 STEP3: 726 + 627 = 1353 STEP4: 1353 + 3531 = 4884

One step here refers to an N-ary addition. In the above example, at least 4 steps were used to obtain the palindrome number 4884.

Write a program, given an N (2<=N<=10 or N=16) base number M (within 100 digits), find the minimum number of steps to get the palindrome number. If it is impossible to get the palindrome number within 30 steps (including 30 steps), then output "Impossible!". When base N>10, use uppercase ‘A’ to represent 10, ‘B’ to represent 11, …, ‘E’ to represent 15.

Input description: two lines, respectively N, M

Output description: STEP=ans

Input example:
9
87
Example output:
STEP=6

Reminder: The following is the content of the text of this article, and the following case is for reference (this is the first time I write it, a pure novice, feel free to point out any mistakes, thank you everyone!)

Directory

topic

Idea analysis

So what about A?

Summarize


Thinking Analysis

Faced with such a question, at first glance it is indeed a bit dizzy. However, as long as we clarify our thinking, we can simplify the complexity and easily write our own answers.

Note that this question has hexadecimal restrictions, that is to say, there will be ABCDEF letters to make trouble, we can’t just scanf %d as usual. Here I have two solutions:

The first one is to read in through a character array, and then perform substitutions according to the ASCII code table during the hexadecimal conversion.

ASCII value

Control characters

ASCII value

Control characters

ASCII value

Control characters

ASCII value

Control characters

0

NUL

32

(space)

64

@

96

,

1

SOH

33

!

65

A

97

a

2

STX

34

66

B

98

b

3

ETX

35

#

67

C

99

c

4

EOT

36

$

68

D.

100

d

5

ENQ

37

%

69

E.

101

e

6

ACK

38

&

70

f

102

f

7

BEL

39

71

G

103

g

8

BS

40

(

72

h

104

h

9

HT

41

)

73

I

105

i

10

LF

42

*

74

J

106

j

11

VT

43

+

75

K

107

k

12

FF

44

,

76

L

108

l

13

CR

45

77

m

109

m

14

SO

46

.

78

N

110

no

15

Si

47

/

79

o

111

o

16

DLE

48

0

80

P

112

p

17

DCI

49

1

81

Q

113

q

18

DC2

50

2

82

R

114

r

19

DC3

51

3

83

x

115

the s

20

DC4

52

4

84

T

116

t

twenty one

NAK

53

5

85

u

117

u

twenty two

SYN

54

6

86

V

118

v

twenty three

TB

55

7

87

W

119

w

twenty four

CAN

56

8

88

x

120

x

25

EM

57

9

89

Y

121

the y

26

SUB

58

:

90

Z

122

z

27

ESC

59

;

91

[

123

{

28

FS

60

<

92

\

124

|

29

GS

61

=

93

]

125

}

30

RS

62

>

94

^

126

~

31

US

63

?

95

127

DEL

We know: 58 is not the so-called character ’10’, because it is stored in bits. So here we need to do a small conversion. Here is a little trick that can help us quickly convert from characters 0123…9 to numbers. For example: ‘4’ becomes 4, we can use the spacing method to quickly get:

4=’4′-‘0’;

So what about A?

Similarly 10=’A’-‘0’-7;

We see that there are 7 positions between A and 9, so we need to subtract this 7. This way we can complete the first small goal.

Then analyze it normally. I leave it here for everyone to think about, and what you write can be discussed in the comment area.

The second solution is derived through heuristics. Since he restricts us in hexadecimal, wouldn’t it be over if we read it directly with %x? Then some students asked: Isn’t this all hexadecimal? What are you doing?

But wait, it’s not over yet. Look at me slowly: After reading the hexadecimal system, we must do the addition operation according to the meaning of the question. Then we can’t add the hexadecimal system directly, so we will change it to decimal system first. The code is as follows: (I believe that this conversion system can be fully grasped by everyone now)

int N,M,a[10],b[10],step;
   scanf("%d %x", &N, &M);
for(int i=0;i<10;i ++ ){
      a[i]=M ;b[i]=0;
      M/=16;
   }

The form of an array is used here, because the addition is not added one by one, so the array is more convenient to handle. Then a[i] and b[i] are two reversed numbers, which are set according to the meaning of the question. We can adjust this 10 later, anyway, I have learned it, hehe. Next we need to build a few functions. understand the process.

In the first step, we have initialized b[i], which is now 0; now a[i] is reversed, and we can understand it according to the program just now.

Here first set the first function, I named it reverse. His main goal is to enter the numbers in a into b in reverse. But we don’t know how many digits are input, so we first need to know where a met the ‘\0’ Here is the method of using the flag variable: first set flag=1 to ensure that it can loop, starting from a【9】 Read forward, read ‘\0’ and let flag=0, this ends the cycle, and set a variable to record this number of digits, I named it cnt.

void reverse(int b[],int a[]){
    int cnt,flag=1;
    for(int i=9;i>=0 & &flag;i--){
       if(a[i]){
          cnt=i;flag=0;
       }
    }
    for(int i=0;i<10;i ++ ) b[i]=0;
    for(int i=0;i<=cnt;i + + ){
       b[i]=a[cnt-i];
    }
 }

The next step is to assign values in reverse. Very simple

The second step is to build a second function, which I named intcmp. This is used to compare the difference between each bit, and return 1 if they are different; 0 if they are the same. Note: The flag variable flag is still used here to help us determine the real-time state of the loop.

int intcmp(int a[],int b[]){
    int flag=0;
    for(int i=0;i<10;i ++ ){
        if(a[i]!=b[i]) flag=1;
     }
     return flag;
 }

This function is used to help us decide whether to continue the addition operation.

So in the third step, let’s write the function construction of addition, which I named add. (easier to remember)

Analysis of ideas: N is the base system, because we have converted the hexadecimal system into decimal system now, but the addition has to be done according to the base system.

But we just need to make one thing clear: the N-ary system is the full N-ary system, which is the same as the decimal system we are familiar with. So we add the digits first.

There are two situations here: the first one is that after the addition is less than N, then we don’t need to do anything else, just assign it to a directly. The second is greater than N, analogous to the decimal system, we only need to subtract N from the obtained number first, and add one to the next digit to achieve it perfectly. Here is the code:

void add(int N,int a[],int b[]){
    for(int i=0;i<10;i ++ ){
        a[i] + =b[i];
        if(a[i]>=N){
            a[i]-=N;a[i + 1] + + ;
         }
     }
 }

Note: Here I directly add the result to the a array, so that the b array does not change. Because the subsequent b is the reverse of a, it has nothing to do with its own initial value, so the obtained sum is directly assigned to a, and we can use the reverse function next time.

The fourth step, after we build the preparatory function, we can write the main function to calculate the number of steps. (cheer!)

 int main(){
   int N,M,a[10],b[10],step;
   scanf("%d %x", &N, &M);
   for(int i=0;i<10;i ++ ){
      a[i]=M ;b[i]=0;
      M/=16;
   }
   for(step=0;step<=31;step + + ){
      reverse(b,a);
      if(intcmp(a,b)){
         add(N,a,b);
      } else break;
   }
   if(step<=30) printf("STEP=%d\\
",step);
   else printf("Impossible!\\
");
   return 0;
 }

That’s the whole picture. Analyze it:

We use the for loop to count the number of steps, once the palindrome condition is met, we will jump out directly. If less than or equal to 30, output step: if greater than, output Impossible! Inside the loop: first reverse a to b, so there are two arrays. Then if judges whether each bit of the two arrays is exactly the same, if they are the same, the palindrome condition is satisfied, intcmp will return zero, and break out directly. If they are not the same, we enter the inside of if, use the addition function to add the two and assign the new number to a, step ++ once, until they are exactly the same and jump out of the for loop. At this point the value of step can be used for judgment.

Overall code:

#include 
 void reverse(int b[],int a[]){
    int cnt,flag=1;
    for(int i=9;i>=0 & &flag;i--){
       if(a[i]){
          cnt=i;flag=0;
       }
    }
    for(int i=0;i<10;i ++ ) b[i]=0;
    for(int i=0;i<=cnt;i + + ){
       b[i]=a[cnt-i];
    }
 }
 void add(int N,int a[],int b[]){
    for(int i=0;i<10;i ++ ){
        a[i] + =b[i];
        if(a[i]>=N){
            a[i]-=N;a[i + 1] + + ;
         }
     }
 }
 int intcmp(int a[],int b[]){
    int flag=0;
    for(int i=0;i<10;i ++ ){
        if(a[i]!=b[i]) flag=1;
     }
     return flag;
 }
 int main(){
   int N,M,a[10],b[10],step;
   scanf("%d %x", &N, &M);
   for(int i=0;i<10;i ++ ){
      a[i]=M ;b[i]=0;
      M/=16;
   }
   for(step=0;step<=31;step + + ){
      reverse(b,a);
      if(intcmp(a,b)){
         add(N,a,b);
      } else break;
   }
   if(step<=30) printf("STEP=%d\\
",step);
   else printf("Impossible!\\
");
   return 0;
 }

Summary

The above is what I want to talk about today. This article mainly solves the whole problem by constructing three simple functions, addition, judging the small conditions of palindrome numbers, reversing the assignment, and skillfully dealing with N-ary numbers. After analysis, this question is very comprehensive, and every small step requires some thinking and summarization. After finishing the question, it is really necessary to review it in time, so as to make better progress. That’s all for now, I wish you progress in your studies!

The knowledge points of the article match the official knowledge files, and you can further learn relevant knowledge algorithm skill treehomepage overview 46815 people are studying systematically