C++ 中的科技数

2025年5月19日 | 阅读 14 分钟

引言

Tech Number 是一个经过数学探索的概念，通常在编程中用来解决特定问题或挑战。这个术语本身并不是数学或计算机科学中的标准概念，但在竞争性编程和编码练习中，它被广泛用于指代具有不同数值属性的某些数字。Tech Number 是围绕着这样一个想法的概念：选择那些当考虑其数字并对其执行操作时，符合某些条件的数字。

Tech Number 被定义为一个满足以下标准的数字：

偶数位数： 数字的位数必须是偶数。这是必需的，因为我们需要将数字分成相等的两半并验证这些属性。
分成相等的两半： 将数字分成两等份。一个简单的例子是像 2025 这样的四位数，它被分成 20 和 25。如果数字有六位，它将被分解成三位数的两部分，依此类推。
两半之和： 因此，一旦数字被分成两半，就将它们相加。为了进行下一步的验证，这是这些两半的总和。
平方和等于原数： 我们计算两半之和的平方。Tech Number 是一个数字，当它的两半之和的平方等于原数时，它就是一个 Tech Number。

举个例子，假设 2025 是一个数字。它有四位，是偶数，可以分成两半：20 和 25。当我们把这两半加起来时，我们得到 20 + 25 = 45。当我们平方这个和，45² = 2025，原数被确认为一个 Tech Number。

应用和相关性

理解数学模式： 搜索和处理特定的数值属性有助于程序员更好地理解数学及其实际应用。
数字操作： Tech Numbers 有助于在处理数字的各个数字、字符串切片、算术运算和类型转换方面建立专业知识，这些我们在编程挑战中经常遇到。
调试和测试： 作为处理 Tech Numbers 的一部分，我们可以处理边缘情况，测试实现逻辑的健壮性，例如处理不符合某些标准或位数奇数的输入。

实现中的挑战

性能优化： 逻辑很简单，但在我们参加的竞争性编程环境中，处理大数或大量输入是困难的。然而，根据输入规模良好地扩展算法是一个重要的考虑因素。
边缘情况： 我们需要支持特殊情况，如个位数、负数或非常大的数字等。对于这种情况，实现可能会变得复杂，并且我们的逻辑可能需要一些额外的检查。

方法-1：基本算术方法

用于确定 Tech Number 的基本算术方法，通过使用 / 和 % 运算符对数字进行数学运算，将数字分成两半，而无需将其转换为字符串。相反，我们首先计算出数字所需的位数以及该数字需要有多少位，然后我们可以通过 10 的幂来分割数字。

它计算两半的总和，并将其与原数的平方进行比较。如果数字匹配，则该数字成为 Tech Number。对于小型输入，这是一种高效的方法，避免了字符串操作，并且适合以算术为中心的编程。但是，成功处理大数字或边缘情况可能会变得复杂。

示例

让我们通过一个使用 C++ 中的基本算术方法来说明 Tech Number 的例子。

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
// Function to count the digits in a number
int countDigits(int num) {
    int count = 0;
    while (num > 0) {
        count++;
        num /= 10;
    }
    return count;
}
// Function to calculate the power of 10 (used for splitting the number)
int powerOf10(int exp) {
    int result = 1;
    for (int i = 0; i < exp; i++) {
        result *= 10;
    }
    return result;
}
// Function to validate user input
bool isValidInput(int num) {
    if (num < 0) {
        cout << "Negative numbers cannot be Tech Numbers.\n";
        return false;
    }
    if (countDigits(num) % 2 != 0) {
        cout << "Number must have an even number of digits.\n";
        return false;
    }
    return true;
}
// Function to check if a number is a Tech Number
bool isTechNumber(int num) {
    if (!isValidInput(num)) return false;
    int digits = countDigits(num);
    // Split the number into two halves
    int halfDigits = digits / 2;
    int divisor = powerOf10(halfDigits);
    int firstHalf = num / divisor;  // Extract the first half
    int secondHalf = num % divisor; // Extract the second half
    // Calculate the sum of the two halves
    int sum = firstHalf + secondHalf;
    // Check if the square of the sum equals the original number
    return (sum * sum == num);
}
// Function to get a list of Tech Numbers in a given range
vector<int> findTechNumbersInRange(int start, int end) {
    vector<int> techNumbers;
    for (int i = start; i <= end; i++) {
        if (isTechNumber(i)) {
            techNumbers.push_back(i);
        }
    }
    return techNumbers;
}
// Function to test predefined examples
void testPredefinedExamples() {
    cout << "\nTesting predefined examples:\n";
    vector<int> examples = {2025, 3025, 9801, 1234, 1001, 123321, 4096};
    for (int num : examples) {
        cout << num << " -> ";
        if (isTechNumber(num)) {
            cout << "Tech Number\n";
        } else {
            cout << "Not a Tech Number\n";
        }
    }
}
// Function to test user-defined range
void testUserDefinedRange() {
    int start, end;
    cout << "\nEnter a range to find Tech Numbers (start and end): ";
    cin >> start >> end;
    if (start > end) {
        cout << "Invalid range. Start must be less than or equal to end.\n";
        return;
    }
    vector<int> techNumbers = findTechNumbersInRange(start, end);
    cout << "\nTech Numbers in the range " << start << " to " << end << ":\n";
    if (techNumbers.empty()) {
        cout << "No Tech Numbers found in the given range.\n";
    } else {
        for (int num : techNumbers) {
            cout << num << " ";
        }
        cout << endl;
    }
}
// Function to check a single number input by the user
void checkSingleNumber() {
    int num;
    cout << "\nEnter a number to check if it's a Tech Number: ";
    cin >> num;
    if (isTechNumber(num)) {
        cout << num << " is a Tech Number.\n";
    } else {
        cout << num << " is NOT a Tech Number.\n";
    }
}
// Main function
int main() {
    cout << "Welcome to the Tech Number Checker Program!\n";
    // Test predefined examples
    testPredefinedExamples();
    // Check a single number
    checkSingleNumber();
    // Test for a range of numbers
    testUserDefinedRange();
    cout << "\nThank you for using the Tech Number Checker Program. Goodbye!\n";
    return 0;
}   

