پایگاه دانش علوم کامپیوتر و مهندسی نرم‌افزار - sref.ir

مسئله‌های چالشی برنامه‌نویسی، داده‌ساختارها و الگوریتم‌ها

پل‌های ارتباطی

روش «برعکس کن جمع بزن» خیلی آسونه. یک عدد انتخاب کنید، ارقام آن را برعکس کرده و با عدد اصلی جمع بزنید. اگر عدد حاصله یک عدد دوطرفه (Palindrome) نیست پس مراحل بالا را مجدد تکرار کنید.

عدد دوطرفه عددی است که از هر دو طرف به یک شکل خوانده شود مانند 5، 65256، 41200214 و 7777. به مثال زیر توجه کنید:

195
591
----
786
687
----
1473
3741
----
5214
4125
----
9339

در این مثال عدد 9339 که بعد از چهارمین جمع بدست آمده است یک عدد دوطرفه می‌باشد.

ابتدا تابعی می‌نویسیم که یک عدد صحیح را برعکس کند. از این تابع برای حل مساله اصلی استفاده می‌کنیم. ایده برعکس کردن عدد به جدا کردن ارقام آن عدد برمی‌گردد و می‌دانیم که باقیمانده تقسیم هر عدد بر 10 برابر رقم سمت راست (یکان) آن عدد است لذا با تکرار این عمل می‌توانیم تمام ارقام یک عدد را جدا کنیم. مطلب «برعکس کردن عدد» بطور اختصاصی به این مورد اشاره دارد.

برای تشخیص دوطرفه بودن عدد کافی است در هر مرحله عدد بدست آمده را با برعکسش مقایسه کنیم. برنامه ساده زیر به زبان C++ یک جواب برای مساله فوق است.

#include <iostream>
using namespace std;
int reverse(int n) {
    int m = 0, r;
    while (n > 0) {
        r = n % 10;
        n /= 10;
        m *= 10;
        m += r;
    }
    return m;
}
int main() {
    int n, rev, count = 0;
    cin >> n;
    rev = reverse(n);
    while (rev != n) {
        rev = reverse(n += rev);
        count++;
    }
    cout << count << " " << n;
}