IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> задача на пермутацию
сообщение
Сообщение #1


Бывалый
***

Группа: Пользователи
Сообщений: 231
Пол: Женский

Репутация: -  6  +


Важно:Сразу прошу вас не пишите готовую программу ,а только объясните сам алгоритм в кратце:
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

Сообщение отредактировано: Perfez -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Сколько чисел максимум в последовательности?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






2 ≤ N ≤ 50000
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Бывалый
***

Группа: Пользователи
Сообщений: 231
Пол: Женский

Репутация: -  6  +


2 ≤ N ≤ 50000
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


В общем такие задачки на олимпиадах надо решать так. Либо угадать закономерность, либо, что в 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
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Бывалый
***

Группа: Пользователи
Сообщений: 231
Пол: Женский

Репутация: -  6  +


По моему пермутация 50000 за 1 секунду...просто невозможно... blink.gif Прав ли я?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


На маленьких N ты поймешь закономерность.

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

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

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

Сообщение отредактировано: Michael_Rybak -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Учиться, учиться еще раз учиться
***

Группа: Пользователи
Сообщений: 158
Пол: Мужской
Реальное имя: Яшар

Репутация: -  3  +


Помоему я нашел кратчайший метод вычисления максимального... cool.gif

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

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



Добавлено через 6 мин.
А вот и кстати прога нахождения максимального(работает очень быстро)... lol.gif


Прикрепленные файлы
Прикрепленный файл  permmaxsum.pas ( 228 байт ) Кол-во скачиваний: 254


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






Цитата
работает очень быстро
Ну, это смотря с каким значением ее запустить... Запусти с 49000, и наслаждайся... Секунд 20-25...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Учиться, учиться еще раз учиться
***

Группа: Пользователи
Сообщений: 158
Пол: Мужской
Реальное имя: Яшар

Репутация: -  3  +


Цитата
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


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






Тебе что, скриншот привести, что на FreePascal-е (!!! 32-бита !!!) это работает 18 секунд?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Бывалый
***

Группа: Пользователи
Сообщений: 231
Пол: Женский

Репутация: -  6  +


Алена и arximed,что вы спорите? lol.gif Толку то какого...задача расчитана на 1 секунду,так что беспокоиться за это не стоит....безполезно по-моему... no1.gif
P.S.:
Спасибо за деталь, arximed. smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Учиться, учиться еще раз учиться
***

Группа: Пользователи
Сообщений: 158
Пол: Мужской
Реальное имя: Яшар

Репутация: -  3  +


Только что проверил на 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...



--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Учиться, учиться еще раз учиться
***

Группа: Пользователи
Сообщений: 158
Пол: Мужской
Реальное имя: Яшар

Репутация: -  3  +


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

P.S но помоему будут проблемы со временем norespect.gif


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Гость






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


Эскизы прикрепленных изображений
Прикрепленное изображение
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Учиться, учиться еще раз учиться
***

Группа: Пользователи
Сообщений: 158
Пол: Мужской
Реальное имя: Яшар

Репутация: -  3  +


Цитата(Алена @ 6.03.2007 0:21) *

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

да ладно черт со временем nea.gif самое главное чтобы прога была эффектной... yes2.gif


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

Время уходит на вывод в консоль. Если перенаправить вывод в файл (а на тимусе, как и везде, вывод перенаправляется в файл, иначе как потом проверять), вы и моргнуть не успеете как она отработает для n = 1000000.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Бывалый
***

Группа: Пользователи
Сообщений: 231
Пол: Женский

Репутация: -  6  +


Ладно с максимум всё понятно,а что с минимум? blink.gif Есть предложение? smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Гость






Цитата
Есть предложение?
На позиции P результирующей последовательности находится число N - P + 1, если P нечетно, и число P - 1, если P - четно ... (по крайней мере при четном N)
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Бывалый
***

Группа: Пользователи
Сообщений: 231
Пол: Женский

Репутация: -  6  +


Спасибо за умное предложение good.gif
Цитата
(по крайней мере при четном N)

А что за проблема когда N нечётно? smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 16:09
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name