C&C++结构实训(国防科大)

第1关：有理数化简

200

• 任务要求
• 参考答案
• 评论220

• 任务描述
• 相关知识
  • 结构
  • 结构的初始化及使用
• 编程要求
• 测试说明

---

任务描述

本关任务：化简有理数。

相关知识

有理数的精确表示一般采用分数形式。分数的分子和分母都是整数，如果有理数为负数，则分子为负数，分母始终为正数。有理数的化简其实就是使分数成为最简分数，即通过化简使分子和分母互质。当分子为0时，分母应为1。

我们可以用两个整型变量来表示一个分数，但由于没有表示两个变量之间的逻辑关系，程序的可读性会很差。更好的方法是使用 C 和 C++ 的结构来表示。

结构

结构定义的一般形式为：

1. struct <结构名>{
2. <成员列表>
3. };

• struct 是关键字，表示结构定义；

• <结构名>是一个标识符，是结构的名字；

• <成员列表>由若干个成员的声明组成，每个成员都是该结构的一个组成部分。

例如，分数包含两个成员：分子和分母，可以定义为一个结构。分数结构名可以取名为 rationalNumber ，两个成员都是整型变量，可以分别取名为 fenzi 和 fenmu，则分数结构可以定义为：

1. struct rationalNumber{
2. int fenzi; // 分子
3. int fenmu; // 分母
4. };

结构的定义是定义一个新的数据类型（新类型名就是结构名），这样不会有内存分配。之后就可以像使用预定义类型（如 int ）那样来使用结构类型。

例如：

1. rationalNumber x,y;

该语句声明了两个 rationalNumber 类型的变量 x 和 y，每个变量中都包含了两个成员：整型的 fenzi 和 fenmu。变量的声明会有内存分配，可以使用 x 和 y 的两个整型变量成员来存储数据，这样就可以把同一个分数的分子和分母存入 rationalNumber 类型的相应变量中，该变量就可以表示一个分数了。

结构的定义是可以嵌套使用的。例如 person 结构中包含生日成员，而生日中又包含年、月、日三个成员，代码如下：

1. // 定义结构date
2. struct date
3. {
4. int year, month, day;
5. };
7. // 定义结构person
8. struct person
9. {
10. int IDNumber; // 身份证号
11. char name[20]; // 姓名
12. char sex; // 性别
13. date birthday; // 生日，嵌套定义
14. };

结构的初始化及使用

结构变量的初始化和数组变量的初始化一样，采用花括号括起来的初始值列表的形式。

例如：

1. rationalNumber x={12,46};

该语句中，其初始化值按序赋值给各个成员，即12和46分别赋值给了 x 的 fenzi 和 fenmu 成员。

结构变量的使用有两种方式：一种是把结构变量当做一个整体使用；另一种是拆开了用，单独操作其中的某个成员：

1. 当结构变量当做一个整体使用时，有两个运算符：赋值运算符 = 和地址运算符 & 可以直接作用于结构变量上；

例如：

1. rationalNumber x = {12,46}, y ;
2. y = x ; // 结构变量中的每个成员分别赋值
3. rationalNumber *p = &x; // 声明结构指针，并初始化为 x 的地址

1. 当结构变量拆开使用时，需要访问结构变量的成员，并可以像使用普通变量那样来使用结构变量的成员，如分数的两个成员就可以看成普通的 int 类型变量。

其中：拆开结构的方式有两种，一种是使用结构名 + 圆点运算符（.）；另一种是使用指向结构变量的指针 + 箭头运算符（->）。

例如：

1. rationalNumber x= {12,46}, y ;
2. y = x ; // 结构变量中的每个成员分别赋值
3. rationalNumber *p = &x; // 声明结构指针 p，并让 p 指向 x
4. x.fenzi = 18; // 使用圆点操作符访问并修改 x 的成员 fenzi
5. p->fenmu = 108; // 使用箭头操作符并修改 x 的成员 fenmu

编程要求

在右侧编辑器中的Begin-End之间补充代码，对输入的有理数（数据由平台提供，已在主函数中获取）进行化简。

测试说明

平台会对你编写的代码进行测试，比对你输出的数值与实际正确数值，只有所有数据全部计算正确才能通过测试：

测试输入：-18/52 预期输出：-9/26

测试输入：128/4 预期输出：32

---

开始你的任务吧，祝你成功！

