Задача на собеседовании - О работе

На собеседовании в .. в числе других задач задаю задачу такого типа

F(x, 0) = x^2
F(0, y) = y^5 — y
F(x,y) = (F(x-1,y))^4 — (F(x,y-1))^3

Найти F

float test(const float&x, const float& y)
{
    if (x == 0)
    {
        return pow(y, 5) - y;
    }
    else if (y == 0)
    {
        return pow(x, 2);
    }
    return pow(test(x - 1, y), 4) - pow(test(x, y-1), 3);
}

Данное решение при сколько нибудь больших x и y не работает.

Вопрос: какое верное решение?

Здравствуйте, navy, Вы писали:

N>Вопрос: какое верное решение?

То же самое, но с использованием массива для хранения уже вычисленных значений — таким образом для каждой пары (x, y) значение будет вычислено не более одного раза. Динамическое программирование, панимаишь...

Здравствуйте, Oyster, Вы писали:

O>То же самое, но с использованием массива для хранения уже вычисленных значений — таким образом для каждой пары (x, y) значение будет вычислено не более одного раза. Динамическое программирование, панимаишь...

Только одно "но" — я предполагал, что x и y — целые. Судя по условию, так оно и есть, иначе вычисление не закончится никогда (если x или y изначально имеет дробную часть, то условие x == 0 или y == 0 никогда не выполнится).

Здравствуйте, navy, Вы писали:

N>На собеседовании в .. в числе других задач задаю задачу такого типа
...
N>Вопрос: какое верное решение?

т.е. ты задаешь задачу не зная решения?

кстати условие противоречиво...

Здравствуйте, Oyster, Вы писали:

O>Здравствуйте, Oyster, Вы писали:

O>>То же самое, но с использованием массива для хранения уже вычисленных значений — таким образом для каждой пары (x, y) значение будет вычислено не более одного раза. Динамическое программирование, панимаишь...

O>Только одно "но" — я предполагал, что x и y — целые. Судя по условию, так оно и есть, иначе вычисление не закончится никогда (если x или y изначально имеет дробную часть, то условие x == 0 или y == 0 никогда не выполнится).

Там еще проблема в том, что значение F растёт с дикой скоростью.

Здравствуйте, Oyster, Вы писали:

O>Здравствуйте, Oyster, Вы писали:

O>>То же самое, но с использованием массива для хранения уже вычисленных значений — таким образом для каждой пары (x, y) значение будет вычислено не более одного раза. Динамическое программирование, панимаишь...

O>Только одно "но" — я предполагал, что x и y — целые. Судя по условию, так оно и есть, иначе вычисление не закончится никогда (если x или y изначально имеет дробную часть, то условие x == 0 или y == 0 никогда не выполнится).

Ну так вещественные числа с нулем сравнивать вообще неблагодарное дело. проверка типа if (fabs(x) < 1.0e-10) даст возможно более приемлемый результат

Здравствуйте, Sap78, Вы писали:

S>Там еще проблема в том, что значение F растёт с дикой скоростью.

Да, действительно. Но если там уже в double не влезает (который "ranging from negative 1.79769313486232e308 to positive 1.79769313486232e308"), то я сдаюсь

Разве что свой double написать...

Здравствуйте, Oyster, Вы писали:

O>Да, действительно. Но если там уже в double не влезает (который "ranging from negative 1.79769313486232e308 to positive 1.79769313486232e308"), то я сдаюсь

Разве что свой double написать...
Копать, имхо, надо в направлении
(F(x-1,y))^4 — (F(x,y-1))^3

т.е. аргументы до вычитания слишком большие, после него вписываются в диапазон. я математику забыл лет 10 назад, так что хз, но возможно можно как-то сократить функцию.

Здравствуйте, olegkr, Вы писали:

O>Копать, имхо, надо в направлении
O>(F(x-1,y))^4 — (F(x,y-1))^3

O>т.е. аргументы до вычитания слишком большие, после него вписываются в диапазон. я математику забыл лет 10 назад, так что хз, но возможно можно как-то сократить функцию.

