【C語言16天強化訓練】從基礎入門到進階：Day 13

?🔥個人主頁：艾莉絲努力練劍

?專欄傳送門：《C語言》、《數據結構與算法》、C語言刷題12天IO強訓、LeetCode代碼強化刷題、洛谷刷題、C/C++基礎知識知識強化補充、C/C++干貨分享&學習過程記錄

🍉學習方向：C/C++方向學習者

??人生格言：為天地立心，為生民立命，為往圣繼絕學，為萬世開太平

前言：距離我們學完C語言已經過去一段時間了，在學習了初階的數據結構之后，博主還要更新的內容就是【C語言16天強化訓練】，之前博主更新過一個【C語言刷題12天IO強訓】的專欄，那個只是從入門到進階的IO模式真題的訓練。【C語言16天強化訓練】既有IO型，也有接口型。和前面一樣，今天依然是訓練五道選擇題和兩道編程算法題，希望大家能夠有所收獲！

一、五道選擇題

1.1? 題目1

1.2? 題目2

1.3? 題目3

1.4? 題目4

1.5? 題目5

二、兩道算法題

2.1? 統計每個月兔子的總數

2.1.1 題目理解

2.1.2 思路

2.2??數列的和

2.2.1 題目理解

2.2.2 思路

結尾

一、五道選擇題

1.1? 題目1

題干：如果x = 2014 ，下面函數的返回值是（）

int fun(unsigned int x)
{int n = 0;while(x + 1){n++;x = x | (x + 1);} return n;
}

A. 20? ? ?B. 21? ? ?C. 23? ? ?D. 25

解析：正確答案就是C選項。

這個作用是對整型中0的個數進行統計，x=x|(x+1);的作用是每次循環把x的二進制中從右往左數的最后一位0變成1，一直到變成全1的時候x+1就溢出為全0，循環結束。2014的二進制是0000 0000 000 0000 0000 0111 1101 1110，所以結果是23。

1.2? 題目2

題干：下列語句定義 x 為指向 int 類型變量 a 的指針，其中哪一個是正確的（）

A. int a , *x = a;? ? ?B. int a , *x = &a;? ? ?C. int *x = &a , a;? ? ?D. int a , x = a;

解析：正確答案就是B選項。

A選項的x是指針，賦值時使用a不合適，C選項在賦值時a變量還沒定義，D選項中的x不是指針，B選項是最合適的。

1.3? 題目3

題干：下面有關空指針和未初始化指針，說法錯誤的是（）

A. 對0x0這個地址取值是非法的

B. 空指針可以確保不指向任何對象或函數; 而未初始化指針則可能指向任何地方? ? ?

C. 空指針與任何對象或函數的指針值都不相等? ? ?

D. malloc在其內存分配失敗時返回的是一個未初始化的指針

解析：正確答案就是D選項。

malloc函數在內存分配失敗時返回NULL，其余選項都正確。

1.4? 題目4

題干：若有定義 int a[8]; ，則以下表達式中不能代表數組元素 a[1] 的地址的是（）

A. &a[0]+1? ? ?B. &a[1] ? ? ?C. &a[0]++? ? ?D. a+1

解析：正確答案就是D選項。

D選項中a計算時是首元素地址，再加1，就是a[1]的地址，AB明顯對，C選項a[0]先和++結合，形成一個表達式，不能對表達式取地址，會報錯。

1.5? 題目5

題干：以下選項中，對基本類型相同的兩個指針變量不能進行運算的運算符是（）

A. +? ? ?B. -? ? ?C. =? ? ?D. ==

解析：正確答案就是A選項。

A選項錯誤，因為兩個地址相加無意義也可能越界，所以規定不允許指針相加；

B選項，可以求出兩個數據元素儲存位置之間的相隔同數據類型的元素個數；

C選項，賦值，沒問題；

D選項，判斷兩指針是否相同。

選擇題答案如下：

1.1? C

1.2? B

1.3? D

1.4? D

1.5? A

校對一下，大家都做對了嗎？

二、兩道算法題

2.1? 統計每個月兔子的總數

牛客網鏈接：HJ37 統計每個月兔子的總數

題目描述：

2.1.1 題目理解

這道題的關鍵在于尋找數字之間的規律，如果細心的友友會發現這其實是一個斐波那契數列。規律：第 n 個月的兔子數量實際上就是第 n - 1 個斐波那契數。

