Thuật toán để phát hiện số thập phân lặp lại?

Question

Có một thuật toán để tìm ra những điều sau đây không?

1. Nếu kết quả của phép chia là số thập phân lặp lại (tính theo hệ nhị phân).
2. Nếu nó lặp lại, ở chữ số nào (được biểu thị bằng lũy ​​thừa của 2) thì sự lặp lại có bắt đầu không?
3. Chữ số nào lặp lại?

Một số ví dụ:

1/2 = 1/10 = 0.1 // 1 = false, 2 = N/A, 3 = N/A, 4 = N/A 
1/3 = 1/11 = 0.010101... // 1 = true, 2 = -2, 3 = 10 
2/3 = 10/11 = 0.101010... // 1 = true, 2 = -1, 3 = 10 
4/3 = 100/11 = 1.010101... // 1 = true, 2 = 0, 3 = 10 
1/5 = 1/101 = 0.001100110011... // 1 = true, 2 = -3, 3 = 1100 

Có cách nào để làm điều này? Hiệu quả là một mối quan tâm lớn. Một mô tả của thuật toán sẽ được ưa thích hơn mã, nhưng tôi sẽ đưa ra câu trả lời tôi có thể nhận được.

Điều đáng lưu ý là cơ sở không phải là vấn đề lớn; Tôi có thể chuyển đổi các thuật toán trên để nhị phân (hoặc nếu nó ở, nói cơ sở 256 để sử dụng char s cho dễ dàng, tôi chỉ có thể sử dụng đó). Tôi nói điều này bởi vì nếu bạn đang giải thích nó có thể được dễ dàng hơn cho bạn để giải thích trong cơ sở 10 :).

Answer 1

Để tìm mô hình lặp lại, chỉ theo dõi các giá trị mà bạn sử dụng dọc theo dòng:

1/5 = 1/101: 

1 < 101 => 0 
(decimal separator here) 
10 < 101 => 0 
100 < 101 => 0 
1000 >= 101 => 1 

    1000 - 101 = 11 

110 >= 101 => 1 

    110 - 101 = 1 

10 -> match 

Như bạn đạt được giá trị tương tự như bạn có ít bit thứ hai, quá trình này sẽ chỉ lặp lại từ đó điểm tạo ra cùng một mẫu bit nhiều lần. Bạn có mẫu "0011" lặp lại từ bit thứ hai (đầu tiên sau dấu tách thập phân).

Nếu bạn muốn mô hình để bắt đầu với một "1", bạn chỉ có thể xoay nó cho đến khi nó phù hợp với điều kiện là:

"0011" from the second bit 
"0110" from the third bit 
"1100" from the fourth bit 

Edit:
Ví dụ trong C#:

void FindPattern(int n1, int n2) { 
    int digit = -1; 
    while (n1 >= n2) { 
     n2 <<= 1; 
     digit++; 
    } 
    Dictionary<int, int> states = new Dictionary<int, int>(); 
    bool found = false; 
    while (n1 > 0 || digit >= 0) { 
     if (digit == -1) Console.Write('.'); 
     n1 <<= 1; 
     if (states.ContainsKey(n1)) { 
     Console.WriteLine(digit >= 0 ? new String('0', digit + 1) : String.Empty); 
     Console.WriteLine("Repeat from digit {0} length {1}.", states[n1], states[n1] - digit); 
     found = true; 
     break; 
     } 
     states.Add(n1, digit); 
     if (n1 < n2) { 
     Console.Write('0'); 
     } else { 
     Console.Write('1'); 
     n1 -= n2; 
     } 
     digit--; 
    } 
    if (!found) { 
     Console.WriteLine(); 
     Console.WriteLine("No repeat."); 
    } 
} 

Được gọi với ví dụ của bạn, kết quả đầu ra:

.1 
No repeat. 
.01 
Repeat from digit -1 length 2. 
.10 
Repeat from digit -1 length 2. 
1.0 
Repeat from digit 0 length 2. 
.0011 
Repeat from digit -1 length 4. 

Answer 2

1. nếu số chia không phải là một sức mạnh của 2 (nói chung, chứa thừa số nguyên tố không được chia sẻ với các cơ sở đại diện)
2. lặp lại chiều dài chu kỳ sẽ được thúc đẩy bởi các yếu tố nguyên tố lớn nhất của cổ tức (nhưng không được kết nối với độ dài biểu diễn của hệ số đó - xem 1/7 tính theo số thập phân), nhưng độ dài chu kỳ đầu tiên có thể khác với đơn vị lặp lại (ví dụ: 11/28 = 1/4 + 1/7 tính theo số thập phân).
3. chu kỳ thực tế sẽ phụ thuộc vào tử số.