Ну если оно там всё хорошо вписывается в ограничение double после сокращения, то, я думаю, можно просто тупо использовать double (потому что тогда любое значение F() вписывается в double, в том числе F(x-1,y) и F(x,y-1), и проблемы будут только в том случае, если очередное значение F() достигнет степени (308/3) или (308/4), что, в общем-то, достаточно дофига). Надо проверять экспериментально, в общем.

Здравствуйте, LaptevVV, Вы писали:

LVV>А F(0,0) — как вычисляется?

Или как F(0, 0) = F(x, 0) = x^2 = 0, или как F(0, 0) = F(0, y) = 0^5 — 0 = 0

N>Вопрос: какое верное решение?

Во первых, использовать float немного некорректно. Вы никогда не найдете решение для F(1.02, 1.02). И отрицательныными эти числа тоже быть не могут.
Во вторых, посмотрев внимательно, можно заметить, что F(x,y) можно посчитав только вычислив до этого F(x-1,y) и F(x,y-1). Если представить это в виде сетки с ячейками, в которой какждая ячейка имеет координату x и y, то все что нам нужно это заполнить матрицу размером x на y. Значения на осях (х=0 и y=0) можно посчитать легко, а остальные значения базируются на них.

Вот пример:
Нам надо посчитать F(5, 2)

Получем таблицу
16 .. .. .. .. (?)

0 -1 .. .. .. ..

0 1 4 9 16 25

Символ (?) — это то что нам надо найти. Точками отмечены значения которые мне лень считать

Реализация — через матрицу.

Как уже отмечали выше — проблема тока в возможности переполнения.. Оно наступит довольно быстро. Например, F(1,2) = 56 698 339 857 713
Как вариант — операции возведения в степень реализовать самому. Результат хранить не в элементарном типе (int или double) а в массиве цифр.
Дальше — дело техники.

Здравствуйте, olegkr, Вы писали:

O>т.е. аргументы до вычитания слишком большие, после него вписываются в диапазон. я математику забыл лет 10 назад, так что хз, но возможно можно как-то сократить функцию.

Сколько ни пытайся что-нибудь сократить, а все равно разность между числами разных порядков (а в функции степени, соответствено, 4 и 3) даст в результате число высшего из этих двух порядков. Попробуйте для примера из 10e310 вычесть 10е309 — получите 9е310... т.е. порядок никак не сократился.

В данном случае, кроме быстро возрастающей функции, есть еще одна проблема: рекурсия. Пока вычисление доберется до уровня F(x,0) и F(0,y), потребуется (с ходу могу ошибиться немножко): (x-1)*(y-1) уровней вложенности. Возможно, именно это приведет к раннему "обвалу" функции, а не порядок результата. Хотя зависит от размера стека.

N>На собеседовании в .. в числе других задач задаю задачу такого типа

мама мия ... надеюсь у вас какой то наукоемкий расчетный софт ... Типа там движение звезд

Здравствуйте, Quintanar, Вы писали:

Q>Надо использовать не массив пар, а одну строку.

А можно подробнее? Я не понял идею...

Здравствуйте, Александр Каширин, Вы писали:

АК>В данном случае, кроме быстро возрастающей функции, есть еще одна проблема: рекурсия. Пока вычисление доберется до уровня F(x,0) и F(0,y), потребуется (с ходу могу ошибиться немножко): (x-1)*(y-1) уровней вложенности. Возможно, именно это приведет к раннему "обвалу" функции, а не порядок результата. Хотя зависит от размера стека.

Ошибся. Максимальный уровень вложенности будет max(x, y).

Вообще-то это функциональное уравнение.
Решать надо видимо аналитически, а не тупо набив функцию на С.

А на какую позицию ты собеседуешься и куда, если не секрет?
Если на программера, то странно давать такие задачки...

Здравствуйте, Oyster, Вы писали:

O>Здравствуйте, Quintanar, Вы писали:

Q>>Надо использовать не массив пар, а одну строку.

O>А можно подробнее? Я не понял идею...

Функции для рекурсии нужны только предыдущие элементы. Если строка N (по y например) у нас есть, то N+1 вычисляется по N легко и просто.

Я был в этой конторе, кстати. Вторая задача мне показалась сложнее.

Здравствуйте, Quintanar, Вы писали:

Q>Здравствуйте, Oyster, Вы писали:

O>>Здравствуйте, Quintanar, Вы писали:

