PI计算器，面试挑战

using System;

class MainApp 
{
    static void Main () 
    {
        double number = 0;
        double pi;
        int i = 1;

        do 
        {
            if ((i/2) % 2 == 0)
            {
                number += (double)(1) / i;
            }
            else
            {
                number -= (double)(1) / i;
            }
            pi = 4 * number;
            i += 2;
        } while (Math.Round(pi,5) != 3.14159);

        Console.Clear();
        Console.WriteLine("Pi can be found using the formula 4 * (1 - 1/3 + 1/5 - 1/7 + ...) with {0} iterations.\n" +
        "At this point 4 is multiplied by: {1} to get {2}\n" +
        "This Rounds up to: {3}",i,number,pi,Math.Round(pi,5));
        Console.ReadKey();
    }
}

#1 楼

在面试中，实际上是否解决问题通常并不重要。最重要的是您（尝试）解决问题的方式。如果他们没有告诉您这应该是可能是最快的解决方案，那么您不应该过早地对其进行优化，而要表明您知道如何编写SOLID代码（如进行适当的封装），使代码可测试等。 br />

在这里，您可以将逻辑分为多种方法，例如，您可以生成一种可以通过测试验证的交替序列[1, -3, 5, -7, 9, -11, ...]：

public static IEnumerable<int> AlternatingSequence()
{
    var i = 1;
    yield return i;
    var b = false;
    while (true) yield return ((b = !b) ? -1 : 1) * (i = i + 2);
}

然后您就可以在PI本身上进行工作并将其用于实际计算，然后就可以像LINQ表达式一样简单： br />您可以显示出各种熟悉的东西，例如DI或策略模式这样的简单任务：

public static double EstimatePI(int sumLength) 
{
    return (4 * AlternatingSequence().Take(sumLength).Sum(x => 1.0 / x));
}

var pi = EstimatePI(500_000).Dump(); // 3,14159065358969

或更高级的DI和封装

public static double EstimatePI(int sumLength, IEnumerable<int> sequenceGenerator) 
{
    return (4 * sequenceGenerator.Take(sumLength).Sum(x => 1.0 / x));
}

var pi = EstimatePI(500_000, AlternatingSequence);

，或者您可以添加一个接口来显示抽象的含义： >这是一个过度的杀伤力吗？可能是，但它向我展示了您能够编写模块化和可测试的代码。编写短代码也是一件好事，但是如果您在求职面试中在Main内只写了五行代码，您将没有希望获得这份工作的回家。同样，在访问中，您应该出售自己的编码技能，而不要表现出用最少的代码行来解决某人的问题时的聪明才智。

#2 楼

我将为tchbot的答案提供另一种方法。

在某些地方需要SOLID主教。

我不认为这是其中之一。在这里，我们有一个简单的“您是否有能力编写循环”的问题-与Fizz Buzz测试的水平大致相同。 ，我认为编写简洁的代码是可以的。应该与其范围成正比。 （Bob C. Martin。）

我可以将变量m命名为togglingNegativeMultiplier之类的描述性名称，但是由于它的整个生命周期只有两行代码，读者可以看到它在做什么。顺便说一句，我写了一个性能测试，比较了Linq解决方案的性能和简单循环的性能。 https://dotnetfiddle.net/M3e649

计算一百万次迭代时：


使用Linq的时间：89毫秒
使用循环的时间：10毫秒

当然，在某些情况下，性能差异是9倍很重要，而在某些情况下，性能无关紧要。但是这里我们正在编写数字运算代码，在这些方面，性能往往很重要。

#3 楼

Flavio的答案解决了对此类问题非常重要的部分问题：舍入错误会杀死您。如果看一下表达式：

$$ 1- \ frac13 + \ frac15- \ frac17 + ... $$

与

$$ \ frac {3-1} {1 \ times3} + \ frac {7-5} {5 \ times 7} + ... $$

很容易看到此序列中的第n个词是

$$ \ frac {2} {（4 \ times n-3）（4 \ times n-1）} $$

Now如果您需要一定数量的精度，则首先要计算所需的项数-现在我们成对出现了项，它们都贡献了正数。这收敛得非常慢...您可以通过注意

$$ \ sum_n ^ \ infty \ frac {1} {x ^ 2} \ approx \ int_ {n- \ frac12}来近似估算^ \ infty \ frac {dx} {x ^ 2} = \ frac {1} {n- \ frac12} $$

因此，如果您需要正确的答案以大于5位数字，您至少需要合计100,000个元素-随着所需精度的提高，您需要携带很多更重要的数字。或者，聪明的人在最后添加估计的误差项，并且无需太多计算即可非常接近正确答案。参见下文。

现在您可能知道单个精度浮点数包含大约23位精度-大约7位数字。如果您不进行反向操作，这实际上会使您试图获得甚至4位精度的尝试弄乱了，从最小的数字开始（这意味着您可以携带小数点后7位的数字，直到总和变大）。

因此您要采取的步骤：


将表达式构造为单调的
确定收敛速度
为您要查找的项数查找表达式需要达到一定的精度
以使精度最大化的顺序执行计算

只有在上述所有方法均失败的情况下，才应诉诸蛮力（使用双精度及以上精度，直到您确定您的答案不会再改变了。

当然，正如其他人指出的那样，对于“纯软件”工作，许多结构正确的代码会起作用-但是，如果任务是数值分析之一，则不只是删除几行代码，那么上述考虑确实很重要。

例如，使用“单精度”（强调问题），对“向前”方向的前100000个术语的表达式求值，得到

pi=3.14138389

向后（从最小项开始）进行操作

pi=3.14158773

区别： -0.00020385;尽管浮点精度“应该比那还要好”，但它们仍与第5位有效数字有所不同-但舍入误差更加复杂！您可以看到“向后”方法已接近3.14159，而“向前”方法将永远无法到达那里。循环执行您要询问的部分仅需四行。我意识到您正在寻找有关C＃代码的注释，但是我概述的原则超越了您使用的语言。

// code that computes the value of pi by evaluating the first few terms
// of the infinite series
// pi = 4*(1/1-1/3+1/5-1/7+...)
//
// three important points:
// rounding error is reduced by evaluating starting with the small values
// rounding error is further reduced by pairing the values
// finally, an analytical estimate of the residual error is used to make the
// result significantly more accurate

#include <stdio.h>
#include <math.h>

int main(void) {
    int N=100;             // number of values to include
    double PI=2*acos(0.0); // to confirm the accuracy later
    float forwardSum, backwardSum, residualSum;
    forwardSum=0;

    for(int ii=1; ii<=N; ii++) {
        forwardSum+=8./((4*ii-3.)*(4*ii-1.));
    }

    // ***** this is the code that does the heavy lifting *****
    backwardSum=0;
    for(int ii=N; ii>=1; ii--) {
        backwardSum+=8./((4*ii-3.)*(4*ii-1.));
    }
    // backwardSum now contains our estimate of pi

    // analytically we know the error should be
    residualSum = 0.5/N;

    printf("Starting with big terms, after %d pairs pi=%.8f\n", N, forwardSum);
    printf("Starting with small terms, after %d pairs pi=%.8f\n", N, backwardSum);
    printf("difference between directions: %.8f\n", backwardSum - forwardSum);
    printf("estimated residual sum = %e\n", residualSum);
    printf("updated estimate of pi: %.8f\n", backwardSum + residualSum);
    printf("after correction, error in pi is %e\n", PI-(backwardSum +residualSum));

    return 0;
}

该代码的输出是： >

Starting with big terms, after 100 pairs pi=3.13659286
Starting with small terms, after 100 pairs pi=3.13659263
difference between directions: -0.00000024
estimated residual sum = 5.000000e-03
updated estimate of pi: 3.14159274
after correction, error in pi is -8.742278e-08

使用单精度，将误差减小到\ $ 10 ^ 7 \ $的大约1份，正如我们期望的那样，它是精度的极限。附带提一下，纠错项是如此之好，以至于您只需100对项就可以得到“正确”的答案。

虽然有时只需要蛮力，但进行一点分析并不是紧随其后的好招。

#4 楼

显然，没有最好的方法。可以预期会出现较慢的收敛速度。
使用简单的算法对项进行成对求和，
然后每次迭代两个单位。 >准确性和收敛速度都很高。
所以我要添加的表达式是：

1 /（n * n + n）

#5 楼

观察和建议


