Здравствуйте. Вопрос возможно не совсем по теме математики, так что удалите тему, если считаете её не уместной. И я заранее извиняюсь))
Задача такая:
Построить алгоритм, который из последовательности, состоящей из N чисел, вычеркивал бы минимальное кол-во элементов так, чтобы оставшиеся образовывали возрастающую последовательность. Так же надо оценить сложность полученного алгоритма.
B голову лезут дурацкие алгоритмы c кучей сравнений, вот думаю, может есть какие быстрые способы до которых не додумался)
Составить алгоритм
Составить алгоритм
Последний раз редактировалось carlos0n 29 ноя 2019, 11:46, всего редактировалось 1 раз.
Причина: test
Причина: test
Составить алгоритм
Мне кажется, чтобы гарантировать минимальность удаленных элементов последовательности, придется иметь сложность - сравнить каждый элемент последовательности c каждым, подсчитывая число инверсий, затем удалить элементы c наибольшим числом инверсий. Ho это, конечно, слишком "в лоб", должен быть более изящный путь...
Последний раз редактировалось jmhan 29 ноя 2019, 11:46, всего редактировалось 1 раз.
Причина: test
Причина: test
Составить алгоритм
теоретически это так наверно можно - строится дерево рекурсивно, a потом ищется в нем самая длинная ... ветка чтоли)
Последний раз редактировалось mihailm 29 ноя 2019, 11:46, всего редактировалось 1 раз.
Причина: test
Причина: test
Составить алгоритм
mihailm, деревья разные бывают))) какое именно вы предлагаете строить?
мне тут подсказали статью по этой теме
[url=http://ru.wikipedia.org/wiki/%D0%97%D0%B0%...%81%D1%82%D0%B8]http://ru.wikipedia.org/wiki/%D0%97%D0%B0%...%81%D1%82%D0%B8[/url]
Ну там и алгоритм.. Если кто понял и может понятно объяснить, то будьте добры, объясните плз))
Я так понимаю, в M у нас и будет наша последовательность или нет?
Да и что значит эта строка в коде? L = index = M[0] = 0
Что я там надо найти бинарным поиском и где, если последовательность не отсортирована, a это алгоритм для отсортированного массива.
И как потом получить эти эл-ты максимальной подпоследовательности?
мне тут подсказали статью по этой теме
[url=http://ru.wikipedia.org/wiki/%D0%97%D0%B0%...%81%D1%82%D0%B8]http://ru.wikipedia.org/wiki/%D0%97%D0%B0%...%81%D1%82%D0%B8[/url]
Ну там и алгоритм.. Если кто понял и может понятно объяснить, то будьте добры, объясните плз))
Я так понимаю, в M у нас и будет наша последовательность или нет?
Да и что значит эта строка в коде? L = index = M[0] = 0
Что я там надо найти бинарным поиском и где, если последовательность не отсортирована, a это алгоритм для отсортированного массива.
И как потом получить эти эл-ты максимальной подпоследовательности?
Последний раз редактировалось carlos0n 29 ноя 2019, 11:46, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 11 гостей