التحقق مما إذا كان الرقم قابلاً للقسمة على 3 [مغلق]

Question

اكتب رمزًا لتحديد ما إذا كان الرقم قابلاً للقسمة على 3.الإدخال إلى الدالة هو أ أعزب بت، 0 أو 1، ويجب أن يكون الإخراج 1 إذا كان الرقم المستلم حتى الآن هو التمثيل الثنائي لرقم قابل للقسمة على 3، وإلا صفر.

أمثلة:

input  "0":       (0)  output 1
inputs "1,0,0":   (4)  output 0
inputs "1,1,0,0": (6)  output 1

ويستند هذا على سؤال المقابلة.أطلب رسمًا للبوابات المنطقية، لكن نظرًا لأن هذا يمثل تدفقًا مكدسًا، فسوف أقبل أي لغة ترميز.نقاط المكافأة لتنفيذ الأجهزة (verilog وما إلى ذلك).

الجزء أ (سهل): الإدخال الأول هو MSB.

الجزء ب (أصعب قليلاً): الإدخال الأول هو LSB.

الجزء ج (صعب): أيهما أسرع وأصغر (أ) أم (ب)؟(ليس من الناحية النظرية بالمعنى الكبير، ولكن من الناحية العملية أسرع/أصغر.) الآن خذ الأبطأ/الأكبر واجعله سريعًا/صغيرًا مثل الأسرع/الأصغر.

Answer 1

هيه

جدول الحالة لـ LSB:

S I S' O
0 0 0  1
0 1 1  0
1 0 2  0
1 1 0  1
2 0 1  0
2 1 2  0

توضيح:0 يقبل القسمة على ثلاثة. 0 << 1 + 0 = 0.كرر الاستخدام S = (S << 1 + I) % 3 و O = 1 لو S == 0.

جدول الحالة لـ MSB:

S I S' O
0 0 0  1
0 1 2  0
1 0 1  0
1 1 0  1
2 0 2  0
2 1 1  0

توضيح:0 يقبل القسمة على ثلاثة. 0 >> 1 + 0 = 0.كرر الاستخدام S = (S >> 1 + I) % 3 و O = 1 لو S == 0.

S' يختلف عما سبق، ولكن O يعمل بنفس الطريقة، منذ ذلك الحين S' هو 0 لنفس الحالات (00 و 11).نظرًا لأن O هو نفسه في كلتا الحالتين، O_LSB = O_MSB، لذا لجعل MSB قصيرًا مثل LSB، أو العكس، ما عليك سوى استخدام الأقصر من كليهما.

Answer 2

هناك خدعة معروفة إلى حد ما لتحديد ما إذا كان الرقم من مضاعفات العدد 11، وذلك عن طريق جمع أرقامه العشرية وطرحها بالتناوب.إذا كان الرقم الذي حصلت عليه في النهاية هو من مضاعفات 11، فإن الرقم الذي بدأت به هو أيضًا من مضاعفات 11:

47278    4 - 7 + 2 - 7 + 8 = 0, multiple of 11     (47278 = 11 * 4298)
52214    5 - 2 + 2 - 1 + 4 = 8, not multiple of 11 (52214 = 11 * 4746 + 8)

يمكننا تطبيق نفس الخدعة على الأعداد الثنائية.الرقم الثنائي هو مضاعف للرقم 3 إذا وفقط إذا كان المجموع المتناوب لبتاته هو أيضًا مضاعف للرقم 3:

4   = 100       1 - 0 + 0 = 1, not multiple of 3
6   = 110       1 - 1 + 0 = 0, multiple of 3
78  = 1001110   1 - 0 + 0 - 1 + 1 - 1 + 0 = 0, multiple of 3
109 = 1101101   1 - 1 + 0 - 1 + 1 - 0 + 1 = 1, not multiple of 3

لا فرق بين أن تبدأ بـ MSB أو LSB، لذا فإن وظيفة Python التالية تعمل بشكل جيد في كلتا الحالتين.يتطلب الأمر مكررًا يقوم بإرجاع البتات واحدة تلو الأخرى. multiplier يتناوب بين 1 و2 بدلاً من 1 و-1 لتجنب أخذ معامل الرقم السالب.

def divisibleBy3(iterator):

    multiplier = 1
    accumulator = 0

    for bit in iterator:
        accumulator = (accumulator + bit * multiplier) % 3
        multiplier = 3 - multiplier

    return accumulator == 0

Answer 3

