剑指信奥 | C 语言之信奥试题详解（四）

前言

今天是我们 C 语言详解信奥试题的第四天，也是整个 C 语言系列的最后一天。

从 2022 年起，信息学竞赛的参赛语言将从现在的 C++、C 和 Pascal 三门变为一门，就是 C++。

C++ 是一门非常强大的语言，它是 C 语言的超集，C 语言中的基础语法与 C++ 大致相同。

我们先学 C 语言是为了学习 C++ 奠定基础，然后再学习 C++ 中增加的那一部分理论内容。

No. 1 质因数分解 🌟

题目

题目描述

已知正整数 n 是两个不同的质数的乘积，试求出两者中较大的那个质数。

输入格式

一个正整数 n。

输出格式

一个正整数 p，即较大的那个质数。

样例输入

样例输出

数据范围

n ≤ 2×10^9

题解

题目分析

这道题的解答非常的简短，但前提我们要做充足的分析。

首先要知道什么是质数：

质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数

Wikipedia

根据这个定义，诸如 3，5，7，11 ... 等都是素数。

看似不难，但在数学上有非常著名的关于质数的猜想，其中之一就是哥德巴赫猜想：

哥德巴赫猜想：该猜想认为每个大于 2 的偶数 n 都可表示成两个质数之和

还有黎曼猜想，至今都尚未解决。

好啦，知道了质数的定义，我们重点关注题目描述中的这句话：

正整数 n 是两个不同的质数的乘积

既然这个正整数是两个质数的乘积，意味着这个数只能分解为这两个质数的乘积（思考：为什么？）

想到这，问题就迎刃而解了。

注意事项

数学上定义，1 不是素数，循环起始于 2

解题过程

从 2 到 n - 1 做循环
第一个能整除 n 的数就是较小的质数
使用除法求得较大的质数并输出

参考代码

#include <stdio.h>

int main() {

    int n;

    scanf("%d", &n);

    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            printf("%d", n / i);
            break;
        }
    }

    return 0;
}

No. 2 陶陶摘苹果 🌟

题目

题目描述

陶陶家的院子里有一棵苹果树，每到秋天树上就会结出 10 个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个 30 厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。

现在已知 10 个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。

输入格式

输入包括两行数据。第一行包含 10 个 100 到 200 之间（包括 100 和 200 ）的整数（以厘米为单位）分别表示 10 个苹果到地面的高度，两个相邻的整数之间用一个空格隔开。

第二行只包括一个 100 到 120 之间（包含 100 和 120 ）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。

输出格式

输出包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。

样例输入

100 200 150 140 129 134 167 198 200 111
110

样例输出

题解

题目分析

这是一道比较简单的题，考察的就是陶陶的身高加上板凳的高度，这个数值不小于第一行里的多少个数

注意事项

数组元素接收数值的方法

解题过程

把第一行 10 个数字存入一个数组
遍历数组，计算数量并输出

参考代码

#include <stdio.h>

int main() {

    int apples[10];
    int high, sum = 0;

    for (int i = 0; i < 10; i++) {
        scanf("%d", &apples[i]);
    }

    scanf("%d", &high);

    for (int i = 0; i < 10; i++) {
        if (high + 30 >= apples[i]) {
            sum++;
        }
    }

    printf("%d", sum);

}

No. 3 不高兴的津津 🌟

题目

题目描述

津津上初中了。妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。

但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。

请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。

输入格式

输入包括 7 行数据，分别表示周一到周日的日程安排。每行包括两个小于 10 的非负整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。

输出格式

一个数字。如果不会不高兴则输出 0，如果会则输出最不高兴的是周几（用 1, 2, 3, 4, 5, 6, 7 分别表示周一，周二，周三，周四，周五，周六，周日）。

如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。

样例输入

样例输出

题解

题目分析

同样是一道比较简单的题目。

需要思考的是怎样做才能实现比较简洁的代码。

注意事项

不要忘了输出 0 的情况

解题过程

对每次输入的 m 和 n 进行判断
存储最大值和星期数
输出

参考代码

#include <stdio.h>

int main() {
    int m, n, day, max = 0;

    for (int i = 0; i < 7; i++) {
        scanf("%d %d", &m, &n);
        if (m + n > max && m + n > 8) {
            max = m + n;
            day = i + 1;
        }
    }

    printf("%d", day);

    return 0;
}

No. 4 文具订购🌟🌟

题目

题目描述

小明的班上共有 n 元班费，同学们准备使用班费集体购买 3 种物品:

圆规，每个 7 元。2.笔，每支4元。
笔记本，每本 3 元。

小明负责订购文具，设圆规，笔，笔记本的订购数量分别为 a,b,c，他订购的原则依次如下:

n 元钱必须正好用光，即 7a+4b+3c=n。
在满足以上条件情况下，成套的数量尽可能大，即 a,b,c 中的最小值尽可能大。
在满足以上条件情况下，物品的总数尽可能大，即 a+b+c 尽可能大。

请你帮助小明求出满足条件的最优方案。可以证明若存在方案，则最优方案唯一。

输入格式

从文件 order.in 中读入数据。仅一行一个整数 n 表示班费数量。

输出格式

输出到文件 order.out 中。若方案不存在则输出 -1。否则输出一行三个用空格分隔的非负整数 a,b,c 表示答案。

样例 1 输入

样例 1 输出

-1

样例 2 输入

样例 2 输出

-1

样例 3 输入

样例 3 输出

-1

样例 3 解释

a=2,b=4,c=1 也是满足条件 1，2 的方案，但对于条件 3，该方案只买了 7 个物品，不如 a=1,b=2,c=6 的方案。

数据范围

对于测试点 1 ∼ 6:n ≤ 14。

对于测试点 7 ∼ 12:n 是 14 的倍数。

对于测试点 13 ∼ 18:n ≤ 100。

对于所有测试点 0 ≤ n ≤ 105。

时间限制

1.0 s

空间限制

256 MB

题解

这道题是今天 NOI Online 考试普及组的第一题，经过这段时间的学习和练习，同学们把这道题作为一个检验这段时间学习成果的一份试卷吧！

信奥竞赛

系列