直接在pi上操作。
您可以消除pi = 4 * number;。
您正在使用不必要的操作。
我更喜欢decimal超过double，以提高精度。 Decimal较慢，精度为6位数，我认为double不会给您带来麻烦。更精确的double可能会引入无法自我纠正的错误。
在循环的一个整体迭代中执行2次迭代，并消除
模运算符%
消除了将int转换为decimal
+和-的平均值将是当前的最佳估计值

如果没有引入舍入误差，则答案将在+和-之间





在评论中回答OP的问题：

将其与您的解决方案或其他建议的解决方案进行测试：

>

#6 楼

我认为您的想法是一个好的开始。我已经对您的代码进行了修改，以使其更加简洁。它不是最好的代码，但希望对您有所帮助。

 public static void Main()
{
    double number = 0;
    double pi;
    int i = 1;
    bool sign = true; // we use a boolean to sum or subtract

    do 
    {
        double div = (double)(1.0 / i);  // calculate the ratio
        number += (sign ? div : -div); // sum or subtract depending on sign being true or false

        pi = 4 * number;
        i += 2;
        sign = !sign;  // toggle sign

    } while ((Math.Round(pi,5) != 3.14159));

    Console.WriteLine("Pi can be found using the formula 4 * (1 - 1/3 + 1/5 - 1/7 + ...) with {0} iterations.\n" +
    "At this point 4 is multiplied by: {1} to get {2}\n" +
    "This Rounds up to: {3}",(i-1)/2,number,pi,Math.Round(pi,5)); // to know the iteration we use i-1 / 2

}
 

#7 楼

我认为代码有问题-很难理解

我认为所有好的代码都应该这样做： 。您编写的大多数代码将比编辑的次数被读取更多。没有注释-如果代码是不言自明的，这不一定很糟糕。这就是我们的目标。
必须易于维护
，如果需要，必须易于进行更改
它必须切实可行：您的测试在哪里！？！

是否值得编写OOP代码，还是我们应该快速又肮脏？

编写纯OOP代码可能会花费一些时间（但可能会更健壮）。这值得么？可能不是。但是，由于这是一个假设，因此让我们沿用OOP方式：

您的代码没有利用彼此发送“消息”的“对象”。 （请谷歌，如果你不知道这意味着什么）。您的代码中有条件语句，也可以提供行为。 OOP旨在让您让对象提供行为，并尽可能地将条件与行为分开。

以下是摘要代码：

public class Pie
{
    /// <summary>
    /// Estimates pi based on the number of fractions we desire it to estimate by.
    /// The way I view it: you basically have 4 * (element0 + element1 + element2 etc.)
    /// where element0, element1 etc are instances of the Element class.        
    /// </summary>
    /// <param name="elementCount"></param>
    /// <returns></returns>
    public double Estimate(int elementCount)
    {
        ElementCollection ec = new ElementCollection(elementCount);
        return 4 * ec.AddAllElements();
    }
}

这里是完整代码：

namespace BKTest
{
    public class Pie
    {
        /// <summary>
        /// Estimates pi based on the number of fractions we desire it to estimate by.
        /// The way I view it: you basically have 4 * (element0 + element1 + element2 etc.)
        /// where element0, element1 etc are instances of the Element class.
        /// I use a factory method to instantiate the element types and use polymorphism to differentiate
        /// between the two different types of elements that are currently out there: Element0 and the others: Element1, Element2 etc .
        /// Element zero is different because you can't divide by zero! (This probably won't make any sense)
        /// Till you attempt the problem yourself.
        ///
        /// </summary>
        /// <param name="elementCount"></param>
        /// <returns></returns>
        public double Estimate(int elementCount)
        {
            ElementCollection ec = new ElementCollection(elementCount);
            return 4 * ec.AddAllElements();
        }
    }

    public class ElementCollection
    {
        private int elementCount;

        public ElementCollection(int elementCount)
        {
            this.elementCount = elementCount;
        }

        public double AddAllElements()
        {
            double result = 0.0;
            for (int i = 0; i < elementCount + 1; i++)
            {
                ElementN element = ElementFactory(i);
                result += element.Value();
            }

            return result;
        }

