Помощь - Поиск - Пользователи - Календарь
Полная версия: задача на пермутацию
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Perfez
Важно:Сразу прошу вас не пишите готовую программу ,а только объясните сам алгоритм в кратце:
yes2.gif Это задача с онлайн:http://acm.timus.ru/problem.aspx?space=1&num=1535 yes2.gif
Преподаватель задал нашёл из интернета и вот задал такую задачу:
1 2 3 4 5 6
То
1*2+2*3+3*4+4*5+5*6
Вот таким способом вычислить максимальное и минимальное умножение как:
6 1 4 3 2 5 (38) Минимум
1 3 5 6 4 2 (80) максимум
что за алгоритм можно применить в этом случае,посоветуйте? smile.gif

Извините за правку rolleyes.gif
Michael_Rybak
Сколько чисел максимум в последовательности?
Гость
2 ≤ N ≤ 50000
Perfez
2 ≤ N ≤ 50000
Michael_Rybak
В общем такие задачки на олимпиадах надо решать так. Либо угадать закономерность, либо, что в 99% случаях приводит к положительному результату, написать перебор для маленьких чисел. Почти уверен, что ответы, например для n = 20, имеют вид 1 11 2 12 3 13 .. 10 20, 1 2 3 4 5 .. 20 или типа того.

Для маленьких N (1, 2, 5) оптимальных ответов будет много, но для N = 12 - совсем нет.

Скорее всего, есть небольшая разница для четных и нечетных N, так что запустишь для 12 и для 13.

Перебор напишешь?

P.S. после олимпиады желательно доказать правильность smile.gif
Perfez
По моему пермутация 50000 за 1 секунду...просто невозможно... blink.gif Прав ли я?
Michael_Rybak
На маленьких N ты поймешь закономерность.

Например, ты увидишь, что для N = 13 ответ, к примеру, такой:

1 3 5 7 9 11 13 12 10 8 6 4 2

И поймешь, что в центр ставится n, а дальше по бокам в порядке убывания. И напишешь программу, которая делает то же самое для любого N.
Bard
Помоему я нашел кратчайший метод вычисления максимального... cool.gif

сначала выводишь все нечетные числа в порядке возрастания,
а потом все четные числа в порядке убывания... good.gif

а насчет минимального надо подумать!!!



Добавлено через 6 мин.
А вот и кстати прога нахождения максимального(работает очень быстро)... lol.gif
Алена
Цитата
работает очень быстро
Ну, это смотря с каким значением ее запустить... Запусти с 49000, и наслаждайся... Секунд 20-25...
Bard
Цитата
6 1 4 3 2 5 (52) Минимум

уважаемый Perfez,помоему вы делаете какую та ошибку потому что в данном тесте минимум=38
6*1+1*4+4*3+3*2+2*5=6+4+12+6+10=38 mega_chok.gif

Добавлено через 2 мин.
Цитата(Алена @ 5.03.2007 23:10) *

Ну, это смотря с каким значением ее запустить... Запусти с 49000, и наслаждайся... Секунд 20-25...

не 20-25 а 7-9 секунд!!! norespect.gif
Алена
Тебе что, скриншот привести, что на FreePascal-е (!!! 32-бита !!!) это работает 18 секунд?
Perfez
Алена и arximed,что вы спорите? lol.gif Толку то какого...задача расчитана на 1 секунду,так что беспокоиться за это не стоит....безполезно по-моему... no1.gif
P.S.:
Спасибо за деталь, arximed. smile.gif
Bard
Только что проверил на Free Pascale-2.0.0. работает ровно
8 секунд(с лишним...но не как не больше 10-и секунд)...

даже прогнал 50000 и то за 10 секунд прошло... blink.gif

Добавлено через 3 мин.
что то с минусом не разберусь...
но есть одна деталь:обрати внимание при n=6 разница между числами нечетное а
при-7 мин=7153426 разница-четное...

P.S стараюсь найти для 20 и 21 blink.gif

Добавлено через 6 мин.
нашшшшшшшшеееееелллллллл....

при н=20 минимум=20 1 18 3 16 5 14 7 12 9 10 11 8 13 6 15 4 17 2 19

но есть одна проблема при н=нечетное число логика не соответствует...
тоесть:

при н=21 минимум=21 1 19 3 17 5 15 7 13 11 10 12 8 14 6 16 4 18 2 20...



Добавлено через 4 мин.
Цитата(arximed @ 5.03.2007 23:41) *

