Статья Автор: Лебедев Дмитрий

Поиск набора с заданной суммой

Дан отсортированный список натуральных чисел \(A = [a_0, \dots,a_{n-1}]\) и натуральное число target
Надо найти набор из k различных индексов \([0\leq i_1<i_2<,\dots <i_k<n]\) такой, что
\(A[i_1] + \dots +A[i_k] = target\)
Задачу можно решить с помощью перебора со сложностью O(n^k), что исключает возможность применения такого подхода даже при k=1
Для k=1 задача принимает "стандартный" вид и имеет эффективное решение с использованием бинарного поиска.
Приведем функцию has_one_summers для решения этой задачи в модификации удобной для следующий рассуждений.

def has_one_summers(n_list,start,end,target):

  ''' Поиск элемента в срезе списка, совпадающего с заданным

  поиск осуществляется методом "Бинарный поиск по ответу"

  n_list - список чисел, среди которых должен осуществляться поиск

  (список отсортирован по неубыванию)

  start - начальный индекс для поиска (>=0)

  end - финальный индекс для поиска

  target - искомое число

  return -

  1. False : если поиск невозможен (индексы вне пределов списка и т.п.)

  2. start -1 : если target < n_list[start]

  3. end + 1 : если target > n_list[end]

  4. кортеж (i, i+1) : если n_list[i] < target < n_list[i + 1]

  5. j : если n_list[j] = target ( j имеет минимальное значение не меньшее start)

'''
Для удобства отладки, анализа результатов и использования функций в формате "матрешка" (функции обращаются к подфункциям) возврат результата "стандартизирован"

логическое значение (получен или не получен результат)
кортеж - значение результата (итогового или промежуточного)
строка - метка возврата

def has_one_summers(n_list, target, start=0, end = -1):
  if end == -1 : # изменяем "умолчание" на фактическое
    end = len(n_list) - 1
  if start >= len(n_list) or start > end : # заявлен поиск вне границ списка
    return False, (start, end), 'oneA' # возврат результата в "стандартной форме" - результата не достигнут
  start, end = max(0, start), min(end, len(n_list) -1) # "загоняем" start, end в границы списка
  if n_list[start] > target : # цель "левее", искать нечего
    return False, (start - 1, start - 1), 'oneB' # возврат результата 
  if n_list[end] < target : # цель "правее", искать нечего
    return False, (end + 1, end + 1), 'oneC'  # возврат результата 
  L, R = start, end # цель "внутри", запуск бинарного поиска по ответу (индексам)
  while R - L > 1 : # бинарный поиск по ответу - ищем индексы
    M = (R + L) // 2 # 
    if n_list[M] < target : L = M
    else : R = M
  if n_list[L] == target : R = L # обработка совпадения с целью
  if n_list[R] == target : L = R
  return True, (L, R), 'oneD' # получили "пользу" - цель между L и R  или L = R = target

# поиск квадратов, между которыми находиться введенное значение
data = [i * i  for i in range(1000001)] # список квадратов
target =  int(input())
print (has_one_summers(data,target))

Перейдем к k=2.
Задачу можно решить за O(n) если воспользоваться методом "Двух встречных указателей":

определим start, end положив srart= 0, end = n-1
пока start < end выполняем:
- если A[start] + A[end] < target, то start +=1
- если A[start] + A[end] > target, то end -=1
- если A[start] + A[end] == target, то поиск завершен (start, end - искомые)
если start стал не меньше end, то такой пары индексов нет

Реализуем этот алгоритм, но немного модифицируем переход к следующему - будем использовать функцию has_one_summers
Используем для решения задания о предствалении числа в виде суммы двух квадратов.

def has_two_summers(n_list, target, start=0, end = -1): 
# описание входных параметров в основном совпадает с has_one_summers  
  if end == -1 : # изменяем "умолчание" на фактическое
    end = len(n_list) - 1
  start, end = max(0, start), min(end, len(n_list) - 1) # "загоняем" start, end в границы списка
  if start >= len(n_list) - 1 or start >= end : # проверяем, что start, end имеет хотя бы два значения 
    return False, (start, end), 'twoA' # возврат результата - результат не достигнут
  if (n_list[start] + n_list[start + 1] > target) or (n_list[end - 1] + n_list[end] < target) : 
    # цель не может быть достигнута (слишком маленькая или слишком большая)
    return False, (start, end), 'twoB' # возврат результата - результат не достигнут
  while start < end : # метод "встречных указателей"
    two_sum = n_list[start] + n_list[end] # сумма значений по указателям
    if two_sum == target : # цель достигнута  !!!
      return True, (start, end), 'twoC' # возврат целевого результата
    if two_sum < target : # сумму надо увеличивать и двигать "левый край" направо
      dif = target - n_list[end] # сколько надо получить слева при фиксации "правого края" 
      rez = has_one_summers(n_list, dif, start, end - 1) # поиск значения, которое должно быть меньше end
      if rez[0] == False : # такого значения НЕТ, возвращаем результат
        return False, rez[1], 'twoD_'+rez[2] # добавляем метку возврата
      start = rez[1][1] # сдвигаем start на значение не меньшее dif
    else : # это случай two_sum > target и надо двигать "правый край" налево
      dif = target - n_list[start] # сколько надо получить справа при фиксации "левого края"
      rez = has_one_summers(n_list, dif, start + 1, end)  # поиск значения, которое должно быть больше start
      if rez[0] == False : # такого значения НЕТ, возвращаем результат
        return False, rez[1], 'twoE_'+rez[2] # добавляем метку возврата
      end = rez[1][0] # сдвигаем end на значение не большее dif
  return False, (start, end),'twoF' # дежурный возврат, сюда прихода быть не должно