Q>>>Надо использовать не массив пар, а одну строку.

O>>А можно подробнее? Я не понял идею...

Q>Функции для рекурсии нужны только предыдущие элементы. Если строка N (по y например) у нас есть, то N+1 вычисляется по N легко и просто.

Q>Я был в этой конторе, кстати. Вторая задача мне показалась сложнее.

Вторая задача сложнее, но более стандартная, там я знал в какую сторону копать

Здравствуйте, VsevolodC, Вы писали:

VC>Здравствуйте, navy, Вы писали:

N>>На собеседовании в .. в числе других задач задаю задачу такого типа
VC>...
N>>Вопрос: какое верное решение?

VC>т.е. ты задаешь задачу не зная решения?

VC>кстати условие противоречиво.

ОписАлся
Задали МНЕ

B>Вообще-то это функциональное уравнение.
B>Решать надо видимо аналитически, а не тупо набив функцию на С.
B>А на какую позицию ты собеседуешься и куда, если не секрет?

Напоминает по стилю ABBYY.

Здравствуйте, navy, Вы писали:

N>Здравствуйте, VsevolodC, Вы писали:

VC>>Здравствуйте, navy, Вы писали:

N>>>На собеседовании в .. в числе других задач задаю задачу такого типа
VC>>...
N>>>Вопрос: какое верное решение?

VC>>т.е. ты задаешь задачу не зная решения?

VC>>кстати условие противоречиво.

N>ОписАлся
N>Задали МНЕ

а "найти F" ?
я считаю, что это совсем не то же самое, что
"написать функцию вычисления F"
по крайней мере это повод уточнить задачу

Здравствуйте, Oyster, Вы писали:

O>Здравствуйте, Александр Каширин, Вы писали:

АК>>В данном случае, кроме быстро возрастающей функции, есть еще одна проблема: рекурсия. Пока вычисление доберется до уровня F(x,0) и F(0,y), потребуется (с ходу могу ошибиться немножко): (x-1)*(y-1) уровней вложенности. Возможно, именно это приведет к раннему "обвалу" функции, а не порядок результата. Хотя зависит от размера стека.

O>Ошибся. Максимальный уровень вложенности будет max(x, y).

Мы оба ошиблись: на самом деле это будет x+y (может быть еще минус 1)

Это действительно не так много, как x*y, так что быстро нарастающая функция таки да быстрее приведет к проблеме.

Здравствуйте, navy, Вы писали:

N>На собеседовании в .. в числе других задач задаю задачу такого типа

N>F(x, 0) = x^2
N>F(0, y) = y^5 — y
N>F(x,y) = (F(x-1,y))^4 — (F(x,y-1))^3

N>Найти F

N>Вопрос: какое верное решение?

В приведённых вами условиях — никакого. Вот смотрите:

F(0, 0) = (F(-1,0))^4 — (F(0,-1))^3 = (-1)^4 — (-2)^3 = 9

Одновременно F(0, 0) = 0^2 = 0

Мы пришли к противоречию, следовательно решений нет.

N>float test(const float&x, const float& y)
N>{
N>    if (x == 0)
N>    {
N>        return pow(y, 5) - y;
N>    }
N>    else if (y == 0)
N>    {
N>        return pow(x, 2);
N>    }
N>    return pow(test(x - 1, y), 4) - pow(test(x, y-1), 3);
N>}
N>

N>Данное решение при сколько нибудь больших x и y не работает.

N>Вопрос: какое верное решение?

Не вникая в суть, на вскидку:
двигатся не от А(x) — > A(x-1) -> ... A (0), а
в обратном направлении F(0,0) -> F(1,1) -> ... F(X,Y)

_авось_ (F(x-1,y))^4 — (F(x,y-1))^3 будет малым лислом

Задача некорректна

из этих втёх формул вывел что 0 = -1

пешите исчо

Здравствуйте, navy, Вы писали:

N>Вопрос: какое верное решение?

Здравствуйте, bkat, Вы писали:

B>Вообще-то это функциональное уравнение.
B>Решать надо видимо аналитически, а не тупо набив функцию на С.

Вообще-то у функционального уравнения ответом должна быть функция, а не число.

Здравствуйте, Tilir, Вы писали:

