C++ ga bir qarash

4-darajaPlatina — dinamik programmalash25–32 darslar

HayotdaMusobaqa

Ikki o’quvchi bir xil algoritmni yozdi, ikkalasi ham to’g’ri. Biriniki o’tdi, ikkinchisiniki «vaqt chegarasidan oshdi» oldi. Farq algoritmda emas edi — tilda. Bu ko’p uchraydigan va ko’p asabga tegadigan holat, shuning uchun uni oldindan bilib qo’ygan ma’qul.

Bu darsdan keyin siz

• Python qayerda yetarli, qayerda yetmasligini raqam bilan bilasiz
• C++ ning uchta asosiy farqini taniysiz
• qachon tilni almashtirish kerakligi haqida ongli qaror qabul qilasiz

Avval rost gap

Bu modul Python’da yozilgan va shunday qoladi. Python’da algoritmni o’rganish osonroq: kod qisqa, sintaksis xalaqit bermaydi va fikr ko’rinib turadi.

Lekin xalqaro olimpiadada (IOI va unga olib boradigan bosqichlarda) qatnashchilarning katta qismi C++ yozadi. Sabab bitta va u oddiy: tezlik.

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 10⁶	n = 10⁷	n = 10⁸
C++ (taxminan)n	10⁶sig‘adi	10⁷sig‘adi	10⁸sig‘adi
Python (taxminan 10 barobar sekin)n log n	10⁷sig‘adi	10⁸chegarada	10⁹sig‘maydi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Jadval qo’pol, lekin nisbat to’g’ri: bir xil algoritm Python’da odatda 10 dan 50 barobargacha sekin ishlaydi. 10⁸ amal C++ da bir soniya, Python’da esa bir necha daqiqa bo’lishi mumkin.

◆Asosiy g'oya

Bu Python «yomon» degani emas. n ≤ 10⁵ bo’lgan masalalarning deyarli hammasi Python’da bemalol o’tadi — bu esa maktab, tuman va viloyat bosqichlarining katta qismi. Muammo faqat eng yuqori bosqichlarda va eng katta chegaralarda boshlanadi.

Uchta asosiy farq

1. Turlar oldindan e’lon qilinadi

Python o’zgaruvchining turini o’zi aniqlaydi va u ishlash paytida o’zgarishi mumkin. C++ da tur oldindan yoziladi va o’zgarmaydi — shuning uchun kompilyator kodni mashina buyruqlariga to’g’ridan-to’g’ri o’giradi.

turlarNusxalash

1int n = 5;2long long katta = 1000000000000;3double kasr = 2.5;4string ism = "Aziza";5vector<int> sonlar = {4, 2, 7};

▲Bu yerda xato qilishadi

int C++ da taxminan 2·10⁹ gacha son saqlaydi va undan oshsa jimgina buziladi — Python’dagi cheksiz butun sonlarga o’rganib qolgan o’quvchi shu yerda birinchi ball yo’qotadi. Yig’indi katta bo’lishi mumkin bo’lsa long long yoziladi.

2. Kod avval kompilyatsiya qilinadi

Python kodni qatorma-qator o’qib bajaradi. C++ da esa kod avval butunlay mashina tiliga o’giriladi, keyin ishga tushadi. Shuning uchun xato turlari ham boshqacha: ko’p xato kompilyatsiya paytida chiqadi, ya’ni programma ishga tushishidan oldin.

3. Kutubxona boshqacha nomlanadi

Ma’nosi bir xil, nomi boshqa. Bu jadval yod olish uchun emas — kerak bo’lganda ochib qarash uchun.

Python	C++	Nima
list	vector	o’zgaruvchan uzunlikdagi ro’yxat
dict	map yoki unordered_map	kalit — qiymat
set	set yoki unordered_set	to’plam
deque	deque	ikki tomonlama navbat
heapq	priority_queue	uyum
bisect_left	lower_bound	ikkilik qidiruv
sorted()	sort()	saralash

Bir masala, ikki tilda

Darsdagi eng oddiy masala — ro’yxatdagi eng katta son. Ikki yechim yonma-yon.

