【算法趣题】Q12 平方根数字

发表: 2018-05-01 浏览: 1617

算法 Python

引言

【算法趣题】是来自图灵程序设计丛书绝云译的《程序员的算法趣题》，书中是用Ruby实现的。这里是用python来实现。

问题描述

平方根，又叫二次方根，表示为〔±√￣〕，其中属于非负数的平方根称之为算术平方根（arithmetic square root）。一个正数有两个实平方根，它们互为相反数；0只有一个平方根，就是0本身；负数有两个共轭的纯虚平方根。例如2的平方根就是±1.414213562373095048...这个无限小数。

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

例） 2的平方根：1.414213562373095048... （0-9全部出现需要19位）

思路

最早让0~9的数字全部出现的话，当然就是前10个数字就包含了0-9这些数字了。如此我们举例来说明2是不是我们要的数。

首先，我们引入math包，使用math.sqrt()方法求平方根。

python默认的是17位小数的精度，这里我们只要求10位，不用担心超精度的问题。

查看如上情况，4的平方根是整数2，只有2位数字，我们也需要把它扩充为10个数字，整数位最多也设计为10个数，因此可以有

针对包含整数部分，那我们就去掉小数点，并截取前10位：

针对只看小数部分，我们只需取小数点后面的字符即可。

而对于我们所获得的10位数，是否包含了0-9的全部数字，我们只需要知道这10位数中是否有重复字符出现，即判断set的长度是否等于10：

所以我们可以知道2不是我们所求的数，因此要继续往下循环判断。我们已经按照思路完整走了一遍，只要再整理下代码即可。

python实现

# 包含整数部分的情况

i = 1

while(True):

    a = '.10f' % (math.sqrt(i))

    s10 = str(a).replace('.','')[0:10]

    if len(set(s10))==10:

        print('满足条件的最小整数是：'+str(i))

        print('其平方根是：'+str(a)[0:11])

        break

    i = i + 1

# 只看小数部分的情况

i = 1

while(True):

    a = '.10f' % (math.sqrt(i))

    s10 = str(a).split('.')[1]

    if len(set(s10))==10:

        print('满足条件的最小整数是：'+str(i))

        print('其平方根是：'+str(a))

        break

    i = i + 1