Answer 3

Kiểm tra decimal expansion và đặc biệt khoảng thời gian một phần.

Answer 4

Tôi có thể đưa ra gợi ý - số thập phân lặp lại trong mười cơ sở đều là phân số với mẫu số có ít nhất một yếu tố chính ngoài hai và năm. Nếu mẫu số không chứa các thừa số nguyên tố hai hoặc năm, chúng có thể luôn được biểu diễn bằng mẫu số của tất cả các gai. Sau đó, người đề cử là phần lặp lại và số lượng gai là chiều dài của phần lặp lại.

3  _ 
- = 0.3 
9 

1 142857  ______ 
- = ------ = 0.142857 
7 999999 

Nếu có hai yếu tố chính ở mẫu số, phần lặp lại không bắt đầu ở vị trí đầu tiên.

17 17  ______ 
-- = ----- = 0.4857142 
35 5 * 7 

Nhưng tôi không thể nhớ cách lấy phần không lặp lại và độ dài của nó.

Điều này dường như dịch tốt ở hai cơ sở. Chỉ phân số với sức mạnh của hai mẫu số là không lặp lại. Điều này có thể dễ dàng kiểm tra bằng cách khẳng định rằng chỉ một bit duy nhất trong mẫu số được thiết lập.

1/2 = 1/10 = 0.1 
1/4 = 1/100 = 0.01 
3/4 = 11/100 = 0.11 
5/8 = 101/1000 = 0.101 

Tất cả các phần với mẫu số lẻ nên được lặp đi lặp lại và các mô hình và chiều dài của nó có thể được thu được bằng cách thể hiện phần với một mẫu số theo hình thức 2^n-1.

             __ 
1/3   = 1/(2^2-1) =  1/11  = 0.01 
                __ 
2/3   = 2/(2^2-1) =  10/11  = 0.10 
         __ 
4/3 => 1 + 1/3 => 1.01 
         __ 
10/3 => 3 + 1/3 => 11.01 
                ____ 
1/5 = 3/15 = 3/(2^4-1) =  11/1111  = 0.0011 
                ________ 
11/17 = 165/255 = 11/(2^8-1) = 10100101/11111111 = 0.10100101 

Đối với cơ sở mười, tôi không thể nói như thế nào để xử lý mẫu số chứa nhưng không phải là một sức mạnh của hai - ví dụ 12 = 3 * 2^2.

Answer 5

Trước hết, một trong các ví dụ của bạn là sai. Phần lặp lại của 1/5 là 0011 thay vì 1100 và bắt đầu ở phần đầu của phần phân đoạn.

Một thập phân lặp lại là một cái gì đó như:

a/b = c + d(2-n + 2-n-k + 2-n-2k + ...)
    = c + 2-n * d/(1 - 2-k)

trong đó n và d là những gì bạn muốn.

Ví dụ,

1/10(dec) = 1/1010(bin) = 0.0001100110011... // 1 = true, 2 = -1, 3 = 0011

có thể được biểu diễn bằng công thức với

a = 1, b = 10(dec), c = 0, d = 0.0011(bin), n = 1, k = 4;
(1 - 2-k) = 0.1111

Do đó, 1/10 = 0.1 * 0.0011/0.1111. Phần chính của biểu diễn thập phân lặp lại được tạo ra bằng cách chia cho (2n - 1) hoặc bất kỳ bội số nào của 2. Vì vậy, bạn có thể tìm cách biểu diễn mẫu số của bạn như vậy (như xây dựng bảng không đổi) hoặc thực hiện phân chia số lớn tương đối chậm) và tìm vòng lặp. Không có cách nào nhanh chóng để làm điều này.

Answer 6

Bạn ca n làm một long division, lưu ý các phần còn lại. Cấu trúc của dư sẽ cung cấp cho bạn cấu trúc của bất kỳ thập phân hợp lý:

1. thời gian còn lại cuối cùng là zero: nó là một số thập phân mà không cần bất kỳ phần nào lặp lại
2. đầu tiên và còn lại cuối cùng đều bình đẳng: các thập phân được lặp lại ngay sau khi chấm
3. khoảng cách giữa đầu tiên và phần còn lại đầu tiên tương đương với cuối cùng là số không lặp lại, phần còn lại là phần lặp lại

Nói chung khoảng cách wi sẽ cung cấp cho bạn số lượng chữ số cho mỗi phần.

Bạn có thể xem thuật toán này được mã hóa trong C++ trong phương thức decompose()here.

Try228142/62265, nó có một khoảng thời gian chữ số!