P1028 数的计算

calendar May 12, 2026 · 3 分钟阅读 · 动态规划 递归  ·
分享到: linkedin copy

文章目录

题目信息

字段 内容
题号 P1028
难度 普及-
知识点 动态规划、递归

题目描述

我们要求找出具有下列性质的数的个数（包括输入的数本身）：

  1. 输入的数是 n
  2. 只需在原数的右边进行以下操作：
    • 将该数翻倍
    • 或者在该数后面加上一个数
    • 添加的数必须小于等于原数的一半（向下取整）

请你找出所有能由 n 生成出来的数的个数。

输入格式

  • 一个整数 n（1 ≤ n ≤ 1000）

输出格式

  • 输出满足条件的数的个数

样例

输入 #1：

7

输出 #1：

3

解释 #1：

  • 7
  • 14（7 翻倍）
  • 73（7 后面加上 3）

共 3 个数。

输入 #2：

3

输出 #2：

2

解释 #2：

  • 3
  • 6（3 翻倍）

解题思路

核心思想

动态规划（DP） 是解决本题的关键。

关键观察：

  • 设 dp[i] 表示以数字 i 开头的、满足条件的数的个数
  • 对于数字 i，可以在其后面添加的数范围是 1, 2, ..., i/2（向下取整）
  • 如果在后面加上数字 j（1 ≤ j ≤ i/2），那么新数的个数等于 dp[j]

递推公式：

dp[i] = 1 + dp[1] + dp[2] + ... + dp[i/2]
       = 1 + Σ dp[j] (j = 1 到 i/2)

其中 1 表示原数 i 本身。

边界条件：

  • dp[1] = 1（只有 1 本身）

算法流程

dp[0] = 0
dp[1] = 1

for i = 2 to n:
    dp[i] = 1
    for j = 1 to i/2:
        dp[i] += dp[j]

answer = dp[n]

完整代码

C++

#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<long long> dp(n + 1, 0);
    dp[1] = 1;

    for (int i = 2; i <= n; ++i) {
        dp[i] = 1;  // 自身
        for (int j = 1; j <= i / 2; ++j) {
            dp[i] += dp[j];
        }
    }

    std::cout << dp[n] << "\n";

    return 0;
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)

	var n int
	fmt.Fscan(in, &n)

	dp := make([]int64, n+1)
	dp[1] = 1

	for i := 2; i <= n; i++ {
		dp[i] = 1
		for j := 1; j <= i/2; j++ {
			dp[i] += dp[j]
		}
	}

	fmt.Println(dp[n])
}

Java

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());

        long[] dp = new long[n + 1];
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = 1;
            for (int j = 1; j <= i / 2; j++) {
                dp[i] += dp[j];
            }
        }

        System.out.println(dp[n]);
    }
}

Python

import sys


def main() -> None:
    n = int(sys.stdin.readline().strip())

    dp = [0] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = 1
        for j in range(1, i // 2 + 1):
            dp[i] += dp[j]

    print(dp[n])


if __name__ == "__main__":
    main()

JavaScript

'use strict';

function main() {
    const input = require('fs').readFileSync('/dev/stdin', 'utf8').trim();
    const n = parseInt(input, 10);

    const dp = new Array(n + 1).fill(0);
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        dp[i] = 1;
        for (let j = 1; j <= Math.floor(i / 2); j++) {
            dp[i] += dp[j];
        }
    }

    console.log(dp[n]);
}

main();

关键代码讲解

动态规划核心

for (int i = 2; i <= n; ++i) {
    dp[i] = 1;  // 自身是一个合法数
    for (int j = 1; j <= i / 2; ++j) {
        dp[i] += dp[j];  // 加上在后面添加 j 能生成的数的个数
    }
}

理解：

  • dp[i] = 1：i 本身满足条件
  • dp[i] += dp[j]：在 i 后面添加数字 j（j ≤ i/2），能生成的数的个数等于 dp[j]

复杂度分析

方法 时间复杂度 空间复杂度
DP 递推 O(n²) O(n)

说明：

  • 外层循环 n 次
  • 内层循环最多 n/2 次
  • 总时间复杂度 O(n²)，n ≤ 1000 完全可解

易错点

  1. 数据类型：结果可能很大，使用 long long（64位整数）
  2. 边界处理：i/2 是整数除法，向下取整
  3. 数组初始化：dp[1] = 1 是初始状态
  4. 递推顺序：必须从小到大计算，因为 dp[i] 依赖 dp[1..i/2]

类似题目