محير على مشكلة المنتج palindromic

Question

لقد كنت أتعلم روبي ، لذلك اعتقدت أنني سأحاول يدي في بعض ألغاز Euler. بشكل محرج ، لقد جعلتها فقط للمشكلة 4 ...

المشكلة 4 تذهب على النحو التالي:

يقرأ رقم palindromic نفس كلا الاتجاهين. أكبر palindrome مصنوع من منتج رقمين من رقمين هو 9009 = 91 × 99.

ابحث عن أكبر palindrome المصنوع من منتج اثنين من رقمين من 3 أرقام.

لذلك كنت أحسب أنني سأقوم بتدوين من 999 إلى 100 في حلقة متداخلة وأجر اختبارًا لـ Palindrome ثم أخرج من الحلقات عندما وجدت الأولى (التي يجب أن تكون الأكبر):

final=nil
range = 100...1000
for a in range.to_a.reverse do
  for b in range.to_a.reverse do
    c=a*b
    final=c if c.to_s == c.to_s.reverse
    break if !final.nil?
  end
  break if !final.nil?
end
puts final

هذا يخرج Palindrome 580085 ، ولكن يبدو أن هذا ليس هو أعلى منتج من رقمين من ثلاثة أرقام ضمن النطاق. الغريب ، أن نفس الكود ينجح في إرجاع 9009 ، كما في المثال ، إذا قمت بتغيير النطاق إلى 10 ... 100.

• هل يمكن لأحد أن يخبرني أين أخطأ؟
• أيضا ، هل هناك طريقة أجمل للخروج من الحلقة الداخلية؟

شكرًا

Answer 1

أنت تختبر 999 * (999 ... 100) ، ثم 998 * (999 ... 100)

وبالتالي سوف تختبر 999 * 500 قبل اختبار 997 * 996.

لذا ، كيف نجد هذا الرقم الصحيح؟

لاحظ أولاً أن الضرب يعكس ، A * B == B * A ، لذلك لا تحتاج B من 999 ... 0 في كل مرة ، فقط A ... 0.

عندما تجد palindrone ، أضف العاملين معًا وحفظ المبلغ (احفظ العاملين أيضًا)

داخل الحلقة ، إذا كان (A+B) أقل من المبلغ المحفوظ ، فقم بالتخلي عن الحلقة الداخلية وانتقل إلى آخر A. عندما تنخفض إلى أقل من المبلغ/2 ، لن تكون هناك قيمة مستقبلية يمكن أن تجدها أعلى من القيمة التي وجدتها بالفعل ، لذلك أنت تنتهي.

Answer 2

المشكلة هي أنك قد تجد palindrome لـ a من 999 و أ b من بين 200 ، لكنك تكسر في وقت مبكر جدًا ، لذلك لا ترى أبدًا أن هناك واحدة لـ 998*997 (أرقام مثال فقط).

تحتاج إما إلى البحث عن جميع palindromes أو بمجرد العثور على الأول ، قم بتعيين ذلك b كحد أدنى ملزمة وتستمر في البحث من خلال a عقدة.

Answer 3

فيما يتعلق بالسؤال الثاني ، تتمثل نصيحتي في التعامل مع المشكلة بطريقة أكثر وظيفية من الطريقة الإجرائية. لذا ، بدلاً من الحلقات ، قد تحاول "وصف" مشكلتك وظيفيًا ، وتدع روبي يقوم بالعمل:

• من جميع أزواج الأرقام المكونة من 3 أرقام ،
  • select فقط أولئك الذين يكون منتجهم هو palindrome ،
    • وابحث عن المنتج الأكبر

على الرغم من أن هذا النهج قد لا يسفر عن أكثر الحلول كفاءة ، إلا أنه قد يعلمك زوجين من التعابير الياقوت.

Answer 4

النظر في أرقام p - دعهم يكونون x و y و z. يجب أن يكون P على الأقل 6 أرقام منذ فترة 111111 = 143 × 777-ناتج اثنين من الأعداد الصحيحة المكونة من 3 أرقام. بما أن p هو palindromic:

P=100000x + 10000y + 1000z + 100z + 10y + x
P=100001x + 10010y + 1100z
P=11(9091x + 910y + 100z)

نظرًا لأن 11 عامًا ، فإن أحد الأعداد الصحيحة A أو B على الأقل يجب أن يكون له عامل 11. لذلك إذا لم يكن A -Divisible بحلول 11 ، فإننا نعلم أن B يجب أن يكون. باستخدام هذه المعلومات ، يمكننا تحديد قيم B التي نتحقق منها اعتمادًا على A.

