对称量化的缩放系数与误差（AI034）- 算法机考高频题型 · 模型量化 / 数值实现题解 | AlgoMooc

AI034. 对称量化的缩放系数与误差

中等

通过率 100% · 提交 2 · 通过 2

模型量化数值实现

这道 OJ 的配套动画

对称量化 · 对应本题的思路、过程和代码

算法机考高频题型改编 · 聚焦「模型量化 / 数值实现」 · 难度：中等

对一组浮点权重做 b 位对称量化，即把每个实数映射为 [-2^(b-1), 2^(b-1)-1] 范围内的整数。规则（必须严格按以下顺序和舍入方式实现）： 1) 记 Q = 2^(b-1) - 1，M = max|x_i|。若 M = 0，输出三行：0.000000、n 个 0、0.000000。 2) 理论缩放系数（scale）s = M / Q；将 s 四舍五入（逢半远离零，即恰好为中点时向远离 0 的方向舍入）保留 6 位小数得到 s'，后续一律使用 s'。 3) 量化 q_i = clip(round(x_i / s'), -2^(b-1), 2^(b-1)-1)，其中 round 表示取整（逢半远离零），clip 表示范围截断（把越界值截断到边界）。 4) 反量化 d_i = q_i × s'；误差 E = max|x_i - d_i|，四舍五入（逢半远离零）保留 6 位小数。注意：本题所有『四舍五入』都指逢半远离零（0.5 → 1，-0.5 → -1），与部分语言默认的银行家舍入不同；由于 s' 已舍入到 6 位小数，最大元素量化后可能超过 Q，此时范围截断必须生效。

这类题属于算法机考高频题型中「模型量化 / 数值实现」方向的高频题型，通常考察对「模型量化 / 数值实现」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

输入描述

第一行两个整数 n b。第二行 n 个实数 x_i，最多 4 位小数。

输出描述

第一行输出 s'（保留 6 位小数）。第二行输出 n 个量化整数，空格分隔。第三行输出最大绝对误差 E（保留 6 位小数）。

数据范围

1 <= n <= 100000；2 <= b <= 8；|x_i| <= 1000，小数位数不超过 4。

示例

示例 1

输入示例

5 4
1.0000 -0.5000 0.2500 -1.0000 0.7500

输出示例

0.142857
7 -4 2 -7 5
0.071428

说明：

常规小数组

示例 2

输入示例

2 2
1.0000 0.5000

输出示例

1.000000
1 1
0.500000

说明：

0.5 边界，逢半远离零

时间限制 3000 ms · 内存限制 256 MB

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

训练营动画视频讲解

对称量化与反量化误差

加载中

正在加载动画…

问小欧 · 图解算法年卡¥99 开通 →

题库上一题下一题

未登录也能直接「运行」调试;「提交」判题需微信登录,你写的代码会自动保留、登录后回到本题继续。

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

1
2

# 在此编写你的代码

写完代码点「提交」，将对全部测试用例判题。

解题思路

先求 M=max|x| 和整数上界 Q，按逢半远离零将 M/Q 保留六位得到 s'。随后对每个元素计算 x/s'、按同一规则取整、截断到量化区间，再反量化并统计最大误差。参考实现把小数转成定点整数，避免二进制浮点影响中点判断。

正确性说明

定点计算中的整数除法按余数比较实现逢半远离零，与题目舍入定义等价。每个 q 经过上下界截断，必在合法整数区间；反量化统一使用已舍入的 s'，因此误差与题目规定的量化流程一致。

复杂度分析

两次线性扫描，时间 O(n)，保存输入和量化结果需要 O(n) 空间。

边界与易错点

全零数组单独输出零 scale、全零 q 和零误差；负端允许到 -2^(b-1)，并且 scale 向下舍入时不能省略截断。

参考代码

import sys


def rha(n: int, d: int) -> int:
    # round half away from zero, d > 0,全整数精确
    if n >= 0:
        return (2 * n + d) // (2 * d)
    return -((-2 * n + d) // (2 * d))


def parse4(tok: str) -> int:
    neg = tok.startswith("-")
    if neg:
        tok = tok[1:]
    if "." in tok:
        i, f = tok.split(".")
    else:
        i, f = tok, ""
    return (-1 if neg else 1) * (int(i) * 10000 + int((f + "0000")[:4] or "0"))


def fmt(v: int, dec: int) -> str:
    d = 10 ** dec
    sign = "-" if v < 0 else ""
    a = abs(v)
    return f"{sign}{a // d}.{a % d:0{dec}d}"


def main() -> None:
    data = sys.stdin.read().split()
    n, b = int(data[0]), int(data[1])
    xs = [parse4(t) for t in data[2:2 + n]]
    Q = (1 << (b - 1)) - 1
    LO = -(1 << (b - 1))
    M = max((abs(x) for x in xs), default=0)
    out = []
    if M == 0:
        out.append("0.000000")
        out.append(" ".join(["0"] * n))
        out.append("0.000000")
    else:
        s6 = rha(M * 100, Q)
        qs = []
        e6 = 0
        for x in xs:
            q = rha(x * 100, s6)
            if q > Q:
                q = Q
            elif q < LO:
                q = LO
            qs.append(q)
            err = abs(x * 100 - q * s6)
            if err > e6:
                e6 = err
        out.append(fmt(s6, 6))
        out.append(" ".join(map(str, qs)))
        out.append(fmt(e6, 6))
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    main()