C++ 中计算 n 位单调数

2025年5月20日 | 阅读 9 分钟

引言

单调数字在数论和组合数学中很重要。这些数字的数字按非递减或非递增顺序排列。因此，这些数字展现出某种对称性。在本文中，我们将构建一个 C++ 程序来计算 n 位单调数字。它包括关于如何实现这一目标的详细描述，从提供分步逻辑到解释方法和实际实现解决方案。

问题陈述

给定 n，计算有多少 n 位数字是单调的。例如

123 被认为是递增的单调数字
另一方面，432 是一个单调数字，但它是递减的。

我们需要找到给定整数 n 的单调类别中的数字的总数。

约束

n≥1
不得存在前导零。

方法

我们将考虑组合数学和动态规划。以下是我们方法的简要概述：

非递减数字
- 可以将 n 个数字分配到 10 个数字（0 到 9）中，从而得到一个非递减数字。
- “N 个相同的物品放入 r 个不同的组有多少种方法”类型的组合问题由公式 C(n+r−1,r−1) 给出，在这种情况下也适用。
非递增数字
- 上述推导出的方程仍然可以用来计算非递增数字。
避免重复计数
- 像 111 这样的数字既被归类为非递减，也被归类为非递增。为了解决这个问题，我们从总值中减去 999，因为由 n 次任何数字（介于 a 和 9 之间）组成的 n 位数字会被重复计数一次。
C++ 中的实现
- 首先，从阶乘计算组合。
- 非递减和非递增数字已经解决，使用循环或函数来对获得的计数进行求和。

示例 1

让我们看一个计算 n 位单调数字的 C++ 代码。

#include <iostream>
#include <vector>
using namespace std;

// Function to calculate factorial
long long factorial(int n) {
    if (n == 0 || n == 1) return 1;
    long long result = 1;
    for (int i = 2; i <= n; ++i) {
        result *= i;
    }
    return result;
}

// Function to calculate combinations: C(n, r) = n! / (r! * (n-r)!)
long long combinations(int n, int r) {
    if (r > n) return 0;
    return factorial(n) / (factorial(r) * factorial(n - r));
}

// Function to count n-digit monotone numbers
long long countMonotoneNumbers(int n) {
    if (n == 0) return 0;

    // Non-decreasing numbers
    long long nonDecreasing = combinations(n + 9, 9);

    // Non-increasing numbers
    long long nonIncreasing = combinations(n + 9, 9);

    // Subtract overcounted numbers (all digits same, 1 through 9)
    long long overlap = 9;

    // Total monotone numbers
    return nonDecreasing + nonIncreasing - overlap;
}

int main() {
    int n;
    cout << "Enter the number of digits (n): ";
    cin >> n;

    cout << "The number of " << n << "-digit monotone numbers is: " 
         << countMonotoneNumbers(n) << endl;

    return 0;
}   

输出

Enter the number of digits (n): 3
The number of 3-digit monotone numbers is: 474

代码说明

阶乘计算：阶乘函数将用于计算对应于组合公式的 n! 的值。
组合计算：C(n,r) 使用高效的组合函数计算，该函数获取 C(n, r) 的值，但可能涉及使用许多阶乘。
主函数
- CountMonotoneNumbers：一个估计递增和递减数字数量的函数。
- 计算 C(n, r)，但重复的部分，例如数字 111，已被考虑并减去，从而避免重复计数。
输入/输出
- 程序接收 n 作为输入，用于计算具有 n 个数字的单调数字的数量。

复杂度分析

时间复杂度：O(n) 用于阶乘计算。
空间复杂度：程序的整体空间复杂度为 O(1)。

示例 2

让我们再举一个例子来说明如何在 C++ 中计算 n 位单调数字。

#include <iostream>
#include <vector>
using namespace std;

