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')
上述題目的答案都不是唯一的,當答案和標準答案不一樣時,會將答案帶入程序運行,通過運行結果來判斷正誤。
- 前言
- 入門訓練四道題
- 基礎練習之閏年判斷——BASIC-1
- 基礎練習之01字串——BASIC-2
- 基礎練習之字母圖形——BASIC-3
- 基礎練習之數列特征——BASIC-4
- 基礎練習之查找整除——BASIC-5
- 基礎練習之楊輝三角形——BASIC-6
- 基礎練習之特殊的數字——BASIC-7
- 基礎練習之回文數——BASIC-8
- 基礎練習之特殊回文數——BASIC-9
- 基礎練習之十進制轉十六進制——BASIC-10
- 基礎練習之十六進制轉十進制——BASIC-11
- 基礎練習之十六進制轉八進制——BASIC-12
- 基礎練習之數列排序——BASIC-13
- 算法訓練之區間K大數查詢——ALGO-1
- 算法訓練之最大最小公倍數——ALGO-2
- 藍橋杯-代碼填空之一
- 藍橋杯-代碼填空之二
- 藍橋杯-代碼填空之三
- 藍橋杯-代碼填空之精品
- 藍橋杯-歷屆試題之翻硬幣
- 藍橋杯-代碼填空之四
- 藍橋杯-結果填空題
- 藍橋杯-結果填空之排座位
- 藍橋杯-歷屆試題之大臣的旅費