-
Notifications
You must be signed in to change notification settings - Fork 900
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
第 3 题:多种方式实现斐波那契数列 #9
Comments
参考实现数学上是以递归的方法来定义 F(0) = 0;
F(1) = 1;
F(n) = F(n - 1) + F(n - 2);
function fib(n) {
if(n < 0) throw new Error('输入的数字不能小于0');
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
} 正常递归版本是一个既简单又直接的逻辑,但是这个版本有个问题就是存在大量重复计算。如:当 n 为 5 的时候要计算
function fib(n) {
if(n < 0) throw new Error('输入的数字不能小于0');
let f0 = 0,
f1 = 1,
curFib = f0;
if (n < 2) {
return n;
}
for (let i = 1; i < n; i++) {
curFib = f0 + f1;
f0 = f1;
f1 = curFib;
}
return curFib;
} 这个版本没有重复计算问题,速度也明显快了很多。这并不代表循环比递归好。循环的问题在于状态变量太多,为了实现 fib 这里使用了 4 个状态变量(f0,f1,curFib,i) 而状态变量 在写、修改、删除的过程中需要格外小心。状态变量多了阅读起来也不那么优美了。
function fib(n) {
if(n < 0) throw new Error('输入的数字不能小于0');
if (n < 2) return n;
function _fib(n, a, b) {
if (n === 0) return a;
return _fib(n - 1, b, a + b);
}
return _fib(n, 0, 1);
} 把前两位数字做成参数巧妙的避免了重复计算,性能也有明显的提升。n 做递减运算,前两位数字做递增(斐波那契数列的递增),这段代码一个减,一个增。
function* fib(n) {
if(n < 0) throw new Error('输入的数字不能小于0');
let f0 = 1,
f1 = 1,
count = 0;
while (count < n) {
yield f0;
[f0, f1] = [f1, f0 + f1];
count++;
}
}
function fib(n) {
if(n < 0) throw new Error('输入的数字不能小于0');
if (n < 2) {
return n;
}
let list = [];
list[0] = 0;
list[1] = 1;
for (let i = 1; i < n; i++) {
list[i + 1] = list[i] + list[i - 1];
}
return list[n];
} |
function fibonacci(n, map = {}) { |
export const fibonacci = (n: number): number => {
const base = Math.sqrt(5)
return (((1 + base) / 2) ** n - ((1 - base) / 2) ** n) / base
}
console.log(fibonacci(8)) |
时间复杂度 O(n) |
使用generator const createAry = function(args){
let handler = {
get: function(target,propKey,reciever){
return Reflect.get(target,propKey<0 ? (+propKey + target.length) : propKey,reciever)
},
set :function (target,propKey,value,reciever){
return Reflect.set(target,propKey<0 ? (+propKey + target.length) : propKey,value,reciever)
}
}
return new Proxy(args,handler)
}
var ary= createAry([1,2,3,4])
console.log(ary[-1]);
ary[-1]='a'
console.log(ary[-1]); |
const fibonacci = (n: number) => {
let pre = 1,
cur = 1;
if (n === 1 || n === 2) {
return 1;
}
for (let i = 3; i <= n; i++) {
[pre, cur] = [cur, pre + cur];
}
return cur;
};
console.assert(fibonacci(1) === 1);
console.assert(fibonacci(2) === 1);
console.assert(fibonacci(3) === 2);
console.assert(fibonacci(4) === 3); |
function fibonacci(n) { |
@Genzhen 写的明显有问题还那么多人点赞,笑死 |
function fabonacci(i , i1 = 1 , i2 = 1){ |
/**
/**
/**
|
function fn (n){
if(n==0) return 0
if(n==1) return 1
return fn(n-2)+fn(n-1)
}
const fn = (n)=>{
let pre = 1;
let cur = 1;
let data ;
for(var i = 3;i<=n;i++){
// 和变成当前项cur,而当前项cur会变成pre
data = pre + cur;
pre = cur
cur = data
}
return data
}
console.log(fn(2)) |
function (n) { |
|
性能最低到50就会卡死
性能大幅提升
性能进一步提升
|
|
function fabonacci(n, n_1, n_2) { |
function fabonacci(max) {
if (max === 1 || max === 2) {
return 1;
}
return fabonacci(max - 1) + fabonacci(max - 2);
} |
function fibonacci(n) {
if (n === 1) {
return 1
} else if (n === 2) {
return 1
} else {
return fibonacci(n -1) + fibonacci(n - 2)
}
} |
|
function fun(length = 10, a = 0, b = 1) {
let arr = []
do {
if (arr.length < 2) {
arr.push(a)
arr.push(b)
} else {
arr.push(arr[arr.length - 2] + arr[arr.length - 1])
}
} while (arr.length < length);
return arr
}
console.log(fun(20));
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181] |
function fibonacci(n) {
if (n < 2) return n
let a = BigInt(0), b = BigInt(1)
for (let i = 2; i <= n; i++) {
[a, b] = [b, a + b]
}
return b
}
|
// =============无备忘录===================
function fibonacci(n) {
if (n === 1 || n === 2) { return 1 };
return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(30))
// =============有备忘录===================
function fibonacci_memo(n, memo = {}) {
if (n === 1 || n === 2) return 1;
if (memo[n]) return memo[n];
let data = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo);
memo[n] = data;
return data;
}
console.log(fibonacci_memo(30))
// =============for迭代===================
function fibonacci_for(n) {
if (n === 1 || n === 2) return 1;
let total = 0, cur = 1, pre = 1;
for (let i = 3; i <= n; i++) {
total = (pre + cur);
pre = cur;
cur = total;
}
return total;
}
console.log(fibonacci_for(30))
// =============generater步进===================
function fibonacci_gen(n) {
function* gen() {
let total = 0, cur = 1, pre = 1
while (1) {
total = cur + pre;
yield total;
[cur, pre] = [total, cur];
}
}
let iterator = gen();
let data = 0;
if (n === 1 || n === 2) data = 1;
else {
for (i = 3; i <= n-1; i++) {
iterator.next();
}
data = iterator.next().value
}
return data;
}
console.log(fibonacci_gen(30)) |
1 similar comment
// =============无备忘录===================
function fibonacci(n) {
if (n === 1 || n === 2) { return 1 };
return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(30))
// =============有备忘录===================
function fibonacci_memo(n, memo = {}) {
if (n === 1 || n === 2) return 1;
if (memo[n]) return memo[n];
let data = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo);
memo[n] = data;
return data;
}
console.log(fibonacci_memo(30))
// =============for迭代===================
function fibonacci_for(n) {
if (n === 1 || n === 2) return 1;
let total = 0, cur = 1, pre = 1;
for (let i = 3; i <= n; i++) {
total = (pre + cur);
pre = cur;
cur = total;
}
return total;
}
console.log(fibonacci_for(30))
// =============generater步进===================
function fibonacci_gen(n) {
function* gen() {
let total = 0, cur = 1, pre = 1
while (1) {
total = cur + pre;
yield total;
[cur, pre] = [total, cur];
}
}
let iterator = gen();
let data = 0;
if (n === 1 || n === 2) data = 1;
else {
for (i = 3; i <= n-1; i++) {
iterator.next();
}
data = iterator.next().value
}
return data;
}
console.log(fibonacci_gen(30)) |
|
答错题了兄弟 |
// 尾递归
function Fibonacci(n, a= 1, b= 1) {
if(n <= 1) {return b};
return Fibonacci(n - 1, b, a + b);
}
console.log(Fibonacci(10)) |
|
var fib = (n) => {
if(n <= 1) return n
return fib(n - 1) + fib(n - 2)
}
console.time('fib-1')
console.log(fib(20))
console.timeEnd('fib-1')
var fib = (n) => {
if(n <= 1) return n
fib.cache = fib.cache || {}
if(fib.cache[n]) return fib.cache[n]
fib.cache[n] = fib(n - 1) + fib(n - 2)
return fib.cache[n]
}
console.time('fib-2')
console.log(fib(20))
console.timeEnd('fib-2')
var fib = (n) => {
if(n <= 1) return n
let one = 0
let two = 1
for(let i = 2; i <= n; i++){
let o = one + two
one = two
two = o
}
return two
}
console.time('fib-3')
console.log(fib(20))
console.timeEnd('fib-3') |
// 记录fib(n - 1)和fib(n-2) 避免重复计算 从下标2开始向上计算 if (n < 2) { let f0 = 0; // 从下标为2开始 while (i <= n) { return fn; var n = 3; |
|
|
我打印出一个数组
|
这个还算稍微简单funciton fb(n) {
if(n == 1) return 1
if(n == 2) return 1
return fb(n-1) + fb(n-2)
}
funciton fb1(n) {
if(n == 1) return 1
if(n == 2) return 1
let start=1, start1 = 1,next
for(let i = 3; i<= n;i++) {
next = start + start1
start = start1
start1 = next
}
return next
} |
// 方法一:循环
function fib(n) {
let val = [0, 1];
if (n < 1) throw Error('参数n不能小于1');
if (n < 3) return val[n - 1];
for (let i = 2; i < n; i++) {
const [a, b] = val;
val = [b, a + b];
}
return val[1];
}
// 方法二:递归
function fib(n = 0, arr = [0, 1]) {
if (n < 1) throw Error('参数n不能小于1');
if (n < 3) return arr[n - 1];
const [a, b] = arr;
return fib(--n, [b, a + b]);
}
// 测试
console.log(fib(1)) // 0
console.log(fib(5)) // 3
console.log(fib(10)); // 34
// 经测试两种方法并无明显性能差别,用很大的数测试都瞬间出结果 |
let map = new Map(); console.log(fbnq(10)); |
3种方式对比 // 1.递归
// 优点:简单、易于理解
// 缺点:存在大量重复计算
function f(n) {
if (n <= 2) return 1
return f(n - 1) + f(n - 2)
}
// 2.动态规划-1
// 优点:避免了大量的重复计算
// 缺点:需要一个长度为 N 的数组空间,但其实我们只需要存储当前项的前两个值就行,所以空间可以优化到 O(1)
function f1(n) {
if (n <= 2) return 1
let dp = [1, 1]
for (let i = 2; i < n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[n - 1]
}
// 3.动态规划-2
// 优点:无重复计算,只需要常数个变量储存空间,空间复杂度为 O(1)
function f2(n) {
if (n <= 2) return 1
let p = 1
let q = 1
let res
for (let i = 2; i < n; i++) {
res = p + q
p = q
q = res
}
return res
} |
|
欢迎在下方发表您的优质见解
The text was updated successfully, but these errors were encountered: