菜鸟记录：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:

1. N1 N2 tag radix
2. <br>

复制代码

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:

1. 6 110 1 10<br>

复制代码

Sample Output 1:

1. 2<br>

复制代码

Sample Input 2:

1. 1 ab 1 2<br>

复制代码

Sample Output 2:

1. Impossible<br><br>

复制代码

标题分析：

一方面，N1和N2的数字输入是不方便用int数组的，因该用字符串来分个存储，如许既方便又高效。另一方面，程序的整体流程就是：

• 输入、存储。
  
• 判断tag，到这大概能写出main函数，根据result变量确定输出数字还是“impossible”
  1. int main() {
  2.      int result;
  3.      scanf("%s %s %d%d",&N1,&N2, &tag, &radix);
  4.          if (tag == 1)
  5.          {
  6.              result = Radix(N1, N2,radix );
  7.          }
  8.          else if(tag==2)
  9.          {
  10.              result = Radix(N2,N1,radix);
  11.          }
  12.          else
  13.          {
  14.              result = 0;
  15.          }
  17.      if (result != 0)
  18.          printf("%d", result);
  19.      else
  20.          printf("Impossible");
  21.     return 0;
  22. }　　

  复制代码
• 编写具体的转换函数，结果返回到result。
  

个人想法：

主题函数很好写，而且不需要在意标题中提到的出现多个可转换的进制输出最小进制，当你第一次遍历得到准确进制数时就可以直接输出。
转换进制的函数Radix(char *tar,char *cha,int radix)，tar数组直接按照radix写一个for循环转换为二进制，cha则多加一个for循环举行多个进制的遍历，（这里注意的是，不是只到36就可以的，我相同的程序在只遍历36次时只有19分，遍历过多又会有超时，最高在999999次时达到24分），转换进制的代码就好写了。

1. 1 int Radix(char *tar,char *cha,int radix) {
2. 2     double sum1 = 0;
3. 3     for (int i = strlen(tar)-1; i >=0; i--)
4. 4     {
5. 5         double tmp;
6. 6         tmp = tar[i];
7. 7         if (tmp > '9')tmp = tmp - 'a' + 10;//a-z
8. 8         else if (tmp < 'a'&&tmp>='0')tmp -= '0';//0-9
9. 9         if (tmp >= radix) return 0;
10. 10         sum1 += tmp * pow(radix,strlen(tar)-i-1);
11. 11     }
12. 12     for (int i = 0; i <= 999999;i++) {
13. 13         double sum2 = 0;
14. 14         for (int j = strlen(cha) - 1; j >= 0; j--) {
15. 15             double tmp;
16. 16             tmp = cha[j];
17. 17             if (tmp > '9')tmp =tmp- 'a' + 10;//a-z
18. 18             else if (tmp < 'a' && tmp >= '0')tmp -= '0';//0-9
19. 19             if (tmp >= i) break;
20. 20             sum2 += tmp * pow(i, strlen(cha) - j - 1);
21. 21         }
22. 22
23. 23         if (sum1 == sum2)return i;
24. 24     }
25. 25     return 0;
26. 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. 1 #include<stdio.h>
2. 2 #include<string.h>
3. 3 #include<math.h>
4. 4 #define _CRT_SECURE_NO_WARNINGS
5. 5 char N1[10],  N2[10];
6. 6 int tag, radix;
7. 7 int Radix(char* tar, char* cha, int radix);
8. 8  int main() {
9. 9      int result;
10. 10      
11. 11      scanf("%s %s %d%d",&N1,&N2, &tag, &radix);
12. 12          if (tag == 1)
13. 13          {
14. 14              result = Radix(N1, N2,radix );
15. 15          }
16. 16          else if(tag==2)
17. 17          {
18. 18              result = Radix(N2,N1,radix);
19. 19          }
20. 20          else
21. 21          {
22. 22              result = 0;
23. 23          }
24. 24
25. 25      if (result != 0)
26. 26          printf("%d", result);
27. 27      else
28. 28          printf("Impossible");
29. 29     return 0;
30. 30  }
31. 31 int Radix(char *tar,char *cha,int radix) {
32. 32     double sum1 = 0;
33. 33     for (int i = strlen(tar)-1; i >=0; i--)
34. 34     {
35. 35         double tmp;
36. 36         tmp = tar[i];
37. 37         if (tmp > '9')tmp = tmp - 'a' + 10;//a-z
38. 38         else if (tmp < 'a'&&tmp>='0')tmp -= '0';//0-9
39. 39         if (tmp >= radix) return 0;
40. 40         sum1 += tmp * pow(radix,strlen(tar)-i-1);
41. 41     }
42. 42     for (int i = 0; i <= 999999;i++) {
43. 43         double sum2 = 0;
44. 44         for (int j = strlen(cha) - 1; j >= 0; j--) {
45. 45             double tmp;
46. 46             tmp = cha[j];
47. 47             if (tmp > '9')tmp =tmp- 'a' + 10;//a-z
48. 48             else if (tmp < 'a' && tmp >= '0')tmp -= '0';//0-9
49. 49             if (tmp >= i) break;
50. 50             sum2 += tmp * pow(i, strlen(cha) - j - 1);
51. 51         }
52. 52
53. 53         if (sum1 == sum2)return i;
54. 54     }
55. 55     return 0;
56. 56 }

复制代码

View Code结果：

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。