Answer 5

C# التنفيذ:

using System;

namespace HighestPalindrome
{
    class Program
    {
        static void Main(string[] args)
        {
            int i, j;
            int m = 1;
            bool flag = false;

            while (true)
            {
                if (flag) j = m + 1;
                else j = m;

                for (i = m; i > 0; i--)
                {
                    Console.WriteLine("{0} * {1} = {2}", 1000 - i, 1000 - j, (1000 - i) * (1000 - j));
                    j++;

                    //--- Palindrome Check ------------------------------

                    int number, temp, remainder, sum = 0;
                    number = temp = (1000 - i) * (1000 - j);

                    while (number > 0)
                    {
                        remainder = number % 10;
                        number /= 10;
                        sum = sum * 10 + remainder;
                    }

                    if (sum == temp)
                    {
                        Console.WriteLine("Highest Palindrome Number is - {0} * {1} = {2}", 1000 - i, 1000 - j, temp);
                        Console.ReadKey();
                        return;
                    }

                    //---------------------------------------------------
                }

                if (flag)
                    m++;
                flag = !flag;
            }

        }
    }
}

Answer 6

الخطأ هو أنك تفترض أنه إذا وجدت palindrom مع أعظم a القيمة سوف تعطي أكبر منتج ليس صحيحًا. الحل هو الاحتفاظ max_product قيمة وتحديثها مقابل الحل الذي تجده.

Answer 7

يمكنني الإجابة على سؤالك الأول: تحتاج إلى العثور على أعلى منتج ، وليس المنتج الذي يحتوي على أعلى عامل. بعبارات أخرى a * b يمكن أن يكون أكبر من c * d حتى لو c > a > b.

Answer 8

أنت تقسم أول palindrome الذي أتيت إليه ، وليس بالضرورة الأكبر.

قل أن لديك ، ب ، ج ، د ، ه. يمكنك اختبار e * a قبل اختبار d * C.

Answer 9

ar=[]
limit = 100..999
for a in limit.to_a.reverse do
  for b in (100..a).to_a.reverse do
    c=a*b
    if c.to_s == c.to_s.reverse
      palndrm=c 
      ar << palndrm
    end  
  end
end
print ar
print"\n"
puts ar.max
puts ar.min 

Answer 10

التنفيذ:

max = 100.upto(999).inject([-1,0,0]) do |m, a|
  a.upto(999) do |b|
    prod = a * b
    m = [prod, a, b] if prod.to_s == prod.to_s.reverse and prod > m[0]
  end
  m
end
puts "%d = %d * %d" % max

مطبوعات 906609 = 913 * 993

Answer 11

الشيء الرئيسي هو أن تمر بجميع القيم الممكنة. لا تحاول كسر عندما تجد الإجابة الأولى ، فقط ابدأ بأفضل إجابة من الصفر ، ثم جرب جميع المجموعات واستمر في التحديث بشكل أفضل. الشيء الثانوي هو محاولة تقليل مجموعة "جميع المجموعات".

شيء واحد يمكنك القيام به هو الحد من الحلقة الداخلية لقيم أقل من أو تساوي (منذ أب == بأ). هذا يضع القيمة الأكبر للمعادلة الخاصة بك دائمًا في A ويقلل بشكل كبير من عدد القيم التي يجب عليك اختبارها.

for a in range.to_a.reverse do
    for b in (100..a).to_a.reverse do

الشيء التالي الذي يمكنك القيام به هو الخروج من الحلقة الداخلية كلما كان المنتج أقل من أفضل قيمة حالية.

c = a*b
next if c < best

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

for a in range.to_a do
    for b in (100..a).to_a do

تُظهر اختباراتي أنه في كلتا الحالتين تجرب حوالي 405 ألف زوج. إذن ماذا عن التفكير في المشكلة بطريقة مختلفة. ما هو أكبر منتج ممكن من رقمين 3 أرقام؟ 999*999 = 998001 والأصغر هو 100*100 = 10000. ماذا عن أخذ الفكرة التي كانت لديك عن كسر الإجابة الأولى ولكن تطبيقها على نطاق مختلف ، والتي تكون من 998001 إلى 10000 (أو 999*999 إلى 100* 100).

for c in (10000...998001).to_a.reverse do

