Falcão (falcao) wrote,
Falcão
falcao

Categories:

задача дня -- 2

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

Даю две формулировки условия. Сначала -- более "математизированная".

Дан массив целых чисел X[1..n]. Требуется найти максимум величины X[i]-X[j] по всем i<=j. Массив разрешается читать только один раз в режиме read-only. Дополнительная память состоит всего из нескольких ячеек (скажем, не больше пяти).

А вот более "занимательная" переформулировка.

Представим себе, что нам стала известна "инсайдерская" информация о курсе доллара на следующий месяц. Мы сидим у монитора, и на экране мелькают цифры -- не слишком быстро (чтобы мы могли проделать простейшие устные вычисления), но и не слишком медленно (записать на бумагу мы уже ничего не можем). Числа идут по дням, и они округлены до целого числа рублей (для простоты). Курс всё время колеблется. У нас есть некоторое количество баксов, и мы хотим наиболее выгодно их продать в один из дней, когда курс достаточно высокий, чтобы чуть позже купить их по подходящей цене, когда курс существенно снизится. Считается, что мы в каждый момент можем удерживать в голове несколько чисел (например, два или три). Требуется определить, на какую максимальную выгоду мы можем рассчитывать при такой сделке. Разницей между курсом покупки и продажи для простоты полагается пренебречь.

UPD (02.05) Раскрываю все комментарии. Спасибо всем, кто участвовал. По отдельности анализировать ответы не буду. Задача действительно была несложной, и все решения используют примерно ту же самую идею. В одном из первых же ответов прозвучало почти буквально то, что бы сказал я сам. Что касается длинных программных кодов, то я их, к сожалению, "не чтец" (для меня это примерно как читать "на чукотском" :)) Но из общих соображений было понятно, что там реализовано примерно то же самое (иногда почему-то длинновато).
Tags: задача-дня, математика
Subscribe

  • задача дня-12

    Попалась на днях одна симпатичная вероятностная задача. В исходной постановке, она достаточно несложная, но более общий вопрос на эту тему для меня…

  • о невычислимых функциях

    Данный пост является "общепросветительским", поэтому он открыт для всех. На эту тему я уже писал https://falcao.livejournal.com/26513.html когда-то…

  • задача дня-11

    Давненько уже не было постов под этим "тегом". А сейчас очень симпатичная задача попалась. В принципе, поучаствовать в её решении могут все желающие,…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 22 comments

  • задача дня-12

    Попалась на днях одна симпатичная вероятностная задача. В исходной постановке, она достаточно несложная, но более общий вопрос на эту тему для меня…

  • о невычислимых функциях

    Данный пост является "общепросветительским", поэтому он открыт для всех. На эту тему я уже писал https://falcao.livejournal.com/26513.html когда-то…

  • задача дня-11

    Давненько уже не было постов под этим "тегом". А сейчас очень симпатичная задача попалась. В принципе, поучаствовать в её решении могут все желающие,…