输出

Welcome to the Tech Number Checker Program!
Testing predefined examples:
2025 -> Tech Number
3025 -> Tech Number
9801 -> Tech Number
1234 -> Not a Tech Number
1001 -> Not a Tech Number
123321 -> Not a Tech Number
4096 -> Not a Tech Number
Enter a number to check if it's a Tech Number: 3025
3025 is a Tech Number.
Enter a range to find Tech Numbers (start and end): 2000 5000
Tech Numbers in the range 2000 to 5000:
2025 3025 
Thank you for using the Tech Number Checker Program. Goodbye!

说明

countDigits

此函数循环遍历数字以计算其中的位数。
示例： 对于 2025，数字的计数是 4。
我们知道数字有偶数个位数，但我们不知何故需要找出。

powerOf10

它通过 10 的幂来分割数字。
示例： 一般来说，powerOf10(n) 返回 10 的 n 次幂，对于 4 位数字，它可以将 2025 分成 2n（第一半）和 (2n+1)（第二半）。

isValidInput

确保输入对于 Tech Number 是有效的： 它必须是非负数。数字的位数必须是偶数。只允许使用适当的输入，如正数，除了奇数位的数字，否则将引发适当的错误消息。

isTechNumber

识别 Tech Number 的核心逻辑。

验证输入。

除法（通过斜杠 /）和取模（通过百分号 %）将数字分成两半。它将两半相加，并查看它们的平方是否等于原始数字。
示例： 对于 2025，20 + 25 = 45，我们有 (45)² = 2025，所以它是一个 Tech Number。

findTechNumbersInRange

用户定义的范围被迭代，并从中找到所有的 Tech Numbers。
示例： 它在 2000-10000 的范围内识别 2025、3025 和 9801。

testPredefinedExamples

它通过使用硬编码的示例来显示程序的正确性。

testUserDefinedRange

用户可以输入一个范围来获取 Tech Numbers，并优雅地处理无效的范围。

复杂度分析

时间复杂度

countDigits(int num)

这个函数会一直循环直到数字变为 0。首先，数字被除以每个除法减少的数，迭代次数与数字中的位数 d 成正比。
显然，countDigits 的时间复杂度为 O(log10(n))，因为对于输入数字 n，d = O(log10(n))。

powerOf10(int exp)

在这个函数中，我们使用一个循环将 10 自身乘以 exp 次。根据 exp 的值，exp 决定我们迭代的次数，通常是 d/2，其中 d 是数字的位数。因此，powerOf10 的时间复杂度为 O(d)（或 O(log10(n))）。

isTechNumber(int num)

countDigits 函数在此函数中找到数字的位数，时间复杂度为 O(log10(n))。之后，它计算用于分割数字的 10 的幂（powerOf10），时间复杂度为数组 d。所有其他操作（平方、除法、加法）都是 O(1) 操作。
因此，isTechNumber 的函数总体时间复杂度为 O(log10(n)) + O(d)，简化为 O(d) = O(log10(n))。

findTechNumbersInRange(int end, int start)

此函数接受从 start 到 end 的范围，并遍历该范围，为范围内的每个数字调用 isTechNumber。
isTechNumber 函数对于范围内的每个数字的时间复杂度为 O(log10(n))。
因此，时间复杂度为 O( k log_10 (n) )，其中 n 是范围内值的平均值。

