很長(zhǎng)時(shí)間沒(méi)做，忙于考研和實(shí)習(xí)，久違的的拾起了算法。做了很長(zhǎng)時(shí)間，其實(shí)總體思路還是很簡(jiǎn)單的，但滿(mǎn)分不知道為什么就是到不了，又因?yàn)榫W(wǎng)上很多答案包括柳神的都是c++，無(wú)法參透，姑且只能這樣了。
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的數(shù)字輸入是不方便用int數(shù)組的，因該用字符串來(lái)分個(gè)存儲(chǔ)，這樣既方便又高效。另一方面，程序的整體流程就是：
- 輸入、存儲(chǔ)。
- 判斷tag，到這大概能寫(xiě)出main函數(shù)，根據(jù)result變量確定輸出數(shù)字還是“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; } - 編寫(xiě)具體的轉(zhuǎn)換函數(shù)，結(jié)果返回到result。
個(gè)人想法：
主題函數(shù)很好寫(xiě)，而且不需要在意題目中提到的出現(xiàn)多個(gè)可轉(zhuǎn)換的進(jìn)制輸出最小進(jìn)制，當(dāng)你第一次遍歷得到正確進(jìn)制數(shù)時(shí)就可以直接輸出。
轉(zhuǎn)換進(jìn)制的函數(shù)Radix(char *tar,char *cha,int radix)，tar數(shù)組直接按照radix寫(xiě)一個(gè)for循環(huán)轉(zhuǎn)換為二進(jìn)制，cha則多加一個(gè)for循環(huán)進(jìn)行多個(gè)進(jìn)制的遍歷，（這里注意的是，不是只到36就可以的，我相同的程序在只遍歷36次時(shí)只有19分，遍歷過(guò)多又會(huì)有超時(shí)，最高在999999次時(shí)達(dá)到24分），轉(zhuǎn)換進(jìn)制的代碼就好寫(xiě)了。
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 }
在多次調(diào)試時(shí)發(fā)現(xiàn)需要注意：
- 輸入N1和N2數(shù)組時(shí)，?scanf("%s %s %d%d",&N1,&N2, &tag, &radix)；%s后面必須有空格，這樣每個(gè)字符才會(huì)被分割到數(shù)組里面。
- 求和變量sum2與sum1不同，需寫(xiě)在for循環(huán)內(nèi)，不然遍歷下一次時(shí)會(huì)sum2因?yàn)椴粫?huì)清0而不斷累加導(dǎo)致一直報(bào)錯(cuò)。
- sizeof（）求出來(lái)整個(gè)數(shù)組的長(zhǎng)度，而strlen()求出有效長(zhǎng)度。eg：110存入a[10]，sizeof(a)=10.strlen(a)=3
- ‘110’在數(shù)組里面的位置是0，1，2，機(jī)器看起來(lái)就是‘011’，反過(guò)來(lái)了，在求和時(shí)要反過(guò)來(lái)
- 輸入的數(shù)字大于當(dāng)前進(jìn)制是不可能的，所以直接退出或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 }
結(jié)果：
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-844205.html
?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-844205.html
到了這里，關(guān)于菜鳥(niǎo)記錄：c語(yǔ)言實(shí)現(xiàn)PAT甲級(jí)1010--Radix的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
