1. 问题背景与需求分析
P1017 [NOIP 2000 提高组] 进制转换这道题目源自全国青少年信息学奥林匹克联赛(NOIP)的历史题库，是算法竞赛中的经典题型。题目要求实现将一个十进制数转换为指定负基数的表示形式，这在常规计算机教学中极为罕见——大多数教材仅覆盖正基数转换。
负基数系统最早由意大利数学家斐波那契在13世纪提出，现代应用包括纠错编码、密码学等领域。例如在平衡三进制系统中，-2进制能更高效地表示某些数学结构。这道题考察的核心能力包括：
- 对进制转换本质的理解（位权展开式的逆向推导）
- 处理数学运算中的边界条件（特别是余数为负的情况）
- 算法设计的严谨性（递归与迭代的实现差异）
2. 负基数转换的数学原理
2.1 常规进制转换回顾
正基数R的进制转换遵循公式：
[ N = d_n \times R^n + d_{n-1} \times R^{n-1} + ... + d_0 \times R^0 ]
其中( 0 \leq d_i < R )。转换方法是通过反复除以R取余数：
python复制def convert_positive(n, R):
digits = []
while n > 0:
digits.append(n % R)
n = n // R
return digits[::-1]
2.2 负基数转换的特殊性
当基数R为负数时（如R=-2），位权系统变为：
[ N = d_n \times (-2)^n + ... + d_0 \times (-2)^0 ]
此时余数可能出现负数，需要特殊处理。关键修正步骤：
-
当余数为负时，调整商和余数：
[ n = q \times R + r ]
令 ( r' = r - R ), ( q' = q + 1 ) -
保证余数始终满足 ( 0 \leq r' < |R| )
以-13转换为-2进制为例：
code复制-13 ÷ (-2) = 6 余 -1 → 调整余数为1，商变为7
7 ÷ (-2) = -3 余 1 → 无需调整
-3 ÷ (-2) = 2 余 1 → 无需调整
2 ÷ (-2) = -1 余 0 → 无需调整