2025年3月16日 星期日 甲辰(龙)年 月十五 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

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

时间:12-26来源:作者:点击数:54

1. 问题描述

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

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

2. 解题分析

这道题目比较含糊。

其实是找平方根(含整数部分或不含整数部分的)前十位数字正好让 0~9的数字全部出现(且不重复)的最小整数—即构成0~9的一个排列(permutation)。

关键在于题目要求既要求“最早”又要求“最小”。

假定按自然数从小到大遍历,只有找到了一个平方根前十位数字正好让 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:
  • """
  • 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()目前只能对付只考虑小数部分的情况,要对付含整数部分的情况的话还需要略修改造一下。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门