Run ❯
Get your
own
website
×
Change Orientation
Change Theme, Dark/Light
Go to Spaces
Python
C
Java
computation_count = 0 def F(n): global computation_count computation_count += 1 if n <= 1: return n else: return F(n - 1) + F(n - 2) computation_count_mem = 0 def F_mem(n): if memo[n] != None: # Already computed return memo[n] else: # Computation needed global computation_count_mem computation_count_mem += 1 if n <= 1: memo[n] = n else: memo[n] = F_mem(n - 1) + F_mem(n - 2) return memo[n] print('F(30) = ',F(30)) print(f'Number of computations: {computation_count}') print('\nUsing memoization:') memo = [None]*31 print('F(30) = ',F_mem(30)) print(f'Number of computations with memoization: {computation_count_mem}') #Python
#include
int computationCount = 0; int computationCountMem = 0; int memo[31]; int F(int n) { computationCount++; if (n <= 1) { return n; } else { return F(n - 1) + F(n - 2); } } int FMem(int n) { if (memo[n] >= 0) { // Already computed return memo[n]; } else { // Computation needed computationCountMem++; if (n <= 1) { memo[n] = n; } else { memo[n] = FMem(n - 1) + FMem(n - 2); } return memo[n]; } } int main() { for (int i = 0; i < 31; i++) { memo[i] = -1; // Initialize memo array with -1 to indicate uncomputed } printf("F(30) = %d\n", F(30)); printf("Number of computations: %d\n\nUsing memoization:\n", computationCount); printf("F(30) = %d\n", FMem(30)); printf("Number of computations with memoization: %d\n", computationCountMem); return 0; } //C
public class Main { private static int computationCount = 0; private static int computationCountMem = 0; private static Integer[] memo = new Integer[31]; public static void main(String[] args) { System.out.println("F(30) = " + F(30)); System.out.println("Number of computations: " + computationCount); System.out.println("\nUsing memoization:"); System.out.println("F(30) = " + FMem(30)); System.out.println("Number of computations with memoization: " + computationCountMem); } public static int F(int n) { computationCount++; if (n <= 1) { return n; } else { return F(n - 1) + F(n - 2); } } public static int FMem(int n) { if (memo[n] != null) { // Already computed return memo[n]; } else { // Computation needed computationCountMem++; if (n <= 1) { memo[n] = n; } else { memo[n] = FMem(n - 1) + FMem(n - 2); } return memo[n]; } } } //Java
Python result:
C result:
Java result:
F(30) = 832040
Number of computations: 2692537
Using memoization:
F(30) = 832040
Number of computations with memoization: 31
F(30) = 832040
Number of computations: 2692537
Using memoization:
F(30) = 832040
Number of computations with memoization: 31
F(30) = 832040
Number of computations: 2692537
Using memoization:
F(30) = 832040
Number of computations with memoization: 31