Cách tìm chữ số K đầu tiên của biểu diễn thập phân của 1/N

Question

Đây là câu hỏi phỏng vấn mà tôi gặp: tìm K chữ số đầu tiên của biểu diễn thập phân của 1/N. Có vẻ như chúng ta chỉ cần tính toán 10^K/N để giải quyết vấn đề. Nó có ý nghĩa không? Có vẻ như tôi đang thiếu thứ gì đó vì giải pháp quá dễ.

Answer 1

Chỉ cần thực hiện lớp học chia dài:

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

Các chi nhánh trên value == 0 là để phát hiện khi 1/n có một đại diện chấm dứt dưới k chữ số.

Ở đây, n là mẫu số trong 1/n và k là số chữ số để in trong biểu thị thập phân của 1/n.

Lưu ý rằng bằng cách thay đổi value *= 10 thành value *= b bạn cũng có thể in biểu diễn b-ary của 1/n.

Answer 2

Nếu nó là k chữ số đầu tiên, không phải là nó rất thẳng về phía trước để nhân tử số bởi 10^k và do đó nó trở nên dễ dàng hơn để chia cho N? Và nếu chúng ta cần câu trả lời, biểu diễn thập phân có nghĩa là, sau đó chúng ta sẽ kết thúc việc chia kết quả bằng 10^K lần nữa sao cho phép nhân trước đó vô hiệu hóa.

Answer 3

Tính 10^K/N có thể cực kỳ tốn kém với số lượng lớn K và N nhỏ.

Đây có thể là gần hơn với giải pháp tốt: long division. Đó là cách chúng tôi sử dụng để chia số trước máy tính. :)

Rõ ràng, bạn chỉ nên thực hiện thuật toán này cho đến khi nó mang lại K chữ số.