求个C++程序
1)问题描述抽签是我们日常生活中经常遇到的一件事,并且其形式有很多种。这里介绍一种抽签游戏,如图3所示,最上面一排是游戏的参加者——称为抽签者,最下面一排是签号(奖品、公差等)。每个人依次顺着竖线往下走,当碰到横线时,即转横向前进,碰到竖线再往下,以此类推,则游戏结束后,抽签者会一一对应到最下面一排的签号。
2. 基本要求
(1) 设计存储结构存储抽签者、签号、游戏用横线、竖线等;
(2) 设计算法实现抽签;
(3) 存储游戏的最终结果。
3. 设计思想
分析上面的抽签游戏的示例,遇到一条横线,代表这两个竖线的数据就要交换顺序,例如,原来的顺序为{A0, A1, A2, A3, A4},经过第0层横线后,顺序为{A1, A0, A3, A2, A4},再经过第1层横线后,顺序为{A1,A3,A0,A2,A4},以此类推,最后顺序为{A4, A1, A0, A2, A3},对应到{p0, p1, p2, p3, p4}。在该游戏中,需解决以下问题:
(1) 抽签游戏可以多人参与,只要加上竖线和横线即可。那么,如何表示这些参与者呢?
解决:假设有n个人参加,可以用一个一维数组A[n]来记录n个抽签者。
(2) 签号如何存储?
解决:签号的存储也可设计成一个一维数组p[n]来记录n个签号。
(3) 如何存储游戏的最终结果?
解决:设计一维数组B[n]存储最终的对应结果,同时在执行过程中记载中间结果。
(4) 当碰到某一横线跨在第i条和第i+1条竖线上时,如何交换数据?
解决:用一维数组B[n]来存放游戏过程中的中间结果和最终结果,通过交换B[i]和B[i+1]的值解决交换数据问题。
(5) 如何表示抽签游戏的竖线和横线布局?
解决:设计一个二维数组M[m][n],M[i][j]表示第i层上第j条和第j+1条竖线之间是否有横线,其值为0或1,1代表有横线,0代表没有横线。图3所述示例对应的数组M如图4所示。
算法设计要点如下:
(1) 按从上到下、由左到右的方式遍历数组M,若某元素值为1,则进行数据交换。
(2) 在数据交换的过程中,用一维数组B来存放游戏过程中的顺序和最终的顺序,即:
如果M[i][j]=1,则B[j]←→B[j+1];
(3) 最后B[n]即为所求;