代码解析：完善程序-1

代码原理分析：
这段程序用“类似 Dijkstra 的逐点扩展”思路，计算：用若干个数字 4，通过 +、差的绝对值、整除（仅在能整除时）这些运算，得到目标整数 n 所需的最少 4 的个数。

代码原理讲解

状态含义
F[v] 表示构造整数 v 所需的最少“4”的个数。初始知道 F[4]=1。
扩展规则（可用运算）
设已经最优确定的两个数为 i 与 x（它们分别需要 F[i] 与 F[x] 个“4”），
允许的合并运算是：
- i + x
- |i - x|
- 若能整除：i / x、x / i
这些合成的结果 y 的候选代价都是 F[i] + F[x]（把两个表达式拼起来），
用它去最小化 F[y]。
为什么像 Dijkstra
每一轮都在“未定型”的数里选 F 值最小的 x，并把它与所有已定型的 i 合并更新。
因为所有被拿来合并的 i 都已经是最优的，所以 t = F[i] + F[x] 一定是真实可行的消耗。
又因为 x 是当前所有未定型里 F 最小者，所以此时确定 x 的值不会被任何将来的组合再降低——与 Dijkstra 选取最短路顶点的逻辑完全一致。于是，当 n 被标记为已访问时，F[n] 就是最少 4 的个数。
为何要用 Vis[i] 作为 ④ 的条件
如果让“尚未最优”的 i 参与合并，t=F[i]+F[x] 可能基于一个“非最优”的 F[i]，会产生错误的松弛顺序，破坏正确性。只允许用“已定型”的 i 可以保证每一步的正确性。
边界与安全
- 循环中选择 x 的枚举从 1 开始，因此不会把 x 选成 0，避免了取模/整除的除零风险。
- M 是可达的上界；如果你需要更大的目标数，把 M 调大即可。
复杂度
- 选最小 F 的过程是一次线性扫（O(M)），外层最多做 M 轮；
  每轮与所有已定型的 i 合并也是一次 O(M) 的扫，
  因此总体最坏复杂度约 O(M^2)（这里 M=10000 时仍可接受）。
- 若想提速，可用优先队列维护“未定型的最小 F”，把选择 x 的过程降到 O(log M)。

小例子

下面把算法前 3 轮（依次选 x=4, x=1, x=8x=4,\;x=1,\;x=8）的全过程按你现在这版代码（含 if (i != x) 才做差值更新）完整展开。记号说明：

F[v] = 用若干个“4”得到整数 v 的最少 4 的个数；
Vis[v]=1 表示 v 已“定型”（就像 Dijkstra 已确定最短路）；
合并时只允许 左操作数 i 已定型（if (Vis[i])），而被更新的目标可以尚未定型；
允许的运算：i + x、|i - x|（只有 i != x 才做）、若能整除则 i / x 与 x / i。

初始：

F[*]=+INF，Vis[*]=0；
置 F[4]=1（这是起点）。

第 1 轮：选 x = 4

进入轮次前：Vis[4]=0，已知 F[4]=1 是所有未定型里最小，选之。
设 Vis[4]=1，然后用 已定型的 i 与 x=4 合并。此时已定型只有 i=4 自身。

i=4, x=4：t = F[4]+F[4] = 1+1 = 2
- 加法：4+4=8 → F[8] ≤ 2
- 差值：i!=x 为假 → 不更新 F[0]（这点很关键）
- 除法：4%4==0 → F[4/4]=F[1] ≤ 2；x%i==0 同样给 F[1] ≤ 2

轮末结果（定型：{4}）：

新得到：F[1]=2, F[8]=2
F[0] 未更新（仍为 +INF，因为差值在 i==x 时被跳过）

第 2 轮：选 x = 1

此时未定型里 F 最小的是 1(2) 与 8(2)，按索引先选 x=1。
设 Vis[1]=1。此时已定型集合为 {1,4}，因此内层会用 i=4 和 i=1 各与 x=1 合并：

i=4, x=1：t = F[4]+F[1] = 1+2 = 3
- 加法：4+1=5 → F[5] ≤ 3
- 差值：|4-1|=3 → F[3] ≤ 3
- 除法：4%1==0 → F[4/1]=F[4] ≤ 3（不改，因 F[4]=1 更优）
  1%4!=0 → 无
i=1, x=1：t = F[1]+F[1] = 2+2 = 4
- 加法：1+1=2 → F[2] ≤ 4（首次给 2 一个上界）
- 差值：i!=x 为假 → 不更新 F[0]
- 除法：1%1==0、1%1==0 → 都是 F[1] ≤ 4（不改）

轮末结果（定型：{4,1}）：