Только что проверил на Free Pascale-2.0.0. работает ровно
8 секунд(с лишним...но не как не больше 10-и секунд)...

даже прогнал 50000 и то за 10 секунд прошло... blink.gif

Добавлено через 3 мин.
что то с минусом не разберусь...
но есть одна деталь:обрати внимание при n=6 разница между числами нечетное а
при-7 мин=7153426 разница-четное...

P.S стараюсь найти для 20 и 21 blink.gif

Добавлено через 6 мин.
нашшшшшшшшеееееелллллллл....

при н=20 минимум=20 1 18 3 16 5 14 7 12 9 10 11 8 13 6 15 4 17 2 19

но есть одна проблема при н=нечетное число логика не соответствует...
тоесть:

при н=21 минимум=21 1 19 3 17 5 15 7 13 9 11 10 12 8 14 6 16 4 18 2 20...

Bard
все написал lol.gif и нахождение минимума теперь их надо собрать в одно целое и вывести единую программу yes2.gif

P.S но помоему будут проблемы со временем norespect.gif
Алена
Не знаю, не знаю... (время в миллисекундах)
Bard
Цитата(Алена @ 6.03.2007 0:21) *

Не знаю, не знаю... (время в миллисекундах)

да ладно черт со временем nea.gif самое главное чтобы прога была эффектной... yes2.gif
Michael_Rybak
Во-первых, у вас ведь компьютеры разные, как можно спорить, у кого сколько работает smile.gif

Во вторых программа работает меньше секунды. Даже меньше 0.01 секунды, я думаю.

Время уходит на вывод в консоль. Если перенаправить вывод в файл (а на тимусе, как и везде, вывод перенаправляется в файл, иначе как потом проверять), вы и моргнуть не успеете как она отработает для n = 1000000.
Perfez
Ладно с максимум всё понятно,а что с минимум? blink.gif Есть предложение? smile.gif
volvo
Цитата
Есть предложение?
На позиции P результирующей последовательности находится число N - P + 1, если P нечетно, и число P - 1, если P - четно ... (по крайней мере при четном N)
Perfez
Спасибо за умное предложение good.gif
Цитата
(по крайней мере при четном N)

А что за проблема когда N нечётно? smile.gif
Michael_Rybak
Странный ты какой-то. Напиши и посмотри.
Perfez
Michael_Rybak,это странность называется просто ленивостью....признаю и извиняюсь unsure.gif Порок smile.gif
Michael_Rybak
smile.gif Скажи честно, ты понял что я предлагаю сделать? Там ведь нефиг писать.
Perfez
Возьмём вариант когда n нечётно, а после будем продвигаться по видоизменённому алгоритму volvo, то еcть:
1-ый индекс = P нечётно, N-P+1=3-1+1=3
2-ой индекс = P чётно, то скорее всего P=2
3-ий индекс = P нечётно, N-P+1=3-3+1
Я прав?
Michael_Rybak
Задачу можно будет считать решенной полностью, когда ты не только угадаешь ответ, а и докажешь его правильность. А угадал ты или нет можно проверить на тимусе.
Perfez
Но я и задачу к тому же изначально неправильно понял: smile.gif
Цитата
С этой целью он хочет на год уехать из Ривенделля, обойти за это время N городов Средиземья, пронумерованных числами от 1 до N (Ривенделль имеет номер 1), и в конце путешествия вернуться назад.

то есть при N=4,путь таков:
1 2 3 4 1
из этого выходит что позиции первого и последнего индекса неизменяемы.Решение задачи повернулось на 90 градусов smile.gif
Будем продолжать испытания... smile.gif yes2.gif
Michael_Rybak
Перебор пишется 5, от силы 10 минут. Пишешь перебор и никаких экспериментов.
Perfez
Извини но я не знаю как делать полный перебор smile.gif ...не проходили... smile.gif и я сам особо вариантами не блещу... unsure.gif
Perfez
огромное спасибо за терпение к этой проблеме,Michael_Rybak. smile.gif good.gif
Michael_Rybak
Тебе нужно для данного набора чисел узнать, как их расставить лучше всего, т.е. какая расстановка даст максимальную/минимальную сумму попарных произведений соседних элементов.

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

Код, генерящий все перестановки данного множества чисел, берешь в ФАКе. Оценочную функцию пишешь сам. Давай, начни, рад буду помочь с проблемами.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.