python C ++ notes

python

Greatest common divisor

Q: What is the greatest common divisor of 51 and 15?

51 ÷ 15 = 3 too much 6
15 ÷ 6 = 2 too much 3 3.6 ÷ 3 = 2 less than 0 A: ３！！

def GCD(m,n):
    if n==0:
        return m
    return GCD(n,m%n)
print(GCD(51,15))

#include <bits/stdc++.h>
using namespace std;
int GCD(int m, int n){
    if (n==0) return m;
    return GCD(n,m%n);
}
int main() {
    cout << GCD(51,15);
}

Fibonacci sequence

output [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049]

fibo = [None]*50
fibo[0]=0
fibo[1]=1
for i in range(2,50):
    fibo[i]=fibo[i-1]+fibo[i-2]
print(fibo)

#include <bits/stdc++.h>
using namespace std;
int main() {
    std::vector<long long> fibo(50);
    fibo[0] = 0, fibo[1]=1;
    for (int i=2;i<50;++i){
        fibo[i]=fibo[i-1]+fibo[i-2];
    }
    for (int i=0;i<50;++i) cout << fibo[i] << "," << " ";
}

Memoize ↓

memo = [-1]*50
memo[0] = 0
memo[1] = 1
def fibo(n):
    if n==0:
        return 0
    elif n==1:
        return 1
        
    if memo[n] != -1:
        return memo[n]
    memo[n] = fibo(n-1)+fibo(n-2)
    return memo[n]

fibo(49)
print(memo)

#include <bits/stdc++.h>
using namespace std;
std::vector<long long> memo;
long long fibo(int n){
    if (n==0) return 0;
    else if (n==1) return 1;
    
    if (memo[n] != -1) return memo[n];
    return memo[n] = fibo(n-1)+fibo(n-2);
}
int main() {
    memo.assign(50,-1);
    fibo(49);
    for (int n=2;n<50;++n){
        cout << memo[n] << ","<< " ";
    }
}