ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачка на минимизацию
13 сообщений из 38, страница 2 из 2
  2  все
Задачка на минимизацию
    #36252635
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
junior idiot,

ноги растут отсюда: http://www.spoj.pl/problems/BRI/
Я сделал поиск минимума половинным делением, но это тормоз: 7с на 100000 тестов.
...
Рейтинг: 0 / 0
15.10.2009, 11:49:23
| Ответить | Цитировать | Написать  
Задачка на минимизацию
    #36252912
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
Золотое сечение вполне себе прокатило.
А методом половинного деления минимум через производную искал, что ли? Как-то это лишний гемор имхо.
...
Рейтинг: 0 / 0
15.10.2009, 13:02:34
| Ответить | Цитировать | Написать  
Задачка на минимизацию
    #36252919
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
junior idiot,

поясни немного про золотое сечение -- я не понимаю о чем речь
(я действительно делал через производную)
...
Рейтинг: 0 / 0
15.10.2009, 13:05:18
| Ответить | Цитировать | Написать  
Задачка на минимизацию
    #36252926
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
В википедии хорошо написано . Для минимизации унимодальных функций (имеющих только один экстремум на известном интервале) -- самое то.
...
Рейтинг: 0 / 0
15.10.2009, 13:08:02
| Ответить | Цитировать | Написать  
Задачка на минимизацию
    #36252960
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
попробую повторить твою успешную сдачу
...
Рейтинг: 0 / 0
15.10.2009, 13:19:08
| Ответить | Цитировать | Написать  
Задачка на минимизацию
    #36253379
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
junior idiot,
глянь мои ответы, а то у меня одни WAs:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
 33 
 11   22   33   44   55   66 
 5147 . 37 
 77   13   58   22   88   99 
 11344 . 83 
 77   13   58   22   88   9 
 8670 . 07 
 77   66   58   22   88   22 
 13669 . 19 
 77   66   58   22   88   2 
 12712 . 02 
 77   66   58   22   8   2 
 1242 . 65
...
Рейтинг: 0 / 0
15.10.2009, 15:01:49
| Ответить | Цитировать | Написать  
Задачка на минимизацию
    #36253413
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
у меня получается так:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
 11   22   33   44   55   66 
 5130 . 288111 
 77   13   58   22   88   99 
 11368 . 418691 
 77   13   58   22   88   9 
 8442 . 761007 
 77   66   58   22   88   22 
 13640 . 973221 
 77   66   58   22   88   2 
 12705 . 242451 
 77   66   58   22   8   2 
 1240 . 088475
Похоже, просто точность тебе надо побольше поставить.
...
Рейтинг: 0 / 0
15.10.2009, 15:13:54
| Ответить | Цитировать | Написать  
Задачка на минимизацию
    #36253435
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
спасибо..... Буду проверять
...
Рейтинг: 0 / 0
15.10.2009, 15:24:33
| Ответить | Цитировать | Написать  
Задачка на минимизацию
    #36253457
Mozok
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Mozok
Участник
RT183.1,

Блин, я кажется чего-то не понимаю. "Золотое сечение", половинное деление... А как насчет геометрии :)?
Полная длина пути: d = s1^2 * (c - x)^2 + s1^2 * a^2 + s2^2 * x^2 + s2^2 * b^2. Что мы имеем? Уравнение параболы. В зависимости от соотношения s1 и s2 ветки будут направлены вверхи или вниз. В любом случае у параболы только одна вершина :). Формулу для её координат помните? Тынц для тех, кто в школе не учился. Граничные всякие случаи типа s1 = s1 проверить уже не сложно.
...
Рейтинг: 0 / 0
15.10.2009, 15:32:37
| Ответить | Цитировать | Написать  
Задачка на минимизацию
    #36253467
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
MozokБлин, я кажется чего-то не понимаю.
Угу. Точка минимума F1(x) = f(x) + g(x) не обязательно совпадает с точкой минимума F2(x) = f(x)^2 + g(f)^2.[/quot]
...
Рейтинг: 0 / 0
15.10.2009, 15:37:18
| Ответить | Цитировать | Написать  
Задачка на минимизацию
    #36254546
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
RT183.1попробую повторить твою успешную сдачу
/* I woke up fucked up off the liquor I drunk... */

Сдал: 2.08с
...
Рейтинг: 0 / 0
16.10.2009, 03:22:41
| Ответить | Цитировать | Написать  
Задачка на минимизацию
    #36273501
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
Заодно сделал и Bridges! More bridges!
Но уже без "золотых сечений", а простым половинным поиском, но не по целевой функции.
...
Рейтинг: 0 / 0
26.10.2009, 21:14:56
| Ответить | Цитировать | Написать  
Задачка на минимизацию
    #36273537
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.1
Участник
junior idiot,
может, если захочешь сделать, вот парочка тест кейсов с моими ответами:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
 3               -- три реки
 22   11   49   15 
 37   11   28 
 1999 
 44   33   11   25 
-- 27901.58

 3               -- три реки
 49   49   18   39 
 22   43   11 
 1555 
 13   31   7   29 
-- 13561.36
...
Рейтинг: 0 / 0
26.10.2009, 21:36:12
| Ответить | Цитировать | Написать  
13 сообщений из 38, страница 2 из 2
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачка на минимизацию
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=36253379&tid=1344146]:
 0ms
get settings:
 4ms
get forum list:
 8ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 186ms
get topic data:
 5ms
get forum data:
 1ms
get page messages:
 27ms
get tp. blocked users:
 1ms
others: 179ms
total:  415ms
созд. / загр.: 415ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]