تحدي برمجي[003][سهل]: كيف تجد الروبوت

  • afaki

هناك روبوت في المستوى الإحداثي الديكارتي يقف عند النقطة (0,0)

اذا علمت ان الروبوت سيتحرك عدد N حركة

في الحركة رقم 1 يتحرك وحدة واحدة إلى اليمين موقعه الجديد هو (1,0)

في الحركة رقم 2 يتحرك وحدتين إلى الأعلى موقعه الجديد هو (1,2)

في الحركة رقم 3 يتحرك ثلاث وحدات إلى اليسار موقعه الجديد هو (-2,2)

في الحركة رقم 4 يتحرك أربع وحدات إلى الأسفل موقعه الجديد هو (-2,-2)

في الحركة رقم 5 يتحرك خمس وحدات إلى اليمين موقعه الجديد هو (3,-2)

وهكذا...

قم بإيجاد موقع الروبوت بعد N حركة


assassinateur أضف ردا

يمكن القيام عبر تفقد هل يقبل القسمة على إثنان وإن كان كذلك هل يقبل القسمة على 4 ومن ثم حساب الاحداثيات

هذه دالة للقيام بالأمر

(بالمناسبة أنت قمت بقلب كتابتك للإحداثيات بالنسبة ل3 و5 فالمفترض العكس)

function  robot(num) {
  if(num % 2 === 0) {
    if (num % 4 === 0) {
      x = num / 2 * -1
      y = num / 2 * -1
    }
    else {
      x = num / 2
      y = num / 2 + 1
    }
  }
  else {
    if (num % 4 === 1) {
      x = Math.ceil(num / 2)
      y = Math.ceil(num / 2 * -1)
    }
    else {
      x = Math.floor(num / 2 * -1)
      y = Math.ceil(num / 2)
    }
  }
  return "for N = " + num + " position is: (" + x + "," + y + ")"
}

مثال حي

assassinateur أضف ردا

رسم بالجافاكسربت يوضع المسار المتبع ورقم المرحلة عند كل محطة

رسم جميل لتتبع المسار، قمت بتعديل بسيط لطابعة الإحداثيات لإستنباط أسهل لخوارزمية الحل

تحسين على الفكرة:

تحتاج لحساب باقي القسمة على الاربعة فقط.

تطبيق:

حل جميل و الاجمل هو ان ال Complexity هي constant يعني O(1)

حلي يعمل في O(n) :3

هل يمكن من فضلك توضيح هذا الحل فلا يبدو لي مسلما

يبدو أنك استعنت بحساب رياضي

هناك نوعان من الحلول

إما أن تأخذ رقما N

تبدأ من الصفر، تقوم بحساب مكانه كل مرة ثم تزيد الرقم وهذا الحل سيستهلك الذاكرة لو كان الرقم كبيرا

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

مثلا إذا كان الرقم زوجيا، ويقبل القسمة على 4 (4، 8، 12، 16...) فسيكون مكانه في الجهة السالبة تماما وتكون إحداثياته هي نصف قيمته

لأستنتج النمط، قمت برسم المسار في ورقة ومددت الرسم إلى المرحلة ال17، ولاحظت نمطا واضحا يتكرر كل 4 مرات، ومنه استخرجت الخوارزمية

هذا الكود يقوم برسم المسار الذي يتبعه الروبوت ومنه تلاحظ النمط