1. 回文数生成算法概述
回文数是指正读反读都相同的数字,比如121、1331、12321等。在算法竞赛和实际编程中,高效生成回文数是一个常见需求。传统方法往往通过暴力枚举所有数字并检查是否为回文,这种方法时间复杂度高达O(10^n),对于大n值效率极低。
本文介绍一种基于数学构造的高效算法,时间复杂度仅为O(10^(n/2)),性能提升显著。该算法的核心思想是:只需生成回文数的前半部分,然后通过数学方法拼接后半部分,避免了对每个数字的回文检查。
提示:理解这个算法需要基本的数学知识和C++编程基础,但我会尽量用通俗易懂的方式解释每个步骤。
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 算法核心原理解析
2.1 回文数的结构特征
回文数的结构可以分为两种情况:
- 长度为奇数:如12321,可以看作"123"+"21",其中后半部分是前半部分"123"去掉最后一位"3"后的反转
- 长度为偶数:如1221,可以看作"12"+"21",后半部分是前半部分的完整反转
这种结构特征告诉我们:只需要确定前半部分,后半部分可以通过数学方法自动生成,无需单独存储或计算。
2.2 前半部分的取值范围
对于n位回文数,前半部分的长度取决于n的奇偶性:
- 奇数长度:前半部分长度=(n+1)/2
- 偶数长度:前半部分长度=n/2
前半部分的最小值是10^(len-1),最大值是10^len-1。例如:
- 5位回文数前半部分长度=3,范围100~999
- 4位回文数前半部分长度=2,范围10~99
3. 算法实现细节
3.1 奇数长度回文数生成
以5位回文数为例,具体步骤如下:
- 前半部分范围:100~999(因为len=(5+1)/2=3)
- 对于每个前半部分数字,如121:
- 取r=121/10=12(去掉最后一位)
- 将r的各位数字逆序拼接到原数字后:
- 取12的个位2,拼接得1212
- 取1的个位1,拼接得12121
- 最终得到回文数12121
关键点在于:通过不断取商和余数,实现数字的反转拼接。
3.2 偶数长度回文数生成
以4位回文数为例:
- 前半部分范围:10~99(因为len=4/2=2)
- 对于每个前半部分数字,如12:
- 直接对12进行
