Знайти глибину Озера

1 Тема від Georgeeee 06.10.2022 17:17:15

Georgeeee
Користувач
Поза форумом

Дата реєстрації: 04.05.2022
Повідомлень: 14

: 2

Тема: Знайти глибину Озера

Суть завдання
В уявному двовимірному світі знаходиться деякий гірський масив. Рельєф цього гірського масиву задано набором висот над рівнем моря: {h1,h2,..., hn}. Після тривалих опадів долини між горами наповнилися водою до найбільшого можливого рівня. Описану ситуацію зображено https://ibb.co/XDc4RHS
Написати програму, яка знаходить глибину найглибшого озера. Допустима складність алгоритму (по пам’яті і по часу) -O(n). Для прикладу, що зображено на шуканий результат - 6.

import numpy as np
import matplotlib.pyplot as plt
arr = [1,5,1,7,1,6,2]
n=len(arr)
deep = 0

for i in range(0,n-1):
    tem_max = 0
    if(arr[i] > arr[i+1]):
        tem_max = arr[i]
        for j in range(i+1,n):
            j_t=arr[j]
            if (tem_max - arr[j] > deep and arr[j] <= tem_max):
                deep = tem_max - arr[j]

print(deep)

x_t = np.arange(0, n, 1)
plt.grid(linestyle='-',c='black')
plt.plot(x_t, arr)
plt.show()

Логіка така що знаходить першу максимальну висоту потім до наступної більшої або такої ж вершини шукає максимальну глибину.
але для простих ламаних воно не до кінця вірно працює.
arr = [1,2,5,6,1,2,2,3,0,1,5,6,7,5,5,7,8,8,2]
для цих даних воно виконується правильно.
Допоможіть оптимізувати і зробити до кінця правильно

2 Відповідь від koala 06.10.2022 21:33:22

koala
Лінива тваринка
Поза форумом

Дата реєстрації: 01.05.2013
Повідомлень: 15 603

Репутація

: 13312

Re: Знайти глибину Озера

Працює неправильно, бо ви враховуєте лише ліву межу. Наприклад, для [5,1,7] ваш код видає правильну відповідь 4, але для [7,1,5] дає 6 - бо алгоритм не розуміє, що вода виллється праворуч.
Ідея правильного алгоритму, я так розумію, десь така.
1. Встановлюємо ліву і праву межі (0 і n-1).
2. В циклі, поки межі не зійдуться:
2. 1. Рухаємо ліву межу праворуч, а праву ліворуч, поки не знайдемо заглибини з обох боків.
2. 2. Нижчу з двох меж рухаємо заглибиною і запам'ятовуємо максимальну глибину, доки заглибина не скінчиться.
Оскільки кожне значення масиву буде перевірено 1 раз (чи 2, коли перевіряли на заглибину) складність буде O(n).

Ще пара порад:
- загорніть алгоритм у функцію. Це дозволить швидко тестувати кілька варіантів.
- вам не потрібен numpy, matplotlib вміє працювати зі звичайним range.
- ось цей вираз можна спростити:

if (tem_max - arr[j] > deep and arr[j] <= tem_max):
    deep = tem_max - arr[j]

Почнемо з другої умови. arr[j] <= tem_max можна переписати у вигляді tem_max - arr[j] >= 0; але оскільки deep на початку дорівнює 0, а далі не зменшується, то друга умова завжди істинна і її можна прибрати. Лишилося

if tem_max - arr[j] > deep:
    deep = tem_max - arr[j]

А це значно простіше записується як

deep = max(deep, tem_max - arr[j])

Подякували: Georgeeee1

koala вебсайт

3 Відповідь від koala 07.10.2022 10:52:32

koala
Лінива тваринка
Поза форумом

Дата реєстрації: 01.05.2013
Повідомлень: 15 603

Репутація

: 13312

Re: Знайти глибину Озера

Крок 2.1 зайвий, його можна включити в 2.2.
У мене вийшло так:

def max_depth(mountains):
    left = 0
    left_height = mountains[left]
    right = len(mountains)-1
    right_height = mountains[right]
    deep = 0
    while left<right:
        if left_height<right_height:
            left += 1
            deep = max(deep, left_height - mountains[left])
            left_height = max(left_height, mountains[left])
        else:
            right -= 1
            deep = max(deep, right_height - mountains[right])
            right_height = max(right_height, mountains[right])
    return deep
    
if __name__=="__main__":
    for mountains, expected in [([5,1,7], 4),
                                ([7,1,5], 4),
                                ([1,5,1,7,1,6,2], 5)]:
        actual = max_depth(mountains)
        if actual != expected:
            print(f"max_depth({mountains}) gives {actual}, but expected is {expected}")

Подякували: Georgeeee1

koala вебсайт