1.進位制數
日常生活中人們都采用十進制數，十進制數用0、1、2、3、4、5、6、7、8、9十個數碼表示數值；其基數為10，規則逢十進一，借一當十，
計算機中采用二進制數，二進制數只用兩個數碼0和1來表示數值；其基數為2，規則逢二進一，借一當二，
由于二進制數書寫比較麻煩，因此，計算機中通常又用八進制數或十六進制數來書寫和表示資訊，
八進制數用0、1、2、3、4、5、6、7八個數碼表示數值；其基數為8，規則逢八進一，借一當八，
十六進制數用0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F十六個數碼表示數值（在這十六個數碼中的A、B、C、D、E、F六個數碼，分別代表十進制數中的10、11、12、13、14、15，這是國際上通用的表示法）；其基數為16，規則逢十六進一，借一當十六，
一般來說，若把它們統稱為 R進制，則R進位制具有下列特點：
（1）在R進制中，具有R個數字符號，它們是0，l，…，（R- 1），
（2）在R進制中，由低位向高位是按“逢R進一”的規則進行計數，
（3）R進制的基數是“R”，R進制數的第 i位的權為“Ri ”，約定整數最低位的位序號i為0（i=n，…2，l，0，-l，-2…），
基數和位權是進位制數的兩個要素，所謂某進位制的基數是指該進位制中允許選用的基本數碼的個數，不同進位制具有不同的基數，基數表明了某一進位制的基本特征，例如對于二進制，有兩個數碼（0，1），且由低位向高位是“逢二進一”，故其基數為2，對于某一進位制數，一個數碼處在數的不同位置時，它所代表的數值是不同的，例如在十進制數333中，數字3在個位數位置上時表示3，即3×100；數字3在十位數位置上時表示30，即3×101；數字3在百位數位置上時表示300，即3×102，可見每個數碼所表示的數值等于該數碼乘以一個與數碼所在位置有關的常數，這個常數叫位權，位權的大小是以基數為底、數碼所在位置的序號為指數的整數次冪，位權表明了同一數字符號處于不同數位時所代表的值不同，
一般而言，對于任意的R進制數
An-1An-2…A1A0 . A-1A-2…A-m (其中n為整數位數，m為小數位數)
可以表示為以下和式：
An-1×Rn-1 +…+A1×R1+A0×R0+A-1×R-1+…A-m×R-m (其中R為基數)
上式稱為“按權展開式”，
我們可以用圓括號外的下標值（如：10、2、8、16）表示該括號內的數是哪一個進位制中的數，或在數的最后加上字母D（十進制、D可省略）、B（二進制）、Q（八進制）、H（十六進制）來區分其前面的數是屬于哪個進位制，例如，十進制數25可以表示為（25）10或25D或25；二進制數101可以表示為101B或（101）2 ，
2．進位制數的相互轉換
同一個數值可以用不同的進位制數表示，例如對于十進制數12，可以表示為二進制數1100，可以表示為八進制數14，也可以表示為十六進制數0C，這表明不同進位制只是表示數的不同手段，它們之間必定可以相互轉換，下面具體介紹計算機中常用的幾種進位制數之間的轉換，即十進制與二進制數之間的轉換，十進制與八進制或十六進制數之間的轉換，
（1）十進制數轉換為二進制數
十進制數轉換為二進制數的基本方法是：對于整數采用“除2取余”，對于小數采用“乘2取整”，具體做法為：對于十進制數整數，用2連續除要轉換的十進制整數及各次所得之商，直除到商等于0時為止，則各次所得之余數即為所求二進制整數由低位到高位的值；對于十進制小數，用2連續乘要轉換的十進制小數及各次所得之積的小數部分，直乘到積的小數部分為0（或滿足所要求的精度）時為止，則各次所得之積的整數部分即為所求二進制小數由高位到低位的值，當十進制數包含有整數和小數兩部分時，可分別將整數和小數轉換，然后相加，
例1 將十進制數53.375轉換成二進制數，
于是， 53.375 = 110101.011B ，
（2）二進制數轉換為十進制數
二進制數轉換為十進制數的基本方法是將二進制數的各位按權展開相加，
例2 將二進制數11011.101轉換成十進制數
11011.101B =1×24+1×23+0×22+1×21+1×20+1×2-1+0×2-2+1×2-3
=16+8+0+2+1+0.5+0+0.125 =27.625
于是， 11011.101B =27.625 ，
【例1】逆序的二進制數
問題描述
把一個十進制整數轉換成二進制，然后將其二進制倒過來得到的新的數的十進制是多少?
例如，十進制整數6的二進制數為110，逆序后為011，去掉前導0，得到的新數為11，對應的十進制數為3，
輸入
輸入第1行為一個整數T（1≤T≤100），表示測驗用例的組數，
之后T行，每行為1個十進制整數X（0≤X≤231?1），
輸出
二進制數逆序后得到的新的十進制數，
輸入樣例
3
6
8
1
輸出樣例
3
1
1
（1）編程思路，
直接采用“除2取余”的方法將輸入的十進制整數轉換為二進制數保存到a陣列中，a[0]保存二進制數的最低位，之后將陣列a中保存的二進制數碼按權值展開即得到逆序后的十進制數，
（2）源程式，
#include <stdio.h> int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); int a[32]; int len=0; // 保存n對應的二進制的位數 while(n) // 將n轉換為二進制數并保存到陣列a中 { a[len++] = n%2; n/=2; } int k; for (k=0;k<len && a[k]==0; k++) ; // 去掉前導0 int i,ans = 0; for (i=k;i<len;i++) // 去掉前導0后，a[k]~a[len-1]正好是逆序后的二進制數 { ans=ans*2+a[i]; } printf("%d\n",ans); } return 0; }
將上面的源程式提交給“http://acm.hdu.edu.cn/showproblem.php?pid=5142 NPY and FFT”，可以Accepted，
（3）十進制數轉換為R進制數
類似于十進制數轉換為二進制數的方法，十進制數轉換為R進制數的基本方法是：對于整數采用“除R取余”，對于小數采用“乘R取整”，具體做法為：對于十進制數整數，用R連續除要轉換的十進制整數及各次所得之商，直除到商等于0時為止，則各次所得之余數即為所求R進制整數由低位到高位的值；對于十進制小數，用R連續乘要轉換的十進制小數及各次所得之積的小數部分，直乘到積的小數部分為0（或滿足所要求的精度）時為止，則各次所得之積的整數部分即為所求R進制小數由高位到低位的值，當十進制數包含有整數和小數兩部分時，可分別將整數和小數轉換，然后相加，
（4）R進制數轉換為十進制數
R進制數轉換為十進制數的基本方法是將R進制數的各位按權展開，然后進行十進制數相加即可，
【例2】十進制數轉換為M進制數
問題描述
將一個十進制數X(1<=X<=10^9)轉換成任意進制數M（2<=M<=16），
輸入
一行兩個正整數X和M，
輸出
輸出X的M進制的表示，
輸入樣例
31 16
輸出樣例
1F
（1）編程思路1，
直接采用“除M取余”的方法將十進制整數X轉換為M進制數，
（2）源程式1，
#include <stdio.h> #include <string.h> char table[16]="0123456789ABCDEF"; int main() { int x,m; scanf("%d%d",&x,&m); char num[33]; int i,j,k=0; do { num[k++]=table[x%m]; x/=m; } while (x!=0); num[k]='\0'; for (i=0,j=k-1;i<j;i++,j--) { char ch; ch=num[i]; num[i]=num[j]; num[j]=ch; } printf("%s\n",num); return 0; }
（3）編程思路2，
由于采用“除M取余”時，所得M進制數是按余數逆序排列的，因此，可以采用遞回演算法完成轉換，
（4）源程式2，
#include <stdio.h> #include <string.h> char table[16]="0123456789ABCDEF"; void change(int n,int m) { if (n==0) return ; change(n/m,m); printf("%c",table[n%m]); } int main() { int x,m; scanf("%d%d",&x,&m); if (x==0) printf("0\n"); else change(x,m); return 0; }
【例3】A+B
問題描述
輸入兩個不超過8位的十六進制整數，求它們的和并轉換為十進制數輸出，
注：十六進制數中的10~15分別用大寫的英文字母A、B、C、D、E、F表示或小寫的英文字母a、b、c、d、e、f表示，
輸入
輸入包括多組測驗用例，每組測驗用例占1行，為兩個十六進制整數A和B，
輸出
對每組測驗用例，輸出一行，為A+B的十進制數，
輸入樣例
1 9
A B
a b
輸出樣例
10
21
21
（1）編程思路，
撰寫函式int hex2dec(char hex[])將保存在字串hex中的十六進制整數按權值展開，轉換為十進制整數作為函式值回傳，
（2）源程式，
#include <stdio.h> #include <string.h> int hex2dec(char hex[]) { int i,num,s=0; for (i=0;hex[i]!='\0';i++) { if (hex[i]>='0' && hex[i]<='9') num=hex[i]-'0'; else if (hex[i]>='A' && hex[i]<='Z') num=hex[i]-'A'+10; else num=hex[i]-'a'+10; s=s*16+num; } return s; } int main() { char a[10],b[10]; while(scanf("%s%s",a,b)!=EOF) { int x; x=hex2dec(a)+hex2dec(b); printf("%d\n",x); } return 0; }
將上面的源程式提交給“http://acm.hdu.edu.cn/showproblem.php?pid=1720 A+B Coming”，可以Accepted，
【例4】可進行數制轉換的計算器
問題描述
某計算器能夠在不同數制之間進行轉換，該計算器顯示屏有7位，除了數字0到9之外，它的按鈕還包括大寫字母A到F，因此它將支持基數2至16的不同進制，
請為該計算器撰寫不同進制的數的轉換程式，
輸入
輸入包含多組測驗用例，每個測驗用例占1行，每行將有三個數字，第一個數字是要轉換的數，第二個數字是要轉換的數的基數，第三個數字是要轉換后的數字的基數，
輸出
輸出將僅是計算器顯示屏上顯示的轉換后的數字，數字應在7位顯示屏中右對齊，如果數字太長而無法顯示在顯示屏上，則在顯示屏上右對齊輸出“ERROR”（不帶引號），
輸入樣例
1111000[bk][bk]2[bk]10
1111000[bk][bk]2[bk]16
2102101[bk][bk]3[bk]10
2102101[bk][bk]3[bk]15
[bk][bk]12312[bk][bk]4[bk][bk]2
[bk][bk][bk][bk][bk]1A[bk]15[bk][bk]2
1234567[bk]10[bk]16
[bk][bk][bk]ABCD[bk]16[bk]15
輸出樣例
[bk][bk][bk][bk]120
[bk][bk][bk][bk][bk]78
[bk][bk][bk]1765
[bk][bk][bk][bk]7CA
[bk][bk]ERROR
[bk][bk]11001
[bk]12D687
[bk][bk][bk]D071
說明：樣例中的一個“[bk]”僅表示一個空格，實際的輸入和輸出時就是一個空格，
（1）編程思路，
為完成基數為A的整數X轉換為基數為B的整數Y，可以先采用X按權值展開的方式將X轉換為十進制整數Z，再將十進制整數Z按“除B取余”的方法轉換為B進制的整數Y，
（2）源程式，
#include <stdio.h> int main() { char str[10]; while (scanf("%s",str)!=EOF) { int a,b; scanf("%d%d",&a,&b); long long sum=0; int i; for (i=0;str[i]!='\0';i++) { if (str[i]>='0'&& str[i]<='9') sum=sum*a+str[i]-'0'; else sum=sum*a+str[i]-'A'+10; } int len=0; int num[30]; do { num[len++]=sum%b; sum/=b; } while(sum); if (len>7) { printf(" ERROR\n"); } else { for (i=0;i<7-len;i++) printf(" "); for (i=len-1;i>=0;i--) if (num[i]>9) printf("%c",num[i]-10+'A'); else printf("%d",num[i]); printf("\n"); } } return 0; }
將上面的源程式提交給“http://acm.hdu.edu.cn/showproblem.php?pid=1335 Basically Speaking”，可以Accepted，
【例5】數位和統計
問題描述
給出2個b進制正整數s和t，算出s和t間所有整數的數位之和，數位和的意思是一個數各個位置上的和，例如，十進制數1357的數位和是16（=1+3+5+7）；十六進制數9A8C的數位和是39（=9+10+8+12），
輸入
第一行一個整數b表示進制，2<=b<=36，A代表10，B代表11，...，Z代表35，以此類推
第二行兩個b進制正整數s和t，s、t在10進制下小于1000000，
輸出
一個十進制整數表示s和t間所有整數的數位之和
輸入樣例
11
A 1A
輸出樣例
76
（1）編程思路，
先將b進制數s和t轉換為十進制整數，再用回圈對s至t之間所有的整數求每個整數在b進制下的各位數字之和，并將這些求得的和累加起來，
（2）源程式，
#include <stdio.h> int digitSum(int n,int b) // 求10進制整數n對應B進制數的各位數字和 { int s=0; while (n!=0) { s+=n%b; n/=b; } return s; } int change(char s[],int b) // 將b進制數轉換為10進制數 { int i,num,sum=0; for (i=0; s[i]!='\0';i++) { num=s[i]-'0'; if (num>9) num-=7; sum=sum*b+num; } return sum; } int main() { int b; scanf("%d",&b); char s[21],t[21]; scanf("%s %s",s,t); int i,x,y; x=change(s,b); y=change(t,b); if (x>y) { int temp; temp=x; x=y; y=temp; } int sum=0; for (i=x; i<=y;i++) sum+=digitSum(i,b); printf("%d\n",sum); return 0; }
【例6】失戀的小W
問題描述
小W在3月7日這天失戀了，傷心的他開始無比討厭3和7這兩個數字，于是他創造了W計數法，W計數法在十進制的基礎上去掉了所有含有數字3和數字7的數，例如2的下一個數是4,29的下一個數是40，小W想知道在這種計數法下X到Y之間有多少個數，
輸入
一行兩個整數表示X、Y，保證1<=X<=Y<=10^9，保證X和Y中不含數字3和數字7，
輸出
一行一個整數表示X到Y之間有多少個數，
輸入樣例
10 100
輸出樣例
57
（1）編程思路，
所謂的W計數法就是八進制數，在W計數法中，有0,1,2,4,5,6,8,9等八個數碼，規則同樣“逢八進一”，只不過W計數法中的“8”相當于十進制數中的“6”，W計數法中的“9”相當于十進制數中的“7”，若給出一個十進制數，要轉換為W計數法中的數，則十進制的4、5、6應分別轉換成3、4、5，8和9要轉換為6和7，也就是說，將十進制整數轉換成W計數法表示的八進制數時，每位的數字轉換為一個數字，若數字超過了7，則減去2；若數字在4~6之間，則減去1；若數字為0~2，則保持不變，W計數法中不存在3和7，
按上面的方法將十進制數X寫成W計數法表示的八進制數后，再將這個八進制數轉換成十進制數，就知道W計數法中，X是第幾個數，同樣，將十進制數Y寫成W計數法表示的八進制數后，再將這個八進制數轉換成十進制數，就知道W計數法中，Y是第幾個數，這樣就知道X到Y之間有多少個數了，
（2）源程式，
#include <stdio.h> void dec2w(int n,char s[]) // 將10進制整數n轉換為w計數法對應的八進制數，并保存到字串s中 { int i,j,k=0; int a[13]; while (n!=0) { a[k]=n%10; if (a[k]>=7) a[k]=a[k]-2; else if(a[k]>=3) a[k]--; n=n/10; k++; } for (i=k-1,j=0;i>=0;i--,j++) s[j]=a[i]+'0'; s[j]='\0'; } int oct2dec(char s[]) // 將s中保存的8進制數轉換為10進制數并回傳 { int i,sum=0; for (i=0; s[i]!='\0';i++) { sum=sum*8+s[i]-'0'; } return sum; } int main() { int x,y; scanf("%d %d",&x,&y); char s[13]; dec2w(x,s); x=oct2dec(s); dec2w(y,s); y=oct2dec(s); printf("%d\n",y-x+1); return 0; }
【例7】Base B
問題描述
小紅非常喜歡數學，他喜歡研究數字，他知道如何將非負整數表示為基數為P的數字，比如，他知道71的基數為2的數字表示是“1000111”，65的基數為5的數字表示是“230”，但小紅希望創建一種所謂“Base B”的數字表達方式，在該表達方式中，其每個數字值不僅等于或大于A，還小于A+B，例如，如果A=1，B=5，那么在“Base 5”中表示數字65，它肯定是“225”，不會是“230”（0超出范圍[1,5]），
225=2*52+2*51+5*50=50+10+5=65
小紅對這種表示法非常感興趣，現在他希望你能為他撰寫一個程式，幫助他在“Base B”中表示一個數字N，
輸入
輸入由多組測驗用例組成，每組測驗用例占1行，每行有三個整數表示N、A、B（0<=N<=10^9、0<=A<=100、2<=B<=100），
輸出
對于每組測驗用例，輸出N在“Base B”中的表示方式，各數字之間用空格分隔，
輸入樣例
65 1 5
15 0 2
輸出樣例
Case 1: 2 2 5
Case 2: 1 1 1 1
（1）編程思路，
先將輸入的十進制整數N轉換為b進制數，由于“Base B”中要求每位上的數不能小于a，因此，需要進行校正，校正方法為：將轉換后得到的b進制數從低位到高位進行處理，如果當前位上數小于a，則從高一位借1，然后當前位加b，
（2）源程式，
#include <stdio.h> int main() { int n,a,b,iCase=0; while (scanf("%d%d%d",&n,&a,&b)!=EOF) { int cnt=0; int digit[32]; while (n) // 將n轉換為b進制保存在陣列digit中 { digit[cnt++]=n%b; n/=b; } int i; for (i=0;i<cnt-1;i++) // 對小于a的數字進行校正 { while (digit[i]<a) { digit[i]+=b; digit[i+1]--; } } printf("Case %d:",++iCase); for (i=cnt-1;i>=0;i--) { printf(" %d",digit[i]); } printf("\n"); } return 0; }
將上面的源程式提交給http://acm.hdu.edu.cn/showproblem.php?pid=2864 “Base B”，可以Accepted，
【例8】約數的和
問題描述
給定一個十進制整數n，計算n的所有約數在m進制中各位數字的平方和，
例如，給定整數n=10，它的約數有1, 2, 5, 10，表示為2進制數為1, 10, 101, 1010，在2進制中，這些約數的各位數字的平方和為
1^2+ (1^2 + 0^2) + (1^2 + 0^2 + 1^2) + .... = 6 = 110（表示為2進制數），
輸入
輸入包括多個測驗用例，每個測驗用例是一行，包括兩個十進制整數n和m（1≤n≤109，2≤m≤16），
輸出
所有約數在m進制中各位數字的平方和，
輸入樣例
10 2
30 5
輸出樣例
110
112
（1）編程思路，
先用回圈求出n的所有約數并保存到陣列a中，再求每個約數在m進制下的各位數字的平方和，并將求得的平方和累加起來，最后將求得的和值（十進制數）轉換為m進制數輸出，
（2）源程式，
#include <stdio.h> #include <math.h> int main() { int n, m; while (scanf("%d%d",&n,&m)!=EOF) { int i,temp = sqrt(n); int cnt = 0; int a[10005]; for (i = 1;i<=temp;i++) // 求出n的所有因子并保存到陣列a中 { if (n%i == 0) { a[cnt++] = i; if (i!= n/i) a[cnt++] = n / i; } } int sum = 0; for (i = 0;i < cnt;i++) // 求出n的所有因子在m進制下的各位數字的平方和 { temp = a[i]; while (temp) { sum += (temp%m)*(temp%m); temp /= m; } } char ans[32]; cnt = 0; while (sum) // 將求得的和值（十進制數）轉換為m進制數輸出 { temp = sum%m; if (temp < 10) ans[cnt++] = temp + '0'; else ans[cnt++] = temp - 10 + 'A'; sum /= m; } for (i = cnt - 1;i >= 0;i--) printf("%c",ans[i]); printf("\n"); } return 0; }
將上面的源程式提交給 http://acm.hdu.edu.cn/showproblem.php?pid=4432 Sum of divisors，可以Accepted，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/538321.html
標籤：其他
上一篇：java基礎——二維陣列基本概念