Как найти 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-арное представление 1/n.

Answer 2

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

Answer 3

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

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

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