خوارزمية لتحديد وجود حل القيم غير السلبية وجود معادلة ديوفانتين الخطية

Question

أنا أبحث عن طريقة لتحديد ما إذا كان هناك حل لمعادلات مثل:3N1 + 4N2 + 5N3 = 456, ، أين N1، N2، N3 هي أعداد صحيحة إيجابية.

أو أكثر عام: هل هناك صفر أو إيجابي أعداد صحيحة N1، N2، N3... أن يحل المعادلة K1N1 + K2N2 + K3N3 ... = م أين K1، K2، K3... و م هي المعدلة الإيجابية المعروفة.

لا أحتاج إلى إيجاد حل - فقط لتحديد ما إذا كان الحل موجودا.

تعديل:

فيما يتعلق بالاستخدام العملي لهذه الخوارزمية:

في مكتبة اتصالات، أريد أن أقرر ما إذا كانت رسالة معينة صالحة وفقا لحجمها، قبل التعامل مع الرسالة. على سبيل المثال: أعرف أن الرسالة تحتوي على عناصر صفرية أو أكثر 3 بايت، عناصر صفر أو أكثر من 4 بايت، وعناصر صفر أو أكثر 5 بايت. تلقيت رسالة من 456 بايت، وأريد تحديد صلاحيته قبل مزيد من تفتيش محتواه. بالطبع يحتوي رأس الرسالة على عدد عناصر كل نوع، لكنني أريد إجراء تفتيش أول في مستوى مكتبة الاتصالات عن طريق تمرير شيء مثل pair<MsgType,vector<3,4,5>>.

Answer 1

أنت تسأل عما إذا كان التعبير العادي

(XXX | XXXX | XXXXX) *

يطابق XX ... X، حيث يحدث X 456 مرة.

إليك حلا في O (n + a ^ 2)، حيث هو أصغر الأرقام الموجودة على الجانب الأيسر (في هذه الحالة 3).

لنفترض أن الأرقام الخاصة بك هي 6،7،15. سأتصل برقم معبر في النموذج 6x + 7Y + 15Z "متاح". أنت للتحقق مما إذا كان رقم معين متاح.

إذا كنت قادرا على الحصول على بعض الأرقام N، فمن المؤكد أنك ستتمكن من الحصول على N + 6، N + 12، N + 18 - بشكل عام، N + 6K لجميع K> = 0. على الجانب الآخر، إذا أنت غير قادر على الحصول على بعض الأرقام n، ثم غير متوفر N-6 بالتأكيد (إذا كنت تستطيع الحصول على (N-6)، ثم (N-6) + 6 = N سيكون متاحا)، وهذا يعني N-12، N-18، N-6K غير متوفر لا.

لنفترض أنك قررت أن 15 متاح ولكن 9 ليس كذلك. في حالتنا، 15 = 6 * 0 + 7 * 0 + 15 * 1 ولكن لن تكون قادرة على الحصول على 9 بأي شكل من الأشكال. لذلك، من خلال المنطق السابق لدينا، يتوفر 15 + 6K لجميع K> = 0 و 9-6K لجميع K> = 0 ليس كذلك. إذا كنت قد حصلت على بعض الأرقام المنقسمة على 6 يعطي 3 كتبقي (3، 9، 15، 21، ...) يمكنك الإجابة بسرعة: الأرقام <= 9 غير متوفرة، والأرقام> = 15 هي.

يكفي لتحديد جميع بقايا القسم الممكنة بنسبة 6 (أي 0،1،2،4،4،5) ما هو أصغر عدد متاح. (لقد أظهرت للتو أن هذا الرقم لبقية 3 هو 15).

كيفية القيام بذلك: إنشاء رسم بياني مع رؤوس 0،1،2،3،4،5. لجميع الأرقام K التي تعطيكها (7،15 - نحن لا نتجاهل 6) إضافة حافة من وزارة الدفاع x إلى (x + k) 6 أعطها الوزن (x + k) div 6. استخدام خوارزمية dijkstra باستخدام 0 كما العقدة الأولية. ستكون المسافات الموجودة في الخوارزمية بالضبط تلك الأرقام التي نبحث عنها.

في قضيتنا (6،7،15) الرقم 7 يؤدي إلى 0 -> 1 (الوزن 1)، 1 -> 2 (الوزن 1)، 2 -> 3 (الوزن 1)، ...، 5 -> 0 (الوزن 1) والعدد 15 يعطي 0 -> 3 (الوزن 2)، 1 -> 4 (الوزن 2)، ...، 5 -> 1 (الوزن 2). أقصر طريق من 0 إلى 3 لديه حافة واحدة - وزنه هو 2. لذلك 6 * 2 + 3 = 15 هو أصغر عدد يعطي 3 كتبل. 6 * 1 + 3 = 9 غير متوفر (حسنا، فحصنا ذلك من قبل اليد).

وما هو الاتصال التعبيرات العادية؟ حسنا، كل تعبير منتظم يحتوي على Automaton المحدود المكافئ، وقد شيدت أحدهم.

هذه المشكلة، مع استعلامات متعددة المسموح بها، ظهرت على أولمبياد البولندية وأرجم الحل. الآن، إذا سمعت الآن شخصا يقول علوم الكمبيوتر غير مفيد للمبرمجين الحقيقيين، فاللغاء في وجهه.

