4.14 自由练习题
4.6 填空：
a)C++在——中存放数值清单。
b)数组元素的关系是——。
c)引用数组元素时，括号中包含的位置号称为——。
d)数组p的4个元素名为——、——、——和——。
e)命名数组、指定数组类型和指定数组中的元素个数称为数组——。
f)将数组元素按升序或降序排列的过程称为——。
g)在双下标数组中，习惯上第一个下标表示数组元素的——,第二个下标表示数
组元素的——。
h)m x n数组包含——行、——列和——个元素。
i)数组d中行3列5的元素名为——。
4.7 判断下列各题是否正确。如果不正确，请说明原因。
a)要引用数组中的特定位置或元素，我们指定数组名和特定元素的值。
b)数组声明为这个数组保留内存空间。
c)要为整型数组p保留100个位置，声明如下：
p[1OO];
d)将15个元素的数组中的元素初始化为0，C++程序至少要包含一个for循环。
e)求双下标数组元素和，C++程序要包含嵌套for结构。
4.8 编写完成下列任务的C++语句：
a)显示字符数组f第七十元素的值。
b)将数值输入单下标浮点数数组b的元素4。
c)将单下标整型数组e的5个元素各初始化为8。
d)求出浮点数数组c的100个元素之和并打印这些元素。
e)将a数组复制到数组b的开头部分。假设“floata[11]，b[34]；”
f)确定和打印99个元素的浮点数数组w中的最小值和最大值。
4.9 考虑2 x 3整型数组t，并编写相应的语句。
a)编写t的声明。
b)t有多少行?
c)t有多少列?
d)t有多少个元素?
e)写出t的第2行所有元素名。
f)写出t的第3列所有元素名。
g)将t中行1列2的元素设置为0。
h)将t的每个元素初始化为0，不用重复结构。
i)用嵌套for结构将t的每个元素初始化为0。
j)从终端输入t的元素值。
k)用一系列语句确定和打印数组t的最小值。
l)显示t的第1行元素。
m)显示t的第4列元素。
n)以整齐的表格形式打印数组t，将列下标设为输出首部的一行，行下标放在输出左部的一列。
4.10 用单下标数组解决下列问题。公司按佣金为员工发工资，销售员每周发200美元加上本周总销售额的9％。例如，如果某个销售员本周总销售额为5000美元，则发200+9％× 5000 = 650美元。编写一个程序(用计数器数组)确定工资在下列范围的员工数(假设将每个销售人员的工资取整)：
a)$200--$299
b)$300--$399
c)$400—$499
d)$500—$599
e)$600--$699
f)$700--$799
g)$800--$899
h)$900--$999
i)$1000以上
4.11 图 4.16 的冒泡排序方法在大数组中不适用，通过下列简单修改可以提高冒泡排序方法的性能。
a)第一遍之后，最大数总是数组中编号最大的元素，第二遍之后，次大数总是数组中编号次大的元素等等。不用每次都作九次比较，而只要第二遭比较8次，第三遍比较七次等等。
b)数组中的数据可能已经有正确或接近正确的顺序，为什么一定要进行九遍比较呢?每遍之后检查是否有所交换。如果没有交换，则数据已经正确排序，程序终止。如果有交换，则至少还要再进行一遍。
4.12 编写一条语句，完成下列单下标数组操作：
a)将整型数组consts的10个元素初始化为0。
b)将整型数组bonus的15个元京分别加10
c)从键盘读取float数组monthlyTemperatures的12个值。
d)用列格式打印整型数组bestScores的5个值。
4.13 寻找下列语句中的错误。
a)假设：char str[5] ；
cin >> str； // User types hello
b)假设：int a[ 3 ]；
cout << a[ 1 ] << " " << a[ 2 ] <<" " << a[ 3 ] << endl；
c) float f[3] = { 1.1,10.0l，100.001，1000.0001)；
d)假设：double d[ 2 ][ 10 ] ；
d [1, 9] = 2.345；
4.14 修改图 4.17 的程序，使函数mode能处理模值的连接。并修改函数median，使偶数个元素的数组中median为两个中间元素的平均值。
4.15 用单下标数组解决下列问题。读取20个数，各为10到100之间的值。读取每个数时，只打印不重复的值。“最糟的情况”是20个值都不重复。用最小的数组解决这个问题。
4.16打印 3 × 5 双下标数组 sales 的元素，表示下列语句中将其设置为0的顺序：
for ( row = 0; row < 3; row++ )
for ( column = 0; column < 5; column++ )
sales[ row ][ column] = 0;
4.17 编写一个程序，模拟投两个骰子。程序用 rand 函数投第一个骰子，并再次用rand函数投第二个骰子，然后计算两个值的和。说明：由于每个骰子显示1到6的整数值，因此两个骰子的和为2到12，7最常见，1和12最不常见。图4．24显示了36种可能的两个骰子的和。程序将投两个骰子36000次，用单下标数组估算每个和出现的次数，用表格形式打印结果。并确定和是否合理，即有六种方式投出7，因此有六分之一的可能投出7。
4.18 下列程序有什么用
1 // ex04 18.cpp
2 #include <iostream.h>
3
4 int whatIsThis( int [], int );
5
6 int main{}
7 {
8 const int arraySize = 10;
9 int a[ arraySize ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } ;
10
11 int result = whatIsThis( a, arraySize );
12
13 cout << "Result is" << result << endl;
14 return 0;
15 }
16
17 int whatIsThis( int b[], int size )
18
19 {
20 return
21 else
22 return b[ size -1 ] + whatIsThis(b, size -1 );
23 }
4.19 编写一个程序，运行1000次投骰子游戏，并回答下列问题：
a)第一次、第二次、…、第十二次和第十二次以后赢了几场?
b)第一次、第二次、…、第十二次和第十二次以后输了几场?
c)赢的机会有多少(投骰子游戏是最公平的游戏之一，为什么)，
d)投骰子游戏平均长度是多少，
e)游戏玩得越久，赢的机会是否越多?
4.20 （航空订票系统）、航空公司购买了一台用于航空订票系统的计算机，要求对新系统编程，对每个航班订座(每班10位)。
程序显示下列菜单选项：Please type 1 for "smoking"和Pleas type 2 for nonsmokijng”。如果输入1，则程序指定吸烟舱位(座位1到5)，如果输入2，则程序指定非吸烟舱位(座位6到10)。程序应打印一个登机牌，表示座位号和是否为吸烟舱位。
用一个单下标数组表示飞机的座位图。将数组的所有元素初始化为0，表示所有座位都是空的。订每个座位时，将数组相应元素设置为1，表示该座位已订。
当然，程序不能再订已经订过的座位。吸烟舱位已满时，应询问可否订非吸烟舱位；同样，非吸烟舱位已满时，应询问可否订吸烟舱位。如果同意，再相应订座，否则打印信息 Next fight leaves in 3 hours.。
4.21 下列程序有什么作用?
1 // ex04_21.cpp
2 #include <iostream,h>
3
4 void someFunction( int [], int );
5
6 int main()
7 {
8 const int arraySize = 10;
9 int a[ arraySize ] = { 32, 27, 64, 18, 95, 14, 90, 70, 60, 37 };
10
11 count << "The values in the array are:" << endl;
12 someFunction( a, arraySize );
13 cout << endl;
14 return 0;
15 }
16
17 void someFunction( int b[], int size )
18 {
19 if ( size > 0 ) {
20 someFunction{&b[1 ],size -1 );
21 cout << b[ 0 ] <<" ";
22 }
23 }
4.22 用双下标数组解决下列问题。公司有4个销售员(1到4)，销售五种产品(1到5)。每天每个销售人员要报告每种产品的销售量，报告中包含：
a)销售员号
b)产品号
c)当日总销售额
这样，每个销售人员每天要送0到5份报告。假设上个月的这些信息都有，编写一个程序，读取上月销售情况的信息，并按每个销售人员和每种产品进行汇总。所有汇总存放在双下标数组sales中。处理上个月的所有信息后，将结果打印成表格形式，每列表示一个销售员，每行表示一种产品。通过交叉求和求出上月每个销售人员的总销售额和每种产品的总销售额。表格输出的右边小计行和下边小计列中应打印这些信息。
4.23 （龟图）Logo 语言在个人计算机用户中非常流行，该语言形成了龟图的概念。假设有个机器海龟，通过 C++ 程序控制在房子中移动。在两个方向之一打开画笔，即向上或向下。
画笔向下时，海龟跟踪移动的形状并留下移动的路径，画笔向上时，海龟自由移动，不写下任何东西。在这个问题中，要模拟梅龟的操作和生成计算机化的草图框。
用 20x20 数组floor，初始化为 0。从数组中读取命令。跟踪任何时候海龟的当前位置和画笔的向上或向下状态。假设诲龟总是从位置0，0开始，画笔向上。程序要处理的海龟命令如下：
-------------------------------------------------
命令 含义
-------------------------------------------------
1 笔向上
2 笔向7
9 右转
4 左转
5,10 前进10格(或几格)
6 打印20x20数组
9 数据结束(标记)
-------------------------------------------------
假设海龟接近平面中心。下列 程序 绘制和打印 12 x 12 正方形并让画笔向上：
2
5，12
3
5，12
3
5，12
3
5，12
1
6
9
面笔向下并移动诲龟时，将数组 floor 的相应元素设置为 1。指定命令6（打印）时，只要数组中有1，就显示星号或选择的其他符号，而。则显示空白。编写一个程序，实现这里介绍的龟图功能。编写几个龟图程序，画一些有趣的图形。增加其他命令以增加龟图语言的功能。
4.24 （骑士旅行）国际象棋中，最有趣的问题之一是骑士旅行问题，最初是由数学家欧拉提出的。问题如下：能否让骑士在空棋盘上移动，在64个方格中经过且只经过一次?下面 要详细介绍这个问题。
骑士的移动按L形路线(一个方向两格，另一垂直方向一格，相当于“马走日”)。这样，从空棋盘中央的方格中，骑士可以有8种不同的移动方向(编号为0到7)，如图4.25。
a)在纸上画一个 8 x 8 棋盘，试用手工移动骑士，在移动的第一个框中标上1、第二个框中标上2、第三个框中标上3等等。事先要估计走多远，总共有64步，能走多远？
b)然后要开发一个在棋盘上移动骑士的程序。棋盘用8 x 8的双下标数组board表示。每个格子初始化为0。我们用水平和垂直组件描述8种可能的移动方式。例如，图4.25中0类型的移动是水平右移两格和垂直上移一格。2类型的移动是水平左移一格和垂直上移两格。左移和上移表示为负数。8种移动可以用两个单下标数组horizontal和vertical
描述如下：
horizontal[ 0 ] = 2
horizontal[ 1 ] = l
horizontal[ 2 ] = -l
horizontal[ 3 ] = -2
horizontal[ 4 ] = -2
horizontal[ 5 ] = -1
horizontal[ 6 ] = l
horizontal[ 7 ] = 2
vertical[ 0 ] = -l
vertical[ 1 ] = -2
vertical[ 2 ] = -2
vertical[ 3 ] = -l
vertical[ 4 ] = l
vertical[ 5 ] = 2
vertical[ 6 ] = 2
vertical[ 7 ] = 1
让变量 currentRow 和 currentColumn 表示骑士当前位置的行和列，要进行 moveNumber 类型的移动（moveNumber 在0到7之间），程序用下列语句：
currentRow += vertical[ moveNumber ]；
currentColumn += horizontal[ moveNumber ]；
计数器应在1到64之间改变．用来记录每一格中骑士最近一次移动的顺序号。记住，要测试各种可能的移动，确定骑士是否已访问过该格。当然，要测试各种可能的移动，保证骑士不会跳到棋盘以外。现在编写在棋盘上移动骑士的程序。运行程序，看看骑士移动了多少位？
c)编写和运行骑士旅行程序之后，可以进行一些透试，我们要开发一个移动骑士的试探程序(或策略)。试探不一定成功，但认真设计的试探方法能提高成功的机会。可以发现，外层格子比在棋盘中心附近的格子更难移动。事实上，最难访问的是四角的格子。
凭直觉，应先将骑士移到最难到达的格子，在旅行即将结束时再访问最容易到达的格子，这样成功的机率较高。
我们可以开发一个访问性试探，将每格进行访问性分类，然后总是设法把骑士移到最难访问的点。我们在双下标数组accessibility中标上每个格能访问的格数。在空棋盘上,中间格的值为8，四角格的值为2，其他格的值为3、4、6，如下所示：
2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
现在用访问性试探值编写骑士旅行程序。任何时候，总是设法把骑士移到最难访问的点。对于格子连接的情况，骑士可能移到任一连接的格子。因此，旅行可以从四角开始(说明：骑土在棋盘上移动时，程序随着越来越多的格子被占而减少访问性值。这样，任何时候，棋盘上任一格子上访问性值是该格子能访问的格数)。运行这个程序，能否一一访问棋盘上的格子?现在修改程序，从棋盘上任何一格开始运行64次旅行，哪些能全部访问，
d)编写一个骑士旅行程序，在遇到两格或几格连接时，确定选哪一格时先考虑从连接的格子能访问的格子。程序应移到下次移动时访问性值最小的格子。
4.25 （骑士旅行：强制方法）练习 4.24 开发了骑士旅行问题的解决方法，这个方法用 访问性试探 能产生许多解法并可以有效地执行。
随着计算机的运算能力越来越强，可以用更简单的算法解决这个问题，即采用强制算法。
a)用随机数产生程序让骑士在棋盘上按L形走法任意移动。程序一步一步走完这个棋盘。
骑士能走多远？
b)通常，上述程序不会走太远。现在修改程序，进行1000次走法。用单下标数组跟踪每次走了几步。程序完成1000次旅行后，以表格形式打印这些信息。最佳结果是什么?
c)通常，上述程序能得到较好地走法，但无法走遍棋盘。现在删除次数限制，让程序一直运行，直到找出走遍棋盘的方法(注意，可能要好几个小时才能在强大的计算机上完成)。以表格形式打印这些信息．看看要多少次才能找出走遍棋盘的方法，花多少时间。
d)比较强制算法与前面介绍的访问性试探方法。哪个需要更认真地分析问题，哪个算法更难开发，哪个需要更强大的计算机功能，利用访问性试探能否事先保证找出走遍棋盘的方法，利用强制算法能否事先保证找出走遍棋盘的方法，比较两种方法的利与弊。
4.26 （八皇后）国际象棋中的另一个难题是八皇后问题。简单地说，空棋盘上能否放八个皇后，使一个皇后不会 攻击 另一个皇后，即不会有两个皇后在同一行、同一列或同一对角线上。用练习4.24的思路设计懈决八皇后问题的算法(提示：棋盘上的每一格可以指定一个值，表示一个皇后可以“删除”多少个格子，每个角指定数值 22，如图4.26)。在64个格子中放上这些“删除”数之后，问题就变成：将下一个皇后放在删除数最少的格子中。
* * * * * * * *
* *
* *
* *
* *
* *
* *
* *
图 4.26 左上角的删除数为 22
4.27 （八皇后：强制算法）这个练习要用几个强制算法解决练习4.26介绍的八皇后问题。
a)用练习4.25介绍的随机强制算法解决八皇后问题。
b)用穷举法，即测试八个皇后在棋盘上的各种组合。
c)说明穷举法为什么不适用于骑士旅行问题?
d)比较随机强制算法与穷举法。
4.28（骑士旅行：闭合线路）在骑士旅行问题中，骑士经过64格中的每一格一次，且只经过一次。闭合线路就是最后又回到出发的地方。修改练习4．24的骑士旅行程序，测试闭合线路是否走遍了棋盘。
4.29 （Eratosthenes 筛选法）质数是只能被1和本身整除的数。Eratesthenos筛选法是一种寻找质数的方法，这个方法如下所示：
a)生成一个数组，将所有元素初始化为1(真)。下标为质数的数组元素保持1，所有其他数组元素最终设置为o。
b)从数组下标1开始(下标1为质数)，每次找到数值为1的数组元素时，对数组余下部分循环，将下标为该下标倍数的元素设置为0。对于数组下标2，数组中下标为2的倍数的所有元素(除2本身，如4、6、8、10等等)都设置为0；对于数组下标3，数组中下标为3的倍数的所有元素（除3本身，如1、6、9、12、15等等）都设置为0，依次类推。
这个过程完成之后，如果数组元素还是1，则下标为质数。这些下标可以打印出来。编写一个程序，用1000个元素的数组确定和打印1到999之间的素数，忽略数组中的元素0。
4.30 （桶排序）桶排序从要排序的单下标正整数的数组开始，并有一个双下标整数数组，行下标为0到9，列下标为。到n-1，其中n为要排序数组中的数值个数。每一行双下标整数数组称为一个桶。编写一个 bucketSorL 函数，取整数数组和数组长度参数，并进行下列操作：
a)将单下标数组的每个值放到桶数组的行中(根据该值的个位)。例如97放在第7行，3放在第3行，100 放在第0行，称为“分布传递”。
b)一行一行地对桶数组进行循环，将值复制回原数组，称为“收集传递”。上述值在单下标数组中的新顺序为 100、3、97。
c)对十位、百位、千位等重复上述过程。
第二遍，100放在第0行，3放在第0行(因为3没有十位)，97放在第9行。经过收集传递之后，上述值在单下标数组中的新顺序为100、3、97。第三遍，将100放在第1行，3和97放在第行0行。经过收集传递之后，上述值在单下标数组中的新顺序为所要的排序结果。
注意，双下标桶数组的长度是要排序的整数数组长度的10倍。这种排序方法提供比冒泡排序更好的性能，但要求更多的内存。冒泡排序方法只要多一个数据元素的空间。这就是用空间交换时间的范例：桶排序方法比冒泡排序更快，但使用更多内存。这个存储桶排序方法要求每遍都将所有数据复制回原数组中。另一种方法是生成第二个双下标数组，在两个桶数组之间重复交换数据。