【例3.3】三个数

GitHub跳转原题关系图返回列表

通过三次比较与交换,将三个整数从大到小排序输出。

OJ: roj

题目 ID: 5055

难度:入门

标签:排序分支结构

创建: 2026-10-09 01:03

更新: 2026-10-09 01:03

形式化题目

输入三个整数 a,b,ca, b, c,你需要按从大到小的顺序将它们输出,用单空格分隔。

数据范围: 题目未明确指定数据范围。经实测,三个整数的值域包含 [−2147483648,2147483647][-2147483648, 2147483647],即恰好落在 32 位有符号整数的取值范围内。

正解

思路

本题要求将三个数从大到小排序。作为分支结构的经典练习题,我们可以通过两两比较并交换变量的值来实现:

假设三个变量分别为 a,b,ca, b, c,目标是达到 a≥b≥ca \ge b \ge c。

  1. 首先比较 aa 和 bb,如果 a<ba < b,则交换它们。此时一定有 a≥ba \ge b。
  2. 接着比较 aa 和 cc,如果 a<ca < c,则交换它们。由于上一步已保证 a≥ba \ge b,且本次交换后 a≥ca \ge c,因此 aa 现在成为了三者中的最大值。
  3. 最后比较 bb 和 cc,如果 b<cb < c,则交换它们。此时保证了 b≥cb \ge c。

经过以上三次比较和交换,三个变量 a,b,ca, b, c 已经按照从大到小的顺序排列,依次输出即可。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-09 00:41
# update_at: 2026-10-09 00:41

import sys


def solve() -> None:
    """读入三个整数,三次比较交换排成降序,单空格分隔输出。"""
    # 题面只说「按从大到小的顺序输出」,未指定实现手段(关键词/括号/标题三步判据全空),
    # 故不调用内置 sorted,保留与 C++ 侧同阶的三次比较交换。
    # 数据含 32 位极值(如三个 -2147483648):这里只做比较与赋值,未取反/取绝对值,无溢出风险。
    data = iter(map(int, sys.stdin.buffer.read().split()))
    a, b, c = next(data), next(data), next(data)

    if a < b:
        a, b = b, a  # 先保证 a >= b
    if a < c:
        a, c = c, a  # 再保证 a >= c,此时 a 已是三者最大
    if b < c:
        b, c = c, b  # 最后保证 b >= c

    print(a, b, c)  # 单空格分隔、行末换行(实测 .out 无行尾空格)


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-09 00:41
 * update_at: 2026-10-09 00:41
 */
// 一本通 5055《【例3.3】三个数》
// 题面只要求「按从大到小的顺序输出」,未指定实现手段,故用三次比较交换。
// 数据里含 32 位极值(problem1 三个 -2147483648、problem2 三个 2147483647),
// 实现全程只做比较与赋值,不做取反/取绝对值/求和,因此用 int 也不会溢出;
// 这里默认用 ll 存题目数据,彻底规避边界风险。
#include <iostream>

using namespace std;

typedef long long ll;

ll a, b, c; // 输入的三个整数

// 三次比较交换,把 a、b、c 排成降序 a >= b >= c。
void solve() {
    if (a < b) { // 先保证 a >= b
        ll temp = a;
        a = b;
        b = temp;
    }
    if (a < c) { // 再保证 a >= c,此时 a 已是三者最大
        ll temp = a;
        a = c;
        c = temp;
    }
    if (b < c) { // 最后保证 b >= c
        ll temp = b;
        b = c;
        c = temp;
    }
    // 单空格分隔、行末换行(实测 .out 无行尾空格)
    cout << a << " " << b << " " << c << "\n";
}

int main() {
    if (!(cin >> a >> b >> c)) return 0; // 无输入时静默退出
    solve();
    return 0;
}

复杂度

  • 时间复杂度:O(1)\mathcal{O}(1)。只进行了固定 3 次比较和至多 3 次交换操作,时间复杂度为常数级别。
  • 空间复杂度:O(1)\mathcal{O}(1)。仅使用了常数个变量存储输入的值。

总结

  • 算法与复杂度:采用三次比较与交换的方法,将三个变量排成降序后输出,各数间单空格分隔。算法的时间、空间复杂度均为 O(1)\mathcal{O}(1)。
  • 数据范围与极值:本题的数据中包含了 32 位有符号整型的极值,例如测试点 p1 的输入是三个 INT_MIN (-2147483648),p2 的输入是三个 INT_MAX (2147483647)。这些极值恰好落在 32 位带符号整型(如 int)的取值范围内。
  • UBSan 实证与 abs(INT_MIN) 反证:
    • 由于算法全程只做比较与赋值,不涉及取反(如 -x)、取绝对值(如 abs(x))或求和/差,因此纯 int 版实测跑全部 10 点 10/10 逐字节一致,且 UBSan 无任何报错(实现无 UB)。
    • 若在实现中误用了 abs 或对负极值取反,则会触发未定义行为。例如针对 p1 里的 -2147483648,求其绝对值会报错:UBSan: runtime error: negation of -2147483648 cannot be represented in type 'int'。
    • 为防患于未然,代码中采用 long long (ll) 来存储变量,这是项目的一般规范与稳妥选择,而不是为了修 bug。
  • 算法选择:通过对题面内容的机械判定(关键词匹配、括号注释、题面前置说明),三步判据全部为空,这意味着题面并未硬性指定具体实现手段(如不能使用 std::sort 等)。保留「三次比较交换」的做法更多是为了贴合教学上的风格,而非硬约束。
  • 输出格式:各整数间采用单空格分隔,行尾无空格,末尾为单换行。
  • 验证强度摘要:通过真实 10 个数据点及穷举小规模极值/反事实验证(如修改为升序验证),本实现通过验证。
  • 跨语言语义一致性清单:
    • 类型转换:无风险
    • 溢出:本题数据虽达到 32 位整型极值,但在当前“仅比较赋值”且默认 ll 接收的逻辑下无溢出;若盲目使用 abs 等函数处理 INT_MIN 会导致 UB 溢出。
    • 整除/取模:无(不涉及)
    • 浮点格式化:无(纯整数题)
    • 排序稳定性 / 字典序:无风险(直接基于值判断,且不区分相等的键值对相对顺序)