Answer 2

بالنسبة الى هذه, ، إذا كان أعظم عامل مشترك من {n1، n2، n3، ...} ليس مقسما مي ثم ليس لديك أي حل. تظهر هذه الصفحة مثالا على {n1 و n2} فقط ولكنها تمتد إلى أنظمة أكبر. المشكلة الجديدة تكتب خوارزمية لإيجاد أكبر عامل مشترك، ولكن هذا تافهة في ضوء المشكلة الأصلية.

ستجد جزء من خوارزمية الخاص بك GCF ({n1، n2، ...}) ثم معرفة ما إذا كان ذلك عامل م. إذا لم يكن كذلك، فلا يوجد حل. هذا لا يظهر بالكامل أن الحل موجود، ولكن يمكن أن يوضح لك بسرعة أنه لا يزال لا يزال مفيدا.

Answer 3

يبدو أنك تتحدث عن نظام عدم المساواة مع القيود الصحيحة. الحقيقة هي أنك حل لهذا النظام:

k1n1+k2n2+k3n3...=m
n1 >= 0
n2 >= 0
n3 >= 0

والقيد الإضافي الذي يعد N1، N2، N3 أعداد صحيحة. هذا البرمجة الخطية مشكلة. لسوء الحظ بالنسبة لك، الحالة العامة لحل مثل هذا النظام القيود الصحيحة هي NP كاملة. وبعد ومع ذلك، هناك العديد من الخوارزميات التي سوف تحلها من أجلك.

Answer 4

هذا يرتبط مشكلة عملة فروغريوس, ، والتي لم تم حلها ل n> 3.

Answer 5

نهج القوة الغاشمة (pseudocode):

def a = 3
def b = 4
def c = 5
def x = 456

for n1 = a to int(x / a) + 1 step a
  for n2 =b to int(x / b) + 1 step b
    for n3 = c to int(x / c) + 1 step c
      if a * n1 + b * n2 + c * n3 = x then
        print n1, n2, n3

أنظر أيضا http://mail.python.org/pipermail/python-list/2000-april/031714.html.

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

Answer 6

إليك شيء في حالة الرقم 2. أنا لم أحسب بعد كيفية توسيع نطاقها:

نظرا 2 أعداد صحيحة رئيسية نسبيا X و Y، هناك أعداد صحيحة إيجابية A و B بحيث ax+by=c للجميع c>=(x-1)(y-1)

في الأساس، هذا يعمل لأنه، إذا افترضت x<y, ، يمكنك التعبير عن جميع الأعداد الصحيحة MOD X مع (0، Y، 2Y، 3Y، ...، (X-1) Y). الآن، عن طريق إضافة بعض المضاعف الإيجابي X، يمكنك الوصول إلى جميع الأعداد الصحيحة بين [(x-1) (y-1)، (x-1) y]، مثل جميع الأعداد الصحيحة بين (x-1) (y- 1) و (X-1) تم التعبير عن Y-1 سابقا.

1. GCD (X، Y). إذا كان C ليس متعددة، فارجع خطأ.
2. إذا GCD (X، Y)> 1، قسم X، Y، C من GCD
3. إذا C> (X-1) (Y-1)، فارجع True
4. أخرى قوة الغاشمة

وبالنسبة للقوة الغاشمة:

if int(c/y) >= c*y^(-1) mod x, return true, 
else return false

Answer 7

ربما المعلومات التالية غير ذات صلة، لأنه لا يتعامل مع الوضع العام، ولكن ...

إذا كانت المشكلة هي تحديد ما إذا كان يمكن تشكيل عدد صحيح موجب مسبقا ك Sum 3*n1 + 4*n2 + 5*n3, بالنسبة للأعداد الصحيحة غير النظيفة N1، N2، N3، ثم الجواب هو "نعم"، ل K> = 3.

الكتاب المدرسي المعروف روزن الرياضيات المنفصلة وتطبيقاتها, ، ص. 287 من الطبعة السادسة، يثبت أن "كل مبلغ من البريد من 12 سنتا أو أكثر يمكن تشكيلها باستخدام طوابع 4 سنت فقط و 5 سنت،" باستخدام الحث.

الخطوة الأساسية هي أن البريد الذي يبلغ من العمر 12 سنتا يمكن تشكيله بأربع طوابع من أربع سنتات.

ترى خطوة التعريفي أنه إذا كان P (K) صحيحا باستخدام الطوابع التي أربع سنتات، فما عليك سوى استبدال ختم أربعة سنت مع ختم من خمسة المائة لإظهار أن P (K + 1) صحيح. إذا كان P (K) صحيحا باستخدام طوابع بدون أربع سنتات، إذن، لأن K> = 12، نحتاج إلى ما لا يقل عن 3 طوابع خمسة في المائة لتشكيل مجموعنا، ويمكن استبدال 3 طوابع خمسة في المائة بأربع سنت الطوابع لتحقيق K + 1.

لتمديد الحل المذكور أعلاه لهذه المشكلة يتطلب فقط النظر في عدد قليل من الحالات.