 |
|
|
 
|
|
Найти аргументы функции по значению 
| distorti |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 15 Регистрация: 25.7.2005 Репутация: нет Всего: нет |
Дана строго возрастайущая функция f ( N * N) = N (N - множество натуральных чисел + 0) и какое-нибудь ее значение z при неизвестных аргументах.
Проблема: найти все такие пары аргументов х и у, при которых f (x,y) = z Например: f (+) 2 ==> [(0 , 2), (1 , 1), (2 , 0)] |
|||
|
||||
Загрузка ...
| maxim1000 |
|
|||
 Эксперт  Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 33 Всего: 110 |
например так:
для начала найти такое a, что f(0,x)>z (лучше взять минимальное, чтобы облегчить себе работу) и для каждого x<a найти соответствующий y (если есть): f(x,y)=z искать можно методом бисекции выглядит не очень эффективно, но чего-то лучше в голову не пришло... -------------------- qqq |
|||
|
||||
| poor_yorik |
|
|||
 Шустрый Профиль Группа: Участник Сообщений: 148 Регистрация: 12.1.2005 Где: Общаги г. Киева Репутация: 3 Всего: 8 |
Вопрос автору, монотонность можно понимать так,
Если a1>a2 b1>b2, то f(a1,b1)>f(a2,b2)? В таком случае можно подмодифицировать двоичній поиск, и делать его отдельно по первой аргументе, отдельно по второй. --------------------
Семь раз отмерь, один раз - откомпиль.... Семь раз отпей, один раз - отлей... Семь раз отъешь, один раз - не жадничай и другим дай... |
|||
|
||||
| maxim1000 |
|
|||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 33 Всего: 110 |
кстати, в том способе, который я предполагал, монотонность понимается так:
f(x+1,y)>f(x,y) f(x,y+1)>f(x,y) -------------------- qqq |
|||
|
||||
| distorti |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 15 Регистрация: 25.7.2005 Репутация: нет Всего: нет |
Верно, монотонность понимается так:
f(x+1,y)>f(x,y) f(x,y+1)>f(x,y) |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20580 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
Во-первых, можно со всей определенностью утверждать, что
f(x,y) >= x+y Это облегчает дело... Т.е. имея заданное z, мы заведомо знаем максимально возможное x при любом предположении значения y. С учетом этих утверждений предложение maxim1000 мне представляется вполне разумным. Итого:
Где solve(z - y) - поиск такого x, что f(x,y)=z, причем x ищется в диапазоне 0 .. z - y -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| maxim1000 |
|
|||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 33 Всего: 110 |
кстати, можно ещё по использовать такой факт, что при увеличении y необходимый x уменьшается
т.е. если f(x1,10), а f(x2,9), то можно быть уверенным, что x2>x1 -------------------- qqq |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20580 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
В смысле если f(x1,y1) = f(x2,y2) и x1 > x2, то y1 < y2 ? -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| maxim1000 |
|
|||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 33 Всего: 110 |
да... f(x1,y1)>f(x2,y1) f(x2,y2)>f(x2,y1) y2>y1 (иначе было бы наоборот) -------------------- qqq |
|||
|
||||
| distorti |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 15 Регистрация: 25.7.2005 Репутация: нет Всего: нет |
Спасибо!
Ключевой момент: f(x,y) >= x+y. Только от куда ето следует? не могу понять... |
|||
|
||||
| maxim1000 |
|
|||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 33 Всего: 110 |
на самом деле f(x,y)-f(0,0) >= x+y сначала доказывается для y=0: последовательно увеличиваем первый аргумент от 0 до x с шагом 1, при этом функция растёт, как минимум, на 1 потом так же увеличиваем второй аргумент от 0 до y... -------------------- qqq |
|||
|
||||
| Akina |
|
|||
|
Советчик Профиль Группа: Модератор Сообщений: 20580 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
а с учетом что f(0,0) >= 0 ... -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
| maxim1000 |
|
|||
|
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 33 Всего: 110 |
да... забыл впрочем, так или иначе, верхняя граница получилась лучше - вместо f(x,y) f(x,y)-f(0,0)  Добавлено @ 13:50 (ну или, по крайней мере, не хуже) -------------------- qqq |
|||
|
||||
| distorti |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 15 Регистрация: 25.7.2005 Репутация: нет Всего: нет |
Спасибо за помощь! Разобрался..
Вытоге получилось вот что :
Это сообщение отредактировал(а) distorti - 10.11.2006, 19:10 |
|||
|
||||
| distorti |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 15 Регистрация: 25.7.2005 Репутация: нет Всего: нет |
хм.... препод не хочет принимать
 Вцелом мой алгоритм выглядит так:
Проблема в том, что если данная функция растет очень быстро (fun (x,y) = x^100+y^100), то невозможно подсчитать значение от верхнего предела в бинарном поиске: f(x,y), где y = z-x-fun(0,0). Нужна более точная оценка для максимального у, чем y = z-x-fun(0,0). При етом надо сохранить логорифмическую сложность алгоритма при поиске у. Есть идеи? |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.1170 ] [ Использовано запросов: 20 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |