3

alt text

Помогите пожалуйста написать на си. Вроде не сложно, но с математикой не идут задачи у меня.

9
  • 2
    я могу ошибаться, но возможно эта задача решается гнездованием. (Рекуррентная формула) 28 мая 2013 в 11:23
  • 1
    Вы случайно не в школе учитесь? Или вы гуманитарий? Иначе бы знали про предел последовательности и про сходимость этой последовательности. Критерий сходимости Коши По нему: 1 + 1/2 + 1/4 + 1/8 + ... + 1/(2*n) + .... сходится, т.к. |1 / (2*n) - 1 / (2*n + 2)| = |2 / ((2*n + 2) * 2*n)| -> 0. Предел данной "суммы членов бесконечного ряда" вроде как равен 2, хотя точно не уверен, лень считать. И еще простой пример, который разобьет вашу логику: 1 + (-1) + 1 + (-1) + .... = 0
    – BOPOH
    5 июн 2013 в 6:19
  • 1
    @BOPOH, ряд (-1)^n расходится и не имеет предела.
    – dzhioev
    5 июн 2013 в 7:32
  • Чего-чего??? Это еще почему? UPD: хотя может быть понял про что вы - если n задано, то от этого n зависит результат, -1, 0 или +1. Я вас правильно понял? Кстати, мой последний пример не удовлетворяет условию Коши. Просто "Здравый смысл подсказывает мне..."))
    – BOPOH
    5 июн 2013 в 7:37
  • Я про ряд 1 + (-1) + 1 + (-1) + ... (это и есть ряд (-1)^n). Вы написали, что "1 + (-1) + 1 + (-1) + .... = 0" Что вы этим имели ввиду?
    – dzhioev
    5 июн 2013 в 7:47

3 ответа 3

8

Ну, смотрите.

Для начала, ваша сумма неправильно раскрыта: для n = 0 имеем x^0 / 0!, то есть 1, а не x.

Итак, начальное значение слагаемого 1. Чтобы перейти к новому слагаемому на i-ой итерации, надо домножить на x^2 и разделить на (2*i - 1) * (2 * i). Дальше ясно?

Кстати, возведение в степень не нужно, если делать, так, как описано.


С другой стороны, известно, что для лучшей точности вычислений необходимо начинать суммирование с наименьших по модулю чисел. То есть, считать лучше с конца. Для этого превратим один цикл в два:

  1. цикл от i = 0, x = 1 пока |x| >= eps увеличиваем i, x домножаем на x0 * x0 и делим на (2*i - 1) * (2 * i)
  2. цикл пока i >= 0 увеличиваем сумму на x, делим x на x0 * x0 и домножаем на (2*i - 1) * (2 * i), уменьшаем i

Как правильно было подмечено в комментариях, вычисляя слагаемые дважды (один раз на пути вправо, и один раз на пути влево), мы теряем точность. Выход — запоминать вычисленные элементы (для этого неплохо бы иметь автоматически растущий контейнер, наподобие std::vector в C++), или делать три прохода: один для вычисления количества слагаемых, второй для вычисления самих слагаемых и запоминания их, третий для суммирования с конца. Вместо первого прохода можно, по идее, грубо оценить количество слагаемых по условию выхода (|x|^n/n! < eps <=> n ln |x| - ln n! < ln eps), применив формулу Стирлинга.

20
  • 1
    >>для лучшей точности вычислений необходимо начинать суммирование с наименьших по модулю чисел А это интересно. Где про это почитать можно? У Кнута? Просто сомнительно как-то, если большие числа (т.е. первые в сравнении с последними слагаемыми) влияют на точность результата, то почему прибавление их не в начале, а в самом конце так же не повлияет на точность результата? Или имеется ввиду что-то типа (для примера): 0.004 + 0.004 (0.008) + 0.004 (0.01) + 1 (1.01) = 1.01 1 + 0.004 (1.00) + 0.004 (1.00) + 0.004 (1.00) = 1.00
    – BOPOH
    28 мая 2013 в 3:08
  • 1
    Да, что-то вроде того. Можете сами попробовать попрогонять программы для этих двух алгоритмов: прямого и обратного суммирования.
    – gecube
    28 мая 2013 в 7:34
  • 2
    @VladD, Ваш второй алгоритм, суммирующий с конца, возможно будет еще хуже по точности, т.к., как известно, чем больше действий, то тем больше знаков теряется. Хорошим вариантом этого избежать, смотрится сохранение промежуточных членов последовательности в массив, но вопрос сколько памяти это займет.
    – gecube
    28 мая 2013 в 7:36
  • 2
  • 1
    >для лучшей точности вычислений необходимо начинать суммирование с наименьших по модулю чисел ооо, спасибо ) новое для себя узнал ) и в принципе согласен с этим утверждением :) > чем больше действий, тем больше знаков теряется эту проблему можно обойти либо массивом, либо полным вычислением очередного члена последовательности :) теряем либо дополнительно время, либо память, либо необходимо смириться с погрешностями :)
    – IVsevolod
    28 мая 2013 в 7:47
