Нахождение максимума функции

@Пьяный Ёжег · Регистрация: 29.04.2010

Студворк — интернет-сервис помощи студентам

Есть функция, которая принимает только целочисленные значения, аргумент у неё тоже целочисленный. Известно, что на промежутке [0; n] она сначала возрастает, потом убывает. Нужно найти значение аргумента, при котором значение функции максимально.

Линейный поиск работает слишком медленно.

Троичный (тернарный) поиск (статья в Википедии: http://ru.wikipedia.org/wiki/%... 1%81%D0%BA) требует, чтобы функция сначала строго возрастала, а потом строго убывала (или наоборот).

Подскажите, пожалуйста, какие ещё есть алгоритмы.

@Хохол · 23.07.2010, 17:22

То есть она нестрого возрастает и нестрого убывает? Тогда, если больше нет информации, другого способа кроме линейного поиска нет, т.к. Функция в таком случае может везде иметь одинаковое значение, кроме одной единственной точки максимума.

@Пьяный Ёжег · 23.07.2010, 17:28 **[ТС]**

Ясно, спасибо.

@Хохол · 23.07.2010, 17:48

С другой стороны, я лишь показал, что в худшем случае нужен линейный поиск. Если это нужно для прикладных целей, думаю вполне можно похимичить (какая-нибудь модификация тернарного поиска) и снизить матожидание времени поиска.

@Пьяный Ёжег · 23.07.2010, 17:55 **[ТС]**

Сообщение от Хохол

какая-нибудь модификация тернарного поиска

например завести массив для значений функции и следить, чтобы соседние элементы не были равны (а если они равны, то удаляем лишние)

Не подходит, т. к. сложно и сожрёт много памяти при больших n.

@darkAngel · 24.07.2010, 08:40

а что за функция то?

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

Насколько я помню, эта задача нелинейного программирования (если функция не линейна). Попробуй порыскать в таких направлениях:
1)Методо шртафных функций
2)Метод множителей Лагранжа
3)Метод возможных направлений

Это всё пойдёт, если тебе известны ограничения функции даваемые интервалом [0;n], т.е. больше и меньше чего она не может быть. Иначе эта задача превращается в задачу безусловной оптимизации:
1)Градиентный метод
2)Метод скорейшего спуска
3)Метод Гаусса-Зейделя

@Хохол · 24.07.2010, 18:19

Пьяный Ёжег, в каком виде задается функция? Просто последовательность значений или аналитически?

@Пьяный Ёжег · 24.07.2010, 19:08 **[ТС]**

Прошу прощения, несколько часов назад узнал, что то, что я пытался сделать уже давно изобрели и называется эта штука массив суффиксов.

Проблема решена.

@Хохол · 24.07.2010, 19:10

Что за массив суффиксов? Расскажите/дайте ссылку.

@Пьяный Ёжег · 24.07.2010, 20:04 **[ТС]**

Статья в Википедии: http://ru.wikipedia.org/wiki/%... 0%B8%D0%B2

Только в функции поиска нужны были небольшие изменения.
А я ступил и пытался прикрутить вместо двоичного поиска троичный и ещё чёрт знает что.

@Хохол · 24.07.2010, 20:14

Какое отношение суффиксный массив имеет к вашей задаче?

@Пьяный Ёжег · 24.07.2010, 20:42 **[ТС]**

Мне нужен был быстрый поиск подстрок в строке. Особенность: если мы нашли только часть подстроки, поиск считается успешным.
Я создавал суффиксный массив и пытался искать нужный элемент с помощью функции, которая сравнивает две строки и возвращает кол-во совпавших байтов.

@Хохол · 24.07.2010, 20:45

Сообщение от Пьяный Ёжег

Мне нужен был быстрый поиск подстрок в строке. Особенность: если мы нашли только часть подстроки, поиск считается успешным.

Это проще всего обычным КМП делать.

Добавлено через 56 секунд
Хотя, смотря сколько подстрок искать. КМП - для одной подстроки больше подойдет.

@Пьяный Ёжег · 24.07.2010, 21:05 **[ТС]**

Сообщение от Хохол

Хотя, смотря сколько подстрок искать.

Много.

@Хохол · 24.07.2010, 21:27

Ну тогда на всякий еще упомяну алгоритм Ахо-Корасик.

Добавлено через 17 минут
Если что, у меня его реализация на цпп есть.

@Пьяный Ёжег · 24.07.2010, 21:33 **[ТС]**

Сообщение от Хохол

Ну тогда на всякий еще упомяну алгоритм Ахо-Корасик.

Там нужно дерево ключевых слов, не хватит памяти.

@Хохол · 24.07.2010, 21:42

Сообщение от Пьяный Ёжег

Там нужно дерево ключевых слов, не хватит памяти.

У тебя будут гигабайты строк?

Добавлено через 4 минуты
Я решал Ахо-Корасиком вот это:
http://acm.timus.ru/problem.as... &locale=ru
Твои ограничения более жестокие?

@Пьяный Ёжег · 24.07.2010, 21:55 **[ТС]**

Сообщение от Хохол

