Учитывая список несортированных целых чисел и целевое целое число, выясните, равна ли разница какой-либо пары в списке целевому целому числу с рекурсией.

 >>> aList = [5, 4, 8, -3, 6]
>>> target = 9
return True

>>> aList = [-1, 5, 4]
>>> target = 3
return False
 

• Циклы For и while не разрешены.
• Импорт не разрешен.
• .sort() не допускается.

Я попробовал это, и это не сработало.

 def calculate(aList, target):

    if len(aList) == 0 and diff != 0:
        return False

    startIndex = 0
    endIndex = len(aList) - 1

    return resursive_sum(aList, target, startIndex, endIndex)

def resursive_sum(aList, targ, start, end):

    print(f'Start: {start}')
    print(f'End: {end}')

    if start == end:
        return False
    elif aList[end] - aList[start] == targ:
        return True
    elif aList[end] - aList[start] < targ:
        return resursive_sum(values, targ, start, end - 1)
    return resursive_sum(aList, targ, start   1, end)
 

Я не уверен, как можно решить эту проблему, если мы не можем использовать циклы для сортировки списка. Даже если бы мы могли использовать рекурсию для сортировки списка, как должна выглядеть рекурсия, чтобы она могла сканировать разницу каждой пары?

Итак, я действительно реализовал это, но в образовательных целях я не собираюсь публиковать это чуть позже (я обновлю его через несколько часов), поскольку я предполагаю, что это для класса или какой-либо другой настройки, где вы должны разобраться самостоятельно.

Предположим, вы пытаетесь достичь цели различия t = 5 и оцениваете произвольный элемент 8 . Есть только два значения, которые позволили 8 бы иметь дополнение в наборе: 8 5 = 13 и 8 - 5 = 3 .

Если 3 бы or 13 был в каких-либо предыдущих элементах, вы бы знали, что набор имеет пару дополнений. В противном случае вы бы хотели записать факт, который 8 был замечен. Таким образом, если 3 было найдено позже, 8 будет запрошено, как 3 5 = 8 будет рассмотрено.

Другими словами, я предлагаю метод, при котором вы рекурсивно просматриваете список и либо

• (базовый вариант) Находятся в конце списка
• Есть текущий элемент a , такой, что a t или a - t был замечен
• Запишите, что текущий элемент был замечен, и перейдите к следующему элементу

В идеале это должно иметь O (n) временную сложность и O (n) пространственную сложность в худшем случае (при условии эффективной реализации с передачей по ссылке или аналогичной, а также амортизированного запроса с постоянным временем). Это также может быть реализовано с использованием базового массива, но я не собираюсь говорить, что это лучше (на python).

Я опубликую свое решение через несколько часов. Удачи!

РЕДАКТИРОВАТЬ 1: Надеюсь, у вас было достаточно времени, чтобы заставить его работать. Метод, который я описал, можно выполнить следующим образом:

 def hasDiffRecur(L, t, i, C):
    """
    Recursive version to see if list has difference
    :param L: List to be considered
    :param t: Target difference
    :param i: Current index to consider
    :param C: Cache set
    """
    # We've reached the end. Give up
    if i >= len(L): 
        return False
    
    print(f" > L[{i}] = {L[i]:2}; is {L[i]-t:3} or {L[i] t:2} in {C}")
    
    # Has the complement been cached?
    if L[i] - t in C: 
        print(f"! Difference between {L[i]} and {L[i]-t} is {t}")
        return True
    
    if L[i]   t in C: 
        print(f"! Difference between {L[i]} and {L[i] t} is {t}")
        return True
    
    # Complement not seen yet. Cache element and go to next element
    C.add(L[i])
    return hasDiffRecur(L, t, i 1, C)

###################################################################

def hasDiff(L, t):
    """
    Initialized call for hasDiffRecur. Also prints intro message. 
    See hasDiffRecur for param info
    """
    print(f"nIs a difference of {t} present in {L}?")
    return hasDiffRecur(L, t, 0, set())

