Калькулятор PI, интервью

Грег Бук говорит здесь , что он просит кандидатов C # создать формулу, которая вычисляет PI. Учитывая, что Pi можно оценить, используя функция \ $ 4 * (1 - \ frac {1} {3} + \ frac {1} {5} - \ frac {1} {7} + \ dots) \ $.

Я далек от интервью C #, но мне нравится вызов. Вот моя попытка формулы. Дайте мне знать, если есть лучший способ сделать это.

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();
    }
}
30 голосов | спросил LearningToCSharp 22 MarpmWed, 22 Mar 2017 22:33:18 +03002017-03-22T22:33:18+03:0010 2017, 22:33:18

8 ответов


35

В интервью обычно не имеет значения, действительно ли вы решаете проблему. Самое главное - это то, как вы (пытаетесь) решить его. Если они не скажут вам, что это должно быть, возможно, самое быстрое решение, когда-либо вы не должны оптимизировать его преждевременно, а вместо этого показать, что вы знаете, как писать SOLID-код, например, инкапсулировать должным образом, сделать проверяемый код и т. Д. Показать, что вы знаете методы.


Здесь вы можете разделить логику на несколько методов, например, вы могли бы генерировать переменную последовательность [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:

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);

или даже более продвинутый DI и инкапсуляция

class PiCalculator
{ 
    private readonly IEnumerable<int> _sequenceGenerator;

    public PiCalculator(IEnumerable<int> sequenceGenerator)
    {
        _sequenceGenerator = sequenceGenerator;
    }

    public double EstimatePi(int sumLength)
    {
        ...
    }
}

или вы можете добавить интерфейс, чтобы показать, что означает абстракция:

interface IPiCalculator
{ 
    double EstimatePi(int sumLength);
}

Это перебор? Возможно, но это показывает, что вы можете писать модульный и проверяемый код. Написание короткого кода тоже хорошо, но если вы пишете только пять строк внутри Main в собеседовании, вы отправитесь домой без каких-либо перспектив получения работы. Опять же, в inteview вы должны продать свои навыки кодирования, а не показывать, насколько вы умны в решении чего-либо с наименьшими возможными строками кода, которые никто не может проверить.

ответил t3chb0t 23 MaramThu, 23 Mar 2017 00:24:35 +03002017-03-23T00:24:35+03:0012 2017, 00:24:35
26

Я собираюсь дать альтернативный подход к ответу tchbot

Есть места, где требуются SOLID prinicpals.

Я не считаю это одним из них. Здесь у нас есть простой вопрос «Вы можете написать цикл» - примерно на уровне теста Fizz Buzz .

Действительно, функция описана в одной строке, и, применяя математические формулы, я думаю, что писать короткий код можно.

using namespace System;

public class Program
{
    public static void Main()
    {
        double t = 0.0;
        for(int i = 1, m = 1, c=0; c < 1000000; i+=2,m*=-1,++c) {
            t += (1.0/i)*m; 
        }
        Console.WriteLine("pi={0}", 4*t);
    }
}


Обратите внимание на один принцип, который я применяю здесь: длина имени переменной должна быть пропорциональна ее объему. ( Bob C. Martin .)

Я мог бы назвать переменную m чем-то описательным, например togglingNegativeMultiplier, но поскольку это целая продолжительность жизни превышает две строки кода, читатель сможет увидеть, что он делает ,


Кстати, я написал тест производительности, чтобы сравнить производительность решения Linq с производительностью простого цикла. https://dotnetfiddle.net/M3e649

При вычислении миллиона итераций:

  • Время с использованием Linq: 89 миллисекунд
  • Время с использованием Loop: 10 миллисекунд

Конечно, бывают ситуации, когда важна девятикратная разница в производительности, а в некоторых - нет. Но здесь мы пишем код с хрустом, и в этих областях производительность имеет важное значение.

ответил Andrew Shepherd 23 MaramThu, 23 Mar 2017 07:53:09 +03002017-03-23T07:53:09+03:0007 2017, 07:53:09
19

Ответ Флавио затрагивает часть того, что имеет большое значение для такого рода проблем: ошибки округления убьют вас. Если вы посмотрите на выражение:

$$ 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)} $$

Теперь, если вам нужно определенное количество цифр точности, вы сначала вычисляете количество терминов, которые вам нужны - теперь, когда у нас есть пары в парах, все они вносят положительную сумму. Это сходит очень медленно ... вы можете оценить это примерно, заметив, что

$$ \ sum_n ^ \ infty \ frac {1} {x ^ 2} \ approx \ int_ {n- \ frac12} ^ \ infty \ frac {dx} {x ^ 2} = \ frac {1} { п \ frac12} $$

