برخی از مشکلات در برنامه نویسی وضعیت کلاسیک را دارند. به طور معمول، چنین وظایفی به ریاضیات مربوط می شود و آنها علاقه زیادی به سؤال از دانشجویان رشته های علوم کامپیوتر و همچنین جویندگان کار در مصاحبه دارند. آنها خوب هستند زیرا به شما کمک می کنند تا تفکر شما را به شکل برنامه نویسی به خوبی تنظیم کنید و همچنین آن را آموزش دهید. یکی از این مشکلات بررسی اینکه آیا یک رشته یک رشته پالیندروم است یا خیر است و ما در این مقاله قصد داریم آن را بررسی کنیم.
پالیندروم چیست و چرا می توان آنها را جستجو کرد
پالیندروم یک عدد، ترکیب حروف، کلمه یا متنی است که در هر دو جهت یکسان خوانده می شود. به طور خلاصه، پالیندروم را می توان هر مجموعه ای از کاراکترها نامید که در وسط آن متقارن باشد. این کلمه از ریشه یونانی است که به معنای واقعی کلمه "دویدن به عقب" را گرفته است (palin به معنای "دوباره، برگشت" و dromos به معنای "دویدن" است). Palindrome در جاوا به معنای همان معنای عام است. نمونه هایی از پالیندروم ها:- 1881
- aaqquqqaa
- ترکیدن
- ظهر
- مرحله
- روتاتور
- باشگاه من
- خانم من آدم هستم
- حالا آقا جنگ برد!
نمونه کد الگوریتم پالیندروم
بیایید فکر کنیم. رشته، دنباله ای از کاراکترها است، شاید بتوان گفت، آرایه ای از کاراکترها. منطقی ترین آن است که این سکانس را از هر دو طرف تا وسط دنبال کنیم و شخصیت های افراطی را با هم مقایسه کنیم. اگر تا زمانی که به وسط برسیم، همه کاراکترهای ما با هم مطابقت دارند، پس ما یک پالیندروم داریم. بیایید یک روش بولی validPalindrome(String s) ایجاد کنیم تا بررسی کنیم که آیا رشته palindrome است یا خیر. کد جاوا اینجاست: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);
}
}
در روش اصلی، رشتههای پالیندرومیک «سطح»، «باحال»، «خانم» و «اکنون، آقا، یک جنگ برنده شد» را بررسی میکنیم. همانطور که می بینید، اول، سوم و چهارم پالیندروم هستند، اما دومی اینطور نیست. برنامه چه خواهد داد؟
آیا سطح یک پالیندروم است؟ درست است که یک پالیندروم جالب است؟ دروغ آیا خانم پالیندروم است؟ false is Now، آقا، جنگ برنده شد! یک پالیندروم؟ نادرست
بنابراین، اولی یک پالیندروم است، دومی نه. با این حال، اشکال سوم و چهارم چیست؟ چرا نتیجه نادرست است ؟ احتمالاً قبلاً حدس زده اید که نکته این است که برخی از کاراکترهای این رشته با حروف بزرگ و برخی کوچک هستند و برای جاوا 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);
}
}
این بار نتیجه برای ما قابل پیش بینی تر است:
آیا سطح یک پالیندروم است؟ درست است که یک پالیندروم جالب است؟ دروغ آیا خانم پالیندروم است؟ درست است حالا آقا، جنگ برنده شد! یک پالیندروم؟ نادرست
خوب ... دقیقا قابل پیش بینی نیست. اوضاع با «خانم» رو به بهبود است، اما چه اتفاقی برای پالیندروم طولانی و شادمان «حالا، آقا، جنگ برنده شد!». اگر به یاد داشته باشید که تمام فاصله ها و علائم نقطه گذاری مانند حروف جاوا هستند، بسیار آسان است. بنابراین ما باید الگوریتم خود را دوباره بهبود دهیم تا این نادیده گرفتن را اصلاح کنیم. بیایید به برنامه خود بیاموزیم که فاصله ها و علائم نگارشی را نادیده بگیرد. به عبارت ساده، ما همه کاراکترهای غیر الفبایی را نادیده می گیریم. در اینجا برنامه palindrome بهبود یافته در جاوا است.
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);
}
}
نتیجه همان مثال اول است
آیا سطح یک پالیندروم است؟ درست است که یک پالیندروم جالب است؟ دروغ آیا خانم پالیندروم است؟ false is Now، آقا، جنگ برنده شد! یک پالیندروم؟ نادرست
اگر می خواهید، می توانید این برنامه را مانند آنچه در مثال اول انجام دادیم، بهبود ببخشید. برای تقویت آموخته هایتان، پیشنهاد می کنیم یک درس ویدیویی از دوره جاوا ما تماشا کنید
GO TO FULL VERSION