###################################################################

hasDiff([5, 4, 8, -3, 6], 9)
hasDiff([-1, 5, 4], 3)
hasDiff([-1, 5, 4, -1, 7], 0) # If concerned about set non-duplicity 
 

ВЫВОД:

 Is a difference of 9 present in [5, 4, 8, -3, 6]?
 > L[0] =  5; is  -4 or 14 in set()
 > L[1] =  4; is  -5 or 13 in {5}
 > L[2] =  8; is  -1 or 17 in {4, 5}
 > L[3] = -3; is -12 or  6 in {8, 4, 5}
 > L[4] =  6; is  -3 or 15 in {8, -3, 4, 5}
! Difference between 6 and -3 is 9

Is a difference of 3 present in [-1, 5, 4]?
 > L[0] = -1; is  -4 or  2 in set()
 > L[1] =  5; is   2 or  8 in {-1}
 > L[2] =  4; is   1 or  7 in {5, -1}

Is a difference of 0 present in [-1, 5, 4, -1, 7]?
 > L[0] = -1; is  -1 or -1 in set()
 > L[1] =  5; is   5 or  5 in {-1}
 > L[2] =  4; is   4 or  4 in {5, -1}
 > L[3] = -1; is  -1 or -1 in {4, 5, -1}
! Difference between -1 and -1 is 0
 

РЕДАКТИРОВАТЬ 2:

Это довольно умное и эффективное решение. Я понимаю, что, возможно, это намерение вообще не допускать никакого обхода (т. Е. Нет запроса на существование для set). Если это так, описанный выше подход может быть выполнен со списком постоянного размера, который предварительно распределен по размеру, равному диапазону значений списка.

Если понятие предварительного выделения для размера диапазона списка все еще слишком много итераций, я могу подумать об исчерпывающем подходе, реализованном рекурсивно. Вероятно, для этого существует более эффективный подход, но вы могли бы свести проблему к задаче, подобной двойному циклу (O (n ^ 2) временная сложность). Это тривиальный алгоритм, и я думаю, вы можете понять его без документации, поэтому я просто добавлю его туда для полноты:

 def hasDiffRecur(L, t, i = 0, j = 1):
    if i >= len(L): return False
    if j >= len(L): return hasDiffRecur(L, t, i 1, i 2)
    if abs(L[i] - L[j]) == t: return True
    return hasDiffRecur(L, t, i, j 1)

###################################################################

print(hasDiffRecur([5, 4, 8, -3, 6], 9))  # True
print(hasDiffRecur([-1, 5, 4], 3))        # False
print(hasDiffRecur([-1, 5, 4, -1, 7], 0)) # True
 

выберите

Я начну с универсальной функции, которая принимает список, t , и количество элементов для выбора, n —

 def choose(t, n):
  if n == 0:
    return [[]]
  elif not t:
    return []
  else:
    return append 
      ( map 
          ( choose(rest(t), n - 1)
          , lambda c: append([first(t)], c)
          )
      , choose(rest(t), n)
      )
 

 print(choose(["a", "b", "c", "d"], 2))
 

 [['a', 'b'], ['a', 'c'], ['a', 'd'], ['b', 'c'], ['b', 'd'], ['c', 'd']]
 

помощники

Ваш вопрос накладывает немало ограничений, а Python — это многопарадигмальный язык, поэтому мы собираемся использовать ряд помощников, чтобы сделать вещи удобочитаемыми

 def first(t):
  return t[0]

def rest(t):
  return t[1:]

def append(t0, t1):
  return t0   t1
 

Я не знаю map , считается ли это импортом, но на всякий случай мы определим наш собственный —

 def map(t, f):
  if not t:
    return []
  else:
    return append 
      ( [f(first(t))]
      , map(rest(t), f)
      )
 

решите

