同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

10025_Fibonacci数列的4种求法之四

2022-5-16 18:16| 发布者: Hocassian| 查看: 66| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504349232400-Problem List-采集的数据-后羿采集器.html

Pro.ID

10025

Title

Fibonacci数列的4种求法之四

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=10025

AC

360

Submit

640

Ratio

56.25%

时间&空间限制

Time Limit: 600/300 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

本题要求采用第四种方法：备忘录方法。做法是：用数组把曾经求出来的Fibonacci数列保存下来，以后要的时候直接取出来。

本题不涉及高精度数。

输入

每行一个整数 i ，表示Fibonacci数列的第i项。 i < 47

输出

Description

本题要求采用第四种方法：备忘录方法。做法是：用数组把曾经求出来的Fibonacci数列保存下来，以后要的时候直接取出来。

本题不涉及高精度数。

Input

每行一个整数 i ，表示Fibonacci数列的第i项。 i < 47

Output

对每个整数i，输出Fibonacci数列的第i项。

Sample Input

1
3
20

Sample Output

1
2
6765

Hint

本题的测试数据量与之三相同。
results是一个数组，用来做“备忘录”

memoized_fibonacci(n)
{
for i = 1 to n // 初始化备忘录
results[i] = -1 // -1 means undefined
return memoized_fibonacci_recurs( results, n )
}

memoized_fibonacci_recurs( results, n )
{
if ( results[n] != -1 )
return results[n]
if ( n == 1 ) val = 1
else if ( n == 2 )
val = 1
else {
val = memoized_fibonacci_recurs( results, n - 2 )
val = val + memoized_fibonacci_recurs( results, n - 1 )
}
results[n] = val
return val
}

这题如果不用递归（搜索）+记忆化，判cheat且封号。

Author

John