Дано n, вычислить:
На любом ЯП.
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуПо заявкам - на haskell:
В "интуитивном" стиле:
f n = sum [((-1) ** k) * (k + 1) / product [1..k] | k <- [0..n]]
и point-free:
g = foldr (+) 0 . ((flip take) (map (\k -> ((-1) ** k) * (k + 1) / fac k) [0..])) . ((+) 1)
where fac = foldr (*) 1 . enumFromTo 1
n=3
как и другие ответы, которые ищут ответ, суммируя числа с плавающей точкой, вместо замкнутой формулы
Вот варианты на clojure
Лобовой вариант (O(N2)), калька с формулы, даже с сигмой в роли сумматора:
(fn [n]
(letfn [(over [a b] (range a (inc b)))
(! [k] (reduce *' (over 1 k))) ;; *' это умножение с расширением
(Σ [coll] (reduce + coll))]
(Σ (for [k (over 0 n)]
(/ (* (Math/pow -1 k)
(+ k 1))
(! k))))))
Из-за точности вычислений с плавающей точкой на больших значениях начинает выдавать белиберду. Но плавающая точка там только из-за Math/pow
, который можно заменить.
В ClojureScript не работает, ибо там нет *'
и длинной арифметики.
Вариант поумнее и побыстрее (O(N)), на ленивой последовательности внутренних слагаемых. Идея в том, что при наличии k
-ого слагаемого и k
можно легко вычислить k+1
'ое, на что reduce
, а точнее его вариация reductions
, великолепно накладывается.
Также интересен тем, что оперирует в рациональных дробях, не переходя на числа с плавающей точкой (ибо нет Math/pow
). Впрочем, только под JVM, в ClojureScript всё равно скатывается к плавающей точке.
(fn [n]
(let [next-inner (fn [prev k]
(* prev -1 (/ (inc k) k k)))
inner-seq (reductions next-inner 1 (iterate inc 1))]
(reduce + (take (inc n) inner-seq))))
n=3
. Сравните с O(1)
решением (для float) для любого n
. Точный результат (рациональная дробь) меньше чем за O(n log (n))
нельзя сделать так как n!
содержит O(n log (n))
цифр.
Вот такая версия на erlang
-module(sum).
-export([sum/1]).
qsum(0) -> [1, 1, 1, 1];
qsum(N) ->
[S, X, Y, Z] = qsum(N-1),
Xn = -1 * X,
Yn = Y + 1,
Zn = Z * N,
Sn = S + (Xn * Yn) / Zn,
[Sn, Xn, Yn, Zn].
sum(N) -> [S|_R] = qsum(N), S.
sum:sum(123).
n>177
. Эффективное решение может вернуть ноль сразу. Не знаком с erlang, не могу сказать насколько точный результат ответ возвращает (к примеру, для N=3
ожидаемый ответ: -1/6 == -0.16666666666666666
как float. Ответы, которые суммированием результат получают, ломаются уже для такого маленького N
(к примеру возвращают: -0.16666666666666652
). Для бо́льших N
ещё хуже точность. Чтобы точную дробь получить, можно замкнутую формулу использовать
Многие представленные решения реализованы неоптимальным образом — с помощью вложенных циклов. Суммирование большого числа элементов будет очень медленным.
Вот решение в лоб на C#:
return 1 + Enumerable
.Range(1, n)
.Scan(
new { a = 1d, k = 1 },
(p, k) => new { a = p.a * k * -1, k })
.Sum(p => (p.k + 1) / p.a);
Первый элемент суммы мы вычисляем явно, последующие члены суммы частично вычисляем из предыдущих. К сожалению, в C# отсутствует функция агрегации, которая возвращает промежуточные результаты (Enumerable.Aggregate
схлопывает последовательность в одно значение), и даже в библиотеке Ix только перегрузка без зерна, поэтому придётся реализовать функцию вручную:
public static IEnumerable<TAccumulate> Scan<TSource, TAccumulate>(
this IEnumerable<TSource> source, TAccumulate seed,
Func<TAccumulate, TSource, TAccumulate> accumulator)
{
foreach (TSource item in source) {
seed = accumulator(seed, item);
yield return seed;
}
}
Пример можно заметно упростить, учитывая, что Enumerable.Select
имеет перегрузку, которая передаёт индекс в селектор, однако индексы при этом сместятся на минус единицу, поэтому придётся подправить формулу:
return 1 + Enumerable
.Range(1, n)
.Scan(1d, (a, k) => a * k * -1)
.Sum((a, k) => (k + 2) / a);
В виде гольфа:
1+Enumerable.Range(1,n).Scan(1d,(a,k)=>a*k*-1).Sum((a,k)=>(k+2)/a);
Еще вариант Common Lisp
(defun f(n)
(loop for k from 0 to n
sum
(/
(* (+ k 1) (if (evenp k) 1 -1))
(apply '* (loop for i from 1 to k collect i))
)
)
)
Почему забыт C++??!! :)
template<typename T, typename = std::enable_if_t<std::is_floating_point<T>::value>>
class Term
{
public:
Term():k(0),value(1.0) {}
Term(const Term&) = delete;
Term(const Term&&) = delete;
~Term() = default;
T operator ++(int)
{
T old = value;
++k;
value = -value*(k+1)/(k*k);
return old;
}
operator T() const { return value; }
private:
int k;
T value;
};
template<typename T, typename = std::enable_if_t<std::is_floating_point<T>::value>>
class Sum
{
public:
Sum(unsigned int n) {
for(Term<T> t; n > 0; sum += t++, --n);
}
~Sum() = default;
friend std::ostream& operator << (std::ostream&os, const Sum& S)
{
return os << S.sum;
}
private:
T sum = T(0);
};
int main(int argc, const char * argv[])
{
std::cout << Sum<double>(10) << endl;
}
import math
print(sum(map(lambda k: (-1)**k*(k+1)/math.factorial(k), range(int(input('n = '))+1))))
map()
тут не нужна. Если нет именованной функции, то map()
менее читаема, чем аналогичный генератор (genexpr). Cравните с f_iter(n)
, но ещё лучше f(n)
Вариант с prolog
f(0, 1, 1, 1,1).
f(K1,M,FCT, Result,Sum ):- K is K1-1,
f(K,M1,FCT1,Result1,Sum1),
M is -M1,
FCT is FCT1*K1,
Result is M/FCT - Result1/K1,
Sum is Sum1+Result.
s(N, Result):-f(N,_,_,_,Result).
И еще один:
f(0, 1, 1, 1).
f(K,M,FCT, Sum ):- K1 is K-1,
f(K1,M1,FCT1,Sum1),
M is -M1,
FCT is FCT1*K,
Sum is Sum1+M*(K+1)/FCT.
s(N, Result):-f(N,_,_,Result).
На С никто не писал :)
Добавим...
double sum(int n)
{
double f = 1.0;
for(int i = 2; i <= n; ++i)
f *= i;
return (1-2*(n%2))/f;
}
n!
?
19 янв 2017 в 5:48
Точный результат на python:
from fractions import Fraction
from math import factorial
def f(n):
return Fraction((-1)**n, factorial(n))
Пример:
S = f(10)
print(S) # -> 1/3628800
print(float(S)) # -> 2.755731922398589e-07
Формула в f(n)
основана на равенстве:
n
____
╲
╲ k n
╲ (-1) ⋅(k + 1) (-1)
╱ ───────────── = ─────
╱ k! n!
╱
‾‾‾‾
k = 0
Стоит заметить, что ответы, которые вычисляют результат итеративно, суммируя, используя арифметику с плавающей точкой, получают неправильный результат уже для n=3
:
def f_iter(n):
return sum((-1)**k * (1 + k) / factorial(k) for k in range(n + 1))
n = 3
S = f(n)
print(S) # -> -1/6
print(float(S).hex()) # -> -0x1.5555555555555p-3
print(f_iter(n).hex()) # -> -0x1.5555555555554p-3
hex представление использовано, чтобы точно показать IEEE-754 double.
Неточность вызвана именно индивидуальными слагаемыми, так как отличие от math.fsum()
варианта, который точную сумму для арифметики в рамках IEEE 754 стандарта получает, только для n=23
появляется:
from math import factorial, fsum
def f_iter_fsum(n):
return fsum((-1)**k * (1 + k) / factorial(k) for k in range(n + 1))
n = 23
S = f(n)
print(S) # -> -1/25852016738884976640000
print(float(S).hex()) # -> -0x1.761b41316381ap-75
print(f_iter(n).hex()) # -> 0x1.927350c308171p-55
print(f_iter_fsum(n).hex()) # -> 0x1.927350c308170p-55
Видно, что отличие точного результата (float(S)
) гораздо больше чем отличие f_iter()
и f_iter_fsum()
.
Для n >= 178
результат в виде IEEE 754 double равен нулю (0x0.0p+0
). Поэтому, чтобы точные значения получить в любом языке программирования (с точностью, которую double допускает), достаточно с помощью приведённого Питон-кода (f(n)
) вычислить сумму для 0 <= n < 178
.
JavaScript:
var a=s=1,n=50;
for(var k=1;k<n;k++){a*=-(k+1)/k/k;s+=a;}
console.log(s);
k
-й член ряда поделить на k-1
-й.
27 апр 2016 в 9:45
Вариант на Scheme (Guile) с использованием замыкания:
(use-modules (srfi srfi-1))
(define (f-lexical-closure n)
(define (make-term)
(let* ((k 0)
(term 1))
(lambda ()
(set! k (+ k 1))
(set! term (+ term (/ (* term -1 (+ k 1)) k)))
term)))
(let ((gen (make-term)))
(let loop ((n n)
(term 1))
(if (positive? n)
(loop (- n 1) (gen))
term))))
Ещё один вариант на Guile Scheme, теперь более функциональный:
(use-modules (srfi srfi-1) ;; Списки
(srfi srfi-19)) ;; Хеш-таблицы
(define (make-caching-generator)
"Генерация последовательных элементов с хешированием результатов."
(let ((hash (make-hash-table)))
(letrec ((func (lambda (k)
(if (zero? k) 1
(let ((term (hashq-ref hash k)))
(if term
term
(hashq-set! hash k (* -1 (+ k 1) (/ 1 k k) (func (- k 1))))))))))
func)))
(define gen (make-caching-generator))
(define (f-fold-left n)
"Свёртка списка элементов с использованием сложения."
(fold + 0 (map gen (iota (+ n 1) 0))))
static int Fact(int n)
{
if (n == 0) return 1;
int fact = 1;
for (int i = 1; i <= n; i++)
{
fact *= i;
}
return fact;
}
static double F(int n)
{
double summ = 0;
for (int k = 0; k <= n; k++)
{
summ += (Math.Pow(-1, k) * (k + 1)) / (Fact(k));
}
return summ;
}