هنا...شيء جديد...كيفية التحقق مما إذا كان الرقم الثنائي بأي طول (حتى آلاف الأرقام) قابلاً للقسمة على 3.

-->((0))<---1--->()<---0--->(1)        ASCII representation of graph

من الصورة.

1. عليك أن تبدأ في الدائرة المزدوجة.
2. عندما تحصل على واحد أو صفر، إذا كان الرقم داخل الدائرة، فستبقى في تلك الدائرة.ومع ذلك، إذا كان الرقم على الخط، فإنك تنتقل عبر الخط.
3. كرر الخطوة الثانية حتى يتم استهلاك كافة الأرقام.
4. إذا انتهى بك الأمر أخيرًا في الدائرة المزدوجة، فسيكون الرقم الثنائي قابلاً للقسمة على 3.

يمكنك أيضًا استخدام هذا لإنشاء أرقام قابلة للقسمة على 3.ولا أعتقد أنه سيكون من الصعب تحويل هذا إلى دائرة.

مثال واحد باستخدام الرسم البياني...

1100000000000101111111111101 يقبل القسمة على 3 (ينتهي في الدائرة المزدوجة مرة أخرى)

جربه بنفسك.

يمكنك أيضًا القيام بحيل مماثلة لتنفيذ MOD 10، عند تحويل الأرقام الثنائية إلى أرقام أساسية 10.(10 دوائر، كل منها محاطة بدائرة مزدوجة وتمثل القيم من 0 إلى 9 الناتجة عن المعامل)

يحرر: هذا بالنسبة للأرقام التي تعمل من اليسار إلى اليمين، ليس من الصعب تعديل آلة الحالة المحدودة لقبول اللغة العكسية.

ملحوظة: في تمثيل ASCII للرسم البياني () يشير إلى دائرة واحدة و (()) يشير إلى دائرة مزدوجة.في آلات الحالة المحدودة تسمى هذه الحالات، والدائرة المزدوجة هي حالة القبول (الحالة التي تعني أنها قابلة للقسمة في النهاية على 3)

Answer 4

إليك طريقة بسيطة للقيام بذلك يدويًا.بما أن 1 = 2² النموذج 3، نحصل على 1 = 2^{2 ن} وزارة الدفاع 3 لكل عدد صحيح موجب.وعلاوة على ذلك 2 = 2^2ن+1 وزارة الدفاع 3.ومن ثم يمكن للمرء تحديد ما إذا كان العدد الصحيح قابلاً للقسمة على 3 عن طريق حساب 1 بت في مواضع البت الفردية، وضرب هذا الرقم في 2، وإضافة عدد البتات 1 في مواضع البت الزوجية، وإضافتها إلى النتيجة والتحقق مما إذا كانت النتيجة قابلة للقسمة بحلول 3.

مثال:57₁₀=111001₂.هناك بتتان في المواضع الفردية، وبتتان في المواضع الزوجية.2*2 + 2 = 6 يقبل القسمة على 3.ومن ثم فإن 57 يقبل القسمة على 3.

هنا أيضًا فكرة لحل السؤال ج).إذا قام أحدهم بعكس ترتيب البت لعدد صحيح ثنائي، فستبقى جميع البتات في مواضع زوجية/فردية أو تتغير جميع البتات.ومن ثم، فإن عكس ترتيب بتات العدد الصحيح n هو عدد صحيح يقبل القسمة على 3 إذا وفقط إذا كان n قابلاً للقسمة على 3.ومن ثم فإن أي حل للسؤال أ) يعمل بدون تغييرات للسؤال ب) والعكس صحيح.حسنًا، ربما يساعد هذا في معرفة النهج الأسرع...

Answer 5

ما عليك القيام بجميع العمليات الحسابية باستخدام المعامل الحسابي 3.هذا هو الطريق

مسب:

number=0
while(!eof)
    n=input()
    number=(number *2 + n) mod 3

if(number == 0)
    print divisible

إل إس بي:

number = 0;
multiplier = 1;
while(!eof)
    n=input()
    number = (number + multiplier * n) mod 3
    multiplier = (multiplier * 2) mod 3

if(number == 0)
   print divisible

هذه فكرة عامة...

الآن، دورك هو أن تفهم لماذا هذا صحيح.

ونعم، قم بواجبك المنزلي بنفسك ;)

Answer 6

