كيفية حساب التكراري سيارة؟

Question

وبالنظر الى اثنين الأعداد الصحيحة a وb، كيف أذهب حول حساب تكرار عشري من a / b؟ هذا يمكن أن يكون في أي لغة. كل ما هو أسهل بالنسبة لك للتعبير عن ذلك في.

Answer 1

ويمكنك أن تفعل ذلك مع القسمة المطولة. حساب رقم واحد في وقت وطرح للحصول على ما تبقى، والتي تتضاعف بنسبة 10 للحصول على البسط للخطوة التالية. وعندما يطابق هذا البسط الجديد واحدا من بسط السابقة، كما تعلمون كنت تريد الذهاب لتكرار من تلك النقطة. كل ما تحتاجه للحفاظ على كومة من بسط السابقة والبحث من خلال ذلك في كل تكرار.

Answer 2

ويمكنك حساب تمثيل عشري a / b باستخدام خوارزمية القسمة المطولة-تعلمته في المدرسة، كما قال مارك فدية. لحساب كل رقم على التوالي، تقسيم الأرباح الحالي (البسط أو ما تبقى) من خلال b، والعثور على أرباح القادم مع ما تبقى مضروبة في 10 ( "اسقاط 0"). عندما تبقى هي نفس بعض ما تبقى السابقة، وهو ما يعني أن الأرقام منذ ذلك الحين ستكرر كذلك، لذلك يمكنك ملاحظة هذه الحقيقة وتتوقف.

ملاحظة احتمال حدوث الأمثل هنا: من بقايا تحصل عند قسمة ب هم في النطاق من 0 إلى 1-ب، وذلك على الحفاظ على البقايا غير صفرية فقط متميزة، لم يكن لديك للبحث من خلال قائمة من سابقة بقايا لمعرفة ما إذا تكرر شيء. لذلك يمكن أن يتم الخوارزمية ليستغرق وقتا ثابتا لكل خطوة الانقسام، والفضاء O(b) بما فيه الكفاية. فقط تتبع ما موقف أرقام وقعت كل ما تبقى لأول مرة في.

و(هذه الحجة، راجع للشغل، هو أيضا البرهان الرياضي أن الجزء المتكررة يمكن أن يكون في معظم ب-1 أرقام طويلة: على سبيل المثال 07/01 = 0 (142857) لديه جزء المتكررة من 6 أرقام، و17/01. = 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))

وتقبل

وتعليقات جيدا