摘要：所幸，满足平方根前十位数字正好让的数字全部出现的数是存在的。上一篇斐波那契数列下一篇满足字母算式的解法本系列总目录参见程序员的算法趣题详细分析和全解
目录
求在计算平方根的时候，最早让0~9的数字全部出现的最小整数。注意这里只求平方根为正数的情况，并且请分别求包含整数部分的情况和只看小数部分的情况。
例）2的平方根 ：1.414213562373095048...（0~9全部出现需要19位）
这道题目比较含糊。
其实是找平方根（含整数部分或不含整数部分的）前十位数字正好让 0~9 的数字全部出现（且不重复）的最小整数—即构成0~9的一个排列（permutation）。
关键在于题目要求既要求“最早”又要求“最小”。
假定按自然数从小到大遍历，只有找到了一个平方根前十位数字正好让 0~9 的数字全部出现的数，你才能确信找到了满足题目条件的最小整数。
在没有找到满足“平方根前十位数字正好让 0~9 的数字全部出现”的数之前，你无法确定后面是不是存在满足“平方根前十位数字正好让 0~9 的数字全部出现”的数，所以你只能继续找下去。
所幸，满足“平方根前十位数字正好让 0~9 的数字全部出现”的数是存在的。
基本步骤如下：
从小到大遍历自然数：
对每一个自然数：
求其平方根
转换成字符串
取前十个（除小数点以外的字符），或取小数点后的前十个字符
判断这十个字符是否恰好包含所有的0~9
如果满足条件则退出，否则继续搜索下一个
代码中用以下判断前十个字符是否满足题设条件：
len(set(list(first10))) == 10这是因为set会自动删除重复元素，因此如果set的长度是10而其可能的元素又只能是0~9的话，那就必然满足条件。
# -*- coding: utf-8 -*-"""Created on Sat Sep 4 08:51:51 2021@author: chenxy"""import sysimport timeimport datetimeimport math# import randomfrom typing import List# from queue import Queue# from collections import dequeclass Solution: def squareRoot1(self, sel:int) -> tuple: """ Find the first interger, for which, either the first 10 digits of its square root, or the first 10 digits of the decimal part of its square root, includes all of 0~9. sel: 0--including integer part; 1: not including integer part ret: """ i = 1 while(1): i_sqrt = math.sqrt(i) i_sqrt_str = str(i_sqrt) # Find the position of decimal point for k in range(len(i_sqrt_str)): if i_sqrt_str[k] == ".": break if sel == 0: first10 = i_sqrt_str[0:k] + i_sqrt_str[k+1:11] else: first10 = i_sqrt_str[k+1:k+11] # print(first10,list(first10),set(list(first10))) if len(set(list(first10))) == 10: return i, i_sqrt i = i+1 def squareRoot2(self) -> tuple: """ Find the first interger, for which, the first 10 digits of the decimal part of its square root, includes all of 0~9. ret: """ num=1 str_num="1.000000000000000" while len(set(list(str_num.split(".")[1][:10])))!=10: num+=1 str_num=str(num**0.5) return num, num**0.5 if __name__ == "__main__": sln = Solution() tStart = time.time() num1,num1_sqrt = sln.squareRoot1(0) # including integer part num2,num2_sqrt = sln.squareRoot1(1) # Only considering fractional part tCost = time.time() - tStart print("num1={0}, num1_sqrt={1:.10f}, tCost = {2:6.3f}(sec)".format(num1,num1_sqrt,tCost)) print("num2={0}, num2_sqrt={1:.10f}, tCost = {2:6.3f}(sec)".format(num2,num2_sqrt,tCost)) tStart = time.time() num3,num3_sqrt = sln.squareRoot2() # Only considering fractional part tCost = time.time() - tStart print("num3={0}, num3_sqrt={1:.10f}, tCost = {2:6.3f}(sec)".format(num3,num3_sqrt,tCost)) 运行结果：
num1=1362, num1_sqrt=36.9052841745, tCost = 0.003(sec)
num2=143, num2_sqrt=11.9582607431, tCost = 0.003(sec)
num3=143, num3_sqrt=11.9582607431, tCost = 0.000(sec)
[2021-09-05]
Bijfah提示了利用字符串方法split()的更间接的代码，作为squareRoot2()追加到以上代码中了。善用python内置函数确实能让代码和运行效率都有脱胎换骨的效果。谢谢Bijfah的指点！但是squareRoot2()目前只能对付只考虑小数部分的情况，要对付含整数部分的情况的话还需要略修改造一下。
上一篇：Q11: 斐波那契数列
下一篇：Q13: 满足字母算式的解法
本系列总目录参见：程序员的算法趣题：详细分析和Python全解
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/119272.html
摘要：使这个字母算式成立的解法只有这一种。在中用内置的函数进行字符串形式的算式值的评估在中判断字符串表达式是否合法依据的规则是多位数字的操作数的第一个字母不能为。上一篇平方根数字下一篇国名接龙本系列总目录参见程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题思路 3. 代码及测试 ...
摘要：接下来就是判断两根线段是否相交的问题了。据此可以得到本题的算法流程代码实现运行结果不过要注意的是，原题说的是最少需要条横线的鬼脚图数，但是最后给出的解其实是正好需要条横线的鬼脚图数。书中给出的解释类似于数学证明中臭名昭著的显而易见。。。 目录 1. 问题描述 2. 实现方案 3. 代码实现...
摘要：且听下回分解基于动态规划策略的优化解法参见程序员的算法趣题偷懒的算盘上一篇程序员的算法趣题同数包夹程序员的算法趣题同数包夹本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述 ...
摘要：汉明距离可以用异或操作实现。这个问题其实可以看作是，具有个节点的全连接无向图，每条边的权重值代表两个节点所代表的数字的段码显示的二进制表示之间的汉明距离。 目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问题描述 问题：求把10个数字全部显示出来时，亮灯/灭...
摘要：基于以上讨论可得，本题求解流程如下所示代码及测试运行结果上一篇水果酥饼日下一篇异或杨辉三角形本系列总目录参见程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问题描述 六度空间理论非常有名。大概的意思是1个人只需要通过6个中间人就...
阅读 2467·2021-11-22 09:34
阅读 4125·2021-11-15 18:13
阅读 2993·2021-09-24 10:24
阅读 1149·2021-09-22 16:01
阅读 2497·2021-09-06 15:02
阅读 891·2019-08-30 13:01
阅读 841·2019-08-30 10:52
阅读 516·2019-08-29 16:36
