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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мы оба ошиблись: на самом деле это будет x+y (может быть еще минус 1) Это действительно не так много, как x*y, так что быстро нарастающая функция таки да быстрее приведет к проблеме.

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


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-го курса такую задачу сделает на раз. Предмет "высшая математика".
И ответ должен быть в виде функции -- при вышеописанных данных

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

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

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

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


немного подумал, вот тебе задача имеющая смысл

Между атомами вселенной существует гравитационное взаимодействие. Число атомов в видимой вселенной примерно 10^85. Нужно посчитать сколько существует связей вызванных гравитационным взаимодействием между всеми возможными парами атомов видимой вселенной?

Считаем:

C = N! / ( 2! * (N-2)! ), где N число атомов во вселенной ( 10^85 )

Хватит ли тебе double для того чтобы вычислить факториал от 10^85?

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

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>Вопрос: какое верное решение?
Берешь таблицу и давай ее заполнять ЗИГЗАГОМ (это дает приемущество!) до нужной клетки (то есть пока CPU не охренеет )

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

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 растёт с дикой скоростью.

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

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

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

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

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

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

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

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

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

Здравствуйте, 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"
по крайней мере это повод уточнить задачу

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

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

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

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

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

Здравствуйте, 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, Вы писали:

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

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

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

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

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

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

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

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

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

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

Похоже ты школьную физику забыл — размеры вселенной это совсем другой порядок. Возраст Вселенной O(10^10) * скорость света O (10^10) см\сек будет порядка 10^20 что никак не даст тебе 10^300 даже если накинуть порядок за перевод в миллиметры

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

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

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

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

EM>Похоже ты школьную физику забыл — размеры вселенной это совсем другой порядок. Возраст Вселенной O(10^10) * скорость света O (10^10) см\сек будет порядка 10^20 что никак не даст тебе 10^300 даже если накинуть порядок за перевод в миллиметры

тогда так, сколько потребуется бензина чтобы проехать через одну точку вселенной 10^100 раз на автомобиле, при условии что автомобиль движется по прямой, скорость 100 км/час, расход 10 л/с?

_M_> 10 л/с?

10 литров на 100 км

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

объем бензина нужно посчитать с точностью +- 1 атом

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

_M_>объем бензина нужно посчитать с точностью +- 1 атом

с учетом того что горизонт вселенной со временем увеличивается

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

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

_M_>объем бензина нужно посчитать с точностью +- 1 атом


Фигня вопрос — количество бензина в баке не может превышать число атомов во Вселенной — 10^80
Дабла по прежнему хватает

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

_M_>>объем бензина нужно посчитать с точностью +- 1 атом


EM>Фигня вопрос — количество бензина в баке не может превышать число атомов во Вселенной — 10^80
EM>Дабла по прежнему хватает

а никто не говорил что весь бензин сразу заправили, по ходу движения к автомобилю будет подлетать звездолет-заправщик и на ходу подзаправлять

_M_>а никто не говорил что весь бензин сразу заправили, по ходу движения к автомобилю будет подлетать звездолет-заправщик и на ходу подзаправлять

сколько всего бензина понадобится?

Возьмем серьезную задачу.

Человечество придумало супер двигатель, который сам синтезирует топливо из вакуума, например путем воздействия на кварковые взаимодействия . Вопрос — какое расстояние пролетит ракета с таким двигателем за 10^1000 лет, если начальной точкой отсчета считать скорость 0.9 C, при которой ракета стабилизирует свою скорость. Достигнет ли ракета горизонта вселенной?

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

_M_>>а никто не говорил что весь бензин сразу заправили, по ходу движения к автомобилю будет подлетать звездолет-заправщик и на ходу подзаправлять

_M_>сколько всего бензина понадобится?


Меньше все равно — сложи все показатели степеней — 300 там не наберется. К тому же столько и не нальют — материи всего 10 в 80 вместе снаружи бака и внутри. Это только в Кремле думают что нефть никогда не закончится ...

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

_M_>Возьмем серьезную задачу.

_M_>Достигнет ли ракета горизонта вселенной?

Ну это самый простой вопрос — посмотри на надувающийся воздушный шарик и прикинь, доедешь ли ты до стенки, нарезая круги по его поверхности ? Я — и пробовать не буду

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

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

Спросить собеседующих, в каких жизненных передрягах такая задача может встретиться.
Пусть доказывают, что это реальная проблема, а не надуманная
А раз переполнение, я б заюзал java.math.BigDecimal