例25 確定進制
問題描述
6*9 = 42 對于十進制來說是錯誤的，但是對于13進制來說是正確的，即
6（13）* 9（13）= 42（13），因為，在十三進制中，42 = 4 * 13 + 2 = 54（10），
撰寫一個程式，輸入三個整數p、q和r，然后確定一個進制B（2<=B<=16），使得在該進制下 p * q = r，如果 B有很多選擇，輸出最小的一個，例如，p = 11，q = 11，r = 121，則有 11（3） * 11（3）= 121（3），還有 11（10）* 11（10）= 121（10），這種情況下，輸出3，如果沒有合適的進制，則輸出0，
輸入格式
三個整數p、q和r，
輸出格式
所確定的進制B，如果沒有合適的進制，則輸出0，
輸入樣例
6 9 42
輸出樣例
13
（1）編程思路，
選擇一個進制B，按照該進制將被乘數p、乘數q、乘積r分別轉換成十進制數pb、qb和rb，然后判斷等式pb*qb==rb是否成立，使得等式成立的最小B就是所求的結果，
設n位B進制數num=（an-1an-2……a1a0），將其按權值展開后求和就可得到對應的十進制數ret，
由上式可以看出，B進制數num轉換為十進制數ret可以寫成一個回圈，方法是：另ret初始值為0，從高位到低位回圈分離出num的各位數字digit，執行 ret=ret*b+digit，回圈結束就可得B進制數num對應的十進制數ret，
撰寫函式int b2ten(int num,int b)完成b進制數num轉換為十進制數，
由于轉換時需要從高位向低位分離數字，而用回圈
while (num!=0)
{
digit = num%10;
num = num/10;
}
能方便地完成從低位向高位分離出num的各位數字，因此，可采用一個陣列digit[]來保存從低位向高位分離出的各位數字，同時num中數字的位數保存到變數cnt中，
（2）源程式，
#include <stdio.h>
int b2ten(int num,int b);
int main()
{
int b,p,r,q;
int pb,qb,rb; // 用來存盤轉換為十進制后的結果
scanf("%d%d%d",&p,&q,&r);
for(b=2;b<=16;b++)
{
pb=b2ten(p,b);
qb=b2ten(q,b);
rb=b2ten(r,b);
if(pb==-1 || qb==-1 || rb==-1) continue;
if (pb*qb==rb)
{
printf("%d\n",b);
break;
}
}
if(b==17)
printf("0\n");
return 0;
}
int b2ten(int num,int b)
{
int ret=0,digit[10];
int cnt=0;
while (num!=0)
{
digit[cnt++]=num%10;
num=num/10;
}
cnt--;
while (cnt>=0)
{
if (digit[cnt]>=b) return -1; // 數字超過B進制的數碼范圍
ret=ret*b+digit[cnt];
cnt--;
}
return ret;
}
習題25
25-1 Faulty Odometer
本題選自北大POJ題庫（http://poj.org/problem?id=2719），
Description
You are given a car odometer which displays the miles traveled as an integer. The odometer has a defect, however: it proceeds from the digit 3 to the digit 5, always skipping over the digit 4. This defect shows up in all positions (the one's, the ten's, the hundred's, etc.). For example, if the odometer displays 15339 and the car travels one mile, odometer reading changes to 15350 (instead of 15340).
Input
Each line of input contains a positive integer in the range 1..999999999 which represents an odometer reading. (Leading zeros will not appear in the input.) The end of input is indicated by a line containing a single 0. You may assume that no odometer reading will contain the digit 4.
Output
Each line of input will produce exactly one line of output, which will contain: the odometer reading from the input, a colon, one blank space, and the actual number of miles traveled by the car.
Sample Input
13
15
2003
2005
239
250
1399
1500
999999
0
Sample Output
13: 12
15: 13
2003: 1461
2005: 1462
239: 197
250: 198
1399: 1052
1500: 1053
999999: 531440
（1）編程思路，
本題的題意是：有一個里程表，表盤上的數字4壞了，因此所有的數字4無法顯示，3之后顯示5，39之后顯示50，…，先給出里程表上顯示的數字，求實際的里程應為多少？
由于里程表上無數字4，因此可以將里程表上的數看成是一個9進制數，有0,1,2,3,5,6,7,8,9共9個數碼，規則逢九進一，因此本題實質是將一個9進制數轉換為一個十進制數，
（2）源程式，
#include <stdio.h>
int main()
{
char odometer[10];
int actual,i,d;
while(scanf("%s",odometer) && odometer[0]!='0')
{
actual=0;
for (i=0;odometer[i]!='\0';i++)
{
d=odometer[i]-'0';
if (d>3) d--;
actual=actual*9+d;
}
printf("%s: %d\n",odometer,actual);
}
return 0;
}
25-2 Skew Binary
本題選自北大POJ題庫（http://poj.org/problem?id=1565），
Description
When a number is expressed in decimal, the kth digit represents a multiple of 10k. (Digits are numbered from right to left, where the least significant digit is number 0.) For example,
81307(10) = 8 * 10^4 + 1 * 10 ^3 + 3 * 10^2 + 0 * 10^1 + 7 * 10^0
= 80000 + 1000 + 300 + 0 + 7
= 81307.
When a number is expressed in binary, the kth digit represents a multiple of 2^k . For example,
10011(2) = 1 * 2^4 + 0 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0
= 16 + 0 + 0 + 2 + 1
= 19.
In skew binary, the kth digit represents a multiple of 2^(k+1)-1. The only possible digits are 0 and 1, except that the least-significant nonzero digit can be a 2. For example,
10120(skew) = 1 * (2^5-1) + 0 * (2^4-1) + 1 * (2^3-1) + 2 * (2^2-1) + 0 * (2^1-1)
= 31 + 0 + 7 + 6 + 0
= 44.
The first 10 numbers in skew binary are 0, 1, 2, 10, 11, 12, 20, 100, 101, and 102. (Skew binary is useful in some applications because it is possible to add 1 with at most one carry. However, this has nothing to do with the current problem.)
Input
The input contains one or more lines, each of which contains an integer n. If n = 0 it signals the end of the input, and otherwise n is a nonnegative integer in skew binary.
Output
For each number, output the decimal equivalent. The decimal value of n will be at most 2^31-1 = 2147483647.
Sample Input
10120
200000000000000000000000000000
10
1000000000000000000000000000000
11
100
11111000001110000101101102000
0
Sample Output
44
2147483646
3
2147483647
4
7
1041110737
（1）編程思路，
按題目描述中給出的展開式進行展開計算即可，
（2）源程式，
#include <stdio.h>
#include <string.h>
int main()
{
char bin[33];
int i,value,p;
while (scanf("%s",bin) && strcmp(bin,"0")!=0)
{
p=1; value=https://www.cnblogs.com/cs-whut/p/0;
for (i=strlen(bin)-1;i>=0;i--)
{
p=p*2;
value+=(bin[i]-'0')*(p-1);
}
printf("%d\n",value);
}
return 0;
}
25-3 數列
本題選自洛谷題庫 （https://www.luogu.org/problem/P1062），
題目描述
給定一個正整數k(3≤k≤15)，把所有k的方冪及所有有限個互不相等的k的方冪之和構成一個遞增的序列，例如，當k=3，時，這個序列是：1,3,4,9,10,12,13,…
（該序列實際上就是：3^0,3^1,3^0+3^1,3^2,3^0+3^2,3^1+3^2,3^0+3^1+3^2,…）
請你求出這個序列的第N項的值（用10進制數表示），
例如，對于k=3，N=100，正確答案應該是981，
輸入格式
2個正整數，用一個空格隔開：
k N（k、N的含義與上述的問題描述一致，且3≤k≤15,10≤N≤1000），
輸出格式
1個正整數，
輸入樣例
3 100
輸出樣例
981
（1）編程思路，
先分析樣例
k=3時，數列為：1,3,4,9,10,12,13，…
轉換成三進制就是：1,10,11,100,101,110,111，…
看起來像是二進制，轉化成十進制就是：1,2,3,4,5,6,7，…
顯然，第n項就是n，
撰寫一個程式，把上面的程序逆回去，即先把n轉換成二進制，再把它當成K進制，重新轉換為十進制，就可以得到結果，
（2）源程式1，
#include <stdio.h>
int main()
{
int a[11]={0},k,n,cnt,i;
scanf("%d%d",&k,&n);
cnt=0;
while (n!=0)
{
a[cnt++]=n%2;
n/=2;
}
long long s=0;
for (i=cnt-1;i>=0;i--)
s=s*k+a[i];
printf("%lld\n",s);
return 0;
}
（3）源程式2，
#include <stdio.h>
int main()
{
int k,n;
scanf("%d%d",&k,&n);
long long s=0,p=1;
while (n!=0)
{
s=s+(n%2)*p;
p*=k;
n/=2;
}
printf("%lld\n",s);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/207639.html
標籤：C