// Function to count monotone numbers of n digits using dynamic programming
long long countMonotoneNumbers(int n) {
    if (n == 0) return 0;

    // DP table for counting non-decreasing numbers
    vector<vector<long long>> dpIncreasing(n + 1, vector<long long>(10, 0));

    // DP table for counting non-increasing numbers
    vector<vector<long long>> dpDecreasing(n + 1, vector<long long>(10, 0));

    // Base case: For 1-digit numbers
    for (int digit = 1; digit <= 9; ++digit) {
        dpIncreasing[1][digit] = 1;
        dpDecreasing[1][digit] = 1;
    }

    // Fill DP tables for numbers with more than 1 digit
    for (int length = 2; length <= n; ++length) {
        for (int digit = 1; digit <= 9; ++digit) {
            // Non-decreasing: Sum of all digits <= current digit
            dpIncreasing[length][digit] = dpIncreasing[length][digit - 1] + dpIncreasing[length - 1][digit];
            // Non-increasing: Sum of all digits >= current digit
            dpDecreasing[length][digit] = dpDecreasing[length][digit - 1] + dpDecreasing[length - 1][digit];
        }
    }

    // Calculate total non-decreasing and non-increasing numbers
    long long nonDecreasing = 0, nonIncreasing = 0;
    for (int digit = 1; digit <= 9; ++digit) {
        nonDecreasing += dpIncreasing[n][digit];
        nonIncreasing += dpDecreasing[n][digit];
    }

    // Subtract overlap (numbers where all digits are the same)
    long long overlap = 9; // 1 digit repeated n times, for each digit 1-9

    return nonDecreasing + nonIncreasing - overlap;
}

int main() {
    int n;
    cout << "Enter the number of digits (n): ";
    cin >> n;

    long long result = countMonotoneNumbers(n);
    cout << "The number of " << n << "-digit monotone numbers is: " << result << endl;

    return 0;
}   

输出

Enter the number of digits (n): 10
The number of 10-digit monotone numbers is: 87507

说明

动态规划表
- dpIncreasing[length][digit]：存储以数字 digit 结尾的 length 位非递减数字的数量。
- dpDecreasing[length][digit]：存储以数字 digit 开头的 length 位非递增数字的数量。
初始化
- 对于 length=1，1 到 9 的每个数字都为两个表贡献一个数字。
转移公式
- 非递减

dpIncreasing[length][digit]=dpIncreasing[length][digit−1]+dpIncreasing[length−1][digit]   

它对以小于或等于 digit 的数字结尾的数字进行求和。

非递增

dpDecreasing[length][digit]=dpDecreasing[length][digit−1]+dpDecreasing[length−1][digit]   

它对以大于或等于 digit 的数字开头的数字进行求和。

4. 重复处理

从结果中减去 999，以计算所有数字都相同的 n 位数字（例如 nnn 位数字）。

复杂度分析

时间复杂度：O(n.9)
填充 DP 表涉及迭代 n 个长度和每个长度的 9 位数字。
空间复杂度：O(n.9)
使用两个 DP 表来存储中间结果。

示例 3

让我们再举一个例子来说明如何在 C++ 中计算 n 位单调数字。

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// Define a type for the memoization key
using Key = pair<int, int>; // <remaining_digits, previous_digit>

// Hash function for pair (to use it in unordered_map)
struct KeyHash {
    size_t operator()(const Key &key) const {
        return hash<int>()(key.first) ^ hash<int>()(key.second);
    }
};

// Recursive function to count monotone numbers
long long countMonotoneHelper(int remaining_digits, int previous_digit, unordered_map<Key, long long, KeyHash> &memo, bool isIncreasing) {
    // Base case: No more digits to add
    if (remaining_digits == 0) return 1;

    // Check if the result is already computed
    Key key = {remaining_digits, previous_digit};
    if (memo.find(key) != memo.end()) return memo[key];

    long long count = 0;

    if (isIncreasing) {
        // Count non-decreasing numbers
        for (int digit = previous_digit; digit <= 9; ++digit) {
            count += countMonotoneHelper(remaining_digits - 1, digit, memo, true);
        }
    } else {
        // Count non-increasing numbers
        for (int digit = previous_digit; digit >= 1; --digit) {
            count += countMonotoneHelper(remaining_digits - 1, digit, memo, false);
        }
    }

    // Store the result in the memo table
    memo[key] = count;
    return count;
}

// Wrapper function to calculate total monotone numbers
long long countMonotoneNumbers(int n) {
    if (n == 0) return 0;

    unordered_map<Key, long long, KeyHash> memoIncreasing; // Memoization for increasing numbers
    unordered_map<Key, long long, KeyHash> memoDecreasing; // Memoization for decreasing numbers

    long long nonDecreasing = 0, nonIncreasing = 0;

    // Calculate non-decreasing numbers
    for (int digit = 1; digit <= 9; ++digit) {
        nonDecreasing += countMonotoneHelper(n - 1, digit, memoIncreasing, true);
    }

    // Calculate non-increasing numbers
    for (int digit = 9; digit >= 1; --digit) {
        nonIncreasing += countMonotoneHelper(n - 1, digit, memoDecreasing, false);
    }

    // Subtract overlap (numbers where all digits are the same)
    long long overlap = 9; // 1 digit repeated n times for each digit 1-9

    return nonDecreasing + nonIncreasing - overlap;
}

