Lecture "Dynamic programming algorithms", exercise 2

[essepuntato]

Choose any recursive algorithm introduced in the previous chapters and provide a new implementation in Python following the dynamic programming approach.

[delete4ever]

def test_exponentiation(int_1, int_2, solution_dict, expected):
    if exponentiation(int_1, int_2, solution_dict) == expected:
        return True
    else:
        return False

def exponentiation(base_number, exponent, solution_dict):
    if base_number not in solution_dict:
        if exponent == 0: 
            solution_dict[base_number] = 1
        elif exponent == 1:
            solution_dict[base_number] = base_number
        else:
            solution_dict[base_number] = base_number*(exponentiation(base_number, exponent-1, solution_dict))
    return solution_dict.get(base_number)

print(test_exponentiation(100, 10, dict(), 100**10)) #True
print(test_exponentiation(2, 100, dict(), 2**100)) #True
print(test_exponentiation(123456, 0, dict(), 1)) #True

[n1kg0r]

from math import factorial as fc

def test_factorial_recursive_dp(n):
    return factorial_recursive_dp(n, dict()) == fc(n)

def factorial_recursive_dp(n, solution_dict):
    if n not in solution_dict:
        if n == 1:
            return 1
        else:
            return n * factorial_recursive_dp(n-1, solution_dict)
    return solution_dict

print(test_factorial_recursive_dp(5))
print(test_factorial_recursive_dp(1))
print(test_factorial_recursive_dp(28))

[EricaAndreose]

Update! Now I know I can use tuples so:

def test_exponentation(base_number, exponent, solution_dict, expected):
    result = exponentation(base_number, exponent, solution_dict)
    if expected == result:
        return True
    else:
        return False


def exponentation(base_number, exponent, solution_dict: dict):
    couple=(base_number, exponent)
    if couple not in solution_dict:
        if exponent == 0:
            solution_dict[couple] = 1
        elif exponent == 1:
            solution_dict[couple] = base_number
        else:
            solution_dict[couple] = base_number * exponentation(base_number, exponent - 1, solution_dict)
    return solution_dict.get(couple)

# Test runs returning True
print(test_exponentation(3, 4, dict(), 81))
print(test_exponentation(17, 1, dict(), 17))
print(test_exponentation(2, 0, dict(), 1))
print(test_exponentation(2, 4, dict(), 16))
print(test_exponentation(3, 2, dict(), 9))
print(test_exponentation(3, 4, dict(), 81))
print(test_exponentation(17, 1, dict(), 17))
print(test_exponentation(2, 0, dict(), 1))
print(test_exponentation(2, 6, dict(), 64))
print(test_exponentation(0, 15, dict(), 0))
print(test_exponentation(0, 0, dict(), 1))

Previous attempt.

def test_exponentation(base_number, exponent, solution_dict, expected):
    result = exponentation(base_number, exponent, solution_dict)
    if expected == result:
        return True
    else:
        return False

def exponentation(base_number, exponent, solution_dict: dict):
    if base_number not in solution_dict:
        if exponent == 0:     # base case 1
            solution_dict[base_number] = 1
        elif exponent == 1:     # base case 2
            solution_dict[base_number] = base_number
        else:    # recursive step
            solution_dict[base_number] = base_number * exponentation(base_number, exponent - 1, solution_dict)
    return solution_dict.get(base_number)

# Test runs returning True
print(test_exponentation(3, 4, dict(), 81))
print(test_exponentation(17, 1, dict(), 17))
print(test_exponentation(2, 0, dict(), 1))
print(test_exponentation(2, 4, dict(), 16))

[lucia1299]

def test_my_exponentiation (base_number, exponent, solution_dict, expected):
    result = exponentiation(base_number, exponent, solution_dict)
    if result == expected:
        return True
    else: 
        return False

def exponentiation(base_number, exponent, solution_dict):
    solution_dict = dict()
    if base_number not in solution_dict:
        if exponent == 0:
            solution_dict[base_number] = 1
        elif exponent == 1:
            solution_dict[base_number] = base_number
        else:
            solution_dict[base_number] = base_number * (exponentiation(base_number, exponent-1, solution_dict))
    return solution_dict.get(base_number)



print(test_my_exponentiation (3, 4, {}, 81)) #True
print(test_my_exponentiation(17, 1, {}, 17)) #True
print(test_my_exponentiation(2, 0, {}, 1)) #True 

[giorgiacrosilla]

def test_exp(base_number, exponent, solution_dict, expected):
    result = exp(base_number, exponent, solution_dict)
    if expected == result:
        return True
    else: 
        return False 

def exp(base_number, exponent, solution_dict):
    if base_number not in solution_dict:
        if exponent == 0:
            solution_dict[base_number] = 1
        elif exponent == 1:
            solution_dict[base_number] = base_number
        else:
            solution_dict[base_number] = base_number * exp(base_number, exponent-1, solution_dict)
    return solution_dict.get(base_number)

print(test_exp(3,4,dict(), 81))
print(test_exp(17,1, dict(), 17))
print(test_exp(2,0,dict(), 1))

[alka2696]

def test_exponentation(base_number, exponent, solution_dict, expected):
    result = exponentation(base_number, exponent, solution_dict)
    if expected == result:
        return True
    else:
        return False


def exponentation(base_number, exponent, solution_dict):
    together=(base_number, exponent)
    if together not in solution_dict:
        if exponent == 0:
            solution_dict[together] = 1
        elif exponent == 1:
            solution_dict[together] = base_number
        else:
            solution_dict[together] = base_number * exponentation(base_number, exponent - 1, solution_dict)
    return solution_dict.get(together)

soultion_dict= dict()
# Test runs returning True
print(test_exponentation(3, 4, dict(), 81)) #True
print(test_exponentation(5, 6, dict(), 15625)) #True