1 準備工作 獲取class文件byte[] public static byte[] getFileBytes(File file) { try (FileInputStream fileInputStream = new FileInputStream(file)) { int availabl ...
我們知道,一個int型整數一般用32位二進位數存儲,所表示的最大整數值為 231-1,對應1個10位的十進位整數。因此,一個更大的整數可能需要更多的二進位位來存儲,在處理時需要對其進行高精度運算處理。
【例1】二進位加法
問題描述
二進位數相加與十進位數的長加非常相似。與十進位數字一樣,從右到左,一次一列地進行各位對應數字的相加。與十進位加法不同,二進位位加法的進位規則是“逢二進一”。
0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
1 + 1 = 10
1 + 1 + 1 = 11
輸入
第一行輸入是整數N(1≤ N≤ 1000),表示測試用例的組數。之後N行,每行是一組測試用例,其中包含兩個由單個空格字元分隔的二進位值。每個二進位值的最大長度為80位(二進位數字)。註:最大長度結果可能是81位(二進位數字)。
輸出
對於每組測試用例,在一行中輸出測試用例編號、空格和加法的二進位結果。必須省略額外的前導零。
輸入樣例
3
1001101 10010
1001001 11001
1000111 1010110
輸出樣例
1 1011111
2 1100010
3 10011101
(1)編程思路。
將二進位數用字元串保存,編寫函數void binAdd(char *a,char *b,char *c),完成二進位數C=A+B這一功能。在函數中,先將字元串表示的二進位數A和B分別轉換到整型數組X和Y中,轉換時註意二進位字元串的最低位(如a[0])對應到數組X的最高位(如x[strlen(a)-1]),二進位字元串的最高位(如a[strlen(a)-1])對應到數組X的最低位(如x[0])。然後將數組X和Y從下標0開始(也是二進位數的個位),逐位對應相加,逢二進一。
(2)源程式。
#include <stdio.h> #include <string.h> void binAdd(char *a,char *b,char *c) { int len1=strlen(a),len2=strlen(b); int x[91],y[91],z[91]; int len=len1>len2?len1:len2; memset(x,0,sizeof(x)); memset(y,0,sizeof(y)); memset(z,0,sizeof(z)); int i; for (i=len1-1;i>=0;i--) x[len1-1-i]=a[i]-'0'; for (i=len2-1;i>=0;i--) y[len2-1-i]=b[i]-'0'; int cf=0; for (i=0;i<len;i++) { z[i]=(x[i]+y[i]+cf)%2; cf=(x[i]+y[i]+cf)/2; } z[len++]=cf; while (len>=0 && z[len-1]==0) // 去前置0 len--; if (len==0) // a+b=0時特判 { c[0]='0'; c[1]='\0'; return ; } for (i=0;i<len;i++) c[i]=z[len-1-i]+'0'; c[len]='\0'; } int main() { char s1[91],s2[91],ans[91]; int n,i; scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%s%s",s1,s2); binAdd(s1,s2,ans); printf("%d %s\n",i,ans); } return 0; }
將上面的源程式提交給 北大POJ題庫 POJ 2845 01000001(http://poj.org/problem?id=2845),可以Accepted。
【例2】最大公約數
問題描述
給出兩個二進位數A和B,求它們的最大公約數。
輸入
輸入的第一行是T(1≤ T≤ 100),代表需要解決的測試用例數。
之後T行,每行包含兩個二進位數A和B。(0< A,B ≤ 21000)
輸出
對於每個測試用例,輸出A和B的最大公約數,這個最大公約數也以二進位數顯示。
輸入樣例
3
10 100
100 110
10010 1100
輸出樣例
Case #1: 10
Case #2: 10
Case #3: 110
(1)編程思路。
設gcd(a,b) 表示求兩個二進位數的最大公約數。有
(1)若a,b都為偶數, 則 gcd(a,b) = 2*gcd(a/2,b/2)。
(2)若 a為偶數,b為奇數,則 gcd(a,b) = gcd(a/2,b)。
(3)若 a,b 都為奇數(設a大於等於b),則 gcd(a,b) = gcd((a-b),b)。
按照這種思路直接求兩個二進位數的最大公約數就比較簡單了。主要涉及二進位的相減運算(a-b),相減時總是大數減小數(即a>b);二進位數除以2,這個操作比較簡單,直接去掉個位數即可,也就是刪除bit數組中的bit[0]元素,同時len減1。
定義結構體類型
struct BigNumber
{
int len; // 保存二進位數的位數
int bit[1005]; // 保存各位的數字,每個數組元素保存二進位數的1位數,其中bit[0]保存二進位數的個位數。
}; 的變數來保存二進位數。
同時定義4個函數,分別實現兩個二進位數的大小比較、兩個二進位數相減、一個二進位數除以2、求兩個二進位數的最大公約數等功能。
(2)源程式。
#include <stdio.h> #include <string.h> struct BigNumber { int len; int bit[1005]; }; int compare(struct BigNumber n1,struct BigNumber n2) // 比較兩個大數的大小,n1小於n2則返回1 { if (n1.len<n2.len) return 1; if (n1.len>n2.len) return 0; int i; for (i=n1.len-1;i>=0;i--) { if (n1.bit[i]<n2.bit[i]) return 1; if (n1.bit[i]>n2.bit[i]) return 0; } return 0; } struct BigNumber minus(struct BigNumber n1,struct BigNumber n2) // 大數n1 - n2 { struct BigNumber ret; int i; ret=n1; for (i=0;i<n2.len;i++) { ret.bit[i]=ret.bit[i]-n2.bit[i]; if (ret.bit[i]<0) { ret.bit[i+1]--; // 向前一位借1當2 ret.bit[i]+=2; } } for (;i<ret.len;i++) // 處理n1比n2多出的高位 { if (ret.bit[i]>=0) // 向更高位不再有借位 break; else { ret.bit[i+1]--; // 向前一位借1當2 ret.bit[i]+=2; } } while (ret.len>=1 && !ret.bit[ret.len-1]) // 去掉前導0 ret.len--; return ret; } struct BigNumber div2(struct BigNumber n) // 大數n除以2 { struct BigNumber ret; ret.len=n.len-1; int i; for (i=0;i<ret.len;i++) // 去掉最末位的0即可 ret.bit[i]=n.bit[i+1]; return ret; } void gcd(struct BigNumber n1,struct BigNumber n2) // 求n1和n2的最大公約數並輸出 { int b=0,i; while (n1.len && n2.len) { if (n1.bit[0]) { if(n2.bit[0]) // n1、n2均為奇數,gcd(n1,n2)=gcd((n2-n1),n1) (設n2大於等於n1) { if (compare(n1,n2)) n2=minus(n2,n1); else n1=minus(n1,n2); } else // n2為偶數,n1為奇數。gcd(n1,n2)=gcd(n1,n2/2) n2=div2(n2); } else { if(n2.bit[0]) // n1為偶數,n2為奇數。gcd(n1,n2)=gcd(n1/2,n2) n1=div2(n1); else // n1、n2都為偶數。gcd(n1,n2)=2*gcd(n1/2,n2/2) { n1=div2(n1); n2=div2(n2); b++; } } } if (n2.len) for (i=n2.len-1;i>=0;i--) printf("%d",n2.bit[i]); else for (i=n1.len-1;i>=0;i--) printf("%d",n1.bit[i]); while (b--) printf("0"); printf("\n"); } int main() { int t,iCase=0; struct BigNumber n1,n2; char str1[1005],str2[1005]; scanf("%d",&t); while (t--) { scanf("%s%s",str1,str2); int i; n1.len=strlen(str1); for (i=0;i<n1.len;i++) // 二進位字元串的str1[0]是二進位數的最高位,二者是逆序的 n1.bit[i]=str1[n1.len-1-i]-'0'; n2.len=strlen(str2); for (i=0;i<n2.len;i++) n2.bit[i]=str2[n2.len-1-i]-'0'; printf("Case #%d: ",++iCase); gcd(n1,n2); } return 0; }
將上面的源程式提交給 HDU題庫 HDU 5050 Divided Land(http://acm.hdu.edu.cn/showproblem.php?pid=5050),可以Accepted。
【例3】N!
問題描述
表達式N!,讀作N的階乘,表示前N個正整數的乘積。如果N的階乘是十六進位的,沒有前導零,你能告訴我們其中有多少個零嗎?例如,15!=(13077775800)16,其中有3個零。
輸入
輸入包含幾個測試用例。每個測試用例有一行,包含非負十進位整數N(N≤ 100)。你需要計算N!對應的十六進位數中的零的個數。負數終止輸入。
輸出
對於每個非負整數N,輸出一行正好包含一個整數,為N!中的零的個數。
輸入樣例
1
15
-1
輸出樣例
0
3
(1)編程思路。
當N值較大時,N!的一個很大的數。為此定義結構體類型
struct BigNumber
{
int len; // 保存十六進位數的位數
int bit[1005]; // 保存各位的數字,每個數組元素保存十六進位數的1位數,其中bit[0]保存十六進位數的個位數。
};
的變數來保存N!的十六進位結果。
編寫一個函數 struct BigNumber mul(struct BigNumber a,int b)完成十六進位整數a與十進位整數b相乘,結果是一個十六進位數並作為函數值返回,在函數中,將bit數組中保存的len位數字從下標0開始,逐位與int型整數b相乘,在相乘的過程中對乘積進行逢十六進一即可。
(2)源程式。
#include <stdio.h> #include <string.h> struct BigNumber { int len; int num[205]; }; struct BigNumber mul(struct BigNumber a,int b) // 十六進位整數a與十進位整數b相乘 { struct BigNumber ret; memset(ret.num,0,sizeof(ret.num)); int i; for (i=0;i<a.len;i++) { ret.num[i]=ret.num[i]+a.num[i]*b; ret.num[i+1]=ret.num[i]/16; // 向前進位 ret.num[i]%=16; } i=a.len; while (ret.num[i]!=0) // 高位繼續向前進位 { ret.num[i+1]=ret.num[i]/16; ret.num[i]%=16; i++; } ret.len=i; return ret; } int main() { struct BigNumber fact[101]; fact[1].len=1; fact[1].num[0]=1; int i,j; for (i=2;i<=100;i++) fact[i]=mul(fact[i-1],i); int ans[101]={0,0}; for (i=2;i<=100;i++) { int cnt=0; for (j=fact[i].len-1;j>=0;j--) if (fact[i].num[j]==0) cnt++; ans[i]=cnt; } int n; while (scanf("%d",&n) && n>=0) { printf("%d\n",ans[n]); } return 0; }
將上面的源程式提交給 HDU題庫 HDU 2940 Hex Factorial(http://acm.hdu.edu.cn/showproblem.php?pid=2940),可以Accepted。
【例4】進位轉換
問題描述
編寫一個程式,將一個基數的數字轉換為另一個基數。有62個不同的數字:{0-9,A-Z,a-z}
輸入
第一行輸入包含一個正整數N,表示測試用例的組數。之後N行,每一行將有一個十進位整數表示的輸入基數,後跟一個十進位整數表示的輸出基數,再跟一個以輸入基數表示的數字。輸入基數和輸出基數都將在2到62的範圍內。A=10,B=11,…,Z=35,a=36,b=37,…,z=61(0-9有其通常的含義)。
輸出
程式的輸出應包括每執行一次基本轉換的三行輸出。第一行應該是十進位的輸入基數,後跟空格,然後是輸入數字(以輸入基數表示)。第二行應該是輸出基數,後跟一個空格,然後是輸出數字(以輸出基數表示)。第三輸出行為空。
輸入樣例
8
62 2 abcdefghiz
10 16 1234567890123456789012345678901234567890
16 35 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 23 333YMHOUE8JPLT7OX6K9FYCQ8A
23 49 946B9AA02MI37E3D3MMJ4G7BL2F05
49 61 1VbDkSIMJL3JjRgAdlUfcaWj
61 5 dl9MDSWqwHjDnToKcsWE1S
5 10 42104444441001414401221302402201233340311104212022133030
輸出樣例
62 abcdefghiz
2 11011100000100010111110010010110011111001001100011010010001
10 1234567890123456789012345678901234567890
16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 333YMHOUE8JPLT7OX6K9FYCQ8A
35 333YMHOUE8JPLT7OX6K9FYCQ8A
23 946B9AA02MI37E3D3MMJ4G7BL2F05
23 946B9AA02MI37E3D3MMJ4G7BL2F05
49 1VbDkSIMJL3JjRgAdlUfcaWj
49 1VbDkSIMJL3JjRgAdlUfcaWj
61 dl9MDSWqwHjDnToKcsWE1S
61 dl9MDSWqwHjDnToKcsWE1S
5 42104444441001414401221302402201233340311104212022133030
5 42104444441001414401221302402201233340311104212022133030
10 1234567890123456789012345678901234567890
(1)編程思路。
一般不同進位轉換是以10進位為中介進行轉換,但若轉換的數較大的話,複雜度較高。可以採用短除法直接將A進位數x直接轉化為B進位數y,其基本原理是將x每次除以B,得到的餘數的逆序列是就B進位表示的結果。每次除的時候,從最高位開始除,商作為x當前位的值保存,得到的餘數乘以A加到下一位,一直到最低位。最後得到的餘數作為B進位數y的某位保存。重覆這一過程,直到A進位數x為0。
用一個例子簡單說明:將十六進位數6E轉換為八進位數。
為方便說明,設用數組x存儲十六進位的各位數字,用數組y存儲轉換後得到的八進位各位數字。
首先將表示十六值數6E的字元串轉換為x中存儲的各位整數。轉換後 x[0]=14,x[1]=6。
從高位開始除,x[1]=6, 6/8商為0,餘數為6,將商保存到當前位x[1]中,x[1]=0,將餘數 6*16加到下一位x[0]中,x[0]=14+6*16=110。
再接著進行下一位的除法。 X[0]=110,110/8商為13,餘數為6,將商保存到當前位x[0]中,x[0]=13,因為這是最低位(個位),一次除法結束,餘數6作為轉換後八進位數的數字保存到y數組中,y[0]=6。
去掉x數組的高位前導0後,x數組中 x[0]=13。
X!=0,繼續重覆上面的過程。x[0]=13,13/8商為1,餘數為5,將商保存到當前位x[0]中,x[0]=1,同樣因為這是最低位(個位),一次除法結束,餘數作為轉換後八進位數的數字保存到y數組中,y[1]=5。
X!=0,繼續重覆上面的過程。x[0]=1, 1/8商為0,餘數為1,將商保存到當前位x[0]中,x[0]=0,同樣因為這是最低位(個位),一次除法結束,餘數作為轉換後八進位數的數字保存到y數組中,y[2]=1。
至此,X等於0,轉換結束。再將數組y中保存的數字按逆序的方式轉換為字元串 156。也就是說,十六進位數6E轉換為八進位數為 156。
(2)源程式。
#include <stdio.h> #include <string.h> #define MAX_LEN 600 void Base1toBase2(char a[],char b[],int base1,int base2) { int num1[MAX_LEN],num2[MAX_LEN]; int n,i,j,k; n = strlen(a); j = 0; for (i = n - 1;i >= 0 ; i --) { if (a[i]>='A' && a[i]<='Z') num1[j++]=a[i]-'A'+10; else if (a[i]>='a' && a[i]<='z') num1[j++]=a[i]-'a'+36; else num1[j++]=a[i]-'0'; } k=0; while (n!=0) { for (i=n-1;i>0;i--) // 短除法 { num1[i-1]+=num1[i]%base2*base1; num1[i]/=base2; } num2[k++]=num1[0]%base2; num1[0]/=base2; while (n>0 && num1[n-1]==0) n--; } for (j=0,i=k-1;i>=0;i--) { if (num2[i]<10) b[j++]=num2[i]+'0'; else if (num2[i]<36) b[j++]=num2[i]-10+'A'; else b[j++]=num2[i]-36+'a'; } b[j]='\0'; } int main() { int t,base1,base2; char src[MAX_LEN],dest[MAX_LEN],tmp[MAX_LEN]; scanf("%d",&t); while (t--) { scanf("%d%d",&base1,&base2); scanf("%s",src); Base1toBase2(src,dest,base1,base2); printf("%d %s\n",base1,src); printf("%d %s\n\n",base2,dest); } return 0; }
將上面的源程式提交給 北大 POJ 題庫 POJ 1220 NUMBER BASE CONVERSION(http://poj.org/problem?id=1220),可以Accepted。