الخلايا المملوءة
المقارنات
الأطول حتى الآن

  • قيد الملء
  • يُقرأ منها
  • الإجابة

مزيد عن أطول متتالية جزئية متزايدة

أطول متتالية جزئية متزايدة (LIS)

في قائمة من الأعداد، كم عددًا يمكنك أن تختار مع الحفاظ على ترتيبها، بحيث يكون كل عدد أكبر من الذي قبله؟ أطول متتالية جزئية متزايدة تجيب عن ذلك. اكتب قائمة وشاهد البرمجة الديناميكية تحسب، لكل موضع، أطول سلسلة تنتهي عنده. اضغط «تشغيل» لمشاهدة الجدول وهو يمتلئ، أو «خطوة» و«رجوع» للتقدم خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع. اكتب قائمة من الأعداد. يحفظ الجدول لكل موضع طول أطول سلسلة متزايدة من القيم تنتهي عنده، والموضع السابق الذي تكمله هذه السلسلة. حدّد خانة «السماح بالقيم المتساوية» للحصول على سلاسل لا تنزل أبدًا. في النهاية تُقرأ السلسلة رجوعًا من قيمتها الأخيرة. «مثال جديد» ينشئ قائمة أخرى. عند تحديد اللوحة، تتقدم مفاتيح الأسهم خطوة، ويشغّل مفتاح المسافة ويوقف مؤقتًا، وينتقل Home وEnd إلى البداية والنهاية.

كيف يعمل

  1. اكتب قائمة من الأعداد مفصولة بفواصل أو مسافات. حدّد خانة «السماح بالقيم المتساوية» للحصول على سلاسل لا تنزل أبدًا.
  2. اضغط «تشغيل»، أو استخدم «خطوة» و«رجوع» للتقدم خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع.
  3. شاهد مقارنة كل موضع بكل موضع قبله، ثم شاهد أطول سلسلة وهي تُقرأ رجوعًا باللون البرتقالي.

كيف يعمل الجدول

للجدول ثلاثة صفوف: القيم، وطول أطول متتالية جزئية متزايدة تنتهي عند كل موضع، والموضع الذي تكمله. القيمة وحدها سلسلة طولها 1. ثم يُفحص كل موضع سابق: إذا كانت قيمته أصغر، أمكن مدّ السلسلة المنتهية عنده بهذه القيمة، فيصبح الطول أكبر من طولها بواحد. يفوز أطول امتداد من هذا النوع، ويُكتب موضعه في الصف الثالث.

قراءة السلسلة رجوعًا

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

الأسئلة المتداولة

ما الفرق بين المتتالية الجزئية والمصفوفة الجزئية؟

المصفوفة الجزئية كتلة من القيم المتجاورة. أما المتتالية الجزئية فتحافظ على الترتيب لكنها قد تتخطى قيمًا، ففي 3, 10, 2, 1, 20 تشكّل القيم 3, 10 و20 متتالية جزئية متزايدة رغم وجود 2 و1 بينها.

ما سرعة خوارزمية LIS؟

طريقة الجدول تقارن كل زوج من المواضع: n·(n − 1)/2 مقارنة لـ n من القيم. أما فرز الصبر فينجز ذلك في O(n log n): فهو يحفظ لكل طول أصغر قيمة تنهي سلسلة بذلك الطول، ويضع كل قيمة جديدة في مكانها بالبحث الثنائي.

هل أطول متتالية جزئية متزايدة وحيدة؟

ليس دائمًا. في 1, 3, 2, 4 طول كل من 1, 3, 4 و1, 2, 4 هو 3. الجدول يعطي الطول، والقراءة رجوعًا تجد إحداهما.

أين تُستخدم أطول متتالية جزئية متزايدة؟

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

هل يُرسل أي شيء إلى أي مكان؟

لا. كل شيء يُحسب في متصفحك، وتبقى آخر إعداداتك في التخزين المحلي لهذا المتصفح.

هل أنت مستعد لتجربتها؟

افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.

الانتقال إلى المحرر