У тебя будут гигабайты строк?

Всё сложнее...
У меня есть 2 массива размером до 100 МБ каждый. Мне нужно сравнить их и записать в файл команды, которые нужно выполнить, чтобы получить из первого массива второй (в основном перестановка данных местами). Я рассматриваю второй массив как много строк (первая начинается с первого байта, вторая - со второго и т. д.) и ищу строки из второго массива в первом.
Но это не значит, что у меня 100 млн строк, средний размер которых 50 МБ! Если мы что-то нашли в первом массиве, от мы продвигаемся вперёд на длину найденной строки. А если не нашли, то нам не нужно просматривать все 50 МБ.

@Sich_Taras · 27.07.2010, 20:56

здесь подойдет простой бинарный поиск 100% за лог(н)

Новые блоги и статьи Все статьи Все блоги /
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .

@Пьяный Ёжег 0 / 0 / 0 Регистрация: 29.04.2010 Сообщений: 18

	Нахождение максимума функции 23.07.2010, 17:12. Показов 6766. Ответов 18 Метки нет (Все метки) Есть функция, которая принимает только целочисленные значения, аргумент у неё тоже целочисленный. Известно, что на промежутке [0; n] она сначала возрастает, потом убывает. Нужно найти значение аргумента, при котором значение функции максимально. Линейный поиск работает слишком медленно. Троичный (тернарный) поиск (статья в Википедии: http://ru.wikipedia.org/wiki/%... 1%81%D0%BA) требует, чтобы функция сначала строго возрастала, а потом строго убывала (или наоборот). Подскажите, пожалуйста, какие ещё есть алгоритмы. 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	23.07.2010, 17:22
	То есть она нестрого возрастает и нестрого убывает? Тогда, если больше нет информации, другого способа кроме линейного поиска нет, т.к. Функция в таком случае может везде иметь одинаковое значение, кроме одной единственной точки максимума. 1

@Пьяный Ёжег 0 / 0 / 0 Регистрация: 29.04.2010 Сообщений: 18
	23.07.2010, 17:28 [ТС]
	Ясно, спасибо. 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	23.07.2010, 17:48
	С другой стороны, я лишь показал, что в худшем случае нужен линейный поиск. Если это нужно для прикладных целей, думаю вполне можно похимичить (какая-нибудь модификация тернарного поиска) и снизить матожидание времени поиска. 1

@darkAngel Технофашист 229 / 217 / 11 Регистрация: 11.03.2009 Сообщений: 887
	24.07.2010, 08:40
	а что за функция то? Добавлено через 14 минут можно попробывать посчитать градиент - т.е. направление движения к точке оптиума. Вообще всем этим занимается область "математическое программирование". Насколько я помню, эта задача нелинейного программирования (если функция не линейна). Попробуй порыскать в таких направлениях: 1)Методо шртафных функций 2)Метод множителей Лагранжа 3)Метод возможных направлений Это всё пойдёт, если тебе известны ограничения функции даваемые интервалом [0;n], т.е. больше и меньше чего она не может быть. Иначе эта задача превращается в задачу безусловной оптимизации: 1)Градиентный метод 2)Метод скорейшего спуска 3)Метод Гаусса-Зейделя 1

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	24.07.2010, 18:19
	Пьяный Ёжег, в каком виде задается функция? Просто последовательность значений или аналитически? 0

@Пьяный Ёжег 0 / 0 / 0 Регистрация: 29.04.2010 Сообщений: 18
	24.07.2010, 19:08 [ТС]
	Прошу прощения, несколько часов назад узнал, что то, что я пытался сделать уже давно изобрели и называется эта штука массив суффиксов. Проблема решена. 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	24.07.2010, 19:10
	Что за массив суффиксов? Расскажите/дайте ссылку. 0

@Пьяный Ёжег 0 / 0 / 0 Регистрация: 29.04.2010 Сообщений: 18
	24.07.2010, 20:04 [ТС]
	Статья в Википедии: http://ru.wikipedia.org/wiki/%... 0%B8%D0%B2 Только в функции поиска нужны были небольшие изменения. А я ступил и пытался прикрутить вместо двоичного поиска троичный и ещё чёрт знает что. 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	24.07.2010, 20:14
	Какое отношение суффиксный массив имеет к вашей задаче? 0

@Пьяный Ёжег 0 / 0 / 0 Регистрация: 29.04.2010 Сообщений: 18
	24.07.2010, 20:42 [ТС]
	Мне нужен был быстрый поиск подстрок в строке. Особенность: если мы нашли только часть подстроки, поиск считается успешным. Я создавал суффиксный массив и пытался искать нужный элемент с помощью функции, которая сравнивает две строки и возвращает кол-во совпавших байтов. 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	24.07.2010, 21:27
	Ну тогда на всякий еще упомяну алгоритм Ахо-Корасик. Добавлено через 17 минут Если что, у меня его реализация на цпп есть. 0

@Sich_Taras 14 / 14 / 4 Регистрация: 08.10.2009 Сообщений: 114
	27.07.2010, 20:56
	здесь подойдет простой бинарный поиск 100% за лог(н) 0