-11

Дано n, вычислить:

formula

На любом ЯП.

16
  • 26
    Напишите ему кто-нибудь на хаскеле каком-нибудь. Пусть удивит учителя
    – Sergey
    22 апр 2016 в 9:29
  • 9
    @Sergey да сразу на brainfuck тогда уж =) 22 апр 2016 в 9:35
  • 6
    Кто там собирался заминусовать и закрыть - вон как народ поднялся на вопросе :)
    – splash58
    22 апр 2016 в 12:30
  • 5
    @АлексейШиманский У одного из участников спонтанного гольфа и сотни репы не было на момент написания ответа здесь, однако +7 он заработал. Интересные ответы на посредственные вопросы всегда были в цене, как до, так и после смены движка.
    – Kyubey
    25 апр 2016 в 22:14
  • 3
    @АлексейШиманский У первого отвечающего совершенно топорный ответ, причём ещё и неэффективный, хотя при чистом императивном подходе сами боги велели. Если сейчас дать подобный ответ, его снова заминусуют. Вы просто не понимаете критериев качества у голосующих.
    – Kyubey
    26 апр 2016 в 11:00

15 ответов 15

40

По заявкам - на :

В "интуитивном" стиле:

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
2
  • 9
    А вот вам Реверс!
    – Nick Volynkin
    6 мая 2016 в 4:24
  • 3
    это выдаёт неверный результат уже для n=3 как и другие ответы, которые ищут ответ, суммируя числа с плавающей точкой, вместо замкнутой формулы
    – jfs
    10 окт 2017 в 6:57
25

Вот варианты на

Лобовой вариант (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))))
5
  • 1
    К вам Реверс приехал, примите посылку. :)
    – Nick Volynkin
    10 окт 2017 в 2:03
  • 1
    результат неверный уже для n=3. Сравните с O(1) решением (для float) для любого n. Точный результат (рациональная дробь) меньше чем за O(n log (n)) нельзя сделать так как n! содержит O(n log (n)) цифр.
    – jfs
    10 окт 2017 в 7:10
  • @NickVolynkin А награждений то всего 6 :)
    – Ver Nick
    5 дек 2018 в 9:19
  • 1
    @VerNick редкий знак )
    – Nick Volynkin
    5 дек 2018 в 9:44
  • @NickVolynkin А ведь так хочется все знаки получить...
    – Ver Nick
    5 дек 2018 в 9:45
17

Вот такая версия на

-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).
2
  • 2
    Очень красивое и эффективное решение. Всем брать пример!
    – Kyubey
    25 апр 2016 в 17:08
  • @Squidward: код использует числа с плавающей точкой [насколько я понимаю], поэтому результат должен быть равен нулю для n>177. Эффективное решение может вернуть ноль сразу. Не знаком с erlang, не могу сказать насколько точный результат ответ возвращает (к примеру, для N=3 ожидаемый ответ: -1/6 == -0.16666666666666666 как float. Ответы, которые суммированием результат получают, ломаются уже для такого маленького N (к примеру возвращают: -0.16666666666666652). Для бо́льших N ещё хуже точность. Чтобы точную дробь получить, можно замкнутую формулу использовать
    – jfs
    10 окт 2017 в 8:23
15

Многие представленные решения реализованы неоптимальным образом — с помощью вложенных циклов. Суммирование большого числа элементов будет очень медленным.

Вот решение в лоб на 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);
5
  • А Scan из MoreLinq? github.com/morelinq/MoreLINQ/blob/master/MoreLinq/Scan.cs
    – VladD
    25 апр 2016 в 17:21
  • @VladD Вот, это уже больше похоже на правду. Но у MoreLinq нет ореола официальности. :)
    – Kyubey
    25 апр 2016 в 17:26
  • Scan - это Aggregate?
    – Grundy
    25 апр 2016 в 17:32
  • @Grundy нет, Scan - это Scan. Отличие от Aggregate - в возвращаемом значении. 25 апр 2016 в 18:10
  • 4
    @Discord: Зато у MoreLinq есть ореол Джона Скита :)
    – VladD
    25 апр 2016 в 18:25
12

Еще вариант 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))
        )
    )
)
12

Почему забыт 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;
}
12

import math
print(sum(map(lambda k: (-1)**k*(k+1)/math.factorial(k), range(int(input('n = '))+1))))
1
10

Вариант с

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).
8

На С никто не писал :)
Добавим...

double sum(int n)
{
    double f = 1.0;
    for(int i = 2; i <= n; ++i)
        f *= i;
    return (1-2*(n%2))/f;
}
4
  • Если я правильно понял, вы ограничились только вычислением n!?
    – Mikhajlo
    19 янв 2017 в 5:48
  • 2
    Этого вполне достаточно - см. тут.
    – Harry
    19 янв 2017 в 5:53
  • Классно! Вывел формулу))
    – Qwertiy
    7 июн 2017 в 14:36
  • 2
    @Qwertiy Перефразируя одну фразу из одного рассказа (ну не помню точно ни автора, ни названия) - был так стар, что при взгляде на него невольно вспоминались времена, когда программированием занимались математики :)
    – Harry
    8 июн 2017 в 6:33
8

Точный результат на :

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.

1
  • чем вызван минус?
    – jfs
    10 окт 2017 в 13:17
7

JavaScript:

var a=s=1,n=50;
for(var k=1;k<n;k++){a*=-(k+1)/k/k;s+=a;}
console.log(s);
6
  • 6
    А где jQuery? :-)
    – VladD
    26 апр 2016 в 15:33
  • @VladD для гольфа jquery не годится из-за размера. за ответы с факториалом, кстати говоря, тс получил бы неуд и на codegolf'е кучу минусов, на любом ЯП. 26 апр 2016 в 16:20
  • 1
    Это да. Я имел в виду, собственно, эту картинку.
    – VladD
    26 апр 2016 в 16:23
  • 2
    @VladD, "жуквери" надо говорить )
    – Nofate
    26 апр 2016 в 19:36
  • 3
    @Sergey ее не надо "замечать". Надо k-й член ряда поделить на k-1-й. 27 апр 2016 в 9:45
6

Пусть и в тоже будет

sum((-1)^(0:n)*((0:n)+1)/factorial((0:n)))
4

Вариант на 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))))
3

Ещё один вариант на 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))))
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;
        }
3
  • 4
    Слишком просто... 25 апр 2016 в 18:08
  • Я бы сказал тривиально
    – Sergey
    26 апр 2016 в 2:16
  • 3
    Ну IntegerOverflowException же
    – Qwertiy
    27 апр 2016 в 20:47

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