#include <iostream>
using namespace std;

struct rationalNumber{
    int fenzi; // 分子
    int fenmu; // 分母
};

// 函数reduction：有理数化简，对传入的有理数n进行化简
// 参数：n-有理数
// 返回值：无化简后的有理数
rationalNumber reduction(rationalNumber n);

int main()
{
    char c;
    rationalNumber x, y;
    cin >> x.fenzi >> c >> x.fenmu;   // 输入有理数，首先读入分子，然后是/，最后是分母
    y = reduction(x);   // 有理数化简
    // 输出化简的结果
    if(y.fenmu == 1)
        cout << y.fenzi << endl;
    else
        cout << y.fenzi << "/" << y.fenmu << endl;
    return 0;
}

rationalNumber reduction(rationalNumber n)
{
    // 请在这里补充代码，实现函数reduction
    /********** Begin *********/
    int t;
    rationalNumber m=n;
    do{
        t=m.fenzi%m.fenmu;
        m.fenzi=m.fenmu;
        m.fenmu=t;
    }while(m.fenmu!=0);
    if(m.fenzi>0)
        m.fenzi=m.fenzi;
    else
        m.fenzi=-m.fenzi;
    n.fenzi/=m.fenzi;
    n.fenmu/=m.fenzi;
    return n;
    /********** End **********/
}

第2关：有理数加法

200

• 任务要求
• 参考答案
• 评论220

• 任务描述
• 相关知识
• 编程要求
• 测试说明

---

任务描述

本关任务：实现两个有理数的相加并返回结果且返回的结果必须是最简分数。

相关知识

函数不仅能通过参数传入结构变量，也可以通过返回值返回结构变量。

例如：下面的 add 函数将分数 x 的分子和分母分别加1后返回：

1. #include <iostream>
2. using namespace std;
4. struct rationalNumber{
5. int fenzi; // 分子
6. int fenmu; // 分母
7. };
9. rationalNumber add(rationalNumber x)
10. {
11. x.fenzi++; // 分子加 1
12. x.fenmu++; // 分母加 1
13. return x; // 返回结果
14. }
16. int main()
17. {
18. rationalNumber a ={23,56}, b ;
19. b=add(a); // 调用add 函数
20. cout << b.fenzi << "/" << b.fenmu << endl; // 输出返回值
21. return 0;
22. }

输出结果为：24/57。

温馨提示：结构变量作为一种新的数据类型，可以和预定义类型一样使用。

编程要求

在右侧编辑器中的Begin-End之间补充代码，实现两个有理数（数据由平台提供，已在主函数中获取）的相加并返回结果且返回的结果必须是最简分数。

测试说明

平台会对你编写的代码进行测试，比对你输出的数值与实际正确数值，只有所有数据全部计算正确才能通过测试：

测试输入：-1/2 5/6 预期输出：1/3

测试输入：-3/6 12/24 预期输出：0

---

开始你的任务吧，祝你成功！

#include <iostream>
using namespace std;

struct rationalNumber{
    int fenzi; // 分子
    int fenmu; // 分母
};

// 函数rnAdd：两个有理数相加
// 参数：x,y-两个有理数
// 返回值：x+y的最简分数形式
rationalNumber rnAdd(rationalNumber x, rationalNumber y);

int main()
{
    char c;
    rationalNumber x, y, z;
    // 输入两个有理数
    cin >> x.fenzi >> c >> x.fenmu;
    cin >> y.fenzi >> c >> y.fenmu;
    z = rnAdd(x,y);     // 有理数相加
    // 输出相加的结果
    if(z.fenmu == 1)
        cout << z.fenzi << endl;
    else
        cout << z.fenzi << "/" << z.fenmu << endl;
    return 0;
}

// 请在此添加代码，实现函数rnAdd
/********** Begin *********/
rationalNumber rnAdd(rationalNumber x, rationalNumber y)
{
	int t,k,common1,common2;
    rationalNumber n=x;
    rationalNumber m=y;
    while(m.fenmu!=0){
        t=n.fenmu%m.fenmu;
        n.fenmu=m.fenmu;
        m.fenmu=t;
    }
    k=x.fenmu*y.fenmu/n.fenmu;
    common1=k/x.fenmu;
    common2=k/y.fenmu;
    m.fenzi=x.fenzi*common1+y.fenzi*common2;
    m.fenmu=k;
    int a=m.fenzi,b=m.fenmu;
    t=0;
    while(b!=0){
        t=a%b;
        a=b;
        b=t;
    }
    m.fenzi/=a;
    m.fenmu/=a;
    return m;
}
/********** End **********/

