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
|
|