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

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

Дан отсортированный список натуральных чисел \(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(nk), что исключает возможность применения такого подхода даже при 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)
  '''
Для удобства отладки, анализа результатов и использования функций в формате "матрешка" (функции обращаются к подфункциям) возврат результата "стандартизирован"
  • логическое значение (получен или не получен результат)
  • кортеж - значение результата  (итогового или промежуточного)
  • строка - метка возврата 


Перейдем к 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
Используем для решения задания о предствалении числа в виде суммы двух квадратов.
 


Перейдем к k=3
Задачу  следуюющим способом:
  • определим startend положив srart= 0end = 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
Используем для решения задания о предствалении числа в виде суммы квадратов трех чисел.

Прикрепленные файлы
93
Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать