Palindromes are cute, but annoying

Palindromes are numbers or strings with a cute property: If you reverse them, they remain the same. For example,

  • 101 is a palindrome.
  • 123 is not a palindrome.
  • hah is a palindrome.
  • haha is not a palindrome.

Reversing a string or integer acts as an intermediate step to check for palindromes. So, it is wise for us to investigate the art of reversing algorithm.

For Python, reversing is easy to handle:

str = "PROGRAMMING ASAP&amp";

print str[::-1]

The code above will print PASA GNIMMARGORP.

When the variable is an integer, Python does it effectively too:

num = 314159
num = str(num)

print num[::-1]

The second line converts the variable type of num from integer to string. Then, we perform it just as before and it will print 951413.

However in C++, there will be more coding to do to tackle reversing. For string,

#include <algorithm>
#include <iostream>
 
using namespace std;
 
int main(){
	string str = "PALINDROME";
	reverse(str.begin(), str.end());
 
	cout << str;
 
	return 0;
}

The code above will print EMORDNILAP.

That doesn’t look much. The challenging one is reverse an integer in C++:

#include <iostream>;
using namespace std;

int main() {
	int num = 271828;

	int rev = 0;
	int tmp = num;
	while(tmp > 0){
		rev = rev*10 + (tmp%10);
		tmp = tmp / 10;
	}

	cout << rev;

	return 0;
}

The variable rev will hold the value of reversed num. To check the correctness of the reversing algorithm above, we must show three things about the loop invariant:

  1. Initialization : It is true prior to the first iteration of the loop.
  2. Maintenance : If it is true before an iteration of the loop, it remains true before the next iteration.
  3. Termination : When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

Initialization : Let j be the number of digit in tmp. Before the first loop iteration, it is true that tmp has j digits with d_1d_2...d_j while rev is empty.

Maintenance : The for loop works by adding a space behind rev and insert the last digit of tmp in it. Then, remove the last digit of tmp. This yield an invariant such that the total number of digit in tmp and rev remains the same.

Termination : After the loop terminates, tmp is d_1d_2...d{j-1} while rev is d_j. After k loop terminations, latex tmp will be d_1d_2...d{j-k} while rev is d_jd_{j-1}...d{j-k+1}. The loop stops when k = j, which means tmp is 0.

Way to check the correctness of loop termination follows Introduction to Algorithm.

Advertisements
Palindromes are cute, but annoying

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s