نصل إلى palindrome بعد 202 اختبار فقط ... المشكلة هي أنها ليست نتاج رقمين من 3 أرقام. لذا يتعين علينا الآن التحقق مما إذا كان palindrome الذي وجدناه هو نتاج من 2 أرقام من رقم 3 أرقام. بمجرد أن نجد قيمة في النطاق الذي يمثل palindrome ومنتج من أرقام مكونة من 3 أرقام. تظهر اختباراتي أننا نجد أعلى palindrome التي تلبي المتطلبات بعد أقل من اختبار 93k. ولكن نظرًا لأن لدينا النفقات العامة في التحقق من أن جميع palindromes إلى هذه النقطة كانت منتجات من رقمين من ثلاثة أرقام قد لا تكون أكثر كفاءة من الحل السابق.

لذلك دعنا نعود إلى التحسن الأصلي.

for a in range.to_a.reverse do
    for b in (100..a).to_a.reverse do

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

نظرًا لأن المنتجات تصبح قطريًا أصغر بواسطة قطري ، يمكنك التوقف بمجرد العثور على رقم palindome. هذا حل فعال حقًا ولكن مع تطبيق أكثر تعقيدًا. اتضح أن هذه الطريقة تجد أعلى palindrome بعد أكثر بقليل من 2200 TRY.

Answer 12

هذا ما توصلت إليه في روبي:

def largest_palindrome_product(digits)
  largest, upper, lower = 0, 10**digits - 1, 10**(digits - 1)

  for i in upper.downto(lower) do
    for j in i.downto(lower) do
      product = i * j
      largest = product if product > largest && palindrome?(product)
    end
  end
  largest
end

وإليك الوظيفة للتحقق مما إذا كان الرقم هو palindrome:

def palindrome?(input)
  chars = input.to_s.chars
  for i in 0..(chars.size - 1) do
    return false if chars[i] != chars[chars.size - i - 1]
  end
  true
end

أعتقد أنه من المحتمل أن يكون هناك حل أكثر كفاءة هناك.

Answer 13

لهذه المشكلة ، لأننا نبحث عن أعلى palindrom ، افترضت أنها ستبدأ بـ 9. وبالتالي ينتهي بـ 9 (palindrom).

إذا كنت تولي اهتمامًا ، للحصول على رقم في 9 ، يمكنك فقط الحصول عليه بأرقام تنتهي بمقدار 9 و 1 و 3 و 3 و 7 و 7.

بعد ذلك ، من غير المجدي التحقق من القيم الأخرى (على سبيل المثال 999*998 لأنها لن تنتهي بـ 9).

ابتداءً من 999 و 991 ، يمكنك بعد ذلك الفرع من 10 إلى 991 ، في محاولة 999 و 981 وما إلى ذلك ... أنت تفعل الشيء نفسه مع 993 و 993 ... 993 * 983 مع 997 * 997 ثم 997 * 987 إلخ. تحتاج إلى الذهاب إلى أبعد من 900 أو 10^4 - 10^3 كما يمكنك التأكد من أن أعلى سيكون من قبل.

int PB4_firstTry(int size)
{
    int nb1 = (int)pow(10.0,size+1.0) - 1, nb2 = (int)pow(10.0,size+1.0) - 1;
    int pal91 = getFirstPalindrome(size,9,1);
    int pal33 = getFirstPalindrome(size,3,3);
    int pal77 = getFirstPalindrome(size,7,7);

    int bigger1 = (pal91 > pal33) ? pal91 : pal33;
    return (bigger1 > pal77) ? bigger1 : pal77;
}

int getFirstPalindrome(int size,int ending1,int ending2)
{
    int st1 =  (int)pow(10.0,size+1.0) - 10 + ending1;
    int comp = st1 - pow(10.0,size);
    int st2 =  (int)pow(10.0,size+1.0) - 10 + ending2;
    int answer = -1;
    while (st1 > comp)
    {
        for (int i = st2; i > comp && st1*i > answer; i-=10)
        {
            if (PB4_isPalindrome(st1*i))
                answer = st1*i;
        }
        st1 -= 10;
    }
    return answer;
}

bool PB4_isPalindrome(int number)
{
    std::string str = intToString(number);
    for (int i = 0; i < (int)(str.length() / 2); i++)
    {
        if (str[i] != str[str.length() - 1 - i])
            return false;
    }
    return true;
}

std::string intToString(int number)
{
    std::ostringstream convert;
    convert << number;
    return convert.str();
}

بالطبع ، هذا يعمل لعوامل 4 أرقام الحجم وما إلى ذلك.