تتمتع بعض المشكلات في البرمجة بحالة المشكلات الكلاسيكية. عادةً ما ترتبط مثل هذه المهام بالرياضيات ويحبذها طلاب تخصصات علوم الكمبيوتر وكذلك الباحثين عن عمل في المقابلات. إنها جيدة لأنها تساعد على إعداد تفكيرك بطريقة برمجية بشكل جيد، بالإضافة إلى تدريبه. إحدى هذه المشاكل هي التحقق مما إذا كانت السلسلة عبارة عن متناظرة أم لا، وسنتناولها في هذه المقالة.
ما هو المتناظر ولماذا تكون قادرًا على البحث عنه
المتناظر هو رقم أو مجموعة حروف أو كلمة أو نص يُقرأ بنفس الطريقة في كلا الاتجاهين. لتلخيص ذلك، يمكن تسمية المتناظر بأي مجموعة من الأحرف المتماثلة في وسطه. الكلمة مأخوذة من جذور يونانية تشتق حرفيًا "الركض للخلف" (بالين تعني "مرة أخرى، رجوع"، ودروموس تعني "الجري".). Palindrome في Java يعني نفس المعنى العام. أمثلة على المتناظرات:- 1881
- aaqquqqaa
- البوب
- وقت الظهيرة
- مستوى
- محور دوار
- ناديي
- سيدتي أنا آدم
- الآن يا سيدي، تم الفوز بالحرب!
مثال على رمز خوارزمية Palindrome
دعونا نفكر. السلسلة عبارة عن سلسلة من الأحرف، كما يمكن للمرء أن يقول، مجموعة من الأحرف. سيكون من المنطقي أكثر اتباع هذا التسلسل من كلا الجانبين إلى المنتصف ومقارنة الأحرف المتطرفة. إذا كانت جميع شخصياتنا متطابقة حتى نصل إلى المنتصف، فسيكون لدينا متناظر. لنقم بإنشاء طريقة منطقية validPalindrome(String s) للتحقق مما إذا كانت String متناظرة. كود جافا هنا:public class PalindromeTest1 {
//method to check if a string is palindrome
public static boolean validPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!"
boolean b1 = validPalindrome(s1);
boolean b2 = validPalindrome(s2);
boolean b3 = validPalindrome(s3);
boolean b4 = validPalindrome(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
في الطريقة الرئيسية، نتحقق من السلاسل المتناوبة "level" و"cool" و"Madam" و"الآن يا سيدي، تم الفوز بالحرب!". كما ترون، الأول والثالث والرابع متناظرون، ولكن الثاني ليس كذلك. ماذا سيعطي البرنامج؟
هل المستوى متناظر؟ صحيح هو بارد متناظرة؟ كاذبة سيدتي متناظرة؟ الكذب هو الآن يا سيدي، لقد تم الفوز بالحرب! متناظرة؟ خطأ شنيع
إذن، الأول متناظر، والثاني ليس كذلك. ولكن ما العيب في الثالثة والرابعة؟ لماذا النتيجة كاذبة ؟ ربما خمنت بالفعل أن النقطة المهمة هي أن بعض الأحرف في هذه السلسلة هي أحرف كبيرة وبعضها صغير، وبالنسبة لـ Java M وm هما حرفان مختلفان. دعونا نحسن البرنامج لأخذ هذا الاختلاف بعين الاعتبار. فيما يلي برنامج للتحقق مما إذا كانت السلسلة عبارة عن متناظرة تحل مشاكل الأحرف الكبيرة والصغيرة.
public class PalindromeTest2 {
//lowercase and uppercase characters should be treated the same:
public static boolean validPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
return false;
}
return true;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!"
boolean b1 = validPalindrome(s1);
boolean b2 = validPalindrome(s2);
boolean b3 = validPalindrome(s3);
boolean b4 = validPalindrome(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
هذه المرة النتيجة أكثر قابلية للتنبؤ بها بالنسبة لنا:
هل المستوى متناظر؟ صحيح هو بارد متناظرة؟ كاذبة سيدتي متناظرة؟ صحيح الآن يا سيدي، تم الفوز بالحرب! متناظرة؟ خطأ شنيع
حسنًا... لا يمكن التنبؤ به تمامًا. الوضع مع "سيدتي" يتحسن، ولكن ماذا عن تناغمنا الطويل والسعيد "الآن يا سيدي، تم الفوز بالحرب!". إنه أمر سهل للغاية، إذا كنت تتذكر أن جميع المسافات ورموز الترقيم هي نفس الحروف في Java. لذلك نحن بحاجة إلى تحسين الخوارزمية لدينا مرة أخرى لتصحيح هذا الخطأ. دعونا نعلم برنامجنا تجاهل المسافات وعلامات الترقيم. ببساطة، نتجاهل جميع الأحرف غير الأبجدية الرقمية. هنا هو برنامج palindrome المحسن في Java.
public class PalindromeTest3 {
//in addition to the above, ignore all non alphanumeric chars like punctuation and spaces
private static boolean isAlphanumeric(char c) {
return Character.isAlphabetic(c) || Character.isDigit(c);
}
public static boolean validPalindromeIgnorePunctuation(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
// skip chars we should ignore
while (j >= 0 && !isAlphanumeric(s.charAt(j))) j--;
while (i < s.length() && !isAlphanumeric(s.charAt(i))) i++;
// overskipped -> nothing left to validate
if (i >= j) return true;
if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
return false;
}
return true;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!";
boolean b1 = validPalindromeIgnorePunctuation(s1);
boolean b2 = validPalindromeIgnorePunctuation(s2);
boolean b3 = validPalindromeIgnorePunctuation(s3);
boolean b4 = validPalindromeIgnorePunctuation(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
على الأقل النتيجة هي ما توقعناه منه:
هل المستوى متناظر؟ صحيح هو بارد متناظرة؟ كاذبة سيدتي متناظرة؟ صحيح الآن يا سيدي، تم الفوز بالحرب! متناظرة؟ حقيقي
ربما، إذا كنت قد بدأت للتو في البرمجة، فمن الصعب عليك فهم كيفية عمل خوارزميات اجتياز السلسلة والمقارنة. بالطبع، من الأفضل التعامل مع هذا، ولكن يمكنك كتابة نسخة مبسطة من المقطع نفسه من خلال مجموعة من الأحرف، والتي هي في الواقع سلسلة. يمكنك استخدام الأسلوب StringBuffer.reverse للتحقق مما إذا كانت السلسلة متناظرة. لنقم بإنشاء الإصدار الأبسط دون التحقق من الرموز غير الأبجدية الرقمية والأحرف الكبيرة والصغيرة.
public class PalindromeTest5 {
public static boolean validPalindrome(String s) {
StringBuffer buffer = new StringBuffer(s);
buffer.reverse();
String data = buffer.toString();
if (s.equals(data)) {
return true;
}
return false;
}
public static void main(String[] args) {
String s1 = "level";
String s2 = "cool";
String s3 = "Madam";
String s4 = "Now, sir, a war is won!";
boolean b1 = validPalindrome(s1);
boolean b2 = validPalindrome(s2);
boolean b3 = validPalindrome(s3);
boolean b4 = validPalindrome(s4);
System.out.println("is " + s1 + " a palindrome? " + b1);
System.out.println("is " + s2 + " a palindrome? " + b2);
System.out.println("is " + s3 + " a palindrome? " + b3);
System.out.println("is " + s4 + " a palindrome? " + b4);
}
}
والنتيجة هي نفسها كما في المثال الأول
هل المستوى متناظر؟ صحيح هو بارد متناظرة؟ كاذبة سيدتي متناظرة؟ الكذب هو الآن يا سيدي، لقد تم الفوز بالحرب! متناظرة؟ خطأ شنيع
إذا أردت، يمكنك تحسين هذا البرنامج كما فعلنا في المثال الأول. لتعزيز ما تعلمته، نقترح عليك مشاهدة درس فيديو من دورة Java الخاصة بنا
GO TO FULL VERSION