很長時間沒做，忙於考研和實習，久違的的拾起了演算法。做了很長時間，其實總體思路還是很簡單的，但滿分不知道為什麼就是到不了，又因為網上很多答案包括柳神的都是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數組的，因該用字元串來分個存儲，這樣既方便又高效。另一方面，程式的整體流程就是：

1. 輸入、存儲。
2. 判斷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;
    }　　
   

3. 編寫具體的轉換函數，結果返回到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 }

在多次調試時發現需要註意：

1. 輸入N1和N2數組時， scanf("%s %s %d%d",&N1,&N2, &tag, &radix)；%s後面必須有空格，這樣每個字元才會被分割到數組裡面。
2. 求和變數sum2與sum1不同，需寫在for迴圈內，不然遍歷下一次時會sum2因為不會清0而不斷累加導致一直報錯。
3. sizeof（）求出來整個數組的長度，而strlen()求出有效長度。eg：110存入a[10]，sizeof(a)=10.strlen(a)=3
4. ‘110’在數組裡面的位置是0，1，2，機器看起來就是‘011’，反過來了，在求和時要反過來
5. 輸入的數字大於當前進位是不可能的，所以直接退出或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 }

結果：