T>В приведённых вами условиях — никакого. Вот смотрите:
T>F(0, 0) = (F(-1,0))^4 — (F(0,-1))^3 = (-1)^4 — (-2)^3 = 9
T>Одновременно F(0, 0) = 0^2 = 0
T>Мы пришли к противоречию, следовательно решений нет.

Ты никогда не видел в математике запись
y(x)=0 при x<0
y(x)=x при x=>0
(тут еще должна быть большая фигурная скобка — не знаю как ее в форуме нарисовать)

Так вот функция это отображения аргументов(в данный момент пары точек) на результат, по определенным правилам.
На первом шаге вычисления ты правилами пренебрег посчитав все это не определением функции, а системой уравнений.
Сам себе злобный буратино

Здравствуйте, Anatolix, Вы писали:

A>Здравствуйте, bkat, Вы писали:

B>>Вообще-то это функциональное уравнение.
B>>Решать надо видимо аналитически, а не тупо набив функцию на С.

A>Вообще-то у функционального уравнения ответом должна быть функция, а не число.

Тфу — попутал с слово функциональное с дифференциальным. Но вообщем смысл такой, что это не уравнение нифига.

Фрагмент кода прилагался или это потуги на реализацию?

N>

N>float test(const float&x, const float& y)
N>{
N>    if (x == 0)
N>    {
N>        return pow(y, 5) - y;
N>    }
N>    else if (y == 0)
N>    {
N>        return pow(x, 2);
N>    }
N>    return pow(test(x - 1, y), 4) - pow(test(x, y-1), 3);
N>}
N>

Студент технического ВУЗа 2-го курса такую задачу сделает на раз. Предмет "высшая математика".
И ответ должен быть в виде функции -- при вышеописанных данных

ЗЫ. Или я чё-т не панимаю

Здравствуйте, navy, Вы писали:

Пусть x,y принимают только целые значения
Допустим x>=y , тогда есть такие m и n что y=m x=m+n

Если расписать F(x,y)

F(x,y)
+F(x-1,y)^4 -F(x,y-1)^3
+(+F(x-2,y)^4 -F(x-1,y-1)^3)^4 -(+F(x-1,y-1)^4 -F(x,y-2)^3)^3
...
дойдем до разложения когда
+(...(+F(x-n,y)^4 ...)...)^4 — -(...(... -F(x,0)^3)...)^3
при таком раскладе если все перемножить а потом сократить + и — (полностью не проверял

но похоже что так
получим всего 2 слагаемых
+(F(x-n,y))^(4*n) — (F(x,0))^(3*n)
после подстановки x и y выраженных через n и m получим
+(F(m,m))^(4*n) — (F(m+n,0)^(3*n)
первое слагаемое можно разложить дальше
((F(0,m)^(4*m) — (F(m,0))^(3*m))^(4*n) — (F(m+n,0)^(3*n)
это выражение уже легко вычислить как выражение от F(x,0) и F(0,y)
вроде развернул рекурсию (если нигде не наврал

Здравствуйте, Oyster, Вы писали:

O>Ну если оно там всё хорошо вписывается в ограничение double после сокращения, то, я думаю, можно просто тупо использовать double (потому что тогда любое значение F() вписывается в double, в том числе F(x-1,y) и F(x,y-1), и проблемы будут только в том случае, если очередное значение F() достигнет степени (308/3) или (308/4), что, в общем-то, достаточно дофига).

Ага. Больше числа атомов во Вселенной. Так что на любой имеющей смысл задаче переполнение Double — бред.

Здравствуйте, navy, Вы писали:

Олимпиадное прошлое говорит что-то о динамическом программировании.

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, EM, Вы писали:

O>>Ну если оно там всё хорошо вписывается в ограничение double после сокращения, то, я думаю, можно просто тупо использовать double (потому что тогда любое значение F() вписывается в double, в том числе F(x-1,y) и F(x,y-1), и проблемы будут только в том случае, если очередное значение F() достигнет степени (308/3) или (308/4), что, в общем-то, достаточно дофига).

EM>Ага. Больше числа атомов во Вселенной. Так что на любой имеющей смысл задаче переполнение Double — бред.

не скажи, вдруг нужно расчитывать размеры вселенной с точностью до миллиметров