        public ElementN ElementFactory(int i)
        {
            if (i == 0)
            {
                return new Element0(i);
            }
            else
            {
                bool even = (i % 2 == 0);

                if (even)
                {
                    return new ElementEven(i);
                }
                else
                {
                    return new ElementOdd(i);
                }
            }
        }

        public class Element0 : ElementN
        {
            public Element0(int elementCount)
                : base(elementCount)
            {
            }

            public override int Sign()
            {
                return 1;
            }

            public override double PosivitveValue()
            {
                return 1.0;
            }
        }

        public class ElementEven : ElementN
        {
            public ElementEven(int elementCount)
                : base(elementCount)
            {
            }

            public override int Sign()
            {
                return 1;
            }
        }

        public class ElementOdd : ElementN
        {
            public ElementOdd(int elementCount)
                : base(elementCount)
            {
            }

            public override int Sign()
            {
                return -1;
            }
        }

        public abstract class ElementN
        {
            private int elementCount;

            public ElementN(int elementCount)
            {
                this.elementCount = elementCount;
            }

            virtual public double Value()
            {
                return Sign() * PosivitveValue();
            }

            virtual public double PosivitveValue()
            {
                return ((1.0) / (2.0 * elementCount + 1));
            }

            /// <summary>
            /// Either the sign is positive or negative
            /// We could probably put this into its own class
            /// and have a factory method but we'll keep it like this for the moment
            /// till one day change requires us to change it. After all, a sign can only
            /// either be positive or negative. (apparently you can also multiple by the
            /// square root of (-1) but that's another matter.
            /// </summary>
            /// <returns></returns>
            abstract public int Sign();
        }
    }
}

这里是测试：

using NUnit.Framework;

namespace BKTest
{
    [TestFixture]
    internal class PieTest
    {
        [Test]
        [TestCase(0, 4)]
        [TestCase(1, 4 * (1 - 1.00 / 3.0))]
        [TestCase(2, 4 * (1 - 1.00 / 3.0 + 1 / 5.0))]
        [TestCase(3, 4 * (1 - 1.00 / 3.0 + 1 / 5.0 - 1 / 7.0))]
        [TestCase(4, 4 * (1 - 1.00 / 3.0 + 1 / 5.0 - 1 / 7.0 + 1 / 9.0))]
        public void Estimate_1Parameter_expect_fourMinusOneThird(int input, double output)
        {
            // set up
            double result = new Pie().Estimate(input);
            Assert.AreEqual(output, result);
        }
    }
}

（注意-原来的代码放在Gist上）


API更易于阅读和理解。隐藏了主要逻辑。
易于更改。如果老板走进来并说他/她希望每4个分数是：1 / e-您的代码将很容易处理吗？我只需要添加一个名为ElementE的新ElementN子类，并向我的工厂方法中添加一个条件，即可立即进行更改。
将我的代码与您的代码进行比较：我已经将条件放在工厂中-这是它们应该在的地方。一切都非常整齐地分开了。我利用一个抽象类，然后提供该抽象类的各种实现。这就是好的OOP代码应该做的。 OOP之所以好，是因为它易于更改，主要是因为类和方法没有紧密地耦合在一起（如果您不知道这是什么意思，请用google搜索）。如我所见，分数只有三种不同的类型：第一种（为一），第二种为正数，第三种为负数。就是这样！因此，我将所有内容分为提供相关行为的三类。而且我只需要1-2个条件就可以使整个工作正常进行。这是一种OOP处理方式。问一个功能程序员，他或她可能会用不同的方式来做，但是再说一次，很难改变。

#8 楼

我认为您的代码看起来并不简单，有点令人困惑。
您使用int i然后隐式将i/2强制转换为int以检查其是否均匀。很奇怪，如果是1.0 / i或1d / i看起来会更好。像这样回答您的问题，尝试使其变得非常简单易读。

/// <summary>
/// Uses the formula 4 * (1 - 1/3 + 1/5 - 1/7 + ...) to estimate pi
/// </summary>
public static double EstimatePi(int iterations)
{
    double series = 0;
    for(int i = 0; i < iterations; i++)
    {
        int sign = i.IsEven() ? 1 : -1;
        series += sign / (2d*i + 1);
    }
    return 4 * series;
}

private static bool IsEven(this int number)
{
    return (number % 2 == 0);
}