testPredefinedExamples()

此函数将遍历给定固定数字的列表，并使用 isTechNumber 检查它是否为 Tech Number。
时间复杂度为 O(m log10 n)，其中 m 是测试用例的数量，n 是列表中测试用例的平均数量。M 和 n 是固定列表大小。

空间复杂度

countDigits(int num)

此函数占用恒定的空间，并且只保存数字和计数器变量。空间复杂度为 O(1)。

powerOf10(int exp)

该函数使用一个循环来计算 10 的幂并保存结果，但会存储任何结果。其空间复杂度也为 O(1)。

isTechNumber(int num)

该函数只需要固定数量的变量（至少用于存储数字的两半、它们的和以及它们的平方……因此，它可以写成 O(1) 空间。

findTechNumbersInRange(int start, int end)

此函数检查 Tech Numbers，并将已识别的 Tech Numbers 存储到 vector 中。这里，空间复杂度是范围内 Tech Numbers 的数量。在最坏的情况下，空间复杂度为 O(k)，其中 k 是范围的大小。

其他函数

testPredefinedExamples() 和 checkSingleNumber() 函数只是几个空间复杂度为 O(1) 的函数，它们只存储少量变量。

方法-2：递归方法

检查数字是否为 Tech Number 的递归方法，它利用了递归和分治法的本质。其思想是反复将数字分成两半，并查看两半之和是否等于原数的平方。该方法通过反复调用一个函数来分割数字，直到达到个位数的基本情况。

在每次递归调用中，数字都会被分成两半，并计算出这两半之和。这个过程会一直重复，直到数字变成一个可以与原数直接比较的数。递归方法极大地简化了代码，并提供了一种解决问题的好方法。它使用了递归（这对于演示目的很有用），但对于大数字可能效率不高。

示例

让我们通过一个使用 C++ 中的递归方法来说明 Tech Number 的例子。

#include <iostream>
#include <cmath>
using namespace std;
// Function to count the number of digits in a number
int countDigits(int num) {
    int count = 0;
    while (num > 0) {
        count++;
        num /= 10;
    }
    return count;
}
// Recursive function to check if a number is a Tech Number
bool isTechNumberHelper(int num, int totalDigits, int digitCount) {
    // Base case: if we reach a single digit, return false since we need two halves
    if (digitCount == 1) {
        return false;
    }
    // Get the power of 10 for the second half (half the total number of digits)
    int powerOf10 = pow(10, totalDigits / 2);
    // Split the number into two halves
    int firstHalf = num / powerOf10;
    int secondHalf = num % powerOf10;
    // Calculate the sum of the halves
    int sum = firstHalf + secondHalf;

    // Check if the square of the sum equals the original number
    if (sum * sum == num) {
        return true;
    }
    // Recursive case: if not a Tech Number, recursively try with fewer digits
    return isTechNumberHelper(num / 10, totalDigits, digitCount - 1);
}
// Wrapper function to handle the recursion and start checking Tech Number
bool isTechNumber(int num) {
    // Base case: handle negative or single-digit numbers
    if (num < 10) {
        return false;
    }
    // Count the digits
    int digitCount = countDigits(num);
    // Check if the number has an even number of digits
    if (digitCount % 2 != 0) {
        return false;
    }
    // Call the recursive helper function
    return isTechNumberHelper(num, digitCount, digitCount);
}
// Function to find Tech Numbers in a range
void findTechNumbersInRange(int start, int end) {
    cout << "Tech Numbers between " << start << " and " << end << " are: " << endl;
    for (int i = start; i <= end; i++) {
        if (isTechNumber(i)) {
            cout << i << " ";
        }
    }
    cout << endl;
}
// Test predefined examples for Tech Numbers
void testPredefinedExamples() {
    int numbers[] = {2025, 3025, 1234, 9, 9999, 12321};
    cout << "Testing predefined numbers:" << endl;
    for (int i = 0; i < 6; i++) {
        if (isTechNumber(numbers[i])) {
            cout << numbers[i] << " is a Tech Number." << endl;
        } else {
            cout << numbers[i] << " is not a Tech Number." << endl;
        }
    }
}
// Function to test a single number entered by the user
void checkSingleNumber() {
    int num;
    cout << "Enter a number to check if it's a Tech Number: ";
    cin >> num;
    if (isTechNumber(num)) {
        cout << num << " is a Tech Number." << endl;
    } else {
        cout << num << " is not a Tech Number." << endl;
    }
}
int main() {
    int choice;
    do {
        cout << "\nTech Number Check Program\n";
        cout << "1. Check if a single number is a Tech Number\n";
        cout << "2. Find Tech Numbers in a range\n";
        cout << "3. Test predefined examples\n";
        cout << "4. Exit\n";
        cout << "Enter your choice: ";
        cin >> choice;
        switch (choice) {
            case 1:
                checkSingleNumber();
                break;
            case 2:
                int start, end;
                cout << "Enter the range (start end): ";
                cin >> start >> end;
                findTechNumbersInRange(start, end);
                break;
            case 3:
                testPredefinedExamples();
                break;
            case 4:
                cout << "Exiting program.\n";
                break;
            default:
                cout << "Invalid choice, please try again.\n";
        }
    } while (choice != 4);

    return 0;
}   

