菜鸟记录：c语言实现PAT甲级1010--Radix
很长时间没做，忙于考研和实习，久违的的拾起了算法。做了很长时间，其实总体思路还是很简单的，但满分不知道为什么就是到不了，又因为网上很多答案包括柳神的都是c++，无法参透，姑且只能这样了。
Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.
Now for any pair of positive integers N1 and N2, your task is to find the radix of one number while that of the other is given.
Input Specification:
Each input file contains one test case. Each case occupies a line which contains 4 positive integers:
N1 N2 tag radix
Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.
Output Specification:
For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.
Sample Input 1:
6 110 1 10
Sample Output 1:
2
Sample Input 2:
1 ab 1 2
Sample Output 2:
Impossible
题目分析：
一方面，N1和N2的数字输入是不方便用int数组的，因该用字符串来分个存储，这样既方便又高效。另一方面，程序的整体流程就是：
- 输入、存储。
- 判断tag，到这大概能写出main函数，根据result变量确定输出数字还是“impossible”
int main() { int result; scanf("%s %s %d%d",&N1,&N2, &tag, &radix); if (tag == 1) { result = Radix(N1, N2,radix ); } else if(tag==2) { result = Radix(N2,N1,radix); } else { result = 0; } if (result != 0) printf("%d", result); else printf("Impossible"); return 0; } - 编写具体的转换函数，结果返回到result。
个人想法：
主题函数很好写，而且不需要在意题目中提到的出现多个可转换的进制输出最小进制，当你第一次遍历得到正确进制数时就可以直接输出。
转换进制的函数Radix(char *tar,char *cha,int radix)，tar数组直接按照radix写一个for循环转换为二进制，cha则多加一个for循环进行多个进制的遍历，（这里注意的是，不是只到36就可以的，我相同的程序在只遍历36次时只有19分，遍历过多又会有超时，最高在999999次时达到24分），转换进制的代码就好写了。
1 int Radix(char *tar,char *cha,int radix) { 2 double sum1 = 0; 3 for (int i = strlen(tar)-1; i >=0; i--) 4 { 5 double tmp; 6 tmp = tar[i]; 7 if (tmp > '9')tmp = tmp - 'a' + 10;//a-z 8 else if (tmp < 'a'&&tmp>='0')tmp -= '0';//0-9 9 if (tmp >= radix) return 0; 10 sum1 += tmp * pow(radix,strlen(tar)-i-1); 11 } 12 for (int i = 0; i <= 999999;i++) { 13 double sum2 = 0; 14 for (int j = strlen(cha) - 1; j >= 0; j--) { 15 double tmp; 16 tmp = cha[j]; 17 if (tmp > '9')tmp =tmp- 'a' + 10;//a-z 18 else if (tmp < 'a' && tmp >= '0')tmp -= '0';//0-9 19 if (tmp >= i) break; 20 sum2 += tmp * pow(i, strlen(cha) - j - 1); 21 } 22 23 if (sum1 == sum2)return i; 24 } 25 return 0; 26 }
在多次调试时发现需要注意：
- 输入N1和N2数组时， scanf("%s %s %d%d",&N1,&N2, &tag, &radix)；%s后面必须有空格，这样每个字符才会被分割到数组里面。
- 求和变量sum2与sum1不同，需写在for循环内，不然遍历下一次时会sum2因为不会清0而不断累加导致一直报错。
- sizeof（）求出来整个数组的长度，而strlen()求出有效长度。eg：110存入a[10]，sizeof(a)=10.strlen(a)=3
- ‘110’在数组里面的位置是0，1，2，机器看起来就是‘011’，反过来了，在求和时要反过来
- 输入的数字大于当前进制是不可能的，所以直接退出或break就好（9和19行）
最后得到的整体代码为：
1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 #define _CRT_SECURE_NO_WARNINGS 5 char N1[10], N2[10]; 6 int tag, radix; 7 int Radix(char* tar, char* cha, int radix); 8 int main() { 9 int result; 10 11 scanf("%s %s %d%d",&N1,&N2, &tag, &radix); 12 if (tag == 1) 13 { 14 result = Radix(N1, N2,radix ); 15 } 16 else if(tag==2) 17 { 18 result = Radix(N2,N1,radix); 19 } 20 else 21 { 22 result = 0; 23 } 24 25 if (result != 0) 26 printf("%d", result); 27 else 28 printf("Impossible"); 29 return 0; 30 } 31 int Radix(char *tar,char *cha,int radix) { 32 double sum1 = 0; 33 for (int i = strlen(tar)-1; i >=0; i--) 34 { 35 double tmp; 36 tmp = tar[i]; 37 if (tmp > '9')tmp = tmp - 'a' + 10;//a-z 38 else if (tmp < 'a'&&tmp>='0')tmp -= '0';//0-9 39 if (tmp >= radix) return 0; 40 sum1 += tmp * pow(radix,strlen(tar)-i-1); 41 } 42 for (int i = 0; i <= 999999;i++) { 43 double sum2 = 0; 44 for (int j = strlen(cha) - 1; j >= 0; j--) { 45 double tmp; 46 tmp = cha[j]; 47 if (tmp > '9')tmp =tmp- 'a' + 10;//a-z 48 else if (tmp < 'a' && tmp >= '0')tmp -= '0';//0-9 49 if (tmp >= i) break; 50 sum2 += tmp * pow(i, strlen(cha) - j - 1); 51 } 52 53 if (sum1 == sum2)return i; 54 } 55 return 0; 56 }
结果：