我已经制作了一个程序,它将大量测试用例作为输入,对于每个测试用例,它需要一个数字作为输入。最后,它会检查您输入的数字是否为斐波那契数字并进行相应打印。我在我的PC上运行它没有任何问题。但是当我将它上传到CodeChef.com(我看到这个问题)时,它显示运行时错误。任何帮助都表示赞赏,因为我是菜鸟,我的代码可能看起来很长。欢迎任何修改。谢谢!
这是我的代码:
def isperfect(n):
import math
if n < 0:
print("No Solution")
return False
else:
test = int(math.sqrt(n))
return test*test == n
test_cases = int(input())
count = 0
store = []
while count < test_cases:
x = int(input())
store.append(x)
count += 1
for each_item in store:
assert isinstance(each_item, int)
s1 = 5*each_item*each_item-4
s2 = 5*each_item*each_item+4
if(isperfect(s1) == True or isperfect(s2) == True):
print("YES")
else:
print("NO")
这是我遇到的最优雅的解决方案:
def is_fibonacci(n):
phi = 0.5 + 0.5 * math.sqrt(5.0)
a = phi * n
return n == 0 or abs(round(a) - a) < 1.0 / n
代码不是我的,由@ sven-marnach发布。原帖:check-input-that-belong-to-fibonacci-numbers-in-python
运行时错误显然是由于异常,但Codechef不提供任何其他信息。它可能是各种各样的事情,包括除以零,内存耗尽,断言失败,......
虽然您的程序适用于许多常用数字,但它不能处理Codechef约束允许的所有输入。特别是,要测试的数字最多可包含1000个数字。如果你尝试像1000位数字这样的大输入,你会发现它失败了。首先它因为你的assert isinstance(each_item, int)
而失败; 12位数或更多的数字不是int
类型。你可以删除断言。发生下一个故障是因为您正在使用浮点sqrt
例程,并且需要将整数转换为浮点。 Python可以处理非常长的整数,但浮点表示的精度更受限制,并且无法处理1000位整数转换。这很难修复,但可以做到。有关平方根的全整数解,请参阅this ActiveState recipe。
我已经想过这可以通过使用Newton-Raphson方法来完成,我已经用Newton-Raphson公式代码替换了函数isperfect()中的代码,删除了断言并且它有效。感谢你的帮助。
这是最终的代码:
def isperfect(n):
x = n
y = (x + n // x) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x*x == n
test_cases = int(input())
count = 0
store = []
while count < test_cases:
x = int(input())
store.append(x)
count += 1
for each_item in store:
s1 = 5*each_item*each_item-4
s2 = 5*each_item*each_item+4
if(isperfect(s1) == True or isperfect(s2) == True):
print("YES")
else:
print("NO")
这将是一种非常有效的方式。
In [65]:
import scipy.optimize as so
from numpy import *
In [66]:
def fib(n):
s5=sqrt(5.)
return sqrt(0.2)*(((1+s5)/2.)**n-((1-s5)/2.)**n)
def apx_fib(n):
s5=sqrt(5.)
return sqrt(0.2)*(0.5*(1+s5))**n
def solve_fib(f):
_f=lambda x, y: (apx_fib(x)-y)**2
return so.fmin_slsqp(_f,0., args=(f,),iprint=0)
def test_fib(fibn):
if fibn<1:
print 'No, it is not'
else:
n=int(round(solve_fib(fibn)))
if int(round(fib(n)))==int(fibn):
print 'Yes, it is. (%d)'%n
else:
print 'No, it is not'
In [67]:
asarray(fib(arange(1,20)), dtype='int64')
Out[67]:
array([ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
144, 233, 377, 610, 987, 1597, 2584, 4181])
In [68]:
test_fib(34)
Yes, it is. (9)
In [69]:
test_fib(4181)
Yes, it is. (19)
In [70]:
test_fib(4444)
No, it is not
这样做相当简单有效
def isInFib(n):
if n == 0: return False
elif n == 1: return True
else:
A = 1
B = 1
FLIP = True
while(True):
new = A + B
if new > n: return False
elif new == n: return True
else:
if(FLIP):
A = new
FLIP = not FLIP
else:
B = new
FLIP = not FLIP
我首先检查我的输入是否等于0或1,并返回适当的。
如果我的输入大于1,我们进入else,无限循环。
A和B代表序列中最后两个前面的数字。我们添加A和B来获得新的当前Fibonacci数。
我们检查new是否等于我们的输入数,如果确实如此,我们返回true,我们完成并完成该功能。
如果它更大,那意味着我们的数字不在Fibonacci序列中,因为我们已超过它。
如果它更少,我们需要继续前进!而这就是我认为解释起来令人困惑的地方。我想将A或B设置为我当前的斐波那契序列号(新),但我确保我不断在它们之间切换,因为我不想让一个人落后。 Fibonacci序列采用前两个数字并将它们加在一起。我希望A和B成为我之前的两笔钱。
我将用一个例子
1,1,2,3,5,8,13
A和B最初是1.所以new等于2。然后我检查一下我的输入数字是否超过或等于它。但如果我的输入数字较少。我想继续前进。
在我们进入while循环的下一次迭代之前,我希望A等于new(value = 2)。因此,在下一次迭代中,new将等于2 + 1作为A + B.
但是,然后循环的下一次迭代,我想将B设置为3,我想让A等于2.所以我必须在A或B中放置当前的斐波那契数字之间切换那就是我有翻转逻辑的原因!它只是在True和False之间切换。
试试这个功能:
def isfib(number):
num1 = 1
num2 = 1
while True:
if num2 <= number:
if num2 == number:
return True
else:
tempnum = num2
num2 += num1
num1 = tempnum
else:
return False
以下是它的工作原理:
num1
和num2
设为0。num2
不小于或等于返回False
的数字。num2
等于返回True
的数字。num1
添加到num2
,将num1
设置为num2
的原始值并返回步骤2。