已有：F[1]=2, F[8]=2
新增/改进：F[5]=3, F[3]=3, F[2]=4
仍未定型：2,3,5,8,…（只有 4,1 已定型）

第 3 轮：选 x = 8

未定型里最小的是 8(2)，选 x=8。设 Vis[8]=1。
此时已定型集合为 {1,4,8}，依次与 x=8 合并：

i=4, x=8：t = F[4]+F[8] = 1+2 = 3
- 加法：4+8=12 → F[12] ≤ 3
- 差值：|4-8|=4 → F[4] ≤ 3（不改，仍为 1）
- 除法：4%8!=0 → 无；8%4==0 → F[8/4]=F[2] ≤ 3（把 F[2] 从 4 降到 3）
i=1, x=8：t = 2+2 = 4
- 加法：1+8=9 → F[9] ≤ 4
- 差值：|1-8|=7 → F[7] ≤ 4
- 除法：1%8!=0 → 无；8%1==0 → F[8/1]=F[8] ≤ 4（不改）
i=8, x=8：t = 2+2 = 4
- 加法：8+8=16 → F[16] ≤ 4
- 差值：i!=x 为假 → 不更新 F[0]
- 除法：8%8==0、8%8==0 → 都给 F[1] ≤ 4（不改）

轮末结果（定型：{4,1,8}）：

关键改进：**F[2] 从 4 降到 3（由 8 ÷ 4 得来）
现有较小值：F[2]=3, F[3]=3, F[5]=3, F[12]=3,
以及 F[7]=4, F[9]=4, F[16]=4 等
下一轮通常会在 F=3 的未定型里按索引先选 x=2（然后继续扩展）

小备注：关于 `F[0]`

你最开始提到“x=4 时定型了 F[0]”。在这版代码里我们写了

if (i != x) update(F[abs(i - x)], t);

所以第 1 轮 i=x=4 不会更新 F[0]。如果你把这条限制去掉，第一轮就会得到 F[0]=2（由 4-4），不过这不会被选作 x，因为挑选 x 的枚举从 1 开始，不包含 0。
是否允许 i==x 的差值，要看题目是否希望把“同一个表达式两次使用”作为一种合法合成方式。

代码注释：

#include <iostream>
#include <cstdlib>
#include <climits>
using namespace std;

const int M = 10000;     // 计算的上界，可按需要调大
bool Vis[M + 1];         // Vis[x] = 1 表示 x 的最优值已确定（已“出队/定型”）
int  F[M + 1];           // F[x] = 得到 x 所需的最少 4 的个数（代价）

// 将 x 更新为更小的 y（最小化）
inline void update(int &x, int y) {
    if (y < x) x = y;
}

int main() {
    int n;
    cin >> n;

    // 1) 初始化所有状态为“不可达”（无穷大）
    for (int i = 0; i <= M; i++) F[i] = INT_MAX;

    // 2) 基础状态：用 1 个“4”就能得到 4
    //   —— 这是整套构造的“起点”
    F[4] = 1;                            // ← ①

    // r 不是必须的变量，只是原题里保留的计数器，这里不影响逻辑
    int r = 0;

    // 3) 主循环：只要目标 n 还没“定型”，就持续扩展
    while (!Vis[n]) {                    // ← ②
        r++;

        // 3.1 在所有“未定型”的数里，选 F 值（用 4 的个数）最小的那个，记为 x
        int x = 0; // 这里 x 不会取到 0，因为下面枚举 i 从 1 开始
        for (int i = 1; i <= M; i++) {
            if (!Vis[i] && F[i] < F[x])  // ← ③ 选未访问且 F 最小的 i
                x = i;
        }

        Vis[x] = 1;                      // 把 x 标记为“已定型”

        // 3.2 用“已定型”的所有数 i 与新定型的 x 进行一次“合并运算”，
        //     产生新的候选数，并用最少 4 的个数去松弛它们
        for (int i = 1; i <= M; i++) {
            if (Vis[i]) {                // ← ④ 只用已经定型的 i（它们的 F[i] 已最优）
                int t = F[i] + F[x];     // 合并 i 与 x 共消耗的“4”的个数

                // 加法：i + x
                if (i + x <= M)
                    update(F[i + x], t);

                // 绝对值差：|i - x|
                if (i != x)              // i==x 时 |i-x|=0，会反复更新 F[0]，含义不大
                    update(F[abs(i - x)], t);

                // 整除：i / x 与 x / i（仅当能整除时，结果才是整数才更新）
                if (x != 0 && i % x == 0)
                    update(F[i / x], t);
                if (i != 0 && x % i == 0)
                    update(F[x / i], t);
            }
        }
    }

    cout << F[n] << endl;
    return 0;
}

Previous Topic

Back to Lesson

Next Topic