输出

Tech Number Check Program
1. Check if a single number is a Tech Number
2. Find Tech Numbers in a range
3. Test predefined examples
4. Exit
Enter your choice: 1
Enter a number to check if it's a Tech Number: 2025
2025 is a Tech Number.
Tech Number Check Program
1. Check if a single number is a Tech Number
2. Find Tech Numbers in a range
3. Test predefined examples
4. Exit
Enter your choice: 2
Enter the range (start end): 2000
5000
Tech Numbers between 2000 and 5000 are: 
2025 3025 
Tech Number Check Program
1. Check if a single number is a Tech Number
2. Find Tech Numbers in a range
3. Test predefined examples
4. Exit
Enter your choice: 4
Exiting program.

说明

代码以一个用于计算数字中位数的函数开始，以便将数字分成两半，然后继续进行。isTechNumberHelper 函数实现了递归方法来检查数字是否为 Tech Number。此函数将数字分成两半；两半都是使用数学运算（如除法和取模）计算的。

之后，它计算这两半之和，如果它们的平方等于给定的数字，那么它就是一个幸运数字。如果满足条件，函数将返回 true，并且该数字是 Tech Number。如果条件不满足，函数将返回 false，因为它会递归地调用自身，将数字分成更少的位数并逐个计数，直到达到个位数的基本情况，此时它返回 false。

主函数 isTechNumber 是一个包装器，它检查一个数字是否有偶数位的长度，如果有，则调用递归辅助函数。如果数字的位数是奇数，则立即认为它不是 Tech Number。

之后，用户可以使用用户友好的界面来检查单个数字是否为 Tech Number，查找给定范围内的所有 Tech Numbers，并测试预定义的示例。它是一个接受单个数字和范围输入类型并据此进行检查的工具。一组预定义的示例会测试各种数字，显示任何给定的数字是否为 Tech Number。这是一个循环程序，因此用户可以继续进行检查，直到他们决定退出。

该方法采用递归方法处理问题，一步一步地分解问题，同时在每个级别上减小问题的大小。然而，多次递归调用的开销可能会使其在大数字上的效率降低。

复杂度分析

时间复杂度

在这种情况下，递归方法的时间复杂度是已知的，主要取决于输入数字的位数。设数字有 d 位。
countChars 函数的运行时间为 O(d)，其中 d 是数字的位数。如前所述，它接受一个数字序列并对其进行一次迭代，以找到每个数字中的总位数。
递归地，isTechNumberHelper 函数将数字分成两半。由于数字被递归地除以二，因此它不再用十进制表示。这意味着它的递归深度与位数成正比，为 O(d)。
在每个递归级别，函数都会执行恒定时间的操作：我们可以在 O(1) 时间内计算两半之和并检查和的平方是否等于原始数字。
由于递归深度直接与位数成正比，并且每个递归步骤需要恒定的工作时间，因此总体时间复杂度为 O(d)。

空间复杂度

空间复杂度受两个主要因素影响：

它的深度为 d，因为我们正在处理的数字有 d 位。这给出了 O(d) 的递归空间复杂度。
但是，其他辅助空间将是恒定的，因为不涉及数据结构，如数组或列表。

下一个主题C++ 中的 std::reference_wrapper

← 上一个下一个 →

C++ 中的科技数

引言

应用和相关性

实现中的挑战

方法-1：基本算术方法

示例

说明

复杂度分析

方法-2：递归方法

示例

说明

复杂度分析

联系信息

关注我们

教程

面试题

在线编译器

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++ 中的科技数

引言

应用和相关性

实现中的挑战

方法-1：基本算术方法

示例

说明

复杂度分析

方法-2：递归方法

示例

说明

复杂度分析

相关帖子

C++ 中的施泰纳树近似

C++ std::remove_volatile

C++ 中的凯内亚数

C++ 中的米迪定理

C++ 中的 std::span::subspan 函数

C++ 中如何将 CSV 文件中的数据读入二维数组？

C++ Tutte 定理

C++ 优先级调度程序

C++ 中的 Giuga 数