Отлично, теперь, когда мы закончили реализацию choose , давайте посмотрим, как мы можем применить это к нашей проблеме

 print(choose([5, 4, 8, -3, 6], 2))
 

 [[5, 4], [5, 8], [5, -3], [5, 6], [4, 8], [4, -3], [4, 6], [8, -3], [8, 6], [-3, 6]]
 

Как вы можете видеть, мы нашли все комбинации из 2 элементов. Нам просто нужно loop пройти через это, и check если пара может быть вычтена для достижения нашей цели, q —

 def solve(t, q):
  def check(p):
    (x, y) = p
    return x - y == q or y - x == q
  def loop(c):
    if not c:
      return False
    else:
      return check(first(c)) or loop(rest(c))    
  return loop(choose(t, 2))
 

 print(solve([5, 4, 8, -3, 6], 9))
print(solve([-1, 5, 4], 3))
 

 True
False
 

позволяя for

Это отличное упражнение для развития ваших навыков рекурсии. Запрещение for — самое сложное ограничение, которое нужно преодолеть. Вот как это могло бы выглядеть, если бы мы могли его использовать —

 def choose(t, n):
  if n == 0:
    yield []
  elif not t:
    return
  else:
    for c in choose(t[1:], n - 1):
      yield [t[0]]   c
    yield from choose(t[1:], n)

def solve(t, q):
  for (x,y) in choose(t, 2):
    if x - y == q or y - x == q:
      return True
  return False
 

 print(solve([5, 4, 8, -3, 6], 9))
print(solve([-1, 5, 4], 3))
 

 True
False
 

Этот вариант имеет дополнительное преимущество в том, что он прекратит вычислять комбинации, как только будет найдено решение. Первый вариант должен сначала вычислить все комбинации, а затем начать перебирать их.

разрешение других встроенных

Встроенные функции Python включают map и any и предлагают нам другой способ обойти for ограничение, но я не уверен, разрешены ли они —

 def choose(t, n):
  if n == 0:
    yield []
  elif not t:
    return
  else:
    yield from map 
      ( lambda c: [t[0]]   c
      , choose(t[1:], n - 1)
      )
    yield from choose(t[1:], n)

def solve(t, q):
  def check(p):
    (x,y) = p
    return x - y == q or y - x == q
  return any(map(check, choose(t, 2)))
 

 print(solve([5, 4, 8, -3, 6], 9))
print(solve([-1, 5, 4], 3))
 

 True
False
 

Проблема:

• учитывая массив int aList и int target ,
• проверьте, равна ли разница между каждым элементом в aList target
• используйте рекурсию
• не используйте .sort()
• не используйте while и for
• не используйте import

Пример:

 >>> aList = [5, 4, 8, -3, 6]
>>> target = 9
return True

>>> aList = [-1, 5, 4]
>>> target = 3
return False
 

Сравнение различий:

       5  4  8  -3 6
-------------------------
5  |  X
4  |  1  X
8  |  3  4  X
-3 |  6  7  11 X
6  |  1  2  2  9  X

where X means that there's no difference (same number)
since we find 9 there, so it should return True (target is 9)
 

Традиционный для циклов

Чтобы решить проблему рекурсии, сначала попробуйте решить ее с помощью традиционных for циклов:

 def compareAll(lst, tgt):
  for x in lst: # let's call this x loop
    for y in lst: # let's call this y loop
      if abs(x-y) == tgt:
        return True
  return False
print( compareAll([5,4,8,-3,6],9) )
print( compareAll([-1,5,4],3) )
 

Это возвращает True тогда False

Рекурсия

Теперь мы можем попробовать использовать цикл рекурсии. Поскольку у нас уже есть for цикл, мы можем преобразовать его следующим образом:

 def compareAll(lst, tgt, x=0, y=0):
  if(len(lst)-1 == x and len(lst) == y):
    return False
  if(len(lst) == x or len(lst) == y):
    return compareAll(lst, tgt, x 1, 0)
  if(abs(lst[x] - lst[y])==tgt):
    return True
  return compareAll(lst, tgt, x, y 1)