int main() {
    int n;
    cout << "Enter the number of digits (n): ";
    cin >> n;

    long long result = countMonotoneNumbers(n);
    cout << "The number of " << n << "-digit monotone numbers is: " << result << endl;

    return 0;
}   

输出

Enter the number of digits (n): 10
The number of 10-digit monotone numbers is: 87507

代码解释

递归函数逻辑
- 函数countMonotoneHelper递归地计算给定剩余数字数量和前一个数字的单调数字数量。
- 它使用两种情况：
  - 非递减：当前数字必须 ≥ 前一个数字。
  - 非递增：当前数字必须 ≤ 前一个数字。
记忆化
- 为了避免重复计算，中间状态（由剩余数字和前一个数字定义）的结果使用 Key 类型存储在 unordered_map 中。
- 它确保我们只计算每个唯一状态一次。
重复处理
- 与其他方法一样，所有数字都相同的数字（例如 111 或 222）在递增和递减类别中都被计算，因此我们减去重复的部分。

复杂度分析

时间复杂度：O(n×9^2)
- 对于每个数字，递归函数最多考虑 9 个下一个数字的选择。通过记忆化，避免了冗余的计算。
空间复杂度：O(n×9)
- 空间用于记忆化表和递归栈。

解决单调计数问题的优势

C++ 中单调计数问题的几个优势如下：

提高算法的智能性：单调计数问题整合了组合数学、动态规划和递归的思想。它们有助于更深入地理解解决问题的方法和算法。
发明更高效的新解决方案：学习如何使用不同的技术（如 DP 或带记忆化的递归）创建算法，可以优化缓慢且效率低下的算法，从而提高时间和空间效率。
为竞争性编程打下基础：竞争性编程竞赛中会遇到困难的问题集。编写解决方案可以使参赛者为这类问题做好准备。
注意可扩展性：当我们遇到阶乘溢出或高空间复杂度等限制时，我们会学到算法必须是可扩展的，这是软件工程中的一个重要经验。

单调数字的应用

C++ 中单调数字的几个应用如下：

数据库系统中的数据验证：单调序列通常用于表示有序数据，例如股票价格或随时间记录的温度。查找或计数单调性将确保数据是正确的。
计算机中的秘密书写：构造或分析单调数字可能在加密算法中用于构建有序密钥或其他识别顺序的序列。
AI/ML 中的模式识别：在机器学习模型构建中，提出具有这些特征的数字很重要，这些模型用于识别时间序列数据中连续递增或递减趋势的存在，例如使用股票市场数据进行分析或天气预报。
排序算法：此外，单调序列可以优化排序算法或减少所需的排序操作次数。
优化问题：单调性是优化问题中的一个典型约束，例如分配资源或排序要执行的任务。
组合数学在实际应用中：例如，这个问题类似于将 n 个相同元素放入 r 个箱子（数字）中，这在库存控制和物流问题中很有用。

未来扩展

处理前导零：扩展概念以在需要时处理允许前导零，例如在二进制或其他特定计数系统中。
可变基数系统：更改逻辑以适应其他基数，例如十六进制的基 16 或八进制的基 8。
可视化表示：通过绘制 DP 表或递归树来为问题的解决方案添加可视化表示，以促进对解决方案的理解。
性能基准测试：为了展示方法的优点和缺点，值得报告所有三种方法的运行时间和内存使用情况，并与一系列 n 值进行比较，以查看是否存在任何差异。

结论

总之，计算组成 n 位单调数字的 n 个变量的数量是一个有趣的问题，因为它展示了组合力量和算法概念的应用。在 C++ 任务中，我们实际上是在将问题简化为非递减和非递增序列的类别。

下一主题Counting-people-who-can-watch-the-movie-in-cpp

C++ 中计算 n 位单调数

引言

问题陈述

约束

方法

示例 1

代码说明

复杂度分析

示例 2

说明

复杂度分析

示例 3

代码解释

复杂度分析

解决单调计数问题的优势

单调数字的应用

未来扩展

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中计算 n 位单调数

引言

问题陈述

约束

方法

示例 1

代码说明

复杂度分析

示例 2

说明

复杂度分析

示例 3

代码解释

复杂度分析

解决单调计数问题的优势

单调数字的应用

未来扩展

结论

相关帖子

C++ 中的重-轻分解

C++ 托普利兹矩阵

C++ 中关于斐波那契数列的有趣事实