Цитата(maxim1000 @ 10.11.2006, 00:00  ) |
| т.е. если f(x1,10), а f(x2,9), то можно быть уверенным, что x2>x1 |
В смысле если f(x1,y1) = f(x2,y2) и x1 > x2, то y1 < y2 ?
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Найти аргументы функции по значению |
| Автор: distorti 8.11.2006, 23:57 |
| Дана строго возрастайущая функция f ( N * N) = N (N - множество натуральных чисел + 0) и какое-нибудь ее значение z при неизвестных аргументах. Проблема: найти все такие пары аргументов х и у, при которых f (x,y) = z Например: f (+) 2 ==> [(0 , 2), (1 , 1), (2 , 0)] |
| Автор: maxim1000 9.11.2006, 00:27 |
| например так: для начала найти такое a, что f(0,x)>z (лучше взять минимальное, чтобы облегчить себе работу) и для каждого x<a найти соответствующий y (если есть): f(x,y)=z искать можно методом бисекции выглядит не очень эффективно, но чего-то лучше в голову не пришло... |
| Автор: poor_yorik 9.11.2006, 13:39 |
| Вопрос автору, монотонность можно понимать так, Если a1>a2 b1>b2, то f(a1,b1)>f(a2,b2)? В таком случае можно подмодифицировать двоичній поиск, и делать его отдельно по первой аргументе, отдельно по второй. |
| Автор: maxim1000 9.11.2006, 13:46 |
| кстати, в том способе, который я предполагал, монотонность понимается так: f(x+1,y)>f(x,y) f(x,y+1)>f(x,y) |
| Автор: distorti 9.11.2006, 20:46 |
| Верно, монотонность понимается так: f(x+1,y)>f(x,y) f(x,y+1)>f(x,y) |
| Автор: Akina 9.11.2006, 21:58 | ||
| Во-первых, можно со всей определенностью утверждать, что f(x,y) >= x+y Это облегчает дело... Т.е. имея заданное z, мы заведомо знаем максимально возможное x при любом предположении значения y. С учетом этих утверждений предложение maxim1000 мне представляется вполне разумным. Итого:
Где solve(z - y) - поиск такого x, что f(x,y)=z, причем x ищется в диапазоне 0 .. z - y |
| Автор: maxim1000 9.11.2006, 23:00 |
| кстати, можно ещё по использовать такой факт, что при увеличении y необходимый x уменьшается т.е. если f(x1,10), а f(x2,9), то можно быть уверенным, что x2>x1 |
| Автор: Akina 9.11.2006, 23:38 | ||
В смысле если f(x1,y1) = f(x2,y2) и x1 > x2, то y1 < y2 ? |
| Автор: maxim1000 10.11.2006, 00:10 | ||
да... f(x1,y1)>f(x2,y1) f(x2,y2)>f(x2,y1) y2>y1 (иначе было бы наоборот) |
| Автор: distorti 10.11.2006, 02:02 |
| Спасибо! Ключевой момент: f(x,y) >= x+y. Только от куда ето следует? не могу понять... |
| Автор: maxim1000 10.11.2006, 12:10 | ||
на самом деле f(x,y)-f(0,0) >= x+y сначала доказывается для y=0: последовательно увеличиваем первый аргумент от 0 до x с шагом 1, при этом функция растёт, как минимум, на 1 потом так же увеличиваем второй аргумент от 0 до y... |
| Автор: Akina 10.11.2006, 13:43 | ||
а с учетом что f(0,0) >= 0 ... |
| Автор: maxim1000 10.11.2006, 13:49 | ||
да... забыл впрочем, так или иначе, верхняя граница получилась лучше - вместо f(x,y) f(x,y)-f(0,0)  Добавлено @ 13:50 (ну или, по крайней мере, не хуже) |
| Автор: distorti 10.11.2006, 19:09 | ||
| Спасибо за помощь! Разобрался.. Вытоге получилось вот что :
|
| Автор: distorti 23.11.2006, 08:53 | ||
хм.... препод не хочет принимать  Вцелом мой алгоритм выглядит так:
Проблема в том, что если данная функция растет очень быстро (fun (x,y) = x^100+y^100), то невозможно подсчитать значение от верхнего предела в бинарном поиске: f(x,y), где y = z-x-fun(0,0). Нужна более точная оценка для максимального у, чем y = z-x-fun(0,0). При етом надо сохранить логорифмическую сложность алгоритма при поиске у. Есть идеи? |
| Автор: Akina 23.11.2006, 10:26 |
| Для поиска следующей оценки на быстрорастущей функции попробуй метод касательных |