chapter_computational_complexity/exercises/

[giscus[bot]]

chapter_computational_complexity/exercises/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_computational_complexity/exercises/

[Zsf111]

有习题了^_^

[cyl911520]

def f(n):
    a = 0
    b = 1
    c = 1
    if n == 0:
        c = 0
    for i in range(1, n + 1):
        if i >= 2:
            c = b + a
            a = b
            b = c
        if n == 1:
            c = 1
    return c

[Dumbliidore]

def fab(n: int) -> int:
    a, b = 0, 1
    while n:
        a, b = b, a+b
        n -= 1

    return a

还有斐波那契数列求和的循环算法

def F(n: int) -> int:
    a, b = 0, 1
    r = 0
    while n > 1:
        a, b = b, a+b
        n -= 1
        r += a

    return r or n

[xmzd-S]

public class TestF {
public static void main(String[] args) {
System.out.println(fib(6)); // 5
}

public static int fib(int n) {
    if (n <= 0) {
        throw new IllegalArgumentException("n must be > 0");
    }
    if (n == 1) return 0;
    if (n == 2) return 1;

    int prev2 = 0; // f(n-2)
    int prev1 = 1; // f(n-1)

    for (int i = 3; i <= n; i++) {
        int curr = prev2 + prev1;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

}

[xqy15521094215]

int fibonacci(int n)
{
if (n == 0) return 0;
if (n == 1) return 1;

int f_pre = 0;
int f_curr = 1;

for (int i = 2; i <= n; i++)
{
	int f_next = f_pre + f_curr;
	f_pre = f_curr;
	f_curr = f_next;
}

return f_curr;

}

[ZL0672]

class Solution {
public int fib(int n) {
if (n == 0 || n == 1)
return n;
else {
int[] nums = new int[n + 1];
nums[0] = 0;
nums[1] = 1;
for (int i = 2; i <= n; i++) {
nums[i] = nums[i - 1] + nums[i - 2];
}
return nums[n];
}
}
}

[brucejqing-code]

#不使用递归的斐波那契数列
def non_recur_list(n):
arr = [0,1]
if n == 0:
return 0
if n == 1:
return 1
if n >= 2:
for i in range(2,n + 1):
t = arr[i - 1]+arr[i - 2]
arr.append(t)
return arr[n]
print(non_recur_list(8))
#使用递归的斐波那契数列
def recur_list(n):
count = 0
if n == 0:
count = 0
if n == 1:
count = 1
if n >= 2:
count = recur_list(n - 1) + recur_list(n - 2)
return count
print(recur_list(8))

[RockyTL]

def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a

print（fib（5））