Python: напишите программу, чтобы найти период (ы) наибольшего падения цены

Question

Я должен решить этот вопрос, но я застрял.

Напишите программу, чтобы найти период (ы) наибольшего падения цены, когда указан список цен (ы). Например, если список [300.301.303.299.300.298.301.305], то есть один период наибольшего падения цен: время 2 от с ценой 303 по времени 5 с ценой 298.

Ниже мое решение, но есть недостаток

def maxdrop(p): 
    high = low = drop = newhigh = 0 
    for i in range(len(p)): 
    if p[i] >= p[high]: 
     newhigh = i # invariant: p[high] <= p[newhigh] 
    else: # so: p[i] < p[high] <= p[newhigh] 
     newdrop = p[newhigh] - p[i] 
     if newdrop >= drop: 
     high, low, drop = newhigh, i, newdrop 
    return ((high, p[high]), (low, p[low]), drop) 
def test(): 
    p = [20,22,19,20,24,18,21,24,27] 
    print p, maxdrop(p) 
    p = list(reversed(p)) 
    print p, maxdrop(p) 
    if __name__ == "__main__": 
    test() 

Если вы попытаетесь с списком ниже [2,1,2,3,4,3,2]

острейшего падения должны происходит в течение 4,3,2 - 3 последних элементов. Но с моим кодом, выход 2,1 - первые 2 элемента.

Пожалуйста, помогите, спасибо!

Answer 1

Вот моя попытка. Он работает правильно на всех примерах, которые вы дали.

Я в основном просто просматриваю массив, и когда между двумя точками происходит переход между двумя точками, ссылаясь на первую точку как A, смотрите вперед, пока не будет значение, превышающее A. Я отслеживаю минимум в этом область. Если разница между А и минимумом больше, чем то, что я уже нашел, я держусь за нее. Затем я снова начинаю искать падение между двумя точками, начиная со следующей точки, которая была выше A.

Вот код. Это не очень Python-esque, но он работает очень хорошо (я бы просто пошел в Cython, если бы мне было нужно, чтобы он был быстрее). Кроме того, он возвращает величину падения.

def maxdrop(p): 
    bestdrop = 0 
    wheredrop = -1,-1 
    i = 0 
    while i < len(p) - 1: 
     if p[i+1] < p[i]: 
      bestlocal = p[i+1] 
      wherelocal = i+1 
      j = i + 1 
      while j < len(p) - 1 and p[j + 1] < p[i]: 
       j += 1 
       if p[j] < bestlocal: 
        bestlocal = p[j] 
        wherelocal = j 
      if p[i] - bestlocal > bestdrop: 
       bestdrop = p[i] - bestlocal 
       wheredrop = i, wherelocal 
      i = j+1 
     else: 
      i += 1 
    return bestdrop,wheredrop 

Большая проблема с вашим кодом, что вы смотрите только на следующее значение для самого большого падения после нового максимума значение найдено.

Answer 2

Python позволяет гораздо более короткий код:

l = [300,301,303,299,300,298,301,305] 

max([(l[i] - l[j], i, j) for i in range(len(l)) for j in range(i, len(l))], key=lambda x:x[0]) 

(5, 2, 5) 

Это может быть, может быть сокращен, но это хорошая отправная точка. Кроме того, как и другие, пожалуйста, используйте метку [домашняя работа], если это необходимо. Редактировать: это ответы (падение, начало, конец).

Answer 3

Его всегда лучше всего распечатать все значения и проверить результаты.

Проблема с вашим кодом при написании p [i]> p [high] вы обновляете значение newhigh, но значение high не меняется.

Просто напишите его как p [i]> p [newhigh] и проверьте, дает ли он правильные результаты. Я не проверял, даст ли он правильный результат. Сделайте это самостоятельно.

Хотя вы всегда можете использовать укороченные версии, упомянутые выше.

Answer 4

Скопировав код и отступом, вы почти у цели. Где вы проверяете:

if p[i] >= p[high]: 

Вы не принимая во внимание, что р [я] может быть> = р [высокий], но меньше, чем р [newhigh].

Answer 5

Вы хотите, чтобы максимальная сумма была непрерывной, но инвертированной. This page имеет лучшее объяснение, которое я видел.

Основной алгоритм будет выглядеть следующим образом:

>>> def min_sum_subsequence(seq): 
...  minsofar = 0 
...  minendinghere = 0 
...  for s in seq: 
...   # invariant: maxendinghere and maxsofar are accurate 
...   # are accurate up to s 
...   minendinghere = min(minendinghere + s, 0) 
...   minsofar = min(minsofar, minendinghere) 
...  return minsofar 
... 
>>> series = [300,301,303,299,300,298,301,305] 
>>> returns = [series[i] - series[i-1] for i in range(1, len(series))] 
>>> min_sum_subsequence(returns) 
-5 

Вы должны добавить код, чтобы отслеживать индекс начала и конца.

Answer 6

Вы запрашиваете самую большую немонотонно убывающую последовательность. Аналогичный вопрос существует для монотонно в this question. Много способов подойти к этой проблеме. Вот рекурсивный подход.

def biggest_drop(sequence): 
    seq_min, seq_max = min(sequence), max(sequence) 
    imin, imax = sequence.index(seq_min), sequence.index(seq_max) 
    if imin == imax: 
     return None 
    if imin < imax: 
     # split the sequence and look for local drops 
     drop_a = biggest_drop(sequence[:imax]) 
     drop_b = biggest_drop(sequence[imax:]) 
     if drop_a is None or drop_b is None: 
      if drop_a: 
       return drop_a 
      return drop_b 
     value_a = drop_a[0] - drop_a[-1] 
     value_b = drop_b[0] - drop_b[-1] 
     if value_a > value_b: 
      return drop_a 
     else: 
      return drop_b 
    return sequence[imax:imin+1] 

Answer 7

Вот мое решение:

start_=stop_=None 
min_=0 
for start in range(len(li)-1): 
    for stop in range(start+1, len(li)): 
     tmp= li[stop]-li[start] 
     if tmp<min_: 
      min_=tmp 
      start_=start 
      stop_=stop 
print min_ 
print (start_, stop_) 

Он работает для образца.

Answer 8

Там более быстрый способ вычисления mins, чем этот пример, но это краткое и читабельная:

>>> data = [300, 301, 303, 299, 300, 298, 301, 305] 
>>> mins = [min(data[i:]) for (i, _) in enumerate(data)] 
>>> mins 
[298, 298, 298, 298, 298, 298, 301, 305] 
>>> drops = [ d - m for (d, m) in zip(data, mins)] 
>>> drops 
[2, 3, 5, 1, 2, 0, 0, 0] 
>>> [ (i, data[i] - drop) for (i, drop) in enumerate(drops) if drop == max(drops) ] 
[(2, 298)] 

Зная, что начало периода 2 и низкая точка 298, конец периода это:

>>> [ i for (i, x) in enumerate(data) if i > 2 and x == 298] 
[5]