《C語言程序設(shè)計》(譚浩強(qiáng)第五版) 第6章 利用數(shù)組處理批量數(shù)據(jù) 習(xí)題解析與答案
2022-04-19 11:26:23

你也可以上程序咖(https://meta.chengxuka.com)，打開大學(xué)幕題板塊，不但有答案，講解，還可以在線答題。

題目1：用篩選法求100 之內(nèi)的素數(shù)。

解：

所謂"篩選法"指的是"埃拉托色尼（Eratosthenes）篩法"。埃拉托色尼是古希臘的著名數(shù)學(xué)家。他采取的方法是，在一張紙上寫上1～1000 的全部整數(shù)，然后逐個判斷它們是否是素數(shù)，找出一個非素數(shù)，就把它挖掉，最后剩下的就是素數(shù)，見圖6.1。

具體做法如下∶

（1）先將1挖掉（因?yàn)?不是素數(shù)）。

（2）用2除它后面的各個數(shù)，把能被2整除的數(shù)挖掉，即把2的倍數(shù)挖掉。

（3）用3除它后面各數(shù)，把3 的倍數(shù)挖掉。

（4）分別用4，5…各數(shù)作為除數(shù)除這些數(shù)以后的各數(shù)。這個過程一直進(jìn)行到在除數(shù)后面的數(shù)已全被挖掉為止。例如在圖6.1中找1～50 的素數(shù)，要一直進(jìn)行到除數(shù)為 47為止。事實(shí)上，可以簡化，如果需要找1～n 的素數(shù)，只須進(jìn)行到除數(shù)為 $ sqrt{n} $（取其整數(shù)）即可，例如對1～50，只須進(jìn)行到將 $ sqrt{7} $ 作為除數(shù)即可。請讀者思考為什么。

上面的算法可表示為∶

（1）挖去1;

（2）用下一個未被挖去的數(shù) p 除 p 后面?zhèn)€數(shù)，把 p 的倍數(shù)挖掉;

（3）檢查p是否小于 $ sqrt{n} $ 的整數(shù)部分（如果 n=1000，則檢查 p<31 是否成立），如果是，則返回（2）繼續(xù)執(zhí)行，否則就結(jié)束;

（4）剩下的數(shù)就是素數(shù)。

用計算機(jī)解此題，可以定義一個數(shù)組 a。a[1]～a[n] 分別代表1～n這 n 個數(shù)。如果檢查出數(shù)組 a的某一元素的值是非素數(shù)，就使它變?yōu)?0，最后剩下不為 0 的就是素數(shù)。

程序如下：

#include <stdio.h>
#include <math.h> //程序中用到求平方根函數(shù) sqrt
int main()
{

	int i, j, n, a[101];	   //定義a數(shù)組包含101個元素
	for (i = 1; i <= 100; i++) // a[0]不用，只用a[1]～a[100]
		a[i] = i;			   //使 a[1]~a[100]的值為1～100
	a[1] = 0;				   //先"挖掉"a[1]
	for (i = 2; i < sqrt(100); i++)
		for (j = i + 1; j <= 100; j++)
		{
			if (a[i] != 0 && a[j] != 0)
				if (a[j] % a[i] == 0)
					a[j] = 0; //把非素數(shù)“挖掉"
		}
	printf("
");
	for (i = 2, n = 0; i <= 100; i++)
	{
		if (a[i] != 0) //選出值不為0的數(shù)組元素,即素數(shù)
		{
			printf("%5d", a[i]); //輸出素數(shù),寬度為5列
			n++;				 //累積本行已輸出的數(shù)據(jù)個數(shù)
		}
		if (n == 10)
		{
			printf("
");
			n = 0;
		}
	}
	printf("
");
	return 0;
}

運(yùn)行結(jié)果：

題目2：用選擇法對10個整數(shù)排序。

解：

選擇排序的思路為：設(shè)有10個元素 a[1]~a[10]，將 a[1] 與 a[2]~a[10] 比較，若 a[1] 比 a[2]～a[10] 都小，則不進(jìn)行交換，即無任何操作。若 a[2]～a[10] 中有一個以上比 a[1] 小，則將其中最大的一個（假設(shè)為 a[i] ）與 a[1] 交換，此時 a[1] 中存放了10 個中最小的數(shù)。第 2 輪將 a[2] 與 a[3]～a[10] 比較，將剩下 9 個數(shù)中的最小者 a[i] 與 a[2] 對換，此時a[2] 中存放的是10 個中第二小的數(shù)。依此類推，共進(jìn)行 9 輪比較，a[1]~a[10] 就已按由小到大的順序存放了。N-S圖如圖6.2 所示。

程序如下∶

#include <stdio.h>
int main()
{
	int i, j, min, temp, a[11];
	printf("enter data:
");
	for (i = 1; i <= 10; i++)
	{
		printf("a[%d]=", i);
		scanf("%d", &a[i]); //輸人10個數(shù)
	}
	printf("
");
	printf("The orginal numbers:
");
	for (i = 1; i <= 10; i++)
		printf("%5d", a[i]); //輸出這10個數(shù)
	printf("
");
	for (i = 1; i <= 9; i++) //以下8行是對10個數(shù)排序
	{
		min = i;
		for (j = i + 1; j <= 10; j++)
			if (a[min] > a[j])
				min = j;
		temp = a[i]; //以下3行將a[i+ 1]~a[10]中的最小值與a[i]對換
		a[i] = a[min];
		a[min] = temp;
	}
	printf("
The sorted numbers:
"); //輸出已排好序的10個數(shù)!
	for (i = 1; i <= 10; i++)
		printf("%5d", a[i]);
	printf("
");
	return 0;
}

運(yùn)行結(jié)果：

輸入10個數(shù)后，程序輸出結(jié)果。

題目3：求一個 3×3 的整型矩陣對角線元素之和。

解：

答案代碼：

#include <stdio.h>
int main()
{
	int a[3][3], sum = 0;
	int i, j;
	printf("enter data:
");
	for (i = 0; i < 3; i++)
		for (j = 0; j < 3; j++)
			scanf("%3d", &a[i][j]);
	for (i = 0; i < 3; i++)
		sum = sum + a[i][i];
	printf("sum=%6d
", sum);
	return 0;
}

運(yùn)行結(jié)果：

關(guān)于輸入數(shù)據(jù)方式的討論：

在程序的 scanf 語句中用"%d"作為輸入格式控制，上面輸入數(shù)據(jù)的方式顯然是可行的。其實(shí)也可以在一行中連續(xù)輸入9個數(shù)據(jù)，如：

結(jié)果也一樣。在輸入完9個數(shù)據(jù)并按回車鍵后，這 9個數(shù)據(jù)被送到內(nèi)存中的輸入緩沖區(qū)中，然后逐個送到各個數(shù)組元素中。下面的輸入方式也是正確的：

或者

都是可以的。

請考慮，如果將程序第7～9行改為

for (j=0;j<3;j++)
scanf(" %d %d %d" , &a[0][j], &a[1][j],&a[2][j]);

應(yīng)如何輸入，是否必須一行輸入3個數(shù)據(jù)，如：

答案是可以按此方式輸入，也可以不按此方式輸入，而采用前面介紹的方式輸入，不論分多少行、每行包括幾個數(shù)據(jù)，只要求最后輸入完9個數(shù)據(jù)即可。

程序中用的是整型數(shù)組，運(yùn)行結(jié)果是正確的。如果用的是實(shí)型數(shù)組，只須將程序第4 行的 int 改為 float 或 double 即可，在輸入數(shù)據(jù)時可輸入單精度或雙精度的數(shù)。

題目4：有一個已排好序的數(shù)組，要求輸入一個數(shù)后，按原來排序的規(guī)律將它插入數(shù)組中。

解：

假設(shè)數(shù)組 a有n個元素，而且已按升序排列，在插入一個數(shù)時按下面的方法處理：

（1）如果插入的數(shù) num 比 a數(shù)組最后一個數(shù)大，則將插入的數(shù)放在 a數(shù)組末尾。

（2）如果插入的數(shù) num不比a數(shù)組最后一個數(shù)大，則將它依次和 a[0]～a[n-1] 比較，直到出現(xiàn) a[i] > num 為止，這時表示 a[0]~a[i-1] 各元素的值比 num 小，a[i] ～a[n-1] 各元素的值比 num 大。num理應(yīng)插到 a[i-1] 之后、a[i] 之前。怎樣才能實(shí)現(xiàn)此目的呢? 將 a[i]～a[n-1] 各元素向后移一個位置（即 a[i] 變成 a[i+1]，…，a[n-1]變成 a[n] 。然后將 num 放在 a[i] 中。N-S圖如圖6.3所示。

答案代碼：

#include <stdio.h>
int main()
{
	int a[11] = {1, 4, 6, 9, 13, 16, 19, 28, 40, 100};
	int temp1, temp2, number, end, i, j;
	printf("array a:
");
	for (i = 0; i < 10; i++)
		printf("%5d", a[i]);
	printf("
");
	printf("insert data:");
	scanf("%d", &number);
	end = a[9];
	if (number > end)
		a[10] = number;
	else
	{
		for (i = 0; i < 10; i++)
		{
			if (a[i] > number)
			{
				temp1 = a[i];
				a[i] = number;
				for (j = i + 1; j < 11; j++)
				{
					temp2 = a[j];
					a[j] = temp1;
					temp1 = temp2;
				}
				break;
			}
		}
	}
	printf("Now aray a:
");
	for (i = 0; i < 11; i++)
		printf("%5d", a[i]);
	printf("
");
	return 0;
}

運(yùn)行結(jié)果：

題目5：將一個數(shù)組中的值按逆序重新存放。例如，原來順序?yàn)?，6，5，4，1。要求改為1，4，5，6，8。

解：

此題的思路是以中間的元素為中心，將其兩側(cè)對稱的元素的值互換即可。 例如，將5和9互換，將8和6互換。N-S圖見圖6.4。

答案代碼：

#include <stdio.h>
#define N 5
int main()
{
	int a[N], i, temp;
	printf("enter array a:
");
	for (i = 0; i < N; i++)
		scanf("%d", &a[i]);
	printf("array a:
");
	for (i = 0; i < N; i++)
		printf("%4d", a[i]);
	for (i = 0; i < N / 2; i++) //循環(huán)的作用是將對稱的元素的值互換
	{
		temp = a[i];
		a[i] = a[N - i - 1];
		a[N - i - 1] = temp;
	}
	printf("
Now,array a:
");
	for (i = 0; i < N; i++)
		printf("%4d", a[i]);
	printf("
");
	return 0;
}

運(yùn)行結(jié)果：

題目6：輸出以下的楊輝三角形（要求輸出 10行）

1
1		1
1		2		1
1		3		3		1
1		4		6		4		1
1		5		10	10	5		1
...

解：

楊輝三角形是 $ (a+b)^n $ 展開后各項(xiàng)的系數(shù)。例如:

$ (a+b)^0 $ 展開后為 1，系數(shù)為1

$ (a+b)^1 $ 展開后為 $ a+b $ ，系數(shù)為1，1

$ (a+b)^2 $ 展開后為 $ （a^2+2ab+b2) $ ，系數(shù)為1，2，1

$ (a+b)^3 $ 展開后為 $ （a^3+3a2b+3ab^2+b3) $ ，系數(shù)為1，3，3，1

$ (a+b)^4 $ 展開后為 $ （a^4+4a3b+6a^2b2+4ab^3+b4) $ ，系數(shù)為1，4，6，4，1

以上就是楊輝三角形的前5 行。楊輝三角形各行的系數(shù)有以下的規(guī)律∶

（1）各行第1個數(shù)都是1。

（2）各行最后一個數(shù)都是1。

（3）從第3行起，除上面指出的第1個數(shù)和最后一個數(shù)外，其余各數(shù)是上一行同列和前一列兩個數(shù)之和。例如，第4行第 2個數(shù)（3）是第3行第2個數(shù)（2）和第3行第1個數(shù)（1）之和?？梢赃@樣表示∶

a[i][j]=a[i-1][j]+a[i-1]ij-1]

其中，i為行數(shù)，，為列數(shù)。

答案代碼如下∶

#include <stdio.h>
#define N 10
int main()
{
	int i, j, a[N][N]; //數(shù)組為10行10列
	for (i = 0; i < N; i++)
	{
		a[i][i] = 1; //使對角線元素的值為1
		a[i][0] = 1; //使第1列元素的值為1
	}
	for (i = 2; i < N; i++) //從第3 行開始處理
		for (j = 1; j <= i - 1; j++)
			a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
	for (i = 0; i < N; i++)
	{
		for (j = 0; j <= i; j++)
			printf("%6d", a[i][j]); // 輸出數(shù)組各元素的值
		printf("
");
	}
	printf("
");
	return 0;
}

說明：數(shù)組元素的序號是從 0 開始算的，因此數(shù)組中 0 行 0 列的元素實(shí)際上就是楊輝三角形中第 1 行第 1 列的數(shù)據(jù)，余類推。

運(yùn)行結(jié)果：

題目7：輸出"魔方陣"。所謂魔方陣是指這樣的方陣，它的每一行、每一列和對角線之和均相等。例如，三階魔方陣為

8 1 6 
3 5 7 
4 9 2

要求輸出 1～n² 的自然數(shù)構(gòu)成的魔方陣。

解：魔方陣中各數(shù)的排列規(guī)律如下∶

（1）將 1 放在第 1 行中間一列。

（2）從 2 開始直到 n×n 止，各數(shù)依次按此規(guī)則存放：每一個數(shù)存放的行比前一個數(shù)的行數(shù)減 1 ，列數(shù)加 1（例如上面的三階魔方陣，5 在 4的上一行后一列）。

（3）如果上一數(shù)的行數(shù)為 1，則下一個數(shù)的行數(shù)為 n（指最下一行）。例如，1 在第 1 行，則 2 應(yīng)放在最下一行，列數(shù)同樣加 1。

（4）當(dāng)上一個數(shù)的列數(shù)為 n 時，下一個數(shù)的列數(shù)應(yīng)為 1，行數(shù)減 1。例如，2 在第 3 行最后一列，則 3 應(yīng)放在第 2 行第 1 列。

（5）如果按上面規(guī)則確定的位置上已有數(shù)，或上一個數(shù)是第 1 行第 n 列時，則把下一個數(shù)放在上一個數(shù)的下面。例如，按上面的規(guī)定，4 應(yīng)該放在第 1 行第 2 列，但該位置已被 1 占據(jù)，所以 4 就放在 3 的下面。由于 6 是第 1 行第 3 列（即最后一列），故 7 放在 6 下面。

按此方法可以得到任何階的魔方陣。

N-S圖如圖6.5所示。

答案代碼：

#include <stdio.h>
int main()
{
	int a[15][15], i, j, k, p, n;
	p = 1;
	while (p == 1)
	{
		printf("enter n(n= 1--15) : "); //要求階數(shù)為1～15 的奇數(shù)
		scanf("%d", &n);
		if ((n != 0) && (n <= 15) && (n % 2 != 0))
			p = 0;
	}
	//初始化
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			a[i][j] = 0;
	//建立魔方陣
	j = n / 2 + 1;
	a[1][j] = 1;
	for (k = 2; k <= n * n; k++)
	{
		i = i - 1;
		j = j + 1;
		if ((i < 1) && (j > n))
		{
			i = i + 2;
			j = j - 1;
		}
		else
		{
			if (i < 1)
				i = n;
			if (j > n)
				j = 1;
		}
		if (a[i][j] == 0)
			a[i][j] = k;
		else
		{
			i = i + 2;
			j = j - 1;
			a[i][j] = k;
		}
	}
	//輸出魔方陣
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
			printf("%5d", a[i][j]);
		printf("
");
	}
	return 0;
}

說明：魔方陣的階數(shù)應(yīng)為奇數(shù)。

運(yùn)行結(jié)果：

題目8：找出一個二維數(shù)組中的鞍點(diǎn)，即該位置上的元素在該行上最大、在該列上最小。也可能沒有鞍點(diǎn)。

解：一個二維數(shù)組最多有一個鞍點(diǎn)，也可能沒有。解題思路是∶先找出一行中值最大的元素，然后檢查它是否為該列中的最小值，如果是，則是鞍點(diǎn)（不需要再找別的鞍點(diǎn)了），輸出該鞍點(diǎn); 如果不是，再找下一行的最大數(shù)……如果每一行的最大數(shù)都不是鞍點(diǎn)，則此數(shù)組無鞍點(diǎn)。

答案代碼：

#include <stdio.h>
#define N 4
#define M 5 //數(shù)組為4行5列
int main()
{
	int i, j, k, a[N][M], max, maxj, flag;
	printf("please input matrix: 
");
	for (i = 0; i < N; i++) //輸人數(shù)組
		for (j = 0; j < M; j++)
			scanf("%d", &a[i][j]);
	for (i = 0; i < N; i++)
	{
		max = a[i][0];			//開始時假設(shè) a[i][0]最大
		maxj = 0;				//將列號0賦給 maxj保存
		for (j = 0; j < M; j++) //找出第i行中的最大數(shù)
			if (a[i][j] > max)
			{
				max = a[i][j]; //將本行的最大數(shù)存放在max中
				maxj = j;	   //將最大數(shù)所在的列號存放在 maxj中
			}
		flag = 1; //先假設(shè)是鞍點(diǎn)，以flag 為1代表
		for (k = 0; k < N; k++)
			if (max > a[k][maxj]) //將最大數(shù)和其同列元素相比
			{
				flag = 0; //如果 max不是同列最小，表示不是鞍點(diǎn)，令flag1為0
				continue;
			}
		if (flag) //如果flagl為1表示是鞍點(diǎn)
		{
			printf("a[%d][%d]=%d
", i, maxj, max); //輸出鞍點(diǎn)的值和所在行列號
			break;
		}
	}
	if (!flag) //如果 flag 為0表示鞍點(diǎn)不存在
		printf("It is not exist!
");
	return 0;
}

運(yùn)行結(jié)果：

①

第 2～5行是輸入的數(shù)據(jù)，最后一行是輸出的結(jié)果。

②

（無鞍點(diǎn)）

題目9：有15個數(shù)按由大到小順序存放在一個數(shù)組中，輸入一個數(shù)，要求用折半查找法找出該數(shù)是數(shù)組中第幾個元素的值。如果該數(shù)不在數(shù)組中，則輸出"無此數(shù)"。

解：從表列中查一個數(shù)最簡單的方法是從第 1 個數(shù)開始順序查找，將要找的數(shù)與表列中的數(shù)一一比較，直到找到為止（如果表列中無此數(shù)，則應(yīng)找到最后一個數(shù)，然后判定"找不到"）。

但這種"順序查找法"效率低，如果表列中有 1000個數(shù)，且要找的數(shù)恰恰是第 1000 個數(shù)，則要進(jìn)行 999 次比較才能得到結(jié)果。平均比較次數(shù)為500次。

折半查找法是效率較高的一種方法。基本思路如下：

假如有已按由小到大排好序的9個數(shù)，a[1]～a[9]，其值分別為

1,3,5,7,9,11,13,15,17

若輸入一個數(shù) 3，想查 3 是否在此數(shù)列中，先找出表列中居中的數(shù)，即 a[5]，將要找的數(shù) 3 與a[5] 比較，今[a5] 的值是 9，發(fā)現(xiàn) a[5]>3，顯然 3 應(yīng)當(dāng)在 a[1]~a[5]這部分，而不會在a[6]～a[9]這部分。這樣就可以縮小查找范圍，甩掉 a[6]～a[9] 這部分，即將查找范圍縮小為一半。再找a[1]～a[5]的居中的數(shù)，即 a[3]，將要找的數(shù) 3 與 a[3]比較，a[3]的值是 5，發(fā)現(xiàn) a[3]>3，顯然3應(yīng)當(dāng)在 a[1]～a[3]這部分。這樣又將查找范圍縮小一半。再將 3 與 a[1]～a[3] 的居中的數(shù) a[2]比較，發(fā)現(xiàn)要找的數(shù) 3 等于 a[2]，查找結(jié)束。一共比較了3 次。如果表列中有 n 個數(shù)，則最多比較的次數(shù)為 $ int(log_2n) +1 $ 。

N-S圖如圖6.6所示。

答案代碼：

#include <stdio.h>
#define N 15
int main()
{
	int i, number, top, bott, mid, loca, a[N], flag = 1, sign;
	char c;
	printf("enter data:
");
	scanf("%d", &a[0]); //輸入第1個數(shù)
	i = 1;
	while (i < N) //檢查數(shù)是否已輸入完畢
	{
		scanf("%d", &a[i]);	  //輸入下一個數(shù)
		if (a[i] >= a[i - 1]) //如果輸人的數(shù)不小于前一個數(shù)
			i++;			  //使數(shù)的序號加 1
		else
			printf("enter this data again:
"); //要求重新輸入此數(shù)
	}
	printf("
");
	for (i = 0; i < N; i++)
		printf("%5d", a[i]); // 輸出全部15個數(shù)
	printf("
");
	while (flag)
	{
		printf("input number to look for:");		//問你要查找哪個數(shù)
		scanf("%d", &number);						//輸入要查找的數(shù)
		sign = 0;									// sign為0表示尚未找到
		top = 0;									// top 是查找區(qū)間的起始位置
		bott = N - 1;								// bott是查找區(qū)間的最末位置
		if ((number < a[0]) || (number > a[N - 1])) //要查的數(shù)不在查找區(qū)間內(nèi)
			loca = -1;								//表示找不到
		while ((!sign) && (top <= bott))
		{
			mid = (bott + top) / 2; //找出中間元素的下標(biāo)
			if (number == a[mid])	//如果要查找的數(shù)正好等于中間元素
			{
				loca = mid;													   //記下該下標(biāo)
				printf("Has found %d,its position is %d
", number, loca + 1); //由于下標(biāo)從0算起，而人們習(xí)慣從1算起，因此輸出數(shù)的位置要加1
				sign = 1;													   //表示找到了
			}
			else if (number < a[mid]) //如果要查找的數(shù)小于中間元素的值
				bott = mid - 1;		  //只須在下標(biāo)為0～mid-1的元素中找
			else					  //如果要查找的數(shù)不小于中間元素的值
				top = mid + 1;
		}										 //只須在下標(biāo)為 mid+1～bott的元素中找
		if (!sign || loca == -1)				 // sign為0或 loca等于—1，意味著找不到
			printf("cannot find %d.
", number); //輸出"找不到"
		printf("continue or not(Y/N)?");		 //問你是否繼續(xù)查找
		scanf("%c", &c);						 //不想繼續(xù)查找輸入'N'或'n'
		if (c == 'N' || c == 'n')
			flag = 0; // lag 為開關(guān)變量.控制程序是否結(jié)束運(yùn)行
	}
	return 0;
}

運(yùn)行結(jié)果：

以上運(yùn)行情況是這樣的∶開始輸入3 個數(shù)，由于順序不是由小到大，程序不接收，要求重新輸入。再輸入15個數(shù)，然后程序輸出這 15 個數(shù)，供核對。程序詢問要找哪個數(shù)，輸入7，輸出"找不到7"。問是否繼續(xù)找數(shù)，回答y表示 yes，再問找哪個數(shù)，輸入12，輸出"找到了。它是第7個數(shù)"。

題目10：有一篇文章，共有3行文字，每行有 80個字符。要求分別統(tǒng)計出其中英文大寫字母、小寫字母、數(shù)字、空格以及其他字符的個數(shù)。

解：N-S圖如圖6.7所示。

答案代碼：

#include <stdio.h>
int main()
{
	int i, j, upp, low, dig, spa, oth;
	char text[3][80];
	upp = low = dig = spa = oth = 0;
	for (i = 0; i < 3; i++)
	{
		printf("please input line %d:
", i + 1);
		gets(text[i]);
		for (j = 0; j < 80 && text[i][j] != '