पुनरावर्ती अंकों की गणना कैसे करें?

Question

दो पूर्णांक a और b दिए गए, मैं a/b के दोहराने वाले दशमलव की गणना करने के बारे में कैसे जाउंगा? यह किसी भी भाषा में हो सकता है; जो कुछ भी आपके लिए इसे व्यक्त करना सबसे आसान है।

Answer 1

आप इसे लंबे विभाजन के साथ कर सकते हैं। एक समय में एक अंक की गणना करें और शेष प्राप्त करने के लिए घटाएं, जिसे आप अगले चरण के लिए अंक प्राप्त करने के लिए 10 से गुणा करते हैं। जब यह नया न्यूमेरेटर पिछले अंकों में से किसी एक से मेल खाता है, तो आप जानते हैं कि आप उस बिंदु से दोहराने जा रहे हैं। आपको केवल पिछले संख्याओं के ढेर को रखने और प्रत्येक पुनरावृत्ति पर इसके माध्यम से खोज करने की आवश्यकता है।

Answer 2

आप स्कूल में सीखे गए लंबे-विभाजन एल्गोरिदम का उपयोग करके a/b के दशमलव प्रतिनिधित्व की गणना कर सकते हैं, जैसा कि मार्क रांसॉम ने कहा था। प्रत्येक क्रमिक अंक की गणना करने के लिए, वर्तमान लाभांश (संख्यात्मक या शेष) को b से विभाजित करें, और अगले लाभांश को शेष 10 के रूप में गुणा करें ("0 को नीचे लाएं")। जब शेष कुछ पिछले शेष के समान होता है, तो इसका मतलब है कि तब से अंक भी दोहराए जाएंगे, ताकि आप इस तथ्य को नोट कर सकें और रोक सकें।

यहां अनुकूलन की संभावना पर ध्यान दें: बी द्वारा विभाजित होने पर आपको प्राप्त होने वाले अवशेष 0 से बी -1 में हैं, इसलिए जब आप केवल अलग nonzero stayders रखते हैं, तो आपको अपनी सूची के माध्यम से खोजना नहीं है पिछली रहती है यह देखने के लिए कि क्या कुछ दोहराता है। तो प्रति विभाजन चरण निरंतर समय लेने के लिए एल्गोरिदम बनाया जा सकता है, और O(b) स्थान पर्याप्त है। बस प्रत्येक शेष राशि पर पहले अंक की स्थिति के बारे में ट्रैक रखें।

(यह तर्क, बीटीडब्लू, यह भी एक गणितीय सबूत है कि पुनरावर्ती हिस्सा अधिकांश बी -1 अंकों में लंबा हो सकता है: उदाहरण 1/7 = 0। (142857) में 6 अंकों का आवर्ती हिस्सा होता है, और 1/17 = 0. (0588235294117647) वास्तव में 16 अंकों की एक आवर्ती हिस्सा है। लंबाई हमेशा बिताते हैं ख -1,।)

यहाँ ऐसा करने के लिए अजगर कोड है, जो O(b) समय में चलाता है।

def divide(a, b): 
    '''Returns the decimal representation of the fraction a/b in three parts: 
    integer part, non-recurring fractional part, and recurring part.''' 
    assert b > 0 
    integer = a // b 
    remainder = a % b 
    seen = {remainder: 0} # Holds position where each remainder was first seen. 
    digits = [] 
    while(True): # Loop executed at most b times (as remainders must be distinct) 
    remainder *= 10 
    digits.append(remainder // b) 
    remainder = remainder % b 
    if remainder in seen: # Digits have begun to recur. 
     where = seen[remainder] 
     return (integer, digits[:where], digits[where:]) 
    else: 
     seen[remainder] = len(digits) 

# Some examples. 
for a, b in [(5,4), (1,6), (17,7), (22,11), (100,17)]: 
    (i, f, r) = divide(a, b) 
    print "%d/%d = %d.%s(%s)" % (a, b, i, ''.join(map(str, f)),''.join(map(str,r))) 
# Output: 
# 5/4 = 1.25(0) 
# 1/6 = 0.1(6) 
# 17/7 = 2.(428571) 
# 22/11 = 2.(0) 
# 100/17 = 5.(8823529411764705) 

तुम भी आकार b के बजाय एक शब्दकोश की एक सरणी (पायथन में एक सूची) है, जो थोड़ा तेज हो जाएगा उपयोग कर सकते हैं (नहीं asymptotics के मामले में है, लेकिन निरंतर कारक में)।

Answer 3

मैं इस लगता है कि आप के लिए क्या देख रहे है ..

public static String divide(int a,int b,boolean decimalDone,boolean isMultiplied,String result){ 
      if(a<b){ 
       a=a*10; 

       if(!decimalDone) {result+=".";decimalDone=true;} 
       else if(isMultiplied) result+="0"; 
       isMultiplied=true; 
       divide(a,b,decimalDone,isMultiplied,result); 

      } 
      else{ 
       result+=a/b; 
       a=a%b; 
       isMultiplied=false; 
       divide(a,b,decimalDone,isMultiplied,result); 
      } 

      return result; 
    } 

Answer 4

मैं एक विशेषज्ञ नहीं हूँ, और मुझे लगता है कि इस समाधान कुशल नहीं हो सकता है, लेकिन कम से कम यह करने के लिए आसान है:

#you want to get a/b 
from fractions import Fraction: 
print float(Fraction(a,b)) 

टिप्पणियाँ अच्छी तरह से स्वीकार कर रहे हैं