दोहराव decimals का पता लगाने के लिए एल्गोरिदम?

Question

क्या निम्नलिखित चीजों को जानने के लिए कोई एल्गोरिदम है?

1. यदि विभाजन का परिणाम दोहराना दशमलव (बाइनरी में) है।
2. यदि यह दोहराता है, तो किस अंक (2 की शक्ति के रूप में प्रतिनिधित्व किया जाता है) पुनरावृत्ति शुरू होता है?
3. कौन से अंक दोहराते हैं?

कुछ उदाहरण:

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 

वहाँ यह करने के लिए कोई तरीका है? क्षमता एक बड़ी चिंता है। कोड पर एल्गोरिदम का विवरण पसंद किया जाएगा, लेकिन मैं जो जवाब प्राप्त कर सकता हूं उसे ले जाऊंगा।

यह भी ध्यान देने योग्य है कि आधार एक बड़ा सौदा नहीं है; मैं एल्गोरिदम को बाइनरी में बदल सकता हूं (या यदि यह है, तो आसानी से char एस का उपयोग करने के लिए आधार 256 कहें, मैं बस इसका उपयोग कर सकता हूं)। मैं यह इसलिए कहता हूं क्योंकि यदि आप समझा रहे हैं तो आधार 10 में व्याख्या करना आपके लिए आसान हो सकता है :)।

Answer 1

दोहराई जाने वाली पद्धति को खोजने के लिए, बस मूल्यों आप रेखा के साथ उपयोग करने का ट्रैक रखने:

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 

आप एक ही मूल्य तक पहुंचने के रूप में के रूप में आप दूसरे बिट में था, इस प्रक्रिया को सिर्फ इतना है कि से दोहराया जाएगा बिंदु पर एक ही बिट पैटर्न का उत्पादन बिंदु। आपके पास दूसरी बिट से दोहराने वाला पैटर्न "0011" है (दशमलव विभाजक के बाद पहले)।

आप पैटर्न एक "1" के साथ शुरू करना चाहते हैं, तो आप बस इसे बारी बारी से कर सकते हैं जब तक यह है कि हालत से मेल खाता है:

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

संपादित करें: सी # में
उदाहरण:

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."); 
    } 
} 

आपके उदाहरणों के साथ बुलाया गया यह आउटपुट:

.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. यदि भाजक 2 के एक शक्ति नहीं है, लेकिन
2. दोहराने चक्र लंबाई लाभांश में से सबसे बड़ी अभाज्य गुणांक के द्वारा संचालित किया जाएगा (सामान्य रूप में प्रधानमंत्री कारकों प्रतिनिधित्व के आधार के साथ साझा नहीं होता है) (नहीं उस कारक के प्रतिनिधित्व की लंबाई से जुड़ा हुआ - दशमलव में 1/7 देखें), लेकिन पहली चक्र लंबाई दोहराने वाली इकाई से भिन्न हो सकती है (उदाहरण के लिए दशमलव में 11/28 = 1/4 + 1/7)।
3. वास्तविक चक्र संख्या पर निर्भर करेगा।

Answer 3

decimal expansion, और विशेष रूप से एक अंश की अवधि के बारे में देखें।

Answer 4

मैं आधार दस में एक संकेत - दोहराव decimals दे सकते हैं कम से कम एक और पांच के अलावा कम से कम एक प्रमुख कारक वाले denominator के साथ सभी अंश हैं। यदि denominator में दो या पांच कोई प्रमुख कारक नहीं है, तो वे हमेशा सभी नाइन के एक denominator के साथ प्रतिनिधित्व किया जा सकता है। फिर नामांकनकर्ता दोहराना हिस्सा है और नाइन की संख्या दोहराने वाले भाग की लंबाई है।

3  _ 
- = 0.3 
9 

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

यदि denominator में दो या पांच प्रमुख कारक हैं, तो दोहराव वाला हिस्सा पहली स्थिति में शुरू नहीं होता है।

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

लेकिन मुझे याद नहीं है कि गैर-दोहराने वाले भाग और इसकी लंबाई को कैसे प्राप्त किया जाए।

यह दो आधार पर अच्छी तरह से अनुवाद करने लगता है। दो denominator की शक्ति के साथ केवल अंश गैर-दोहराना है। यह आसानी से जांच कर किया जा सकता है कि denominator में केवल एक ही बिट सेट है।

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

सभी अंश अजीब हरों साथ दोहरा किया जाना चाहिए और पैटर्न और इसकी लंबाई प्रपत्र 2^n-1 में एक विभाजक के साथ अंश व्यक्त करके प्राप्त की जा सकती है। उदाहरण 12 = 3 * 2^2 के लिए -

             __ 
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 

आधार दस का सवाल है, मैं कैसे युक्त हरों लेकिन दोनों में से एक शक्ति नहीं किया जा रहा संभालने के लिए नहीं बता सकता।

Answer 5

सबसे पहले, आपके उदाहरणों में से एक गलत है। 1/5 का दोहराव हिस्सा 00111100 के बजाय है, और यह आंशिक भाग की शुरुआत में ही शुरू होता है। जिसमें

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

n और d आप क्या चाहते हैं:

एक दोहराई जाने वाली दशमलव की तरह कुछ है।

उदाहरण के लिए

,

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

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

इसलिए, 1/10 = 0.1 * 0.0011/0.1111 साथ सूत्र द्वारा प्रतिनिधित्व किया जा सकता है। दोहराने वाले दशमलव प्रतिनिधित्व का मुख्य भाग (2n - 1) या उसके किसी भी एकाधिक 2 से विभाजित करके उत्पन्न होता है। तो आप या तो अपने denominator को व्यक्त करने के लिए एक रास्ता खोज सकते हैं (जैसे निरंतर तालिकाओं का निर्माण), या एक बड़ी संख्या विभाजन (जो है अपेक्षाकृत धीमी) और लूप पाएं। ऐसा करने का कोई त्वरित तरीका नहीं है।

Answer 6

आप ca n long division, रहने वालों को ध्यान में रखते हुए करें। शेष की संरचना आप किसी भी तर्कसंगत दशमलव की संरचना दे देंगे:

1. पिछले शेष शून्य है: यह किसी भी दोहरा हिस्सा
2. पहली और आखिरी शेष बराबर हैं के बिना एक दशमलव है: दशमलव सही डॉट के बाद दोहरा रहा है
3. पहले और पहले शेष पिछले करने के लिए बराबर के बीच की दूरी गैर अंक समान हैं, शेष दोहरा हिस्सा

सामान्य दूरी वाई में है आपको प्रत्येक भाग के लिए अंकों की राशि देगी।

आप इस एल्गोरिथ्म विधि decompose()here में सी ++ में कोडित देख सकते हैं।

Try228142/62265, यह अंक की अवधि है!