تصف هذه المقالة أطول مشكلة شائعة (LCS) لخوارزميات Java. شاركه للرجوع إليه ، على النحو التالي:
وصف المشكلة: يتم حذف تسلسل معين من تسلسل معين بعد عدة عناصر من التسلسل. أن تكون دقيقة ، إذا تم إعطاؤها التسلسل x = {x1 ، x2 ، ... ، xm} ، فإن تسلسل آخر z = {z1 ، z2 ، ... ، zk} هو تابع x يشير إلى وجود تسلسل ترتيب متزايد بدقة {i1 ، i2 ، ... ، ek} ، من هذا القبيل لجميع j = 1،2 ، ... على سبيل المثال ، التسلسل z = {b ، c ، d ، b} هو تابع للتسلسل x = {a ، b ، c ، b ، d ، a ، b} ، وتسلسل التراجع التزايدي المقابل هو {2،3،5،7}. بالنظر إلى تسللين x و y ، عندما يكون التسلسل الآخر z هو بعد إطار x و y ، يسمى z بعد التسلسل الشائع للسلسلة x و y. A} هو أيضًا إطار شائع لـ x و y. علاوة على ذلك ، فإن الأخير هو واحد من أطول اللوانين الشائعة لـ x و y ، لأن x و y ليس لهما بعد الطول الشائع أكبر من 4. بالنظر إلى تسلفين x = {x1 ، x2 ، ... ، xm} و y = {y1 ، y2 ، ...
تحليل المشكلة: دع x = {a ، b ، c ، b ، d ، a ، b} ، y = {b ، d ، c ، a ، b ، a}. أسهل طريقة لإيجاد أطول فترة شائعة من X و Y هي الطريقة الشاملة. بالنسبة إلى عدة متسلسلات من X ، تحقق مما إذا كان أيضًا بعدًا من Y ، وبالتالي تحديد ما إذا كان هناك بعد شائع لـ X و Y. من خصائص المجموعة ، فإن مجموعة مع عناصر M لها ما مجموعه 2^م إطار مختلف ، لذلك تتطلب الطريقة الشاملة وقت التشغيل الأسي. مزيد من التحلل من خصائص المشكلة ، فإن أطول مشكلة شائعة في الفترة اللاحقة لديها في الواقع خصائص البنية التحتية المثلى.
لنفترض أن أطول فترة شائعة للتسلسلات x = {x1 ، x2 ، ... xm} و y = {y1 ، y2 ، ... yn} هي z = {z1 ، z2 ، ... zk}. ثم هناك:
(1) إذا كان xm = yn ، ثم zk = xm = yn ، و ZK-1 هو أطول فترة شائعة من xm-1 و yn-1.
(2) إذا كان XM! = YN و ZK! = XM ، فإن Z هو أطول فترة شائعة لـ XM-1 و Y.
(3) إذا كان xm! = yn و zk! = yn ، فإن z هو أطول فترة شائعة من x و yn-1.
حيث ، xm-1 = {x1 ، x2 ... xm-1} ، yn-1 = {y1 ، y2 ... yn-1} ، zk-1 = {z1 ، z2 ... zk-1}.
العلاقة العودية: استخدم C [i] [J] لتسجيل طول أطول فترة شائعة للتتابعات XI و YJ. حيث ، xi = {x1 ، x2 ... xi} ، yj = {y1 ، y2 ... yj}. عندما i = 0 أو j = 0 ، يكون التسلسل الفارغ هو أطول فترة شائعة من الحادي عشر و YJ. في هذا الوقت ، c [i] [j] = 0 ؛ عندما i ، j> 0 ، xi = yj ، c [i] [j] = c [i-1] [j-1] +1 ؛ عندما أنا ، j> 0 ، xi! = yj ،
c [i] [j] = max {c [i] [j-1] ، c [i-1] [j]} ، وبالتالي إنشاء العلاقة العودية على النحو التالي:
بناء الحل الأمثل: من التحليل أعلاه ، يمكننا أن نرى أنه للعثور على أطول فترة شائعة من x = {x1 ، x2 ، ... Y. عندما يتم حل XM! = YN ، يجب حل مشكلتين فرعيتين ، أي للعثور على واحدة من أطول التسلسل الفرعي الشائع لـ XM-1 و Y وواحد من أطول التسلسلات الفرعية الشائعة لـ X و YN-1. أطول من هذين اللاعبين الشائعين هو أطول فترة شائعة لـ X و Y. لنفترض أن الصفيف B [i] [J] يسجل قيمة C [i] [J] التي يتم الحصول عليها من المشكلات الفرعية. بدءًا من B [M] [n] ، ابحث في Array B وفقًا لقيمته. عندما B [i] [j] = 1 ، فإن أطول وقت شائع لـ Xi و YJ هو اللاحق الذي تم الحصول عليه عن طريق إضافة Xi إلى ذيل Xi-1 و YJ-1. عندما يكون B [i] [j] = 2 ، فهذا يعني أن أطول فترة شائعة من الحادي عشر و YJ هي نفس الأطول الشائع لـ XI-1 و YJ-1. عندما يكون B [i] [j] = 3 ، أطول وقت شائع لـ Xi و YJ هو نفس الأطول الشائع لـ Xi و YJ-1.
الرمز كما يلي:
حزمة LCS ؛ الفئة العامة lcs {public static int [] [] lcslength (string [] x ، string [] y) {int m = x.length ؛ int n = y.length ؛ int [] [] b = new int [x.length] [y.length] ؛ int [] [] c = new int [x.length] [y.length] ؛ لـ (int i = 1 ؛ i <m ؛ i ++) {c [i] [0] = 0 ؛ } لـ (int i = 1 ؛ i <n ؛ i ++) {c [0] [i] = 0 ؛ } لـ (int i = 1 ؛ i <m ؛ i ++) {for (int j = 1 ؛ j <n ؛ j ++) {if (x [i] == y [j]) {c [i] [j] = c [i-1] [j-1]+1 ؛ ب [i] [j] = 1 ؛ } آخر إذا (c [i-1] [j]> = c [i] [j-1]) {c [i] [j] = c [i-1] [j] ؛ ب [i] [j] = 2 ؛ } آخر {c [i] [j] = c [i] [j-1] ؛ ب [i] [j] = 3 ؛ }}} return b ؛ } lcs static void static (int [] [] b ، string [] x ، int i ، int j) {if (i == 0 || j == 0) return ؛ if (b [i] [j] == 1) {lcs (b ، x ، i - 1 ، j - 1) ؛ system.out.print (x [i] + "") ؛ } آخر إذا (b [i] [j] == 2) {lcs (b ، x ، i - 1 ، j) ؛ } آخر LCS (B ، X ، I ، J-1) ؛ } public static void main (String args []) {system.out.println ("نتائج اختبار wulin.com:") ؛ String [] x = {"" ، "a" ، "b" ، "c" ، "b" ، "d" ، "a" ، "b"} ؛ String [] y = {"" ، "b" ، "d" ، "c" ، "a" ، "b" ، "a"} ؛ int [] [] b = lcslength (x ، y) ؛ system.out.println ("أطول بعد شائع من x و y هو:") ؛ LCS (B ، X ، X.Length - 1 ، Y.Length - 1) ؛ }}نتائج التشغيل:
لمزيد من المعلومات حول خوارزميات Java ، يمكن للقراء المهتمين بهذا الموقع عرض الموضوعات: "بنية بيانات Java وبرنامج تعليمي الخوارزمية" ، "ملخص" Tips Java ".
آمل أن يكون هذا المقال مفيدًا لبرمجة Java للجميع.