print( compareAll([5,4,8,-3,6],9) )
print( compareAll([-1,5,4],3) )
 

Как я преобразую for цикл в это:

• for цикл python на самом деле foreach является циклом в большинстве других языков
• итак, чистый for цикл в python будет выглядеть так:

 def compareAll(lst, tgt):
  x = 0
  while x < len(lst): # let's call this x loop
    y = 0
    while y < len(lst): # let's call this y loop
      if abs(lst[x]-lst[y]) == tgt:
        return True
      y = y 1
    x = x 1
  return False
print( compareAll([5,4,8,-3,6],9) )
print( compareAll([-1,5,4],3) )
 

• обратите внимание на условие остановки x loop : когда все элементы массива были зациклены
  • итак, мы добавляем условие остановки здесь: if(len(lst)-1 == x and len(lst) == y): return False
• обратите внимание на условие остановки y loop : когда все элементы массива были зациклены
  • итак, мы добавляем условие остановки здесь: if(len(lst) == x or len(lst) == y): return compareAll(lst, tgt, x 1, 0)
  • это останавливает текущее y loop и продолжает x loop
• затем мы добавляем фактическое содержимое цикла: if(abs(lst[x] - lst[y])==tgt): return True
• наконец, мы должны продолжить цикл: return compareAll(lst, tgt, x, y 1)

Ключ к преобразованию цикла for в рекурсивный цикл — это просто определить, когда цикл должен завершиться, и когда цикл должен продолжаться.

Это должно сработать и довольно лаконично:

 def q(target, aList, memo=set()):
    if len(aList) == 0:
        return False
    num = aList.pop()
    memo.add(num)    
    if target   num in memo:
        return True
    return q(target, aList, memo)


q(target=9, aList=[5, 4, 8, -3, 6]) # True    
q(target=3, aList=[-1,5,4]) # False
 

Ключевым моментом для меня является то, что цель t и заданное число n , разница d известны. Dict / set / hashmaps быстро обнаруживают членство, независимо от того, сколько элементов добавлено. Итак … просто pop просмотрите список значений и поместите их в hashmap для последующего сравнения.

Проблема может быть решена путем проверки каждой возможной пары чисел в списке на предмет решения. Если вам разрешено использовать стандартную библиотеку Python, то решение довольно простое.

 from itertools import product

def check(xs, target):
    return any(map(lambda x: x[0]-x[1] == target, product(xs, xs)))

 

Разбивка

• product(xs, xs) дает перекрестное произведение xs с самим собой
• any(iterable) возвращает true, если какой-либо элемент iterable является истинным
• map(function, iterable) лениво (применяет функцию к каждому элементу итерации)
• lambda arg_tuple: expression анонимная функция с аргументами arg_tuple и возвращает результат выражения

Оператор return в check использует отложенные структуры, поэтому он выполняет столько работы, сколько необходимо, и экономит пространство.

Предполагая, что это всего лишь упражнение в рекурсии, это, вероятно, не исключает подхода «грубой силы». Вы можете использовать рекурсию для сопряжения каждого значения с остальными, пока не найдете совпадающую разницу.

Например:

 def hasDiff(L,diff,base=None):
    if not L: return False    # empty list: no match
    if base is None:          # search with amp; without first as base      
        return hasDiff(L[1:],diff,L[0]) or hasDiff(L[1:],diff)
    return abs(base-L[0]) == diff or hasDiff(L[1:],diff,base) # match or recurse
    
print(hasDiff([5, 4, 8, -3, 6],9)) # True
print(hasDiff([-1, 5, 4],3))       # False
 

Когда функция выполняет рекурсию с базовым значением, она просто проверяет первый элемент в оставшейся части списка и выполняет рекурсию для других значений. Когда функция выполняет рекурсию без базового значения, она пытается найти новые пары, которые не включают первый элемент (т. Е. В остальной части списка)