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

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), что, в общем-то, достаточно дофига). Надо проверять экспериментально, в общем.

Здравствуйте, 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

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

Здравствуйте, 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>На собеседовании в .. в числе других задач задаю задачу такого типа

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

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

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

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

Здравствуйте, 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>Я был в этой конторе, кстати. Вторая задача мне показалась сложнее.

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