題意理解——計算斐波那契數列的第n項（從第1項開始：1,1,2,3,5,...），因為兔子生長規律與斐波那契數列相同。如下圖所示，博主這里畫了一個簡單的示意圖——

這道題是IO型的，下面是C語言的模版（如果是IO型就可以不用管它們了）——

2.1.2 思路

1、兔子從出生后第三個月開始每月生一只，且不死。

2、設第n個月兔子總數為 f(n)，則：

（1）第 1 個月：f(1)=1；

（2）第 2 個月：f(2)=1；

（3）第 n 個月（n ≥ 3）：f(n) = f(n - 1)+f(n - 2)（因為新生的兔子數等于兩個月前的兔子總數）。

3、直接使用迭代法（循環）計算斐波那契數列即可。

代碼演示：

//C語言實現
#include <stdio.h>int main()
{int n;scanf("%d", &n);if (n <= 2){printf("1\n");return 0;}int a = 1, b = 1, c;for (int i = 3; i <= n; i++){c = a + b;a = b;b = c;}printf("%d\n", b);return 0;
}

時間復雜度：O(n)，需要迭代n次；

空間復雜度：O(1)，僅需幾個變量。

同樣的，我們知道這里是一個斐波那契數列之后，代碼也可以這樣實現——

代碼演示：

//C語言實現
#include <stdio.h>
int main()
{int n;while (~scanf("%d", &n)) {int num1 = 1, num2 = 1, ret = 0;for (int i = 2; i < n; i++) {ret = num1 + num2;num1 = num2;num2 = ret;}printf("%d\n", ret);} return 0;
}

時間復雜度：O(n)，需要迭代n次；

空間復雜度：O(1)，僅需幾個變量。

我們學習了C++之后也可以嘗試用C++來實現一下，看看自己前段時間C++學得怎么樣——

代碼演示：

//C++實現
#include <iostream>
using namespace std;int main()
{int n;cin >> n;if (n <= 2){cout << 1 << endl;return 0;}int a = 1, b = 1, c;for (int i = 3; i <= n; i++){c = a + b;a = b;b = c;}cout << b << endl;return 0;
}

時間復雜度：O(n)，空間復雜度：O(1)。

我們目前要寫出來C++的寫法是非常考驗前面C++的學習情況好不好的，大家可以嘗試去寫一寫，優先掌握C語言的寫法，博主還沒有介紹C++的算法題，之后會涉及的，敬請期待！

2.2??數列的和

牛客網鏈接：REAL246 數列的和

題目描述：

2.2.1 題目理解

給定n和m，計算數列：n, sqrt(n), sqrt(sqrt(n)), ...（共m項）的和，保留兩位小數。

2.2.2 思路

（1）第一項為n，之后每一項是前一項的平方根；

（2）循環m次，每次將當前項加到總和，并更新當前項為它的平方根；

（3）注意精度：使用double類型，輸出保留兩位小數。

這道題是IO型的，下面是C語言的模版（如果是IO型就可以不用管它們了）——

代碼演示：

#include <stdio.h>
#include <math.h>int main() 
{int n, m;while (scanf("%d %d", &n, &m) != EOF) {double sum = 0;double current = n;for (int i = 0; i < m; i++) {sum += current;current = sqrt(current);}printf("%.2f\n", sum);}return 0;
}

時間復雜度：O(m)，每次循環計算一次平方根（通常為常數時間操作）；

空間復雜度：O(1)，僅需幾個變量。

既然明確了我們調用C語言math庫，就可以這樣——

求取一個數字的平方根可以使用數學庫中的double sqrt(double num) 函數完成，接下來只需要從數字自身開始進行求和并在求和后將 n 自身計算成為自身的平方根即可。

代碼演示：

#include <stdio.h>
#include <math.h>int main()
{double m, n;while (~scanf("%lf %lf", &n, &m)) {double sum = 0;while (m-- > 0) {sum += n;//從自身開始以及每次的平方根進行求和n = sqrt(n);//n成為當前自身的平方根}printf("%.2lf\n", sum);} return 0;
}

時間復雜度：O(n)；

空間復雜度：O(1)。

我們學習了C++之后也可以嘗試用C++來實現一下，看看自己前段時間C++學得怎么樣——

代碼演示：

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;int main() 
{int n, m;while (cin >> n >> m) {double sum = 0;double current = n;for (int i = 0; i < m; i++) {sum += current;current = sqrt(current);}cout << fixed << setprecision(2) << sum << endl;}return 0;
}