eng-katta.pyNusxalash

1import sys2malumot = sys.stdin.buffer.read().split()3n = int(malumot[0])4a = [int(x) for x in malumot[1 : 1 + n]]5print(max(a))

eng-katta.cppNusxalash

1#include <bits/stdc++.h>2using namespace std;3int main() {4  ios::sync_with_stdio(false);5  cin.tie(nullptr);6  int n;7  cin >> n;8  vector<int> a(n);9  for (int i = 0; i < n; i++) cin >> a[i];10  cout << *max_element(a.begin(), a.end()) << endl;11}

To’rtinchi va beshinchi qatorlar — olimpiadada deyarli har faylning boshida turadigan ikki sehrli qator. Ular kirish-chiqishni tezlashtiradi va ularsiz C++ ning o’zi ham sekin bo’lib qoladi.

kompilyatorcompiler

Manba kodni mashina buyruqlariga o’giruvchi programma. C++ kodi ishga tushishidan oldin albatta kompilyatsiya qilinadi.

Qachon almashtirish kerak

Qoida sodda. Yechimingiz to’g’ri, algoritmi ham to’g’ri, lekin vaqt chegarasidan o’tmayapti — va uni tezlashtirishning boshqa yo’li qolmagan. Faqat shundagina til almashtiriladi.

Amalda bu shuni bildiradi: 1–3-darajadagi masalalarning deyarli hammasi Python’da o’tadi. 4-darajadan boshlab ba’zi masalalarda chegaralar Python’ni siqib qo’yadi, 5-darajada esa bu odatiy holga aylanadi.

◆Asosiy g'oya

Tilni algoritmni tushunmaguningizcha almashtirmang. Sekin Python yechimi tez C++ yechimidan qimmatliroq: birinchisini tezlashtirish mumkin, ikkinchisini esa tushunmasdan yozib bo’lmaydi.

O’zingizni sinang

1Nega olimpiadada C++ ko'p ishlatiladi?

Javobni ko'rish

Tezlik. Bir xil algoritm Python’da odatda 10–50 barobar sekin ishlaydi, eng yuqori bosqichlarda esa chegaralar aynan shu farqni hisobga olib qo’yiladi.

2C++ da int va long long farqi nima?

Javobni ko'rish

int taxminan 2·10⁹ gacha son saqlaydi, long long esa 9·10¹⁸ gacha. Chegaradan oshsa int xato bermaydi — jimgina noto’g’ri son beradi.

3Python'ning bisect_left funksiyasi C++ da nima deb ataladi?

Javobni ko'rish

lower_bound. Ma’nosi bir xil: saralangan ketma-ketlikda berilgan qiymatdan kichik bo’lmagan birinchi element.

4Qachon Python'dan C++ ga o'tish kerak?

Javobni ko'rish

Algoritm to’g’ri, uni tezlashtirishning boshqa yo’li qolmagan va yechim baribir vaqt chegarasidan o’tmayotgan bo’lsa. Bundan oldin emas.

5ios::sync_with_stdio(false) nima qiladi?

Javobni ko'rish

C++ ning kirish-chiqishini C tilinikidan ajratadi va shu bilan uni sezilarli tezlashtiradi. Katta kirishli masalalarda bu qator ballga ta’sir qiladi.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

Yuqoridagi jadvalni daftaringizga ko’chiring. Keyin oldingi darslarda yozgan uchta yechimingizni oling va har birida qaysi Python vositalari ishlatilganini, ularning C++ dagi nomini yozib chiqing.

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

Bitta oddiy masalani (masalan 01-eng-katta) C++ da yozib ko’ring va uni onlayn kompilyatorda ishga tushiring. Birinchi urinishda qanday xatolar chiqdi?

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Bir xil algoritmni ikki tilda yozing va n = 10⁷ da vaqtini o’lchang. Nisbat qancha chiqdi? Keyin Python yechimini tezlashtirishga urinib ko’ring (sys.stdin.buffer, ro’yxat tushunchalari) — nisbat qanchaga o’zgardi?