目錄

1. 問題描述

2. 解題分析

3. 代碼及測試

1. 問題描述

????????求在計算平方根的時候，最早讓0~9的數(shù)字全部出現(xiàn)的最小整數(shù)。注意這里只求平方根為正數(shù)的情況，并且請分別求包含整數(shù)部分的情況和只看小數(shù)部分的情況。

例）2的平方根 ：1.414213562373095048...（0~9全部出現(xiàn)需要19位）

2. 解題分析

????????這道題目比較含糊。

????????其實是找平方根（含整數(shù)部分或不含整數(shù)部分的）前十位數(shù)字正好讓 0~9 的數(shù)字全部出現(xiàn)（且不重復(fù)）的最小整數(shù)—即構(gòu)成0~9的一個排列（permutation）。

????????關(guān)鍵在于題目要求既要求“最早”又要求“最小”。

????????假定按自然數(shù)從小到大遍歷，只有找到了一個平方根前十位數(shù)字正好讓 0~9 的數(shù)字全部出現(xiàn)的數(shù)，你才能確信找到了滿足題目條件的最小整數(shù)。

????????在沒有找到滿足“平方根前十位數(shù)字正好讓 0~9 的數(shù)字全部出現(xiàn)”的數(shù)之前，你無法確定后面是不是存在滿足“平方根前十位數(shù)字正好讓 0~9 的數(shù)字全部出現(xiàn)”的數(shù)，所以你只能繼續(xù)找下去。

????????所幸，滿足“平方根前十位數(shù)字正好讓 0~9 的數(shù)字全部出現(xiàn)”的數(shù)是存在的。

基本步驟如下：

????????從小到大遍歷自然數(shù)：

?????? ????????對每一個自然數(shù)：

????????????? ????????求其平方根

????????????????????? 轉(zhuǎn)換成字符串

????????????????????? 取前十個（除小數(shù)點以外的字符），或取小數(shù)點后的前十個字符

????????????????????? 判斷這十個字符是否恰好包含所有的0~9

????????????????????? 如果滿足條件則退出，否則繼續(xù)搜索下一個

????????代碼中用以下判斷前十個字符是否滿足題設(shè)條件：

len(set(list(first10))) == 10

????????這是因為set會自動刪除重復(fù)元素，因此如果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))      

運行結(jié)果：

????????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內(nèi)置函數(shù)確實能讓代碼和運行效率都有脫胎換骨的效果。謝謝Bijfah的指點！但是squareRoot2()目前只能對付只考慮小數(shù)部分的情況，要對付含整數(shù)部分的情況的話還需要略修改造一下。

? ? ? ? 上一篇：Q11: 斐波那契數(shù)列

? ? ? ? 下一篇：Q13: 滿足字母算式的解法

????????本系列總目錄參見：程序員的算法趣題：詳細(xì)分析和Python全解