如何用Python递归实现smallestSquare函数：寻找拼接平方数的最小k

要实现递归版的smallestSquare函数，核心思路是按k的位数从小到大依次尝试：先找1位的k，再找2位、3位……直到找到能让n和k拼接后成为完全平方数的最小k。具体逻辑如下：

完整代码 #

from math import sqrt

def isSquare(n):
    return n == int(sqrt(n) + 0.5) ** 2

def smallestSquare(n):
    n_str = str(n)
    n_len = len(n_str)
    
    def recursive_find(m):
        # m代表当前尝试的k的位数，拼接后的数总长度为n的长度+m
        min_square = 10 ** (n_len + m - 1)
        max_square = 10 ** (n_len + m) - 1
        
        # 计算对应平方数的平方根范围
        x_start = int(sqrt(min_square))
        if x_start ** 2 < min_square:
            x_start += 1
        x_end = int(sqrt(max_square))
        
        # 遍历所有可能的平方根，检查平方数是否符合要求
        for x in range(x_start, x_end + 1):
            square = x * x
            square_str = str(square)
            if square_str.startswith(n_str):
                # 提取k的部分并返回
                return int(square_str[n_len:])
        # 当前位数没找到，递归尝试更长的位数
        return recursive_find(m + 1)
    
    # 从1位的k开始尝试
    return recursive_find(1)

代码说明 #

1. 字符串转换：把n转为字符串n_str，方便后续快速判断平方数是否以n的数字开头。
2. 递归核心函数：recursive_find(m)负责处理位数为m的k：
   • 先确定拼接后数的范围：比如n是2位数、m=3时，拼接后的数是5位数，范围是10000到99999。
   • 计算该范围内所有完全平方数对应的平方根区间，遍历每个平方根计算平方数。
   • 检查平方数的字符串是否以n_str开头，符合条件则提取后面的子串作为k返回（因为我们按位数从小到大尝试，第一个找到的就是最小的k）。
   • 如果当前位数没有找到，递归调用自身尝试下一位数。
3. 初始调用：从m=1开始，也就是先找最短的k。

测试验证 #

• 输入n=1，返回6（拼接后16是4²）
• 输入n=4，返回9（拼接后49是7²）
• 输入n=35，返回344（拼接后35344是188²）

内容的提问来源于stack exchange，提问作者Ana Marques