哈夫曼樹 1.概念： 給定n個權值最為n個葉子的節點，構建成一顆二叉樹。如果次樹的帶權路徑長度最小，則稱此二叉樹為最優二叉樹，也叫哈夫曼樹。 WLP：帶權路徑長度 公式： **Wk:**第k個葉子的節點權值 **Lk:**根節點到第k個葉子的節點長度 例如下列二叉樹： 給定4個葉子節點，權值分別為{ ...
46、十六進位數是在程式設計時經常要使用到的一種整數的表示方式。它有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16個數位，分別表示十進位數的0至15。十六進位的計數方法是滿16進1，所以十進位數16在十六進位中是10，而十進位的17在十六進位中是11，以此類推，十進位的30在十六進位中是1E。
編寫函數void fun(int a, char s[])，其功能是：將十進位非負整數a（0<=a<=2147483647），轉換為十六進位數並保存到字元串s中。
例如，若a=30，則得到的字元串s為“1E”（s[0]='1'，s[1]='E’，s[2]=‘\0’）。
#include <stdio.h> void fun(int a, char s[]) { } int main() { int n; char s[9]; printf("請輸入一個十進位整數n (0<=a<=2147483647) : "); scanf("%d",&n); fun(n,s); printf("轉換為十六進位數為 %s\n",s); return 0; }
void fun(int a, char s[]) { char table[17]="0123456789ABCDEF"; int digit[9],cnt=0; do { digit[cnt++]=a%16; a=a/16; } while (a!=0); int i,j; for (i=cnt-1,j=0;i>=0;i--) s[j++]=table[digit[i]]; s[j]='\0'; }參考程式
此題可以變形為：將十進位整數轉換為八進位數，或將十進位整數轉換為二進位數。參考程式如下。
#include <stdio.h> void fun(int a, char s[]) { int digit[11],cnt=0; do { digit[cnt++]=a%8; a=a/8; } while (a!=0); int i,j; for (i=cnt-1,j=0;i>=0;i--) s[j++]=digit[i]+'0'; s[j]='\0'; } int main() { int n; char s[12]; printf("請輸入一個十進位整數n (0<=a<=2147483647) : "); scanf("%d",&n); fun(n,s); printf("轉換為八進位數為 %s\n",s); return 0; }十進位整數轉換為八進位數
#include <stdio.h> void fun(int a, char s[]) { int cnt=0; do { s[cnt++]=a%2+'0'; a=a/2; } while (a!=0); s[cnt]='\0'; int i,j; for (i=0,j=cnt-1;i<j;i++,j--) // 字元串s逆序 { char ch; ch=s[i]; s[i]=s[j]; s[j]=ch; } } int main() { int n; char s[33]; printf("請輸入一個十進位整數n (0<=a<=2147483647) : "); scanf("%d",&n); fun(n,s); printf("轉換為二進位數為 %s\n",s); return 0; }十進位整數轉換為二進位數
47、編寫一個函數int fun(char s[])，其功能是：將字元串s中保存的十六進位數轉換為對應的十進位整數，並作為函數值返回。
#include <stdio.h> int fun(char s[]) { } int main() { int n; char s[9]; printf("請輸入一個不超過8位的十六進位數: "); scanf("%s",s); n=fun(s); printf("轉換為十進位數為 %d\n",n); return 0; }
int fun(char s[]) { int num=0,i,t; for (i=0;s[i]!='\0';i++) { if (s[i]>='A' && s[i]<='F') t=s[i]-'A'+10; else if (s[i]>='a' && s[i]<='f') t=s[i]-'a'+10; else t=s[i]-'0'; num=num*16+t; } return num; }參考程式
48、一個二進位數將其轉換成八進位數，可以使用如下轉換方法：
如果二進位的數字的位數不能被三整除，則在左側補 0 直到數字位數是 3 的倍數。
將這個二進位數每三位分成一組。每組的二進位可用如下所示的數字替換。
000 ----- 0 001 ----- 1 010 ----- 2 011 ----- 3 100 ----- 4 101 ----- 5 110 ----- 6 111 ----- 7
編寫函數void fun(char bin[], char oct[])，其功能是：將字元串bin中保存的二進位整數，轉換為八進位數並保存到字元串oct中。
例如，設bin中的字元串為“11001100”，執行函數後，oct數組中保存的字元串為“314”。
#include <stdio.h> #include <string.h> void fun(char bin[], char oct[]) { } int main() { char s2[101],s8[35]; printf("請輸入一個不超過100位的二進位數: "); scanf("%s",s2); fun(s2,s8); printf("轉換為八進位數為 %s\n",s8); return 0; }
void fun(char bin[], char oct[]) { if (bin[0]=='0') { oct[0]='0'; oct[1]='\0'; return ; } int len=strlen(bin),i,j; if (len%3==0) { i=0; j=0; } else if (len%3==1) { i=1; j=1; oct[0]='1'; } else { i=2; j=1; oct[0]=(bin[0]-'0')*2+(bin[1]-'0')+'0'; } for (;bin[i]!='\0';i+=3) { oct[j++]=(bin[i]-'0')*4+(bin[i+1]-'0')*2+(bin[i+2]-'0')+'0'; } oct[j]='\0'; }參考程式
此題可以變形為：將二進位整數轉換為十六進位數。參考程式如下。
#include <stdio.h> #include <string.h> void fun(char bin[], char hex[]) { char table[17]="0123456789ABCDEF"; if (bin[0]=='0') { hex[0]='0'; hex[1]='\0'; return ; } int len=strlen(bin),i,j; if (len%4==0) { i=0; j=0; } else if (len%4==1) { i=1; j=1; hex[0]='1'; } else if (len%4==2) { i=2; j=1; hex[0]=(bin[0]-'0')*2+(bin[1]-'0')+'0'; } else { i=3; j=1; hex[0]=(bin[0]-'0')*4+(bin[1]-'0')*2+(bin[2]-'0')+'0'; } for (;bin[i]!='\0';i+=4) { hex[j++]=table[(bin[i]-'0')*8+(bin[i+1]-'0')*4+(bin[i+2]-'0')*2+bin[i+3]-'0']; } hex[j]='\0'; } int main() { char s2[101],s16[26]; printf("請輸入一個不超過100位的二進位數: "); scanf("%s",s2); fun(s2,s16); printf("轉換為十六進位數為 %s\n",s16); return 0; }二進位數轉換為十六進位數
49、1221是一個非常特殊的數，它從左邊讀和從右邊讀是一樣的。編寫函數void fun (int a[], int *n)，其功能是：找出所有這樣的四位十進位數，將它們按從小到大的順序保存到數組a中，並通過形參n返回找到的這些四位數的個數。
#include <stdio.h> void fun (int a[], int *n) { } int main() { int aa[9000],n, i ; fun (aa,&n) ; printf("The Result is : \n"); for ( i = 0 ; i < n ; i++ ) { printf("%6d", aa[i]) ; if ((i + 1) % 10 == 0) printf("\n") ; } return 0; }
void fun (int a[], int *n) { int i,cnt=0; for (i=1000;i<=9999;i++) { int qw=i/1000; int bw=i%1000/100; int sw=i%100/10; int gw=i%10; if (qw==gw && bw==sw) a[cnt++]=i; } *n=cnt; }參考程式1
void fun (int a[], int *n) { int i,cnt=0; for (i=10;i<=99;i++) { int qw=i/10; int bw=i%10; a[cnt++]=i*100+10*bw+qw; } *n=cnt; }參考程式2
50、12321是一個非常特殊的數，它從左邊讀和從右邊讀是一樣的；123321也是一個非常特殊的數，它從左邊讀和從右邊讀也是一樣的。編寫函數void fun (int sum,int a[], int *n)，其功能是：找出所有這樣的五位和六位十進位數，滿足各位數字之和等於sum，將它們按從小到大的順序保存到數組a中，並通過形參n返回找到的這些五位和六位十進位數的個數。
例如，若sum=52，則找到的十進位數為899998、989989和998899。
#include <stdio.h> void fun (int sum,int a[], int *n) { } int main() { int aa[9000],s,n, i ; printf("Please input the Sum (2<=sum<=54) : "); scanf("%d",&s); fun (s,aa,&n) ; printf("The Result is : \n"); for ( i = 0 ; i < n ; i++ ) { printf("%7d", aa[i]) ; if ((i + 1) % 10 == 0) printf("\n") ; } return 0; }
void fun (int sum,int a[], int *n) { int i,cnt=0; for (i=10;i<=99;i++) // 構造五位數 { int ww=i/10; // 萬位 int qw=i%10; // 千位 int bw=sum-2*(ww+qw); // 百位 if (bw>=0 && bw<=9) { a[cnt++]=i*1000+bw*100+10*qw+ww; } } if (sum%2==0) // 若sum為偶數，可以構造六位數 { for (i=100;i<=999;i++) { int sww=i/100; // 十萬位 int ww=i%100/10; // 萬位 int qw=i%10; // 千位 if (sum==2*(sww+ww+qw)) { a[cnt++]=i*1000+100*qw+10*ww+sww; } } } *n=cnt; }參考程式
