Вычислить сумму ряда с заданной точностью с помощью рекурсии, Рекурсия Опции

[dog]

Вычислить сумму ряда с заданной точностью e(epsilon)>0

Есть решение, нет уверенности, что правильно:

PROGRAM PRP6;
var e, res, a, b : REAL;

FUNCTION comp(x, y, e: REAL):real;{функция нахождения суммы}
var w, z, sum: real;
BEGIN
     w:=x;
     z:=y;
     sum:=1/(w*z);
     IF 1/(w*z) >= e
      then
      BEGIN
      sum:=comp(x, y, e);
      w:=w+4;
      z:=z+4;
      END
      else comp:=sum;

END;

BEGIN
    WRITELN('Введите точность e');
    READLN(e);
    a:=3;
    b:=5;
    res:=comp(a, b, e);
    WRITELN('Сумма ряда', res:5:2);
END.

Просьба проверить и поправить, если что неправильно

[TarasBer]

Так ты сначала у себя запусти, проверь. Ты ж не проверял.
Если 1/(w*z) >= e, то, во-первых, делается рекурсивный вызов с теми же параметрами (что приведёт к переполнению стека - рекурсии неоткуда выйти), а во-вторых, в результат ничего не записывается.
И, в третьих, с математической точки зрения то, что очередной член ряда стал меньше епсилон, ещё отнюдь не означает, что мы просуммировали ряд с достаточной точностью (я так могу гармонический ряд "просуммировать", ага). Вообще принято сначала рассчитать оценку погрешности через очередной член ряда (для каждого ряда оценка своя), а потом через эту оценку и определять, достигли мы точности, или нет.

[dog]

Она при некоторых значениях епсилон выдает всегда один и тот же ответ, а при некоторых действительно происходит переполнение стека.

А если так?

FUNCTION comp(x, y, e: REAL):real;{функция нахождения суммы}
var w, z, sum: real;
BEGIN
     w:=x;
     z:=y;
     sum:=1/(w*z);
     IF 1/(w*z) >= e
      then
      BEGIN
      sum:=comp(w, z, e);{исправлено}
      w:=w+4;
      z:=z+4;
      END
      else comp:=sum;

END;

Ну на самом деле сложная задача, ряды да еще и рекурсия.

Сообщение отредактировано: dog - 2.02.2010 23:36

[TarasBer]

Дык проверь сначала, чего меня спрашивать. От замены двух букв на равные им ничего не изменится, очевидно.

[volvo]

Ну на самом деле сложная задача, ряды да еще и рекурсия.

На самом деле рекурсия - проще, чем итерация. Если понимаешь сам принцип написания рекурсивных функций. Не веришь? Смотри:

1. Для начала определимся с тем, что наша рекурсия будет принимать, и что - возвращать... Ну, возвращать она будет Real, это очевидно. А принимать - 2 числа которые стоят в знаменателе, так? Не совсем. Зачем передавать их оба, если можно передать одно, только X, а зная X вычислять Y когда нужно?. Итак, с заголовком определились:

function f(X: integer; eps: real): real;

2. Теперь делаем то, без чего работающей рекурсивной функции не может существовать - опишем условие выхода из функции. Когда надо выходить? Правильно, если 1/(x * (x+2)) станет меньше eps... Так и запишем... Хм. А что запишем? Что должно вернуться, когда пришло время выйти из функции? Функция у нас считает сумму ряда, значит надо вернуть какое-то значение, которое эту сумму не испортит. Такое значение у нас только одно: ноль...

Вот, значит, и пишем условие выхода:

if 1/(x * (x+2)) < eps then f := 0

3. Ну хорошо, если условие выполнилось, понятно что будет. А если НЕ выполнилось - что делать? Словами описываем алгоритм: сложить значение текущего члена с суммой последующих. Так? Так... А на Паскаль перевести?

else { Не выполнилось условие }
  f := (1/(x * (x+2))) + f(x + 4, eps); { сложим текущий с последующими }

Итого - собираем все вместе:

function f(X: integer; eps: real): real;
begin
  if 1/(x * (x+2)) < eps then f := 0
  else f := (1/(x * (x+2))) + f(x + 4, eps);
end;

Вот и все... Сложно? По-моему, нет...

НО. (опять это НО, я всегда ловлю себя на мысли, что слишком часто получаются какие-то оговорки, ничего не бывает просто и без проблем). Эта функция будет работать, но до определенного предела. Где предел, и почему функция не работает дальше (в настройках компилятора выставить все Run-time проверки !!!) - вот вопрос...

Первый, кто ответит на этот вопрос, правильно объяснит причину, и приведет способ исправления моей функции - получает +1 к рейтингу ...

Сообщение отредактировано: volvo - 25.02.2010 14:31

[Unconnected]

Наверное, проблема с максимальной точностью значения, которое может принять real?)

[Client]

ошибка в этом месте

if 1/(x * (x+2)) < eps then f := 0

