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

M. Munkhbagana

• 2025-02-04
• competitive programming

Өмнөх нийтлэлд бид “Competitive Programming-ийг Эхлэх нь” сэдвийн дагуу эхлэхээс өмнө юуг анхаарах талаар дурдсан бол энэ удаад бодлого бодох явцыг жишээ бодлогоор дэлгэрэнгүй тайлбарлалаа.

Бидний сонгож авсан бодлого бол SPOJ сайт дахь RGB7 цувралын хамгийн эхний бодлого болох RGB7002 – Гурвалжин юм.

SPOJ (Sphere Online Judge) нь олон улсын онлайн програмчлалын бодлого бодох платформ бөгөөд алгоритм, өгөгдлийн бүтэц, математик, динамик программчлал зэрэг сэдвүүдээр олон мянган бодлого агуулсан байдаг. Энэхүү платформ нь программчлалын ур чадвараа хөгжүүлэхийг хүссэн сурагч, оюутан, мэргэжилтнүүдэд нээлттэй.

SPOJ RGB7 нь spoj.com сайтын дотоод хэсэг бөгөөд Монгол инженерүүдийн зохиосон болон орчуулсан бодлогуудын цуглуулга юм. Энэ хэсэг нь Монгол хэл дээрх бодлогуудыг багтаасан тул Монгол хэлээр суралцаж буй сурагч, оюутнууд өрсөлдөөнт програмчлалын ур чадвараа хөгжүүлэхэд илүү хялбар болгодог. Цаашид бид энэхүү сайтаас бодлого бодох болно.

1. Эхлээд өгүүлбэрээ унших.

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

2. input буюу оролтын хэсгийг унших.

Энэ хэсэгт нь бид  бодлогыг бодоход ямар өгөгдөл ашиглах талаар анхны ойлголтыг авах болно. 

Өгөгдлийн дагуу бид бүхэл тоон утгатай гурван талын уртыг ашиглан гурвалжны периметрийг олох болно.

3. output буюу гаралтын хэсгийг унших.

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

4. Жишээ тестийг харах.

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

Энэхүү жишээн дээр гурвалжны талууд 3,4,5 гэж өгөгдсөн ба бидний илгээх хариулт 12 буюу түүний периметрийн утга байна.

5. Хугацааны хязгаар болон файлын хэмжээг харах.

Энэхүү бодлогын хугацааны хязгаар нь 1 секунд байна. Энэ нь ихэнх онлайн системд ойролцоогоор 1,000,000–10,000,000 үйлдэл хийх боломжтой гэсэн үг. Тиймээс бид энэхүү хязгаараас хэтрэхгүй, аль болох бага үйлдлээр бодлогоо бодох шаардлагатай.

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

6. Одоо алгоритмаа олцгооё.

Энэ алхмаас эхлэн бид бодлогоо бодох үндсэн шат руу орно. Асуудлыг шийдэх явцын 80% нь энд л явагдана. Өгөгдсөн асуудлыг дэд хэсгүүдэд хуваах нь хамгийн сайн арга юм.

Эхлээд бид гурвалжны 3 тал буюу 3 бүхэл тоог өгөгдөл болгон авах талаар ойлголттой болсон билээ. Тэгэхээр эхний алхам бол гурвалжны талыг зөв аван, шаардлагатай мэдээллийг тодорхойлох бөгөөд энэ нь бидний шийдлийн суурь болно.

• Гурвалжны талыг тодорхойлох
• Периметрийг тооцоолох :

  • Гурвалжны периметрийг тооцоолох нь маш энгийн бөгөөд энэ бол гурван талын уртыг нэмэх үйлдэл юм:

    P=a+b+c

  • Энд:

    • a, b, c нь гурвалжны 3 талын урт юм.
• Гаралтын утгыг хэвлэх : :
  • Энэ хэсэгт тооцоолсон олсон периметрийн утга буюу P -г хэвлэх болно.

7. Кодын хэсэг.

Одоо бид зохиосон алгоритмын дагуу код оо бичих ёстой билээ. Бид програмчлалын хэлээр C++ ийг сонгосон ба та өөрт тохирох хэлийг хэрхэн сонгох талаар “Competitive programming – д тохиромжтой хэлийг хэрхэн сонгох вэ? “ нийтлэлээс дэлгэрэнгүй уншаарай.

#include <iostream>  // Толгой сан
using namespace std;
int main()
{
    int a,b,c,p;  // Ашиглагдах хувьсагчдыг зарлав.
    cin>>a>>b>>c; // Оролтын хэсэг
    p = a + b + c; // Бодолт
    cout<<p<<endl; // Гаралтын хэсэг
    return 0;
}

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

8. Тестээр турших.

Бидэнд өгөгдсөн жишээ тестийг өөрсдийн бодолтон дээр туршин үзэн зөв эсэхийг шалгах хэрэгтэй.

Бичсэн кодоо ажлуулан жишээ оролтыг хийхэд гаралтын утга зөв гарсан тул бид бодолтоо зөв хийсэн гэж үзэж болно. Энэ нь бидний бодлогоо зөв хэрэгжүүлсэн, алгоритм маань зөв ажиллаж байгаа гэсэн үг.

9. Бодолтоо илгээх.

Өөрсдийн бодлогыг жишээ тестээр шалган зөв гэдгийг баталгаажуулсан тул одоо submint solution буюу бодолт шалгах хэсэгт кодоо оруулан илгээж шалгах хэрэгтэй.

Кодоо оруулан илгээснээр бидний бодолт зөв болсон эсэхийг сайт шалгах ба урьдчилан бэлдсэн тестүүдийг оруулан гаралтын утгыг тааруулан бүх утга зөв үед ногоон болон accepted буюу зөвшөөрөгдсөн тэмдэглэгээг өгдөг.

Ийнхүү бид бодлого бодох үйл явцтай дэлгэрэнгүй танилцлаа. Дараагийн нийтлэлүүдэд сонирхолтой шийдлүүдийг багтаасан бодлогуудыг онцлон танилцуулах болно. Энэ хүртэл шимтэн уншсан та бүхэнд баярлалаа. Амжилт хүсье!