1

@VlaD, комментарии закончились, решил выложить пример на питоне

# решение в лоб, суммируем слева направо
def check(x = 0, eps = 0):
    sumPart = 1.
    curSum = 0

    n = 1
    while sumPart > eps:
        curSum += sumPart
        sumPart = sumPart * x * x / (n * (n + 1))
        n += 2
    return curSum

# решение через рекурсию (по формуле @dzhioev), суммирование справа налево
def calc(x = 0, eps = 0, n = 1, mulPart = 1):
    sumPart = 1. * (x * x) / (n * (n + 1))
    stepSum = mulPart * sumPart
    if stepSum < eps:
        return 1
    return 1 + sumPart * calc(x, eps, n + 2, stepSum)

# хвостовая рекурсия, суммирование слева направо
def tailLRSum(x = 0, eps = 0, n = 1, mulPart = 1, result = 1):
    currentSumPart = 1. * (x * x) / (n * (n + 1))
    stepSum = mulPart * currentSumPart
    if stepSum < eps:
        return result
    return tailLRSum(x, eps, n + 2, stepSum, result + stepSum)

# хвостовая рекурсия, суммирование справа налево (используем lambda)
def tailRLSum(x = 0, eps = 0, n = 1, mulPart = 1, result = None):
    sumPart = 1. * (x * x) / (n * (n + 1))
    stepSum = mulPart * sumPart
    if result == None:
        result = lambda value: value
    if stepSum < eps:
        return result(0)
    return tailRLSum(x, eps, n + 2, stepSum, lambda value: result(1 + sumPart * value))

Как видно - каждый метод дает свои результаты.

Первые три - почти одни и те же, а вот последний ведет себя странно - точность у него не eps, а 10*eps. Т.е. если ему в проверке сделать if stepSum < eps * 0.1, то точность будет та, что нужна (вывод в скобках). И в данном случае (т.е. при eps * 0.1) точность будет выше, чем у остальных.

Для себя понял, что ни фига не знаю как все работает внутри. Ведь по сути (по крайней мере для меня) второй и четвертый вариант должны отрабатывать одинаково - сначала вычисляются правые члены, затем добавляются левые. Аналогично и первый и второй - сначала вычисляются левые, затем правые члены. Но видно в каком-то месте (для меня неочевидном) происходит потеря точности. Причем где-то в последнем методе вообще что-то не хорошее творится...

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

Есть кто-нить, кто может прокомментировать результаты?

1
  • Кстати, в питоне хвостовая рекурсия отсутствует. Пример я привел чтобы можно было портировать на языки, где она есть.
    – BOPOH
    9 июл 2013 в 5:10
-1

Методом гнездовых процедур

12
  • Дабы не захламлять верхний ответ продолжаю тут: @dzhioev, уважаемый я не просто так сделал абстракцию на этом моменте. Посмотрите формулу и сообразите сами, что там у вас высчитывается в функции рекурсии. 4 июн 2013 в 9:24
  • @VladD, если вы считаете, что прибавляется единица - вы не понимаете формулу, сами посмотрите прибавляется НЕ единица 4 июн 2013 в 21:29
  • 1
    Не знаю зачем я это пишу, ведь я уверен, что вы неправы. Я напишу вам рекурсивную функцию для вычисления (рекурсия, кстати, только вредит, т.к. использует O(n) памяти, в отличии от итеративного вычисления), без условия остановки, а вы мне напишите условие: double f(double x, int n) { if (/* условие которое вы должны написать */) { return 0.0; } else { return 1.0 + x * x / (2 * n - 1) / (2 * n) * f(x, n + 1); } } Вперед.
    – dzhioev
    5 июн 2013 в 7:41
  • x * x / (2 * n - 1) / (2 * n) < E и еще мне почему то кажется что у вас в формуле ошибка, т.к. формулу обычно разрывают на плюсе. так же в заголовке не хватает переменной точности (Е) для сравнения. 5 июн 2013 в 8:23
  • 2
    @Сергей: Это неправильно. В вопросе чётко указан критерий остановки: x^2n / (2n)! < eps.
    – VladD
    5 июн 2013 в 8:26

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.