Помогите пожалуйста написать на си. Вроде не сложно, но с математикой не идут задачи у меня.
-
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– BOPOH5 июн 2013 в 6:19
-
1@BOPOH, ряд (-1)^n расходится и не имеет предела.– dzhioev5 июн 2013 в 7:32
-
Чего-чего??? Это еще почему? UPD: хотя может быть понял про что вы - если n задано, то от этого n зависит результат, -1, 0 или +1. Я вас правильно понял? Кстати, мой последний пример не удовлетворяет условию Коши. Просто "Здравый смысл подсказывает мне..."))– BOPOH5 июн 2013 в 7:37
-
Я про ряд 1 + (-1) + 1 + (-1) + ... (это и есть ряд (-1)^n). Вы написали, что "1 + (-1) + 1 + (-1) + .... = 0" Что вы этим имели ввиду?– dzhioev5 июн 2013 в 7:47
3 ответа
Ну, смотрите.
Для начала, ваша сумма неправильно раскрыта: для n = 0
имеем x^0 / 0!
, то есть 1
, а не x
.
Итак, начальное значение слагаемого 1
. Чтобы перейти к новому слагаемому на i
-ой итерации, надо домножить на x^2
и разделить на (2*i - 1) * (2 * i)
. Дальше ясно?
Кстати, возведение в степень не нужно, если делать, так, как описано.
С другой стороны, известно, что для лучшей точности вычислений необходимо начинать суммирование с наименьших по модулю чисел. То есть, считать лучше с конца. Для этого превратим один цикл в два:
- цикл от
i = 0
,x = 1
пока|x| >= eps
увеличиваемi
,x
домножаем наx0 * x0
и делим на(2*i - 1) * (2 * i)
- цикл пока
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
), применив формулу Стирлинга.
-
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– BOPOH28 мая 2013 в 3:08
-
1Да, что-то вроде того. Можете сами попробовать попрогонять программы для этих двух алгоритмов: прямого и обратного суммирования.– gecube28 мая 2013 в 7:34
-
2@VladD, Ваш второй алгоритм, суммирующий с конца, возможно будет еще хуже по точности, т.к., как известно, чем больше действий, то тем больше знаков теряется. Хорошим вариантом этого избежать, смотрится сохранение промежуточных членов последовательности в массив, но вопрос сколько памяти это займет.– gecube28 мая 2013 в 7:36
-
2
-
1>для лучшей точности вычислений необходимо начинать суммирование с наименьших по модулю чисел ооо, спасибо ) новое для себя узнал ) и в принципе согласен с этим утверждением :) > чем больше действий, тем больше знаков теряется эту проблему можно обойти либо массивом, либо полным вычислением очередного члена последовательности :) теряем либо дополнительно время, либо память, либо необходимо смириться с погрешностями :) 28 мая 2013 в 7:47
@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) точность будет выше, чем у остальных.
Для себя понял, что ни фига не знаю как все работает внутри. Ведь по сути (по крайней мере для меня) второй и четвертый вариант должны отрабатывать одинаково - сначала вычисляются правые члены, затем добавляются левые. Аналогично и первый и второй - сначала вычисляются левые, затем правые члены. Но видно в каком-то месте (для меня неочевидном) происходит потеря точности. Причем где-то в последнем методе вообще что-то не хорошее творится...
Насчет произвольной хвостовой рекурсии, дайте пример - посмотрю, а так ничего не скажу, т.к. не знаю.
Есть кто-нить, кто может прокомментировать результаты?
-
Кстати, в питоне хвостовая рекурсия отсутствует. Пример я привел чтобы можно было портировать на языки, где она есть.– BOPOH9 июл 2013 в 5:10
Методом гнездовых процедур
-
Дабы не захламлять верхний ответ продолжаю тут: @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); } } Вперед.– dzhioev5 июн 2013 в 7:41
-
x * x / (2 * n - 1) / (2 * n) < E и еще мне почему то кажется что у вас в формуле ошибка, т.к. формулу обычно разрывают на плюсе. так же в заголовке не хватает переменной точности (Е) для сравнения.– Сергей5 июн 2013 в 8:23
-
2@Сергей: Это неправильно. В вопросе чётко указан критерий остановки:
x^2n / (2n)! < eps
.– VladD5 июн 2013 в 8:26