需要找到最小的数字 P,使得给定整数 N
注意:递归解决方案对于大的N值,比如10 ** 9,速度太慢了。
PS:我想找出需要多少个数字使得返回的值等于整数N,比如(例如6)。
编辑:此问题的动态规划解决方案可以是:
sum of f(x)>=N. where f(x)=f(1)+f(2)+.....+f(p) where f(a) is number of times a number and then its quotient is divisible by 5 for example 100 is divisible by 5 two times as 100/5=20 and 20/5=4 but 4 is not divisible so f(100)=2
其中函数被定义为数字及其商可以被5整除的次数。例如,对于N=6,P将是25,因为1、2、3、4、6、7、8、9、11、12、13、14、16、17、18、19、21、22、23和24都不能被5整除,而只有5能够被5整除。
f(5)=1,and same
f(10)=1,
f(15)=1,
f(20)=1
(20/5=4 but 4 is not divisible by 5) but 25 is divisible by 5
通过两次计算(25/5=5,5/5=1),我们得到f(25)=2,因此f(x)=f(1)+f(2)+.....f(25)=6。这就是答案,所以最小的P应该是25。以下是我的代码,但在某些情况下我遇到了问题。
def myround(x, base=5):
return ((base * round((x)/base)))
n=int(input())
count=0
i=5
while(n/i>=1):
count+=1
i=i*5
res=count+1
counter=0
for j in range(1,res+1):
gcd_cal=((1/5)**j)
counter+=gcd_cal
end_res=(n/counter)
zz=(myround(end_res))
reverse=zz-5
re=zz+5
counter1=0
for xx in range(1,res+1):
div=int(5**xx)
temp=(zz//div)
counter1+=temp
counter2=0
for xx in range(1,res+1):
div=int(5**xx)
temp=(reverse//div)
counter2+=temp
counter3=0
for xx in range(1,res+1):
div=int(5**xx)
temp=(re//div)
counter3+=temp
if (counter1==n):
print(zz)
elif(counter2==n):
print(reverse)
elif(counter3==n):
print(re)
else:
print(max(zz,reverse,re))
注意:递归解决方案对于大的N值,比如10 ** 9,速度太慢了。
PS:我想找出需要多少个数字使得返回的值等于整数N,比如(例如6)。
编辑:此问题的动态规划解决方案可以是:
dict={}
def fa(x):
if x in dict:
return dict[x]
if not x%5 and x%25 and x>0:
dict[x]=1
return 1
elif not x%5 and not x%25 and x>0:
dict[x]=1+fa(x//5)
return 1+fa(x//5)
else:
return 0
def F(N):
counter=0
s=0
while s<N:
counter+=5
s+=fa(counter)
return counter
for _ in range(int(input())):
n=int(input())
print(F(n))
N=5
会发生什么? - T C Molenaar