C++ 中的双基回文数

2025 年 5 月 23 日 | 阅读 4 分钟

在本文中，我们将讨论 C++ 中的双基回文数及其示例、时间复杂度和空间复杂度。

双基回文数

正向和反向读取都相同的字符或数字序列称为回文数。例如，在十进制中，数字 121 是一个回文数，因为它从左到右或从右到左读取都相同。一个数字必须同时满足十进制和另一个基数 k 的回文数条件，才能被视为双基回文数。

示例-110 2

小于 10 且在十进制和二进制中都是回文数的数字：1, 3, 5, 7, 9。

求和1 + 3 + 5 + 7 + 9 = 25.

示例- 2 100 2

小于 100 且在十进制和二进制中都是回文数的数字：1, 3, 5, 7, 9, 33, 99。

求和 1 + 3 + 5 + 7 + 9 + 33 + 99 = 157.

方法-1

确定给定数字是否为十进制回文数： 对于每个小于 n 的数字，第一步是确定它是否为十进制回文数。如果一个数字（例如 121 或 333）正向和反向读取都相同，则它是回文数。一种确定方法是反转其数字并将其与原始数字进行比较。
将数字转换为基数 k： 下一步是，如果一个数字是十进制回文数，则将其转换为基数 k。这涉及重复将数字除以 k 并存储余数，余数将表示新基数中的数字。
验证给定数字是否为基数 k 回文数： 将数字转换为基数 k 后，查看新基数的数字是否构成回文数。可以比较两端的数字（即第一个和最后一个数字）以确保它们相同。
如果两个条件都满足，则将数字添加到总和中： 如果该整数在十进制和基数 k 中都是回文数，则将其包含在当前总和中。通过此步骤，最终的总和将确保只包含满足这两个要求的数字。

示例

让我们举一个例子来说明 C++ 中的双基回文数。

#include <iostream>
#include <vector>
#include <cmath>
// Function to check if a number is palindrome in base 10
bool isPalindrome(int num) 
{
    int original = num;
    int reversed = 0;
    while (num > 0)
    {
        int digit = num % 10;
        reversed = reversed * 10 + digit;
        num /= 10;
    }
    return original == reversed;
}
// Function to convert a number to base k and check if it's palindrome
bool isPalindromeInBaseK(int num, int k)
{
    std::vector<int> digits;
    // Convert the number to base k
    while (num > 0) 
    {
        digits.push_back(num % k);
        num /= k;
    }
    // Check if the digits array is a palindrome
    int left = 0, right = digits.size() - 1;
    while (left < right) 
    {
        if (digits[left] != digits[right])
        {
            return false;
        }
        left++;
        right--;
    }
    return true;
}
// Function to find the sum of all numbers less than n that are palindrome in both base 10 and base k
int findSum(int n, int k)
{
    int sum = 0;
    for (int i = 1; i < n; i++) 
    {
        if (isPalindrome(i) && isPalindromeInBaseK(i, k))
        {
            sum += i;
        }
    }
    return sum;
}
int main()
{
    int n, k;
    // Taking input for n and k
    std::cout << "Enter the value of n: ";
    std::cin >> n;
    std::cout << "Enter the base k: ";
    std::cin >> k;
    // Find the sum of numbers less than n that are palindrome in both base 10 and base k
    int result = findSum(n, k);
    // Output the result
    std::cout << "The sum of numbers that are palindrome in both base 10 and base " << k << " is: " << result << std::endl;
    return 0;
}   

输出

Enter the value of n: 100
Enter the base k: 2
The sum of numbers that are palindrome in both base 10 and base 2 is: 157

复杂度分析

时间复杂度： O(n*log(n))
辅助空间： O(log(n))

说明

此 C++ 程序计算同时在十进制和指定基数 k 中是回文数且小于给定整数 n 的数字之和。isPalindrome() 函数通过反转数字的位来确定它是否是十进制回文数。isPalindromeInBaseK() 函数保留数字的位，将其转换为基数 k，并确定它们是否构成回文数。findSum() 方法遍历 1 到 n-1 之间的每个整数，并对满足两个回文数要求的数字求和。在接收 n 和 k 作为输入后，main() 函数调用 findSum() 并输出结果。通过此方法，总和将只包含满足两个回文数要求的数字。

下一主题C++ 中的龙形曲线序列

C++ 中的双基回文数

双基回文数

方法-1

示例

复杂度分析

说明

联系信息

关注我们

教程

面试题

在线编译器

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

示例

复杂度分析

说明

相关帖子

C++ std::logic_error

C++ std::packaged_task 类

C++ 状态设计模式

C++ 中的普罗思数

C++ 中的卡迈克尔数

C++ 中的最小基因突变

C++ 中用 Sundaram 筛法打印小于 n 的所有素数

C++ 中的不区分大小写搜索

C++ 中计算时针和分针之间的角度

C++ 中的最后一场 NBA 比赛配对

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题