الفكرة هي أن الرقم يمكن أن ينمو بشكل تعسفي، مما يعني أنه لا يمكنك استخدامه mod 3 هنا، نظرًا لأن رقمك سوف يتجاوز قدرة فئة الأعداد الصحيحة الخاصة بك.

الفكرة هي ملاحظة ما يحدث للرقم.إذا كنت تضيف بتات إلى اليمين، فإن ما تفعله فعليًا هو الانتقال إلى اليسار بمقدار بت واحد وإضافة البت الجديد.

Shift-left هو نفس الضرب في 2، وإضافة البت الجديد يعني إما إضافة 0 أو 1.على افتراض أننا بدأنا من 0، يمكننا القيام بذلك بشكل متكرر بناءً على modulo-3 للرقم الأخير.

last | input || next | example
------------------------------------
0    | 0     || 0    | 0 * 2 + 0 = 0
0    | 1     || 1    | 0 * 2 + 1 = 1
1    | 0     || 2    | 1 * 2 + 0 = 2
1    | 1     || 0    | 1 * 2 + 1 = 0 (= 3 mod 3)
2    | 0     || 1    | 2 * 2 + 0 = 1 (= 4 mod 3)
2    | 1     || 2    | 2 * 2 + 1 = 2 (= 5 mod 3)

---

الآن دعونا نرى ما سيحدث عند إضافة القليل إلى اليسار.أولا لاحظ أن:

2^{2 ن} الوضع 3 = 1

و

2^2ن+1 الوضع 3 = 2

لذا يتعين علينا الآن إضافة 1 أو 2 إلى الوضع بناءً على ما إذا كان التكرار الحالي فرديًا أو زوجيًا.

last | n is even? | input || next | example
-------------------------------------------
d/c  | don't care | 0     || last | last + 0*2^n = last
0    | yes        | 1     || 0    | 0 + 1*2^n = 1 (= 2^n mod 3)
0    | no         | 1     || 0    | 0 + 1*2^n = 2 (= 2^n mod 3)
1    | yes        | 1     || 0    | 1 + 1*2^n = 2
1    | no         | 1     || 0    | 1 + 1*2^n = 0 (= 3 mod 3)
1    | yes        | 1     || 0    | 2 + 1*2^n = 0
1    | no         | 1     || 0    | 2 + 1*2^n = 1

Answer 7

input  "0":       (0)  output 1
inputs "1,0,0":   (4)  output 0
inputs "1,1,0,0": (6)  output 1

لا ينبغي أن يكون هذا الإدخال الأخير 12, ، أم أنني أسيء فهم السؤال؟

Answer 8

في الواقع فإن طريقة LSB ستجعل هذا الأمر أسهل.شركة:

طريقة MSB:

/* 
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_msb(char *input) {
  unsigned value = 0;
  char *p = input;
  if (*p == '1') {
    value &= 1;
  }
  p++;
  while (*p) {
    if (*p != ',') {
      value <<= 1;
      if (*p == '1') {
        ret &= 1;
      }
    }
    p++;
  }
  return (value % 3 == 0) ? 1 : 0;
}

طريقة LSB:

/* 
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_lsb(char *input) {
  unsigned value = 0;
  unsigned mask = 1;
  char *p = input;
  while (*p) {
    if (*p != ',') {
      if (*p == '1') {
        value &= mask;
      }
      mask <<= 1;
    }
    p++;
  }
  return (value % 3 == 0) ? 1 : 0;
}

أنا شخصياً أجد صعوبة في تصديق أن أحدهما سيكون مختلفاً بشكل كبير عن الآخر.

Answer 9

أعتقد أن ناثان فيلمان يسير على الطريق الصحيح للجزء أ وب (باستثناء ب يحتاج إلى جزء إضافي من الحالة:تحتاج إلى تتبع ما إذا كان موضع أرقامك فرديًا أو زوجيًا).

أنا يفكر الحيلة الخاصة بالجزء C هي إلغاء last القيمة في كل خطوة.أي.0 يذهب إلى 0، 1 يذهب إلى 2 و 2 يذهب إلى 1.

Answer 10

يقبل العدد القسمة على 3 إذا كان مجموع أرقامه يقبل القسمة على 3.

لذا يمكنك إضافة الأرقام والحصول على المجموع:

• إذا كان المجموع أكبر أو يساوي 10 استخدم نفس الطريقة
• إذا كان 3، 6، 9 فهو قابل للقسمة
• إذا كان المجموع مختلفًا عن 3، 6، 9 فهو غير قابل للقسمة