# введите натуральное число, программа выведет представление его в сумме квадратов двух чисел (в пределе 1 000 000 
# 836391403520 для примера

Перейдем к k=3
Задачу следуюющим способом:

определим start, end положив srart= 0, end = n-1
пока start + 1 < end выполняем:
1. если A[start] + A[end-1] + A[end] < target, то start +=1
2. если A[start] + A[start+1] + A[end] > target, то end -=1
- если положение start, end "возможны" (пункты a), b) не выполняются) , то определяем goal = target - A[start] и
  - ищем на отрезке start+1, end пару с суммой равной goal
  - если решения нет, тоstart +=1
если start стал не меньше end-1, то такой тройки индексов нет

Реализуем этот алгоритм, использовать функцию has_two_summers
Используем для решения задания о предствалении числа в виде суммы квадратов трех чисел.

def has_three_summers(n_list, target, start=0, end = -1): 
# описание входных параметров в основном совпадает с has_two_summers  
  if end == -1 : # изменяем "умолчание" на фактическое
    end = len(n_list) - 1
  start, end = max(0, start), min(end, len(n_list) - 1) # "загоняем" start, end в границы списка
  if start >= len(n_list) - 2 or start >= end - 1 : # проверяем, что start, end имеет хотя бы три значения 
    return False, (start, end), 'threeA' # возврат результата - результат не достигнут
  if (n_list[start] + n_list[start + 1] + n_list[start + 2] > target) or\
  (n_list[end - 2] + n_list[end - 1] + n_list[end] < target) : 
    # цель не может быть достигнута (слишком маленькая или слишком большая)
    return False, (start, end), 'threeB' # возврат результата - результат не достигнут
  while start < end - 1 : # метод "встречных указателей"
    flag = True
    while flag : # сдвигаем границы по крайним условиям
      flag = False
      if n_list[start] + n_list[end] + n_list[end - 1]  < target : # сумму надо увеличивать и двигать "левый край" направо
        dif = (target - n_list[end - 1] - n_list[end]) # сколько надо получить слева при фиксации "правого края" 
        rez = has_one_summers(n_list, dif, start, end) # поиск значения для "левого края"
        if rez[0] == False : # такого значения НЕТ, возвращаем результат 
          return False, rez[1], 'threeC_'+rez[2] # добавляем метку возврата
        start = rez[1][1] # сдвигаем start на значение не меньшее dif
        flag = True
      if n_list[start] + n_list[start + 1] + n_list[end] > target: # сумму надо уменьшать и двигать "правый край" налево
        dif = (target - n_list[start] -n_list[start +1]) # сколько надо получить справа при фиксации "левого края" 
        rez = has_one_summers(n_list, dif, start, end) # поиск значения для "правого края"
        if rez[0] == False : # такого значения НЕТ, возвращаем результат
          return False, rez[1], 'threeD_'+rez[2] # добавляем метку возврата
        end = rez[1][0] # сдвигаем start на значение не меньшее dif
        flag = True
    goal = target - n_list[start] # определяем сумму для пары при фиксации "левой грани"
    rez = has_two_summers(n_list, goal, start + 1, end) # поиск пары 
    # rez возвращает результаты поиска пары, если start и индексы пары возрастают и подходят
    if rez[0] and (n_list[start] + n_list[rez[1][0]] + n_list[rez[1][1]] == target) :
      return True, (start, rez[1][0], rez[1][1]),'threeE'
    start +=1
  return False, (start, end), 'threeF'  

# введите натуральное число, программа выведет представление его в сумме квадратов трех чисел (в пределе 1 000)

Прикрепленные файлы
93

Чтобы оставить комментарий нужна авторизация

Печать