Хамтдаа бодоцгооё №4

M. Munkhbagana

• 2025-04-15

Цуврал нийтлэлээ шимтэн уншдаг та бүхэнтэйгээ дахин уулзахад таатай байна. Бид энэ удаа SPOJ сайтын RGB7 хэсгээс нэгэн сонирхолтой бодлогыг онцолж, түүнийг хэрхэн үр дүнтэй бөгөөд оновчтой байдлаар бодож болох талаар өгүүлэх болно.

Шинэ мэдлэг, шинэ сорилтуудыг хамтдаа судалцгаая.

Энэ удаад сонгож авсан бодлого маань энгийн хэрэгжүүлэлтийн (implementation) ийн бодлого ч гэсэндээ бидэнд хэд хэдэн чухал зүйлсийг ойлгуулах болно. Өмнө үзсэнчлэн эхлээд бид бодлогын өгүүлбэрийн сайтар уншиж ойлгох хэрэгтэй. Бид өгөгдсөн бүхэл (integer) тоог тонгорох буюу хөрвүүлэн хэвлэх ёстой байх нь.

Жишээлбэл :

Оролт : 12344556

Гаралт : 65544321 болох нээ

Хугацаа болон санах ойн хязгаарлалт харгалзан өгөгдсөн ба бүхэл тоон хязгаар өгөгдөөгүй тул бид алгоритмын ажиллах хугацааг урьдчилан тооцоолох боломжгүй байна.

Ингээд бид бодлогын өгүүлбэр болон хязгаарлалтыг уншиж ойлгосон тул өөрсдийн алгоритм аа олох цаг ирлээ.

Алгоритм

1. Тоог авна.
2. Хөрвүүлнэ.
3. Хэвлэнэ.

Тийм ээ маш энгийн харагдаж байгаа биз. Гэхдээ сайн анзаарвал бид хөрвүүлэх үйлдлийг хэрхэн хийх талаараа огтоос дурдсангүй. Үүнээс өмнө бид бүхэл тоон дурын цифрийн утгыг хэрхэн олдог талаар дэлгэрүүлэн тайлбарлая.

Тооны цифрүүдийг хэрхэн олох вэ?

Бид бага ангийн тооны хичээл дээр тоог орон тус бүрээр нь задалж, ойлгодог байлаа. Жишээлбэл, 1234 гэдэг тоог авч үзвэл:

• 4 нь нэгжийн орон
• 3 нь аравтын орон
• 2 нь зуутын орон
• 1 нь мянгатын орон гэсэн бүтэцтэй байна.

Одоо харин бид энэ 1234 гэсэн тооноос зөвхөн нэгжийн орон болох 4-ийг хэрхэн салгаж авч болох вэ? Бидэнд бага ангийн нэг ойлголт тус болно.

Тоог орон тус бүрээр нь задлах буюу:

1234=1*1000+2*100+3*10+4*1 = 1234

гэсэн хэлбэртэйгээр бичиж болно. Эндээс харахад:

• Аравтын орон нь 3, учир нь тэр нь 10-т үржигдсэн байна.
• Нэгжийн орон нь 4, учир нь 1-ээр үржигдсэн байна.

Програмчлалын аргаар хэрхэн олох вэ?

1234 тооноос зөвхөн нэгжийн орныг авахын тулд дараах энгийн үйлдлийг хийж болно:

% буюу modulus оператор нь тоог хуваан үлдэгдэл хэсгийг өгдөг билээ. Тиймээс бид энэхүү оператор ийг ашиглан нэгжийн орныг олж болох нь. 1234 % 10 = 4 өөрөөр хэлбэл бид 1234 тоог 10 -т хуваан үлдэгдлийн аван ашиглах нь.

#include <iostream> // Стандарт сан
using namespace std;

int main() {
    int number = 1234;  // Тоо

    // Тооны нэгжийн орон олох

    int digit = number % 10;

    cout << "Нэгжийн орон: " << digit << endl;  // Гаралт: 4

    return 0;
}

Дээрх жишээ код нь дурын тооны нэгжийн орон буюу төгсгөлийн цифрийг олох билээ. Одоо тэгвэл бид тоог хэрхэн хөрвүүлэх вэ ? Тооны бүх орон (цифр) тус бүрийг салгахын тулд тоог 10-д хуваах (/) ба үлдэгдэл авах (%) аргыг ашиглана. Ингэснээр бид тоог нэг нэгээр нь цифрүүд болгон хөрвүүлж байна гэсэн үг. Салгаж авсан цифрүүдээ 10 аар үржүүлэн нэмсээр байвал эцэст нь бид тоогоо хөрвүүлж дуусна.

Жишээ нь :

1234 = ((4*10 + 3)*10 + 2)*10 + 1 = 4321 болох билээ. Бид нэгжийн орныг хэрхэн тооцоолох оо мэдэх тул энгийн давталт бичээд дээрх үйлдлийг гүйцэтгэж чадах болно.

#include <iostream>  // Стадарт сан
using namespace std;

int main() {
    int num;
    int reversed = 0;
    cin>>num;   // Оролтын утгийг авах

    while (num > 0) {  // Цифр дуустал ажиллана
        int digit = num % 10;               // Нэгжийн орон - г салгаж авна
        reversed = reversed * 10 + digit;   // Урвуу тоог шинэ оронгоор бүтээнэ
        num = num / 10;                     // Дараагийн орон руу шилжих
    }

    cout << reversed << endl;  // Гаралт

    return 0;
}

Жишээ оролт : 123142454

Гаралт : 454241321

Ингээд бид бодлогоо логик боловсруулалт, алгоритмчилах, код бичих, турших гэсэн үндсэн алхмуудын дагуу амжилттай бодож дуусгалаа. Энгийн боловч цаашид маш их ашиглагдах % (modulus) оператор ийг хэрэглэн тоог хөрвүүлэх үйлдэл хийсэн билээ. Харин дараагийн дугаарт уншигч та бүхэндээ илүү сонирхолтой, оюун ухаан сорьсон бодлогын тайлбар хүргэхээр бэлдэж болно.