资讯专栏INFORMATION COLUMN

程序员的算法趣题Q12: 平方根数字

loostudy / 2675人阅读

摘要:所幸,满足平方根前十位数字正好让的数字全部出现的数是存在的。上一篇斐波那契数列下一篇满足字母算式的解法本系列总目录参见程序员的算法趣题详细分析和全解

目录

1. 问题描述

2. 解题分析

3. 代码及测试


1. 问题描述

        求在计算平方根的时候,最早让0~9的数字全部出现的最小整数。注意这里只求平方根为正数的情况,并且请分别求包含整数部分的情况和只看小数部分的情况。

例)2的平方根 1.414213562373095048...0~9全部出现需要19位)

2. 解题分析

        这道题目比较含糊。

        其实是找平方根(含整数部分或不含整数部分的)前十位数字正好让 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的话,那就必然满足条件。

3. 代码及测试

# -*- 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

相关文章

  • 序员算法趣题Q13: 满足字母算式解法

    摘要:使这个字母算式成立的解法只有这一种。在中用内置的函数进行字符串形式的算式值的评估在中判断字符串表达式是否合法依据的规则是多位数字的操作数的第一个字母不能为。上一篇平方根数字下一篇国名接龙本系列总目录参见程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题思路 3. 代码及测试 ...

    Clect 评论0 收藏0
  • 序员算法趣题Q54: 偷懒算盘

    摘要:且听下回分解基于动态规划策略的优化解法参见程序员的算法趣题偷懒的算盘上一篇程序员的算法趣题同数包夹程序员的算法趣题同数包夹本系列总目录参见程序员的算法趣题详细分析和全解程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 4. 后记 1. 问题描述   ...

    wangzy2019 评论0 收藏0
  • 序员算法趣题Q37: 翻转7段码(1)

    摘要:汉明距离可以用异或操作实现。这个问题其实可以看作是,具有个节点的全连接无向图,每条边的权重值代表两个节点所代表的数字的段码显示的二进制表示之间的汉明距离。 目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问题描述         问题:求把10个数字全部显示出来时,亮灯/灭...

    RdouTyping 评论0 收藏0
  • 序员算法趣题Q19: 朋友朋友还是朋友吗?

    摘要:基于以上讨论可得,本题求解流程如下所示代码及测试运行结果上一篇水果酥饼日下一篇异或杨辉三角形本系列总目录参见程序员的算法趣题详细分析和全解 目录 1. 问题描述 2. 解题分析 3. 代码及测试 1. 问题描述         六度空间理论非常有名。大概的意思是1个人只需要通过6个中间人就...

    oogh 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<