Итак, если вам нужно, чтобы ответ был прав до 5 цифр, вам нужно суммировать не менее 100 000 элементов - и по мере того, как требуемая точность повышается, вам нужно нести более значимые цифры. В качестве альтернативы, умный человек добавляет оценочный срок ошибки в конце - и получает ужасно близкий к правильному ответу, не так много вычислений. См. Ниже.

Теперь вы можете знать, что число с плавающей точкой с одной точностью содержит около 23 бит точности - около 7 цифр. Это действительно испортит вашу попытку получить даже 4 цифры точности, если вы не будете работать в обратном направлении, начиная с наименьших чисел (это означает, что вы можете нести цифры за 7-ю десятичную до тех пор, пока сумма не станет больше).

Итак, шаги, которые вы предпринимаете:

  1. Сформулируйте выражение монотонное
  2. Определите скорость конвергенции
  3. Найти выражение для количества терминов, необходимых для достижения определенной точности
  4. Выполните вычисления в порядке, который максимизирует точность

Только если все вышеприведенные ошибки не прибегают к грубой силе (используя двойную точность и выше, продолжая идти, пока не убедитесь, что ваш ответ больше не меняется).

Конечно, как указывали другие, для работы с «чистым программным обеспечением» возникает много проблем правильно структурированного кода, но если задача является одним из численного анализа, а не просто отбрасыванием нескольких строк кода, то эти соображения действительно имеют значение.

Например, оценивая выражение для первых 100000 терминов в направлении «вперед», используя одинарную точность (что подчеркивает проблему), вы получаете

pi=3.14138389

Выполняя это в обратном направлении (начиная с наименьшего срока), вы получаете

pi=3.14158773

Разница: -0.00020385; они отличаются от 5-го значащего числа, даже несмотря на то, что точность с плавающей запятой «должна быть лучше, чем эта», но ошибки округления сложны! Вы можете видеть, что метод «назад» приближается к 3.14159, в то время как метод «вперед» никогда не будет там.

Вот код C, который я написал, чтобы продемонстрировать эти моменты - обратите внимание, что фактический цикл, который делает часть, которую вы просили, занимает всего четыре строки. Я понимаю, что вы ищете комментарии к своему 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

Используя одинарную точность, ошибка уменьшается примерно до 1 части в \ $ 10 ^ 7 \ $, как и мы ожидаем как предел точности. Кстати, срок исправления ошибок настолько хорош, что вы получаете «правильный» ответ всего за 100 пар терминов.

В то время как грубая сила иногда нужна вам всем, небольшой анализ - не плохой трюк, чтобы поддерживать ваш рукав.

ответил Floris 24 MarpmFri, 24 Mar 2017 21:04:45 +03002017-03-24T21:04:45+03:0009 2017, 21:04:45
12

Совершенно очевидно, что для этого не существует «лучшего способа». Из подхода «Численный анализ», вы никогда не должны так суммировать серию с переменными знаками: можно ожидать потери точности и медленной скорости конвергенции. Используйте простую арифметику для суммирования членов в парах, а затем итерации по двум единицам за раз. Если вы сделаете это, вы получите много как в точности, так и в скорости конвергенции. Таким образом, я бы добавил следующее выражение:

1 /(n * n + n)

ответил Flaviano de Fusco 23 MarpmThu, 23 Mar 2017 17:58:05 +03002017-03-23T17:58:05+03:0005 2017, 17:58:05
8

Наблюдения и предложения

  • Работайте непосредственно на pi.

  • Вы можете исключить pi = 4 * number;.

  • Вы используете больше операций, чем необходимо.

  • Я предпочитаю decimal поверх double для точности.
    Decimal работает медленнее и с точностью до 6 цифр. Думаю, double может вызвать у вас проблемы. Более высокая точность double может приводить к ошибкам, которые не самокорректируются.

  • Сделайте 2 итерации в одной общей итерации цикла и устраните оператор modulo %

  • Устранить отливку int до decimal

  • Среднее значение + и - будет лучшей текущей оценкой

  • Ответ будет между + и - если ошибка округления не была введено

    public static decimal PI3()
    {   
        decimal pi = 4m, iteration = 3m;
        do
        {  
             pi -= 4m / iteration;
             iteration += 2m;
             pi += 4m / iteration;
             iteration += 2m;
             //Debug.WriteLine(pi);
        } while (Decimal.Round(pi, 5)  !=  3.14159m);
        return Decimal.Round(pi, 5);
    }
    

В ответ на вопрос OP в комментариях:

Протестируйте это по сравнению с вашим решением или другими предлагаемыми решениями:

public static decimal PI4()
{
    decimal pi = 4m, iteration = 3m, piAvg;
    do
    {   
        pi = Decimal.Subtract(pi, Decimal.Divide(4m, iteration));
        piAvg = pi;
        iteration = decimal.Add(iteration, 2m);
        pi = Decimal.Add(pi, Decimal.Divide(4m, iteration));
        piAvg = Decimal.Divide(Decimal.Add(pi, piAvg), 2m);
        iteration = decimal.Add(iteration, 2m);
        if(decimal.Add(iteration, 1m) % 100000m == 0) {
            Debug.WriteLine(piAvg);
        }
    } while (Decimal.Round(piAvg, 10) != 3.1415926536m);      //3.1415926535897932384626433833
    return Decimal.Round(piAvg, 10);
}
ответил paparazzo 23 MaramThu, 23 Mar 2017 00:14:55 +03002017-03-23T00:14:55+03:0012 2017, 00:14:55
3

Я думаю, что вы пришли, это хорошее начало. Я отредактировал ваш код, чтобы улучшить и сделать более кратким. Это не лучший код, но я надеюсь, что это поможет вам.

 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

}
ответил peval27 22 MarpmWed, 22 Mar 2017 23:28:32 +03002017-03-22T23:28:32+03:0011 2017, 23:28:32
3

то, что я считаю неправильным с кодом - трудно понять

Вот что я думаю, что все хорошие коды должны делать:

  1. прежде всего это должно быть понятно. Большая часть кода, который вы пишете, будет читаться много раз, чем отредактировано. Нет комментариев - это не обязательно плохо, если код не требует пояснений. для чего мы должны стремиться. 2. Его необходимо легко поддерживать.
  2. и при необходимости должны быть легко вносить изменения.
  3. он должен действительно работать: где ваши тесты!?!

Стоит ли писать код ООП, или мы должны быстро и грязно?

запись чистого кода OOP может занять немного больше времени (но, вероятно, будет более надежным). стоит ли оно того? Возможно, это не так. но поскольку это гипотетично, давайте опустим путь ООП:

код не использует «объекты», которые отправляют «сообщения» друг другу. (Пожалуйста, google, если вы не знаете, что это значит). У вас есть условные обозначения в коде, которые также обеспечивают поведение. ООП предназначен для того, чтобы вы могли снабжать объекты поведением и как можно больше отделять условные обозначения от поведения.

ok здесь код

Форматирование в SO ужасно, поэтому мне нужно было создать сущность, где это получается лучше: см. здесь полный код + тесты:

  • здесь это ================= Gist

Резюме:

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();
    }
}

О точках кода

  • API проще читать и понимать. Основная логика скрыта.
  • Легко поддается изменению. Что, если босс идет и говорит, что он хочет, чтобы каждая четвертая фракция была равна: 1 /e - будет ли ваш код легко справляться с этим? Я бы просто добавил новый подкласс ElementN под названием ElementE и добавил условие к моему заводскому методу, и изменения будут сделаны мгновенно.
  • Сравните мой код с вашим: я поставил условные обозначения на заводе - и где они должны быть. все очень аккуратно разделено. я использую абстрактный класс, а затем поставляю различные реализации этого абстрактного класса. это то, что должен делать хороший код ООП. и ООП хорош, потому что легко поддается изменению, главным образом потому, что классы и методы не тесно связаны друг с другом (pls google, если вы не знаете, что это значит). как я вижу, существует только три разных типа фракций: первая (одна), вторая - положительная, а третья - отрицательная. вот и все! поэтому я подклассифицирую все на три класса, которые обеспечивают соответствующее поведение. и мне нужно всего 1-2 условности, чтобы все это работало. Это способ ООП обрабатывать его. спросите функционального программиста, и он или она может сделать это по-другому, но опять же, это труднее изменить.
ответил BKSpurgeon 23 MarpmThu, 23 Mar 2017 14:49:42 +03002017-03-23T14:49:42+03:0002 2017, 14:49:42
0

Я думаю, что ваш код не выглядит простым и немного запутанным. Вы используете int i, а затем неявно лидируете i/2 в int, чтобы проверить, равно ли оно.

Кастинг для двойки также кажется странным, он выглядел бы лучше, если бы он был 1.0 / i или 1d / i.

Кроме того, вам не нужно умножать на 4 каждой итерации, так как умножение распределяется по добавлению.

Мой ответ выглядит так, пытаясь сделать его очень простым и удобочитаемым.

/// <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);
}
ответил Gabriel Prá 25 MarpmSat, 25 Mar 2017 23:48:23 +03002017-03-25T23:48:23+03:0011 2017, 23:48:23

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132