проиходит тогда, когда знаменатель становится 33489 и х=183 (видимо операцию, значение которой больше 32767, в рекурсии нельзя выполнить).Поэтому, делаю проверку на вхождение в дипазон типа integer.

if (sqrt(maxint)<x ) then f:=0
     else
        if 1/(x*(x+2)) < eps then f:=0
        else f:=(1/(x * (x+2))) + f(x+4,eps);

Добавлено через 14 мин.
это я так думаю

Сообщение отредактировано: Client - 3.02.2010 15:16

[volvo]

Оба предыдущих ответа не содержат правильной идеи... Во-первых, Real-а вполне себе хватает. А во-вторых,

видимо операцию, значение которой больше 32767, в рекурсии нельзя выполнить

- в рекурсии можно вычислять и гораздо бОльшие результаты. Рекурсия в этом смысле ничем от итерации не отличается.

Думаем дальше

[TarasBer]

> else f := (1/(x * (x+2))) + f(x + 4, eps);

Тут какая-то неприятность со стеком сопроцессора должна произойти.
Надо

else begin
  tmp_f := (1/(x * (x+2))) + f(x + 4, eps);
  f := tmp_f;
end;

[volvo]

Тут какая-то неприятность со стеком сопроцессора должна произойти.

Ничего не должно произойти, без разбиения все прекрасно вычисляется. Можно, конечно сделать то, что ты написал, но это не имеет решающего значения, можно обойтись и без этого.

Еще идеи есть? Client, ведь ты показал скриншот, который должен был заставить тебя задуматься кое над чем... Чего ты не задумался?

P.S. А где, собственно, топикстартер? Ей не интересно? Или ждет, когда всё решат, все ошибки исправят, а потом втихую заберет, и все, добилась своего?

[TarasBer]

Тут про переполнение типа говорили.
Я бы написал дробь как (1/x)*(1/(x+2))

[volvo]

Я бы написал дробь как

Хм... (Показать/Скрыть)

Вот от тебя (с твоей тягой к оптимизации) я это ожидал услышать меньше всего. Нам, конечно, мало одного деления, Добавим еще одно, чтоб еще дольше вычислять значение, и еще больше загрузить стек сопроцессора. Может, тогда он переполнится, и твое предположение из поста №9 окажется истинным?

[Client]

x * (x+2)

ошибка именно здесь, даже без деления. ты про 1 картинку на 1 скрине?

[TarasBer]

[offtop]
> Вот от тебя (с твоей тягой к оптимизации) я это ожидал услышать меньше всего.

Моя тяга к оптимизации упала в обморок при виде вычисления ряда через рекурсию и валяется без сознания, поэтому молчит.
[/offtop]

Проверил у себя. Вываливается именно с ~8 итераций.

А так - не вываливается:

tmp_f := f(x + 4, eps);
f := tmp_f + 1/(longint(x)*(x+2))

[dog]

P.S. А где, собственно, топикстартер? Ей не интересно? Или ждет, когда всё решат, все ошибки исправят, а потом втихую заберет, и все, добилась своего?

volvo, спасибо за простое и понятное объяснение рекурсии!

Тут тут я просто неожиданно как-то даже, что рекурсия так просто. Просто в легком шоке даже немножко от простоты рекурсии. Над "подводным камнем" думаю тоже.

[dog]

f := tmp_f + 1/(longint(x)*(x+2))

То есть как я понимаю при определенной величине происходит обыкновенное деление на ноль? Поэтому программа и вылетает? А ноль образуется в результате переполнения переменной x?

Вот замена входного параметра eps в функции f на double по моему немножко отодвинула порог вылета, но кардинально вопрос не решила. Будем думать дальше.

Сообщение отредактировано: dog - 5.02.2010 1:56

[TarasBer]

> Поэтому программа и вылетает?

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

[Client]

volvo, кажется больше идей нету... тут приведение типов как в С может и помогло бы...
хотелось бы узнать, в чем кроется секрет.

[volvo]

Приведение типов не нужно... Явное по крайней мере. Приведи неявно.

+ к этому - пока никто не показал окончательный код, который не будет вылетать при eps = 1E-8 независимо от настроек компилятора Турбо-Паскаля. То есть, независимо от того, выбран у меня режим эмуляции сопроцессора или режим 8087/80287... Окончательную версию в студию можно? А то выцеживаете по одной строке... Я что, одну строку привел?

[Krjuger]

Я думаю,что для начала надо разобраться почему вылетело RT215(Arithmetic overflow),а не RT205(Floating point overflow).
Arithmetic overflow - целочисленное переполнение - возникает при выполнении арифметической операции над целыми числами, когда результат операции выходит за границы соответствующего типа.

Как говорил Client, при 33к с копейками в знаменателе уже происходит вылет, при этом есть тип Short, который может содержать целые числа о -32,768 до 32,767.Принципи вот из-за этого и происходит переполнение,но для мен лично небольшая загадка почему именно тип short береться для выполнения операций,а не сам integer.

Это лиш мои догадки,скорее всего я не прав.