1 Тема від Q-bart Востаннє редагувалося Q-bart (17.04.2018 11:29:13)

  • Q-bart
  • Q-bart
  • Хочу бути модератором, щоб такі штуки ставити
  • Поза форумом
  • Звідки: Центр інтернету
  • Дата реєстрації: 14.06.2014
  • Повідомлень: 1 356
    • Репутація: 535

Тема: Температура і бінарний пошук

Hello!

В мене теж трабли з алгоритмами)

Така задачка:

Прихований текст
Протягом N днів робились записи температури. Але сталось так, що записи втратили, і залишились лише перший і останній.
Знаючи перший і останній запис температури, і також те, що за один день температура не може змінюватись більше як на K градусів, знайти макс. і мін. можливу температуру.

Напр. якщо сьогодні темп. 3 градуси, а K=4, то завтра вона може бути між -1 і 7 градусів.

Приклад:
N=4, K=7
First=-10
Last=1

Результат:
4, -13

Можливі розвитки:
-10 > -3 > 4 > 1
-10 > -13 > -6 > 1

Прихований текст
Ага, викладач сказав, що тут має бути бінарний пошук  :D

От і не шарю більше нічого)

Навчаюсь вчитись, щоб навчатись.

2 Відповідь від koala Востаннє редагувалося koala (17.04.2018 11:39:52)

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Звідки: Мати міст руських
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 6 655
    • Репутація: 4970

Re: Температура і бінарний пошук

Нащо бінарний пошук? Тут тупо лінійні рівняння. Температура з першого дня може йти вгору за графіком

y=t1+(x-1)*K

а спускатися до останнього - за графіком 

y=tN-(x-N)*K

Де y - значення температури, x - номер дня (від 1 до N, зокрема при x=1 y(1)=t1+0*K=t1, при x=N y(N)=tN-0*K=tN).
Прирівнюємо:

t1+(x-1)*K = tN-(x-N)*K
t1 + K*x - K = tN - K*x + K*N
2*K*x = tN-t1 + K*(N+1)
x = (tN-t1)/(2*K) + (N+1)/2

Оце наш максимум. Мінімум знаходиться аналогічно.
Раджу побудувати графіки, там це стає очевидним.

Подякували: Q-bart, 0x9111A, leofun01, HetmanNet, varkon5

3 Відповідь від Q-bart

  • Q-bart
  • Q-bart
  • Хочу бути модератором, щоб такі штуки ставити
  • Поза форумом
  • Звідки: Центр інтернету
  • Дата реєстрації: 14.06.2014
  • Повідомлень: 1 356
    • Репутація: 535

Re: Температура і бінарний пошук

koala написав:

Нащо бінарний пошук? Тут тупо лінійні рівняння. Температура з першого дня може йти вгору за графіком

y=t1+(x-1)*K

а спускатися до останнього - за графіком 

y=tN-(x-N)*K

Де y - значення температури, x - номер дня (від 1 до N, зокрема при x=1 y(1)=t1+0*K=t1, при x=N y(N)=tN-0*K=tN).
Прирівнюємо:

t1+(x-1)*K = tN-(x-N)*K
t1 + K*x - K = tN - K*x + K*N
2*K*x = tN-t1 + K*(N+1)
x = (tN-t1)/(2*K) + (N+1)/2

Оце наш максимум. Мінімум знаходиться аналогічно.
Раджу побудувати графіки, там це стає очевидним.

А хібa x, це не день?

Навчаюсь вчитись, щоб навчатись.

4 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Звідки: Мати міст руських
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 6 655
    • Репутація: 4970

Re: Температура і бінарний пошук

Q-bart написав:
koala написав:

x - номер дня

А хібa x, це не день?

Га?

5 Відповідь від Q-bart

  • Q-bart
  • Q-bart
  • Хочу бути модератором, щоб такі штуки ставити
  • Поза форумом
  • Звідки: Центр інтернету
  • Дата реєстрації: 14.06.2014
  • Повідомлень: 1 356
    • Репутація: 535

Re: Температура і бінарний пошук

ну  а треба ж макс температуру

Навчаюсь вчитись, щоб навчатись.

6 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Звідки: Мати міст руських
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 6 655
    • Репутація: 4970

Re: Температура і бінарний пошук

Q-bart написав:

ну  а треба ж макс температуру

Тобто ви хочете сказати, що не можете з цих формул за x отримати y?
Тут іноді піднімають питання, нащо програмістам математика. Буду тепер відправляти у цю тему.

Подякували: Q-bart, leofun01, HetmanNet3

7 Відповідь від Q-bart

  • Q-bart
  • Q-bart
  • Хочу бути модератором, щоб такі штуки ставити
  • Поза форумом
  • Звідки: Центр інтернету
  • Дата реєстрації: 14.06.2014
  • Повідомлень: 1 356
    • Репутація: 535

Re: Температура і бінарний пошук

Дякую

Навчаюсь вчитись, щоб навчатись.

8 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Звідки: Мати міст руських
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 6 655
    • Репутація: 4970

Re: Температура і бінарний пошук

І побудуйте графіки.

9 Відповідь від Q-bart Востаннє редагувалося Q-bart (23.04.2018 22:06:18)

  • Q-bart
  • Q-bart
  • Хочу бути модератором, щоб такі штуки ставити
  • Поза форумом
  • Звідки: Центр інтернету
  • Дата реєстрації: 14.06.2014
  • Повідомлень: 1 356
    • Репутація: 535

Re: Температура і бінарний пошук

але цей код дав іншу відповідь, ніж в прикладі

N = 4
K = 7

t1 = -10
tN = 1

x = (tN - t1) / (2.0 * K) + (N + 1) / 2.0
print(x)

y = t1 + (x - 1) * K
print("max temp = ", y)

result:

3.28571428571
('max temp = ', 6.0)

приклад:

max = 4

Навчаюсь вчитись, щоб навчатись.

10 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Звідки: Мати міст руських
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 6 655
    • Репутація: 4970

Re: Температура і бінарний пошук

А ви побудували графіки?

11 Відповідь від Q-bart

  • Q-bart
  • Q-bart
  • Хочу бути модератором, щоб такі штуки ставити
  • Поза форумом
  • Звідки: Центр інтернету
  • Дата реєстрації: 14.06.2014
  • Повідомлень: 1 356
    • Репутація: 535

Re: Температура і бінарний пошук

так

Навчаюсь вчитись, щоб навчатись.

12 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Звідки: Мати міст руських
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 6 655
    • Репутація: 4970

Re: Температура і бінарний пошук

Ну а тепер уважно подивіться на точки перетинів. Правда ж, вони зовсім не обов'язково цілі?

13 Відповідь від Q-bart Востаннє редагувалося Q-bart (Вчора 00:08:34)

  • Q-bart
  • Q-bart
  • Хочу бути модератором, щоб такі штуки ставити
  • Поза форумом
  • Звідки: Центр інтернету
  • Дата реєстрації: 14.06.2014
  • Повідомлень: 1 356
    • Репутація: 535

Re: Температура і бінарний пошук

https://i.imgur.com/QOScibF.png

Навчаюсь вчитись, щоб навчатись.

14 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Звідки: Мати міст руських
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 6 655
    • Репутація: 4970

Re: Температура і бінарний пошук

А тепер знайдіть на цих прямих найвищу точку із цілою абцисою (для цього достатньо округлити абцису, бо нахили однакові, отже, більша точка буде просто в бік округлення). Це видно?