المتداول حول الأرقام الجارية

Question

أقوم بترقيم الملفات التي تم إنشاؤها برقمين من 00 إلى 99 وأريد الاحتفاظ بآخر 50.يجب أن تخبرني الخوارزمية برقم الملف الحالي الذي أنا على وشك حفظه وأي الملفات السابقة يجب إزالتها.

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

1. طالما أن هناك أقل من 5 ملفات، يمكننا فقط إضافة الملفات.يتم تمثيل هذا في الكتلة الأولى أدناه.
2. بمجرد وجود 5 ملفات سابقة، يجب حذف الملف الأقدم.وهذا أمر تافه طالما أننا لم نصل إلى الحد الأقصى للعدد، هنا 9.يتم تمثيل هذا في الكتلة الثانية أدناه.
3. بمجرد الوصول إلى أعلى الأرقام، يجب أن يتم الترقيم، وهنا تصبح الأمور صعبة.انظر الكتلة الثالثة أدناه.

__prev__    __curr__   __drop__  
<no files>     0         null
0              1         null
0 1            2         null
0 1 2          3         null
0 1 2 3        4         null

0 1 2 3 4      5          0 
1 2 3 4 5      6          1
2 3 4 5 6      7          2
3 4 5 6 7      8          3
4 5 6 7 8      9          4

5 6 7 8 9      0          5
6 7 8 9 0      1          6
7 8 9 0 1      2          7
8 9 0 1 2      3          8
9 0 1 2 3      4          9

بعض التعليمات البرمجية الزائفة لتوضيح التقدم الذي أحرزته:

if length(prev) < 5
   curr = length(prev)
   drop = null

else

if 9 not in prev
   curr = (1+max(prev)) mod(10)
   drop = curr-5

if 9 in prev

...وهذا هو المكان الذي أنا عالقة فيه.لقد جربت طرح 10 من كل عنصر prev.

أنا متأكد من أن الأمر تافه وأنه سيصدمني عندما لا أتوقعه على الإطلاق.لدي أيضًا شعور مزعج بأنني سأجد تعبيرًا يعمم كلتا الحالتين (مع وبدون max في prev).

Answer 1

ما كنت تحاول تنفيذه هو بنية بيانات ذات حجم ثابت يدخل أولاً يخرج أولاً (FIFO)، والتي تسمى عادةً طابور دائري, أو مخزن مؤقت دائري أو مخزن مؤقت دوري أو مخزن مؤقت حلقي.

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

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

كما هو الحال مع التعليمات البرمجية الخاصة بك، يجب علينا استخدام تقنية modulo.فيما يلي تطبيق Javascript بسيط ويعمل بشكل كامل.يتم تشغيل كل من عملية التشغيل والتحديث $O(1)$.

// From 0 to limit-1 are all usable numbers.
// At any moment, at most maximumKept numbers can be retained.
// For example, if we use 00-99 to parametrize names of at most 50 files,
// we should use createCircularQueue(100, 50).
function CreateCircularQueue(limit, maximumKept) {
    this.limit = limit;
    this.kept = maximumKept;

    this.count = 0;  // count of all numbers ever used.

    // return the number to remove and the next available number.
    this.get = function () {
        if (this.count <= this.kept - 1) {
            return [null, this.count];
        }
        else {
            const next = this.count % this.limit;
            let toRemove = next - this.kept;

            return [toRemove + ((toRemove >= 0) ? 0 : this.limit), next];
        }
    };

    this.update = function () {
        this.count += 1;  // this will NOT overflow before 2**53-1=9007199254740991.
    }

}

---

يعمل التنفيذ أعلاه مع جميع أزواج الأعداد الصحيحة الممكنة Limit >= MaxKept.على وجه الخصوص، فإنه يعمل حتى لو كان الحد الأقصى.

هنا عينة من الاستخدام:

function myLog(wantedNumbers) {
    console.log("number to remove: " + wantedNumbers[0]
        + "    next number to use: " + wantedNumbers[1])
}

let cq = new CreateCircularQueue(5, 3);
myLog(cq.get());
cq.update();
myLog(cq.get());
cq.update(); cq.update();
myLog(cq.get());
cq.update();
myLog(cq.get());
cq.update(); cq.update();
myLog(cq.get());

Answer 2

من المضحك كيف أن شرح المشكلة يجعلك تتعامل معها بشكل مختلف (بطة مطاطية, ، أي واحد؟).

أعتقد أنني تمكنت من تجميع السلوك الذي أبحث عنه.الفكرة هي أنه إذا كانت القائمة تحتوي على الرقم الأخير (أي. n-1, ، هنا 9)، n يضاف إلى كل عدد أكبر من n/2.

الآن، جافا سكريبت ليست لغتي الأولى بالتأكيد، لذا يرجى أن تكون لطيفًا وتحاول رؤية الفكرة بدلاً من الفوضى التي تسببها لغة js الخاصة بي ...

العب بها هنا أو مجرد إلقاء نظرة على العرض أدناه.بالطبع سأكون ممتنًا للحل الأفضل.

function roll(n) {
  const half = n/2 ;
  const last = n-1 ;
  var iter = half * 3 ;
  var prev = [] ;
  var curr = null ;
  var drop = n ;
  var temp ;

  while(iter--) {
    console.log(prev) ;
    curr = prev.length ;
    if (curr < half) {
      prev = update(prev,curr,drop) ;
      continue ;
    }
    temp = [].concat(prev) ;
    if (temp.includes(last)) {
      for (var t=0 ; t<temp.length ; t++) {
        if (temp[t] < half)
          temp[t] += n ;
      }
    }
    drop = Math.min.apply(null, temp) % n ;
    curr = Math.max.apply(null, temp) + 1 ;
    curr %= n ;
    prev = update(prev,curr,drop) ;
  }
}

function update(p,c,d) {
  for (var i=0 ; i<p.length ; i++) {
    if (p[i] == d)
      p.splice(i,1) ;
  } 
  p.push(c) ;
  return p ;
}

roll(10) ;

Answer 3

يعد سلوك الدالة modulo في العديد من لغات البرمجة غريبًا بعض الشيء، وقد يعتمد على إشارة الوسيط.ومع ذلك، إذا قمت بالحساب $أ \bmod ب$ للإيجابية $أ،ب$, ، سوف تحصل على إجابة في النطاق $0،\ldots،b-1$.

لنفترض الآن أننا نريد حساب الفرق $x-y \pmod{b}$, ، وهدفنا هو الحصول على إجابة في النطاق $0،\ldots،b-1$.يمكننا أن نفترض ذلك $x,y$ هم في نفس النطاق.لو $ص> س$, ، ثم $x - ص $ ستكون سلبية، وبالتالي قد نحصل على إجابة سلبية.ولمنع ذلك، يمكننا الحساب $x + (ب-ص)$ بدلاً من.هذا سوف يعطي دائما الإجابة الصحيحة.