s*****e
发帖数: 115 | 1 Please take 60 minutes to work on this and send it back to me when you are
done. The test must be done in C++ and you must do a recursive solution.
/**
* The Fibonacci sequence is Fn = Fn-1 + Fn-2. Seed values F0=0, F1=1.
* Example: 0+1=1, 1+1=2, 1+2=3, 2+3=5, 3+5=8, ...
* Write a program that calculates the Fibonacci sequence, and then returns
all primes up to the nth prime Fibonacci number, where n is an
* option passed in on the cmd line.
* Example: In the above calculation - prime_fib 3 -> 2 3 5
* If a non-integer value is passed in on the command line, you should print
a statement " is not a number" as an error output, and then continue
processing data.
*
* ./prime_fibs 1 2 7 foo 5
* calculate the first 1 prime fibonacci numbers.
* 2
* calculate the first 2 prime fibonacci numbers.
* 2 3
* calculate the first 7 prime fibonacci numbers.
* 2 3 5 13 89 233 1597
* foo is not a number.
* calculate the first 5 prime fibonacci numbers.
* 2 3 5 13 89
*
*/
诸位看官，一个小时要做出来，这是要几年的经验才能不用准备就能做出来？
我当时做的时候，prime这个公式可以马上google出来，fibonacci这个我第一时间想到
是DP， RECURSION的话有两种，不带DP的recursion，2年前我实现过，n只能到大约37
， 带DP的recursion不见得比纯DP要好啊？
我当时想做到one pass，多想一会，时间就过了，还是自己功力不够 | k******n
发帖数: 184 | 2 这题要用到一点同余知识推出一个比较简单的关于项数i和值结论
感觉考点就是高中奥数。。。╮(╯▽╰)╭ | l***i
发帖数: 1309 | 3 fibo numbers grow very fast, so n is very small. | t****b
发帖数: 2484 | 4 分别对每个数求是不是素数
用二分也是常数复杂度吧 | w*******d
发帖数: 59 | 5 真的假的……现在数学家还不知道是不是有无穷多 fibonacci primes...... 唯一有用
的结论大概就是Fibonacci prime对应的n一定是prime，然后用筛法找吧……
【在 k******n 的大作中提到】
: 这题要用到一点同余知识推出一个比较简单的关于项数i和值结论
: 感觉考点就是高中奥数。。。╮(╯▽╰)╭
| s**x
发帖数: 7506 | | G***G
发帖数: 16778 | 7 easy
first Fibonacci sequence
then check if it is prime
returns
print
【在 s*****e 的大作中提到】
: Please take 60 minutes to work on this and send it back to me when you are
: done. The test must be done in C++ and you must do a recursive solution.
: /**
: * The Fibonacci sequence is Fn = Fn-1 + Fn-2. Seed values F0=0, F1=1.
: * Example: 0+1=1, 1+1=2, 1+2=3, 2+3=5, 3+5=8, ...
: * Write a program that calculates the Fibonacci sequence, and then returns
: all primes up to the nth prime Fibonacci number, where n is an
: * option passed in on the cmd line.
: * Example: In the above calculation - prime_fib 3 -> 2 3 5
: * If a non-integer value is passed in on the command line, you should print
| G****A
发帖数: 4160 | 8 每找到一个Fibonacci number立刻check prime, check prime需要用memorization
returns
print
【在 s*****e 的大作中提到】
: Please take 60 minutes to work on this and send it back to me when you are
: done. The test must be done in C++ and you must do a recursive solution.
: /**
: * The Fibonacci sequence is Fn = Fn-1 + Fn-2. Seed values F0=0, F1=1.
: * Example: 0+1=1, 1+1=2, 1+2=3, 2+3=5, 3+5=8, ...
: * Write a program that calculates the Fibonacci sequence, and then returns
: all primes up to the nth prime Fibonacci number, where n is an
: * option passed in on the cmd line.
: * Example: In the above calculation - prime_fib 3 -> 2 3 5
: * If a non-integer value is passed in on the command line, you should print
|
|
