python C++ メモ

python

最大公約数

Q: 51と15の最大公約数は？
1. 51÷15 = 3 あまり6
2. 15÷6 = 2あまり3
3. 6÷3 = 2あまり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);
}

フィボナッチ数列

出力
[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] << "," << " ";
}

メモ化すると↓

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] << ","<< " ";
    }
}