طريقة للتحقق مما إذا كانت أرقام Num1 هي الأرقام في Num2 دون التحقق من كل رقم؟
https://stackoverflow.com/questions/567165
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
دعنا نقول أنني خمنت رقم اليانصيب من:
1689
والطريقة التي يعمل بها أعمال اليانصيب، لا يهم ترتيب الأرقام طالما أن الأرقام تتطابق مع 1: 1 مع الأرقام في رقم اليانصيب الفعلي الفائز.
لذلك، سيكون الرقم 1689 رقم اليانصيب الفائز مع:
1896، 1698، 9816، إلخ ..
طالما كان كل رقم في تخمينك موجودا في الرقم المستهدف، فأنت تفوز في اليانصيب.
هل هناك طريقة رياضية يمكنني القيام بذلك؟
لقد قمت بحل هذه المشكلة مع حلقات o (n ^ 2) التحقق من كل رقم مقابل كل رقم من رقم اليانصيب الفائز (فصلها باستخدام المعد). وهو ما يرام، إنه يعمل ولكن أريد أن أعرف ما إذا كان هناك أي حيل الرياضيات أنيق يمكنني القيام به.
على سبيل المثال، في البداية ... اعتقدت أنني يمكن أن أكون صعبا وتلقى مجموع المنتج والمنتج لكل رقم في كلا الأرقام وإذا كنت تتوافق ثم فزت.
^ هل تعتقد أن هذا سيعمل؟
ومع ذلك، قمت بدعورته بسرعة هذا عندما وجدت أن اليانصيب تخمين: 222، و 124 لديهم أرقام مختلفة ولكن نفس المنتج والمجموع.
أي شخص يعرف أي حيل الرياضيات التي يمكنني استخدامها لتحديد ما إذا كانت الأرقام في Num1 تطابق الأرقام في Num2 بغض النظر عن النظام؟
المحلول
ماذا عن الذهاب من خلال كل رقم، وعد عدد مظاهر كل رقم (إلى صفيفين مختلفين عن العنصر)؟ بعد أن فعلت المجموع، قارن عدد من كل رقم. نظرا لأنك تنظر فقط إلى كل رقم مرة واحدة، فهذا هو (ن).
الرمز سوف يبدو شيئا مثل:
for(int i=0; i<digit_count; i++)
{
guessCounts[guessDigits[i] - '0']++;
actualCounts[actualDigits[i] - '0']++;
}
bool winner = true;
for(int i=0; i<10 && winner; i++)
{
winner &= guessCounts[i] == actualCounts[i];
}
أعلاه الرمز يجعل الافتراض أن SimDigits و ActualDigits كلاهما سلاسل سحر؛ إذا احتفظوا بالأرقام الفعلية، فيمكنك فقط تخطي - '0' اعمال.
ربما هناك تحسينات من شأنها أن تجعل هذا يأخذ مساحة أقل أو إنهاء عاجلا، لكنه مثال مباشر للغاية لنهج O (ن).
بالمناسبة، كما ذكرت في تعليق، فإن مقارنة الضرب / المبلغ بالتأكيد لن تعمل بالتأكيد بسبب الأصفار. النظر في 0123 و 0222. المنتج هو 0، مجموع هو 6 في كلتا الحالتين.
نصائح أخرى
انقسام إلى صفيف، صفيف الفرز، انضم إلى سلسلة، مقارنة السلاسل.
(وليس خدعة الرياضيات، وأنا أعلم)
يمكنك وضع الأرقام في صفيف، فرز الصفيف، ثم قارن عنصر الصفوف حسب العنصر. هذا سيمنحك تعقيد O (NLGON) أفضل من O (N ^ 2).
إذا كان N يمكن أن يصبح كبيرا، فرز الأرقام هو الجواب.
لأن الأرقام 0..9 يمكنك حساب عدد تكرارات كل رقم من إجابة اليانصيب في صفيف [0..9].
للمقارنة، يمكنك طرح 1 لكل رقم يواجهه في تخمين. عندما تواجه رقما الرقم حيث يكون العد بالفعل 0، فأنت تعرف التخمين مختلفا. عندما تحصل من خلال جميع الأرقام، فإن تخمين هو نفسه (طالما أن التخمين لديه أكبر عدد ممكن من الأرقام وجواب اليانصيب).
لكل رقم D يتضاعف مع رقم (D + 1)
هذا هو أكثر الرياضية ولكن أقل كفاءة من الأساليب الفرز أو دلو. في الواقع هي طريقة دلو في تمويه.
كنت فرز كل من أرقام العدد ومقارنتها.
إذا كنت تعامل فقط مع 4 أرقام، فأنا لا أعتقد أن عليك أن تضع الكثير من الخوارزمية التي تستخدمها. سوف جميعهم جميعا تقريبا نفس الشيء.
أيضا 222 و 124 لا تملك نفس المبلغ
عليك أن تنظر في أنه عندما يكون N صغيرا، فإن ترتيب الكفاءة غير ذي صلة، ويبدأ الثوابت في المسألة أكثر. كيف كبيرة يمكن أن تحصل أعدادك في الواقع؟ يمكنك الحصول على ما يصل إلى 10 أرقام؟ 20؟ 100؟ إذا كانت الأرقام الخاصة بك لديها مجرد عدد قليل من الأرقام، n ^ 2 حقا ليست سيئة. إذا كان لديك سلاسل من الآلاف من الأرقام، فقد تحتاج فعليا إلى القيام بشيء أكثر ذكاء مثل الفرز أو التواء. (أي عد 0S، عد 1S، إلخ)
أنا أسرق الجواب من Yuliy، و Starblue (upvotefe لهم)
Bucketing هو الأسرع بصرف النظر عن O (1)
lottonumbers == mynumbers;
الفرز O (NLOG2N)
Bucketsort هي خوارزمية O (ن).
لذلك كل ما عليك فعله هو أن تفعل ذلك مرتين (مرة واحدة لأرقامك، مرة واحدة للمجموعة المستهدفة)، وإذا أضف أرقام الأرقام، فإنها تتطابق معها. أي نوع من الفرز هو العلبة العامة الإضافية غير ضرورية في هذه الحالة.
array[10] digits;
while(targetnum > 0)
{
short currDig = targetnum % 10;
digits[currDig]++;
targetnum = targetnum / 10;
}
while(mynum > 0)
{
short myDig = mynum % 10;
digits[myDig]--;
mynum = mynum / 10;
}
for(int i = 0; i < 10; i++)
{
if(digits[i] == 0)
continue;
else
//FAIL TO MATCH
}
ليس أجمل رمز، سوف أعترف.
إنشاء مجموعة من 10 أعداد صحيحة تم نقلها [0 .. 9].
تهيئة كل عنصر لعدد رئيسي مختلف
تعيين المنتج إلى 1.
استخدم كل رقم من الرقم، إلى التركيز في الصفيف، وسحب الرقم الأول، وضرب المنتج به.
هذا يمنحك تمثيلا فريد من نوعه وهو أمر محدد.
قم بنفس الإجراء للرقم الآخر.
إذا تطابق الممثل الفريد، فإن الأرقام الأصلية تطابق.
إذا لم تكن هناك أرقام متكررة مسموح بها (غير متأكد من أن هذا هو الحال، فاستخدم رقم ثنائي 10 بت. يمثل الأهم قليلا من الرقم 9 ويمثل LSB الرقم 0. العمل من خلال كل رقم بدوره وقلب قليلا لكل رقم تجده
لذلك 1689 سيكون: 1101000010
و 9816 سيكون أيضا: 1101000010
ثم XOR أو طرح سيغادر 0 إذا كنت فائزا
هذا هو مجرد شكل بسيط من الدواء
فقط للمتعة، والتفكير خارج المعتاد، بدلا من الفرز وغيرها من الطرق، قم بحذف شيء. إذا كانت هذه النتائج فارغة، فستكون لديك فائز!
Dim ticket As String = "1324"
Dim WinningNumber As String = "4321"
For Each s As String In WinningNumber.ToCharArray
ticket = Replace(ticket, s, "", 1, 1)
Next
If ticket = "" Then MsgBox("WINNER!")
If ticket.Length=1 then msgbox "Close but no cigar!"
هذا يعمل مع الأرقام المتكررة أيضا ..
فرز الأرقام قبل تخزين عدد. بعد ذلك، ستكون أرقامك متساوية.
حل لطيف لطيف هو استخدام متغير zobrist hashing.. وبعد (نعم، أعرف أنها مبالغة، وكذلك الاحتمال، ولكن مهلا، إنها "ذكية".)
تهيئة صفيف عشرة العنصر a[0..9] للأعداد الصحيحة عشوائي. ثم، لكل رقم d[], ، حساب مجموع a[d[i]]. وبعد إذا كانت الأرقام تحتوي على نفس الأرقام، فستكون الأرقام الناتجة متساوية؛ مع احتمال كبير (~ 1 في عدد الإمكانات الموجودة هناك)، العكس هو الصحيح كذلك.
(إذا كنت تعرف أنه سيكون هناك ما مجموعه 10 أرقام 10 أرقام، فيمكنك استخدام الأرقام الثابتة 1، 10، 100، ... بدلا من الأرقام العشوائية لنجاح مضمون. هذا هو فرز دلو في عدم تمويه غير للغاية. في
