Как найти K первых цифр десятичного представления 1 / N

Question

Это вопрос интервью, с которым я столкнулся: найдите K первые цифры десятичного представления 1/N.Похоже, нам нужно просто вычислить 10^K/N, чтобы решить проблему.Имеет ли это смысл ?Похоже, я что-то упустил, потому что решение слишком простое.

Answer 1

Просто внедрите длинное деление в начальной школе:

int value = 1;
bool outputDecimalSeparator = false;
int digitsOutput = 1;
while(digitsOutput <= k) {
    if (value == 0) {
        Console.Write(0);
    }
    else {
        if (value < n) {
            Console.Write(0);
            value *= 10;
        }
        else {
            Console.Write(value / n);  
            value %= n;
        }
   }
   if (outputDecimalSeparator == false) {
       outputDecimalSeparator = true;
       Console.Write('.');
   }
   digitsOutput++;
}
Console.WriteLine();

Ветвь на value == 0 должна обнаруживать, когда 1 / n имеет конечное представление менее чем k цифр.

Здесь n - знаменатель в 1 / n, а k - количество цифр для печати в десятичном представлении 1 / n.

Обратите внимание, что при изменении value *= 10 на value *= bВы также можете распечатать b-ary представление 1 / n.

Answer 2

Расчет 10 ^ K / N может быть чрезвычайно дорогостоящим при больших K и малых N.

Возможно, это ближе к хорошему решению: длинное деление .Это то, как мы делили числа перед калькуляторами.:)

Очевидно, вы должны выполнять этот алгоритм только до тех пор, пока он не даст K цифр.

Answer 3

Если это первые k цифр, разве не очень просто умножить числитель на 10 ^ k, и поэтому становится легче разделить на N? И если нам нужен ответ, десятичное представление, то есть, мы закончим делением результата снова на 10 ^ K, так что предыдущее умножение аннулирует.