N進制小數—車票找零方案計數—串的反轉—串的輪換—大數分塊乘法—二進制串轉整數 ①N進制小數 將任意十進制正小數分別轉換成2,3,4,5,6,7,8,9進制正小數，小數點后保留8位，并輸出。例如：若十進制小數為0.795，則輸出： 十進制正小數 0.795000 轉換成 2 進制數為: 0.11001011 十進制正小數 0.795000 轉換成 3 進制數為: 0.21011011 十進制正小數 0.795000 轉換成 4 進制數為: 0.30232011 十進制正小數 0.795000 轉換成 5 進制數為: 0.34414141 十進制正小數 0.795000 轉換成 6 進制數為: 0.44341530 十進制正小數 0.795000 轉換成 7 進制數為: 0.53645364 十進制正小數 0.795000 轉換成 8 進制數為: 0.62702436 十進制正小數 0.795000 轉換成 9 進制數為: 0.71348853 以下代碼提供了這個功能。其中，dTestNo表示待轉的十進制小數。iBase表示進制數。請填寫缺失的部分。 ~~~ void fun(double dTestNo, int iBase) { int iT[8]; int iNo; printf("十進制正小數 %f 轉換成 %d 進制數為: ",dTestNo, iBase); for(iNo=0;iNo<8;iNo++) { dTestNo *= iBase; iT[iNo] = ________________; if(___________________) dTestNo -= iT[iNo]; } printf("0."); for(iNo=0; iNo<8; iNo++) printf("%d", iT[iNo]); printf("\n"); } void main ( ) { double dTestNo= 0.795; int iBase; for(iBase=2;iBase<=9;iBase++) fun(dTestNo,iBase); printf("\n"); } ~~~ 這道題看到函數傳進來的是一個小數和進制數， 題中建立一個大小為8的數組，再看看輸出，就知道，是把每一個相應進制數存在數組中， 在本上算一算就發現，小數乘以相應進制，整數部分即為該進制第一個小數（這個是小數轉換進制的基礎知識）， 顯然題目，也是這么做的，填空就不難了，第一個就是取整數部分，直接強制類型轉換就可以， 第二個就是判斷什么時候需要減去整數部分，前面是*=，原來的小數變化了，求下一個數，肯定要把整數部分清零， 所以就是，當數組內容不為0的時候，也可以說是大于0的時候。 答案：（答案不唯一，只要能滿足要求即可） 空1： ?(int)dTestNo ?? 空2： ?dTestNo>=1.0 ? ②車票找零方案計數 公交車票價為5角。假設每位乘客只持有兩種幣值的貨幣：5角、1元。 再假設持有5角的乘客有m人，持有1元的乘客有n人。由于特殊情況，開始的時候，售票員沒有零錢可找。 我們想知道這m+n名乘客以什么樣的順序購票則可以順利完成購票過程。 顯然，m < n的時候，無論如何都不能完成，m >=n的時候，有些情況也不行。 比如，第一個購票的乘客就持有1元。 下面的程序計算出這m+n名乘客所有可能順利完成購票的不同情況的組合數目。 注意：只關心5角和1元交替出現的次序的不同排列，持有同樣幣值的兩名乘客交換位置并不算做一種新的情況來計數。 //m: 持有5角幣的人數 //n: 持有1元幣的人數 //返回：所有順利完成購票過程的購票次序的種類數 ~~~ int f(int m, int n) { if(m < n) return 0; if(n==0) return 1; return _______________________; } ~~~ 這道題，一看函數類型int 還有終止條件，顯然是遞歸， 遞歸的話就簡單了，你是 return f(m-1,n-1)+1還是 return f(m-1,n)+f(m,n-1) 呢？ m-1，n-1就是 當前人數，先來一個五毛錢的，再來一個1元的， 那排序基本上就是 0.5 ?1 ? 0.5 ? 1顯然方案不全， 所以就是m-1,n + m,n-1了， 答案： f(m-1, n) + f(m, n-1) ③反轉串 我們把“cba”稱為“abc”的反轉串。 下面的代碼可以把buf中的字符反轉。其中n表示buf中待反轉的串的長度。請補充缺少的代碼。 ~~~ void reverse_str(char* buf, int n) { if(n<2) return; char tmp = buf[0]; buf[0] = buf[n-1]; buf[n-1] = tmp; _______________________________; } ~~~ 題目要求很簡單，就是把串反轉，看題干，也很明白它的做法， 就是取頭尾，互換，下一步肯定是往里縮進一格，首位都縮進，肯定長度減少2了， 這樣，接著把串和長度傳下去就可以了，也是一個遞歸，因為傳遞的是指針，所以不需要返回值。 答案： reverse_str(buf+1,n-2) （答案不唯一） ④串的輪換 串“abcd”每個字符都向右移位，最右的移動到第一個字符的位置，就變為“dabc”。這稱為對串進行位移=1的輪換。同理，“abcd”變為：“cdab”則稱為位移=2的輪換。 下面的代碼實現了對串s進行位移為n的輪換。請補全缺失的代碼。 ~~~ void shift(char* s, int n) { char* p; char* q; int len = strlen(s); if(len==0) return; if(n<=0 || n>=len) return; char* s2 = (char*)malloc(_________); p = s; q = s2 + n % len; while(*p) { *q++ = *p++; if(q-s2>=len) { *q = ___________; q = s2; } } strcpy(s,s2); free(s2); } ~~~ 這道題，我是從下往上看的，看到最后有個 strcpy(s,s2) 和 free(s2) ?就明白， 它的方法就是建立一個中間串s2，s2存儲正確順序，最后直接賦值給s， 過程，malloc肯定就是開辟s2的空間，開辟空間大小顯然與s長度len有關， 后面p指針指向s頭部，q指向中間串s2的相應位置，n%len 就是計算具體指向那個地方， 然后通過循環，當p!=NULL時，將p指向內容賦值給q指向內容，然后兩者再往后移動， 這里要注意是先賦值再移動， 假如題目是 ?abcd 2，那么通過上述循環，s2串內容將是 ? 空空ab ?(空代表什么都沒有） 那個if就是判斷q是否指到了末尾，當指到末尾，就給q賦值為NULL， 將q指向s2頭部，接著賦值。這樣就達到了構建s2的目的。 簡單的說，就是： p是從s頭指向尾不變， 而q從s2中間位置向后移動，如果長度大于等于串長度，再指向s2頭部， 以 abcd 2為例就是： p從指向a移動到d， q先指向c的位置，將a，b，賦值到s2串第3,4的位置，if成立，所以將后面第5個設置NULL， 指回s2頭部，這是p指向的是c，到指到d下一個是空，所以循環跳出，s2串構建完成。 答案： len+1 0（指的是空，也可以寫成NULL或者‘\0'或者（char）0 ⑤大數分塊乘法 ? 對于32位字長的機器，大約超過20億，用int類型就無法表示了，我們可以選擇int64類型， 但無論怎樣擴展，固定的整數類型總是有表達的極限！如果對超級大整數進行精確運算呢？ 一個簡單的辦法是：僅僅使用現有類型，但是把大整數的運算化解為若干小整數的運算，即所謂：“分塊法”。 ? 如圖  表示了分塊乘法的原理。可以把大數分成多段（此處為2段）小數，然后用小數的多次運算組合表示一個大數。 可以根據int的承載能力規定小塊的大小，比如要把int分成2段，則小塊可取10000為上限值。 注意，小塊在進行縱向累加后，需要進行進位校正。 以下代碼示意了分塊乘法的原理（乘數、被乘數都分為2段）。 ~~~ void bigmul(int x, int y, int r[]) { int base = 10000; int x2 = x / base; int x1 = x % base;? int y2 = y / base; int y1 = y % base;? int n1 = x1 * y1;? int n2 = x1 * y2; int n3 = x2 * y1; int n4 = x2 * y2; r[3] = n1 % base; r[2] = n1 / base + n2 % base + n3 % base; r[1] = ____________________________________________; // 填空 r[0] = n4 / base; r[1] += _______________________; ?// 填空 r[2] = r[2] % base; r[0] += r[1] / base; r[1] = r[1] % base; } int main(int argc, char* argv[]) { int x[] = {0,0,0,0}; bigmul(87654321, 12345678, x); printf("%d%d%d%d\n", x[0],x[1],x[2],x[3]); return 0; } ~~~ 這題應該比較簡單了，根據圖很容易填上第一個空， 要注意它的r[3]、r[2]、r[1]、r[0]對應圖中r4,r3,r2,r1， 第二個空，根據下面r0也可以照葫蘆畫瓢的填出來。 答案：（答案不唯一） n2 / base + n3 / base + n4 % base ?? r[2] / base ? ? ? ? ? ? ? ? ? ?? ⑥二進制串轉整數 下列代碼把一個二進制的串轉換為整數。請填寫缺少的語句； ~~~ char* p = "1010110001100"; int n = 0; for(int i=0;i<strlen(p); i++) { n = __________________; } printf("%d\n", n); ~~~ 就是將2進制的串轉換成10進制， 如果有cmath庫函數，直接用個Pow, 這題好像沒提供， 但是，不要忘了，將10進制轉換2進制可以用while循環做： ~~~ i=0 while(num>2) { arr[i++]=num%2; num/=2; } ~~~ 這題完全可以逆著來。 還要注意一下，題目中的是字符，而不是數字。 答案： n * 2 + (p[i] - '0') 上述題目的答案都不是唯一的，當答案和標準答案不一樣時，會將答案帶入程序運行，通過運行結果來判斷正誤。