Code Golf:Pi的Leibniz公式

Question

我最近在" 你更有争议的编程意见是什么 "中发布了我最喜欢的采访白板编码问题之一,即编写一个使用Leibniz公式计算Pi的函数.

它可以通过多种不同的方式进行处理,退出条件需要一些思考,所以我认为它可能会成为一个有趣的代码高尔夫问题.最短的代码获胜!

假设Pi可以使用函数4*(1 - 1/3 + 1/5 - 1/7 + ...)估算,更多项更精确,可以编写一个函数来计算Pi到0.00001以内.

编辑:2008年1月3日

正如评论中所建议的那样,我将退出条件更改为0.00001,因为这就是我的真实含义(由于四舍五入,精确度小数点后五位更难,所以我不想在面试中问这个,而在0.00001以内是更容易理解和实现退出条件).

另外,为了回答评论,我想我的意图是解决方案应该计算迭代次数,或检查它何时做得足够多,但没有什么可以阻止你预先计算迭代次数并使用该数字.我真的有兴趣问这个问题,看看人们会想出什么.

Answer 1

J,14个字符

4*-/%>:+:i.1e6

说明

• 1e6 数字1后跟6个零(1000000).
• i.y生成第一个y非负数.
• +: 是一个将list参数中的每个元素加倍的函数.
• >: 是一个函数,它使list参数中的每个元素递增1.

因此,表达式>:+:i.1e6生成第一个一百万个奇数:

1 3 5 7 ...

• % 是倒数运算符(分子"1"可以省略).
• -/ 对list参数中的每个元素进行替换.

因此,表达式-/%>:+:i.1e6生成前一百万个奇数的倒数的交替和:

1 - 1/3 + 1/5 - 1/7 + ......

• 4*乘以4.如果乘以前一个和的四,则得到π.

而已!J是一种强大的数学语言.

编辑:自生成9!(362880)交替金额的条款足以具有5位十进制数字的准确度,并且因为莱布尼兹公式也可以这样写:

4 - 4/3 + 4/5 - 4/7 + ......

...你可以写一个较短的,12个字符版本的程序:

-/4%>:+:i.9!

Answer 2

语言:Brainfuck,Char计数:51/59

这算数了吗？=]

因为Brainfuck中没有浮点数,所以很难让分区正常工作.格儿.

没有换行符(51):

+++++++[>+++++++<-]>++.-----.+++.+++.---.++++.++++.

换行(59):

+++++++[>+++++++>+<<-]>++.-----.+++.+++.---.++++.++++.>+++.

Answer 3

Perl的

26个字符

26只是功能,27来计算,31来打印.从评论到这个答案.

sub _{$-++<1e6&&4/$-++-&_}       # just the sub
sub _{$-++<1e6&&4/$-++-&_}_      # compute
sub _{$-++<1e6&&4/$-++-&_}say _  # print

28个字符

28只是计算,34来打印.从评论.请注意,此版本不能使用"说".

$.=.5;$\=2/$.++-$\for 1..1e6        # no print
$.=.5;$\=2/$.++-$\for$...1e6;print  # do print, with bonus obfuscation

36个字符

36只是计算,42来打印.从评论中看,哈德森对dreeves的重新安排采取了措施.

$/++;$\+=8/$//($/+2),$/+=4for$/..1e6
$/++;$\+=8/$//($/+2),$/+=4for$/..1e6;print

关于迭代计数:就我的数学记忆而言,400000可证明足够精确到0.00001.但是一百万(或低至8e5)实际上使十进制扩展实际上匹配了5个小数位,并且它是相同的字符数,所以我保持这一点.

Answer 4

Ruby,33个字符

(0..1e6).inject{|a,b|2/(0.5-b)-a}

Answer 5

另一个C#版本:

(60个字符)

4*Enumerable.Range(0, 500000).Sum(x => Math.Pow(-1, x)/(2*x + 1));  // = 3,14159

Answer 6

Python中的 52个字符:

print 4*sum(((-1.)**i/(2*i+1)for i in xrange(5**8)))

(51从xrange中删除'x'.)

Octave(或Matlab)中的36个字符:

l=0:5^8;disp((-1).^l*(4./(2.*l+1))')

(执行"format long;"以显示所有有效数字.)省略'disp'我们达到30个字符:

octave:5> l=0:5^8;(-1).^l*(4./(2.*l+1))'
ans = 3.14159009359631

Answer 7

Oracle SQL 73字符

select -4*sum(power(-1,level)/(level*2-1)) from dual connect by level<1e6

Answer 8

语言:C,字数:71

float p;main(i){for(i=1;1E6/i>5;i+=2)p-=(i%4-2)*4./i;printf("%g\n",p);}

语言:C99,字数:97(包括所需换行)

#include <stdio.h>
float p;int main(){for(int i=1;1E6/i>5;i+=2)p-=(i%4-2)*4./i;printf("%g\n",p);}

我应该注意上面的版本(它们是相同的)跟踪额外的迭代是否会影响结果.因此,它执行最少数量的操作.要添加更多的数字,替换1E6用1E(num_digits+1)或4E5用4E(num_digits)(取决于版本).对于完整的程序,%g可能需要更换. float也可能需要更改double.

语言:C,字数:67(见注释)

double p,i=1;main(){for(;i<1E6;i+=4)p+=8/i/(i+2);printf("%g\n",p);}

此版本使用已发布算法的修改版本,正如其他一些答案所使用的那样.此外,它不像前两个解决方案那样干净/高效,因为它强制进行100 000次迭代,而不是检测何时迭代变得毫无意义.

语言:C,字数:24(作弊)

main(){puts("3.14159");}

但是,数字计数> 6不起作用.

Answer 9

哈斯克尔

我把它降到了34个字符:

foldl subtract 4$map(4/)[3,5..9^6]

评估时,此表达式生成3.141596416935556.

编辑:这是一个使用foldl1而不是foldl的更短版本(33个字符):

foldl1 subtract$map(4/)[1,3..9^6]

编辑2:9 ^ 6而不是10 ^ 6.一个必须经济;)

编辑3:分别用foldl和foldl1替换foldl'和foldl1' - 由于编辑2,它不再溢出.感谢ShreevatsaR注意到这一点.

Answer 10

MATLAB中的23个字符:

a=1e6;sum(4./(1-a:4:a))

Answer 11

F#:

尝试#1:

let pi = 3.14159

作弊？不,它以风格赢得胜利!

尝试#2:

let pi =
    seq { 0 .. 100 }
    |> Seq.map (fun x -> float x)
    |> Seq.fold (fun x y -> x + (Math.Pow(-1.0, y)/(2.0 * y + 1.0))) 0.0
    |> (fun x -> x * 4.0)

它不像它可能获得的那么紧凑,但非常惯用的F#.

Answer 12

常见的口齿不清,55个字符.

(loop for i from 1 upto 4e5 by 4 sum (/ 8d0 i (+ i 2)))

Answer 13

Mathematica,27个字符(可以说低至26,或高达33)

NSum[8/i/(i+2),{i,1,9^9,4}]

如果删除初始"N",则它将答案作为(巨大的)分数返回.

如果作弊,Mathematica不需要打印语句输出其结果,那么前缀" Print@"总共33个字符.

注意:

如果硬编码术语的数量是作弊的,那么我认为没有任何答案可以做到这一点.检查当前术语何时低于某个阈值并不比硬编码术语数更好.仅仅因为当前术语仅改变第6或第7位并不意味着足够的后续术语的总和不会改变第5位数.

Answer 14

在交替序列中使用误差项的公式(因此,实现所需精度的必要迭代次数不会硬编码到程序中):

public static void Main(string[] args) {
    double tolerance = 0.000001;
    double piApproximation = LeibnizPi(tolerance);
    Console.WriteLine(piApproximation);
}

private static double LeibnizPi(double tolerance) {
    double quarterPiApproximation = 0;

    int index = 1;
    double term;
    int sign = 1;
    do {
        term = 1.0 / (2 * index - 1);
        quarterPiApproximation += ((double)sign) * term;
        index++;
        sign = -sign;
    } while (term > tolerance);

    return 4 * quarterPiApproximation;
}