第3关：有理数平均数

300

• 任务要求
• 参考答案
• 评论220

• 任务描述
• 相关知识
  • 结构数组
  • 访问结构数组成员
• 编程要求
• 评测说明

---

任务描述

本关任务：计算n（n<100）个有理数的平均数并返回，要求输出结果为最简分数形式。

相关知识

结构数组

结构的定义是定义一个新的数据类型，所以可以使用结构名（类型）来声明结构数组。结构数组的每一个数组元素都是一个结构变量。

使用结构数组时，首先像使用数组那样，用数组名加下标的方式访问数组元素，数组元素即结构变量，然后再访问结构变量的成员（使用圆点运算符或者箭头运算符），结构变量的成员则可以当普通变量使用。

下面的程序定义了结构 student，声明了 student 类型的数组 cs（ cs 包含5个元素，分别是 cs[0] 、cs[1] 、cs[2] 、cs[3] 、cs[4] ），并同时对数组 cs 进行了初始化：

1. struct student {
2. int num;
3. char name[20];
4. float score;
5. }cs[5]={{110, ″Zhang Ping″, 45},
6. {102, ″Li Xiaoming″, 92},
7. {153, ″Wang Ming″, 52.5},
8. {134, ″Cheng Ling″, 87},
9. {105, ″Wang Xiaofang″, 95},
10. };

由于 cs 是数组，所以初始化语法为花括号括起来的逗号分开的5个数据，由于 cs 数组的每个元素都是结构变量，所以对结构变量的初始化语法为花括号括起来的各个成员的值。

第一个花括号部分{110, ″Zhang Ping″, 45}初始化给 cs[0] ，其中110给了cs[0].num，“Zhang Ping”给了cs[0].name（其实cs[0].name也是一个数组，也是逐个数组元素初始化，‘Z’给了cs[0].name[0]，…… ），45则给了cs[0].score。

访问结构数组成员

要使用结构数组，也需要拆开了使用，数组使用循环遍历，用[]加下标访问其数组元素，结构变量则使用圆点运算符拆开即可。

如下面的程序输出了数组 cs 的所有信息：

1. for(int i = 0; i < 4; i++)
2. {
3. cout<<cs[i].num<<", "<<cs[i].name<<": "<<cs[i].score<<endl;
4. }

编程要求

在右侧编辑器中的Begin-End之间补充代码，计算n（n<100）个有理数（数据由平台提供，已在主函数中获取）的平均数并返回，结果为最简分数形式；

评测说明

平台会对你编写的代码进行测试，比对你输出的数值与实际正确数值，只有所有数据全部计算正确才能通过测试：

测试输入：

1. 3
2. 1/2 3/4 5/6

预期输出：25/36

测试输入：

1. 5
2. -1/2 2/3 -3/4 4/5 -5/6

预期输出：-37/300

---

开始你的任务吧，祝你成功！

#include <stdlib.h>
#include <stdio.h>

struct rationalNumber
{
    int fenzi; // 分子
    int fenmu; // 分母
};

// 函数rnMean：计算n个有理数的平均数
// 参数：a-存放有理数的数组,n-有理数的个数
// 返回值：n个有理数的平均数
struct rationalNumber rnMean(struct rationalNumber a[], int n);

int main()
{
    char c;
    struct rationalNumber a[100],z,k;
    int n, i;
    // 输入有理数个数
    scanf("%d", &n);
    // 输入n个有理数
    for(i = 0; i < n; i++)
        scanf("%d%c%d", &a[i].fenzi, &c, &a[i].fenmu); 
    z = rnMean(a,n);     // 计算有理数平均数
    // 输出平均数
    if(z.fenmu == 1)
        printf("%d\n", z.fenzi);
    else
        printf("%d/%d\n", z.fenzi, z.fenmu);
    return 0;
}
//求每个的最大的公约数并简化
struct rationalNumber rnMax(struct rationalNumber n){
    int t;
    rationalNumber m=n;
    m.fenzi=n.fenzi>0?n.fenzi:-n.fenzi;
    while(m.fenmu!=0){
        t=m.fenzi%m.fenmu;
        m.fenzi=m.fenmu;
        m.fenmu=t;
    }
    n.fenzi=n.fenzi/m.fenzi;
    n.fenmu=n.fenmu/m.fenzi;
    return n;
}
struct rationalNumber rnAdd(struct rationalNumber x, struct rationalNumber y){
    x.fenzi=x.fenzi*y.fenmu+x.fenmu*y.fenzi;//分子之和
    x.fenmu=x.fenmu*y.fenmu;//分母相同
    return rnMax(x);
}
/********** Begin *********/
struct rationalNumber rnMean(struct rationalNumber a[], int n)
{
    int i;
    for(i=0;i<n-1;i++)  
        a[i+1]=rnAdd(a[i],a[i+1]);
    a[i].fenmu*=n;
    return a[i];
}
/********** End **********/

