Codility Ladder javascript - عدم فهم التفاصيل التي تقفز الإجابة من 37 إلى 100٪

1

أحاول حل جميع الدروس حول قابلية البرمجة ، لكنني فشلت في القيام بذلك بشأن المشكلة التالية: سلم حسب قابلية البرمجة

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

لذا ، قبل نشر الرمز ، سأشرح التفكير.

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

الآن ، بعد ذلك ، أخبروا أننا يجب أن نعيد عدد مجموعات التركيبات 2 ^ B [i].

حتى الآن جيد جدًا ، وقررت إرساله دون فار ماكس ، ثم حصلت على درجة 37٪ .. لقد بحثت في جميع أنحاء الإنترنت وكانت النتيجة 100٪ مشابهة لي ولكنهم أضافوا أن max = Math.pow (2،30).

يمكن لأي شخص أن يشرح لي كيف ولماذا يؤثر هذا الحد الأقصى على النتيجة؟

رمز بلدي: 

// Powers 2 to num
function pow(num){
    return Math.pow(2,num);
}
// Returns a array with all fibonacci numbers except for 0
function fibArray(num){
    // const max = pow(30); -> Adding this max to the fibonaccy array makes the answer be 100% 
    const arr = [0,1,1];
    let current = 2;

    while(current<=num){
        current++;
        // next = arr[current-1]+arr[current-2] % max; 
        next = arr[current-1]+arr[current-2]; // Without this max it's 30 %
        arr.push(next);
    }

    arr.shift(); // remove 0
    return arr;

}

function solution(A, B) {
    let f = fibArray(A.length  + 1);
    let res = new Array(A.length);

    for (let i = 0; i < A.length; ++i) {
        res[i] = f[A[i]] % (pow(B[i]));
    }

    return res;
}

console.log(solution([4,4,5,5,1],[3,2,4,3,1])); //5,1,8,0,1 

// Note that the console.log wont differ in this solution having max set or not.
// Running the exercise on Codility shows the full log with all details 
// of where it passed and where it failed.

1 إجابة

3
افضل جواب

حدود معلمات الإدخال هي:

Assume that:

  • L is an integer within the range [1..50,000];
  • each element of array A is an integer within the range [1..L];
  • each element of array B is an integer within the range [1..30].

لذا الصفيف f في fibArray يمكن أن يكون طوله 50،001.

تنمو أرقام فيبوناتشي بشكل كبير. وفقًا لهذه الصفحة ، فإن الرقم 50.000 فيب يحتوي على 10000 رقم.

لا يحتوي جافا سكريبت على دعم مضمن للأعداد الصحيحة الدقيقة التعسفية ، وحتى الزوجي لا يقدم سوى ~ 14 sf من الدقة. حتى مع التعليمات البرمجية المعدلة ، ستحصل على قيم "القمامة" لأي قيمة كبيرة من L . هذا هو السبب في أنك حصلت على 30 ٪ فقط.

ولكن لماذا max ضروري؟ يخبرنا حساب Modulo الرياضيات أن: 

(a + b) % c = ([a % c] + [b % c]) % c

لذلك من خلال تطبيق % max إلى خطوة الحساب التكراري arr[current-1] + arr[current-2] ، كل عنصر في fibArray يصبح رقم Fib المقابل لها max ، دون أي متغير يتجاوز قيمة max (أو أنواع صحيحة مدمجة) في أي وقت : 

fibArray[2] = (fibArray[1] + fibArray[0]) % max = (F1 + F0) % max = F2 % max
fibArray[3] = (F2 % max + F1) % max             = (F2 + F1) % max = F3 % max
fibArray[4] = (F3 % max + F2 % max)             = (F3 + F2) % max = F4 % max
and so on ...
(Fn is the n-th Fib number)

لاحظ أنه مثل B[i] لن يتجاوز 30 أبدًا ، pow(2, B[i]) <= max ؛ لذلك ، منذ ذلك الحين max قابل للقسمة دائمًا pow(2, B[i]) ، تطبيق % max لا يؤثر على النتيجة النهائية.

:مؤلف
مشاركة الرابط

أسئلة ذات صلة

أسئلة شائعة:

علامات السؤال:
algorithm
فوق
قائمة طعام