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 sys
import time
import datetime
import math
# import random
from   typing import List
# from   queue import Queue
# from   collections import deque

class 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: The total number of IP satisfying the requirement
        """                
        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
                    
if __name__ == '__main__':        
            
    sln    = Solution()            
    
    tStart = time.time()
    num1,num1_sqrt = sln.squareRoot1(0)
    num2,num2_sqrt = sln.squareRoot1(1)
    tCost  = time.time() - tStart
    print('num1={0}, num1_sqrt={1:.10f}, tCost = {1:6.3f}(sec)'.format(num1,num1_sqrt,tCost))    
    print('num2={0}, num2_sqrt={1:.10f}, tCost = {1:6.3f}(sec)'.format(num2,num2_sqrt,tCost))

運行結果：

num1=1362, num1_sqrt=36.9052841745, tCost = 0.002(sec)
num2=143, num2_sqrt=11.9582607431, tCost = 0.002(sec)

上一篇：Q11: 斐波那契數列

本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/297525.html

標籤：其他

上一篇：31歲，熬夜學習到2點的背后，是一個丈夫和父親的責任與擔當

下一篇：?軟體測驗之“支付功能”測驗

程式員的演算法趣題Q12: 平方根數字

1. 問題描述

2. 解題分析

3. 代碼及測驗