第4关：书籍排序

500

• 任务要求
• 参考答案
• 评论220

• 任务描述
• 相关知识
• 编程要求
• 测试说明

---

任务描述

本关任务：编写一个完整的程序，对输入的n（n<100）本书进行排序并输出。

相关知识

完成本关需要具备的知识介绍请参见前面三个关卡。

编程要求

在右侧编辑器中的Begin-End之间补充代码，编写一个完整的程序，对输入的n（n<100）本书进行排序并输出，具体要求如下：

温馨提示：程序是可以拼凑的，本关可以使用结构数组来求解，数据的输入参照前面几关的代码，然后再加上一个排序程序，随便改改就成了。

• 程序输入

程序首先输入一个正整数n，然后输入n本书的信息，每本书用两行输入，第一行输入书的名称（书名最长不超过50个字符，中间可能有空格），第二行输入价格，价格为浮点数。

例如：

1. 3
2. Programming in C
3. 21.5
4. 数据结构与算法
5. 18.5
6. 三体（一）
7. 28.0

• 程序输出

程序要求对n本书按价格从低到高排序，如果价格相同，则按书名（字符串）字典序从小到大排序。最后输出排序结果，每行输出一本书的信息，首先输出价格，然后输出书名，中间用一个英文逗号和一个空格分开。

如上面输入对应的输出结果为：

1. 18.5, 数据结构与算法
2. 21.5, Programming in C
3. 28, 三体（一）

测试说明

平台会对你编写的代码进行测试，比对你输出的数值与实际正确数值，只有所有数据全部计算正确才能通过测试：

测试输入：

1. 3
2. Programming in C
3. 21.5
4. 数据结构与算法
5. 18.5
6. 三体（一）
7. 28.0

预期输出：

1. 18.5, 数据结构与算法
2. 21.5, Programming in C
3. 28, 三体（一）

测试输入：

1. 5
2. Programming in C
3. 21.5
4. 数据结构与算法
5. 18.5
6. 三体（一）
7. 28.0
8. 三国志
9. 56.9
10. 第一滴血
11. 22.3

预期输出：

1. 18.5, 数据结构与算法
2. 21.5, Programming in C
3. 22.3, 第一滴血
4. 28, 三体（一）
5. 56.9, 三国志

---

开始你的任务吧，祝你成功！

#include <string.h>
#include <iostream>

using namespace std;

//请在此添加代码，实现书籍数据的输入、排序和输出
/********** Begin *********/
typedef struct book{
	char name[30];
	float price;
}cs;//重新声明
int main()
{
    int n,i,j,k;
    cin>>n;
	cs mbook[100];
    cs t;
	for(i=0;i<n;i++){ 
        getchar();//吸收cin中的空格
		cin.getline(mbook[i].name,30);//输入流，cin.getline(字符指针(char*),字符个数N(int),结束符(char))，最后一位以‘\0’结束 
		cin>>mbook[i].price;
	}  
    for(i=0;i<n-1;i++){
    	k=i;
		for(j=i+1;j<n;j++){
			if(mbook[k].price>mbook[j].price)
			 k=j;
			else if(mbook[k].price==mbook[j].price&&strcmp(mbook[k].name, mbook[j].name)>0)
			 k=j; 
		} 
		if(k!=i){  
			t=mbook[k];
			mbook[k]=mbook[i];
			mbook[i]=t;	
		}
	} 
	for(i=0;i<n;i++){
		cout<<mbook[i].price<<", "<<mbook[i].name<<endl;
	}
    return 0;
}
/********** End **********/