שאלות ממבחני עבר

בחלק זה תתרגלו מספר שאלות רקורסיה שנשאלו במבחני עבר. נסו לפתור אותן בעצמכם - מומלץ אפילו בדף ועט! לאחר מכן בדקו את תשובותיכם. קיימים גם פתרונות אפשריים שמוצעים לכם פה, אך מדובר בפתרון אחד אפשרי. אם הפתרון שלכם רקורסיבי ועובד, הוא יקבל את הנקודות.

תשפ”ב סמסטר ב’ מועד א’

פתחו את המבחן 2223BmoedA וענו על שאלות: 1.ג, 1.ד.

פתרונות

1.C

def squared_ways(target, base=1):
    result = base ** 2
    if target == result:
        return 1
    if target < result:
        return 0
    op1 = squared_ways(target - result, base + 1)
    op2 = squared_ways(target, base + 1)
    return op1 + op2

print(squared_ways(50))
print(squared_ways(25))
print(squared_ways(6))

3
2
0

1.D

def max_val_sub(lst, size):
    if size == 0:
        return 0
    if len(lst) == 0:
        return 0
    if len(lst) == 1:
        return lst[0]
    op1 = lst[1] + max_val_sub(lst[2:], size - 1)
    op2 = lst[0] + max_val_sub(lst[2:], size - 1)
    op3 = max_val_sub(lst[2:], size)
    return max(op1, op2, op3)

print(max_val_sub([3, 1, 8, 9, 6], 3))
print(max_val_sub([1,2,3,4,5], 3))

18
11

תשפ”ב סמסטר ב’ מועד ב’

פתחו את המבחן 2223BmoedB וענו על שאלות: 1.ג, 1.ד. יש להתעלם מהדרישה לממואיזציה.

פתרונות

1.C

def subset_sums(nums):
    # Print current subset
    if len(nums) == 0:
        return [0]
    opts = []
    op1 = subset_sums(nums[:-1])
    # Subset excluding nums[-1]
    opts.extend(op1)
    # Subset including nums[-1]
    for elem in op1:
        elem += nums[-1]
        opts += [elem]
    return opts 

print(subset_sums([]))
print(subset_sums([2,3]))
print(subset_sums([1,3,4]))

[0]
[0, 2, 3, 5]
[0, 1, 3, 4, 4, 5, 7, 8]

1.D (Ignore memoization)

def min_diff(lst):
    return min_diff_rec(lst)

def min_diff_rec(pres_lst, first=0, second=0, index=0):
    if len(pres_lst) == index:
        return abs(first - second)
    
    op1 = min_diff_rec(pres_lst, first + pres_lst[index], second, index + 1)
    op2 = min_diff_rec(pres_lst, first, second + pres_lst[index], index + 1)
    return min(op1, op2)

print(min_diff([]))
print(min_diff([100,30,20,45]))
print(min_diff([10 ,10 ,30]))

0
5
10