Dərs 1: C++ dilinin olimpiada üçün təməlləri

İlk dərsə xoş gəldiniz! Bu dərsdə C++ dili və olimpiadada onun istifadəsindən danışacağıq. Artıq C++ bilirsinizsə, bu, əladır, sizə təkrar olacaq. Əks halda, kəmərləri bağlayın, çünki bu dərsdən sonra artıq C++-da proqramlar yaza biləcəksiniz! Dərsin özünə keçməzdən əvvəl bu qeydlərin mövcudluğu və məqsədi haqqında danışaq. Necə ki, şagirdlər dərsə cavab verməyə hazırlaşır, müəllimlər də dərsə hazırlaşırlar ki, yaxşı və planlı dərs keçə bilsinlər. Ona görə də, bu qeydlər, ilk olaraq, mənim öz hazırlığım üçündür. Ondan əlavə olaraq, yazmağı da sevirəm deyə bunu bir imkan kimi görürəm. Əmin olun ki, bu qeydlərin yazılmasına və hazırlanmasına kifayət qədər əmək sərf olunur — hətta, ola bilsin, dərsdə bir şeyi deməyi unuduruq və ya axırda vaxtımız çatmır. Ona görə də, ümid edirəm ki, bu qeydləri tam şəkildə oxuyarsınız. Həm də, öz təcrübəmdən bilirəm ki, bəzi uşaqlar oxumaqla daha rahat öyrənirlər, bu, onlar üçün də yaxşı olar. Vaxtımın azlığı səbəbilə bu yazıları redaktə edə bilmirəm, ona görə də, texniki, qrammatik və ya məna səhvləri tapdıqda, mənə bildirməyiniz yaxşı olar. İndi isə qayıdaq dərsə.

Gəlin, hər şeydən öncə C++-da hər yerdə görə biləcəyiniz "Salam Dünya!" koduna baxaq:

#include <iostream>
using namespace std;
int main() {
  cout << "Salam, əziz olimpiaçılar!" << endl;
  return 0;
}

Bu kodu sətir-sətir anlamağa çalışaq, sonra isə bu kodun eynisinin "olimpiada stilində" yazılışına baxaq. İlk sətir #include <iostream> kitabxanadan "idxaldır". Yəni, iostream adlanan kitabxananın daxilindəki bütün kodu bu koda köçürmə. Bu köçürməni biz görmürük və çox vaxt onları görmək də istəmərik — onların içində yazılan kodlar həmişə oxunaqlı olmurlar. Hazırkı iostream kitabxanası (ayostrim kimi oxunur) bizə proqramda giriş və çıxış üçün operatorlar verir, elə onun açılışı input-output stream deməkdir (tərcüməsi: giriş-çıxış axını). Qısaca, dili yazanlar bizim üçün giriş və çıxış əməlləri yazıblar, biz isə onların yazdığı kodu idxal edib birbaşa istifadə edirik.

Sonrakı sətirdə isə using namespace std; görürük. Bu, əslində, anlamaq üçün daha çətin bir sətirdir... C++-da biraz qəliz işləyən və namespace adlanan "ad çoxluqları" var. Onlar, əsasən, eyni adlı şeyləri (dəyişənlər, funksiyalar və sair) ayırmaq üçündür. Məsələn, cout funksiyası (o, əslində, funksiya deyil, obyektdir, amma bunlar kampın əhatəsindən kənar olduğu üçün bəzən belə səhvləri qəsdən edəcəyəm. maraqlananlar Piazzada sual kimi soruşa bilərlər.) std (estede və ya standart kimi oxunur) adlanan ad çoxluğunda təyin olunub. Əgər bu sətri yazmasaq, hər dəfə həmin ad çoxluğunu birbaşa istifadə etməliyik. Onda std::cout yazmalı olardıq. Amma biz olimpiadaçılarıq və sürətli kod yazmağı xoşlayırıq, ona görə bu sətri yazaq. Bunları da gəlin öz məqsədimiz üçün idxal kimi anlayaq. std ad çoxluğunda bizə olimpiadada lazım olan hər şey var.

Sonra isə int main() funksiyası var, hansı ki, riyaziyyatdakı çoxluq işarəsi ilə açılıb və ən sonda bağlanıb. main adlanan funksiyalar xüsusi olur — kompüter proqramı başlatdıqda bu funksiyanı avtomatik çalışdıracaq. Başqa sözlərdə, main proqramnı giriş funksiyasıdır. Funksiyalar haqqında daha sonra danışacağıq. Çoxluq işarələri isə kod blokları yaradır. Kod blokları haqqında da ayrıca danışacağıq. Məsələn, burada funksiyanın içi özü bir blokdur və onun içində başqa bloklar yoxdur.

Sona yaxınlaşırıq. İndi isə cout və arxasında gələn kiçikdir işarələri var. O işarələrə biz bu kodda axın işarələri deyəcəyik. cout-un necə işlədiyinin dərinliyinə girmək istəmirəm, amma təsəvvür edin ki, o, konsola (yəni, proqramı işlədəndə çıxan "qara ekrana") sətirlər yazmaq üçün istifadə olunur və siz çıxışa verilənləri ona "axın" ilə ötürürsünüz. Sətrin sonundakı endl isə (endlayn kimi oxunur) yeni sətir deməkdir.

Ən son sətrimiz isə return 0 olandır. Bayaq dedik ki, main funksiyadır. Onu int main kimi təyin edirik, bu da onun hansısa int tipində dəyər alması deməkdir. Bu xüsusi funksiyada onun aldığı dəyər proqramın necə bitməsini göstərir. 0 uğurlu bitməsi göstərir, ona görə də, biz həmişə 0 dəyərini verəcəyik. (Onu qeyd edim ki, funksiyanın "aldığı dəyər" və "qaytardığı dəyər" ifadələri əks səslənsə də, proqramlaşdırma onların mənası eynidir. return tərcümədə qaytarmaq deməkdir və proqramçı dəyərir funksiyada çağırana qaytarır. Funksiya isə o dəyəri almış olur. Yəni, qaytarılma funksiyanı çağırana aiddir, alma isə funksiyanın özünə.)

Əla! C++-da ən sadə proqramı indi super şəkildə başa düşürük! Düşürükmü? Əgər yuxarıda yazılanlar haqqında hər şeyi tam ətraflı başa düşmədinizsə, heç narahat olmayın. Olimpiadada bunların heç birini bilməyə ehtiyacım yoxdur, amma mən istəyirəm ki, siz onları da anlayasınız, ona görə də, nə haqda suallarınız olarsa, Piazzada yazmaqdan çəkinməyin. Bu kiçik kodda, doğrudan da, çox ciddi şeylər baş verir.

print("Salam, əziz olimpiadaçılar!")

Yuxarıdakı isə eyni kodun Python 3 dilində yazılmasıdır. Necə də sadə və gözəl, elə ingilis dili kimi oxunur. Bəs biz niyə istifadə etmirik bu dildən? Python mənim ən sevdiyim 3 dildən biridir, amma olimpiada üçün onu istifadə etməyəcəyik. Bir çox kodu çox qısa etsə də, sürəti çox zəifdir. Bu yaxında, respublika olimpiadalarında bir şagirdin Pythonda yazılmış düzgün həlli zaman limitini ötürdü (həmin halda həll düz olsa da, bal verilmir). Eyni alqoritm isə C++-da çox rahatlıqla keçir. Python çox vaxt 5-10 dəfə, bəzi hallarda isə (xüsusən, alqoritmlərlə işləyəndə) 100 dəfəyə qədər gec işləyə bilir.

Öncədən dediyim kimi, mən istəyirəm ki, yazdığınız kodu hərtərəfli başa düşəsiniz, amma olimpiadada bəzən bu şeylərdən keçə bilirik. Sizdən bu tipli cəmi bir xahişim olacaq.

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << "Salam, əziz olimpiaçılar!" << endl;
  return 0;
}

Yuxarıdakı kod əvvəlki kod ilə eyni işi görür, amma ilk sətir fərqlidir və əlavə iki sətrimiz var. Adətən, iostream bizə bəs etmir, məsələn, vector tipindən istifadə etmək üçün #include <vector> lazımdır. Olimpiadada bizim bunları nə əlavə etməyə, nə də hansı funksiyanın və ya tipin hansı kitabxanada əzbərləməyə vaxtımız yoxdur. Ona görə də, ikinci koddakı kitabxana bizim üçün olimpiadada lazımlı bütün kitabxanaları idxal edir. Yəni, biraz kompleks kodda 10-15 sətir idxal üçün yazmağa vaxtımız getmir (xüsusən də canlı yarışlarda). Digər iki sətri daha dərindən izah etməyəcəm, amma onlar isə giriş və çıxış əməllərinin daha sürətli işləməyi üçündür. Onlar ən çox böyük girişi olan məsələlərdə proqramı çox sürətləndirirlər. İstəməzsiniz ki, sizin olmayan səhvə görə az bal alasınız, ona görə də, həmin iki sətri kodunuzda həmişə yazın. Qeyd edim ki, ola bilsin bəziləriniz printf və scanf funksiyaları ilə tanışsınız və onlardan istifadə edirsiniz. Bu sətirlər onların işləməyinə problem yaradacaq (onlar onsuz da sürətli işləyirlər). Amma mən çox ciddi şəkildə tövsiyə edirəm ki, siz olimpiadalarda həmişə cout və cin işlədəsiniz. Bu, həm də arzuolunmayan xətaların qarşısını ala bilir.

Unutmayın ki, hər sətrin sonunda nöqtə-vergül işarəsi mütləqdir. Bu, sətirləri ayırmaq üçün lazımdır. Bu arada, C++ kodlarını yazıb çalışdırmaq üçün mən Code::Blocks proqramını tövsiyə edirəm. Yükləmək qaydaları üçün dərs videosuna baxın (mingw-setup olan versiyanı bu linkdən yükləyin).

İndi isə dilin təməllərinə keçək. Bilirəm ki, bir çoxunuz C++ dilində artıq təcrübəlisiniz, amma ümid edirəm yuxarıdakı izahlar sizlərə də maraqlı oldu. Çalışacam ki, arada daha az bilinən taktika və metodlar da göstərim. C++ dili statik tiplərlə işləyir. Yəni, tiplər proqramın başından bəlli olur və ən sona qədər eyni qalır. Bu o deməkdir ki, eyni dəyişəndən həm söz ifadə etmək üçün, həm də ədəd ifadə etmək üçün istifadə edə bilmərik (bu cümləyə sonra qayıdacağıq). Python, Javascript və sair dillər isə dinamik tiplərdən istifadə edirlər, onlarda çoxlu maraqlı imkanlar var. Amma proqramlaşdırmada ən böyük prinsiplərdən biri imkanları artırmaq yox, onları qəsdən azaltmaqdır. Bu, təhlükəsizlik üçündür. Ona görə də proqramçılar statik tipli dillərə üstünlük verirlər (bu yaxında keçirilən məşhur bir sorğu bəlli etdi ki, insanların çoxu JavaScript dili əvəzinə TypeScript dilində yazırlar, hansı ki, eyni bilin statik tipli versiyasıdır). C++ dili statik tipli olsa da, ona heç də təhlükəsiz dil demək olmaz, çünki yaddaşla birbaşa işləyə bilirik. Gəlin nümunələrlə baxaq. C++-dakı bəzi tiplər bunlardır (bəzi dəyərlər təxminidir):

double tipi üçün C++-da standart ölçü olmasa da, çox vaxt 8 bayt (32 bit olaraq nəzərdə tutulur) olur (kompilyatordan asılıdır). C++-da başqa tiplər də var, məsələn, unsigned int, float, long double və sair. Amma o tiplər demək olar ki, olimpiadada heç vaxt istifadə olunmurlar. Yuxarıdakı tiplərin hamısı ilə asanlıqla işləyə bilərik, gəlin nümunəyə baxaq:

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int a = 2000000000; // 9 sıfır
  long long b = 20000000000; // 10 sıfır
  char c = 'k'; // nəzərə alın ki, char ' işərələri arasında yazılır
  bool d = false; // və ya true
  double pi = 3.14159;
  return 0;
}

Yaxşı xəbər budur ki, bu tiplərin hamısı cin və cout ilə birbaşa işləyirlər. Yəni, heç bir əlavə zəhmət olmadan, ardıcıl bütün tipləri daxil etmək və ya çıxışa vermək mümkündür. Məsələn, bu proqram int və long long tipləri daxil edir, ondan sonra isə onların və 0.5 ədədinin cəmini dəyişənə yazıb çıxışa verir:

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int a;
  long long b;
  cin >> a >> b;
  double c = a + b + 0.5;
  cout << c << endl;
  return 0;
}

Özünü yoxla
İki int tipi girişə verib dörd sətirdə onların cəmini, fərqini, hasilini, qismətini və böldükdə olan qalığı çıxışa verin. a ədədini b ədədinə böldükdə qalan qalıq modulo adlanan əməl ilə aparılır və a % b kimi yazılır.

Özünü yoxladakı proqramı mütləq edin, amma izahı dərs videosunda var. O koddan istifadə edərək bir neçə maraqlı hallar müşahidə edin:

1. 10 və 4 ədədlərinin qisməti nəyə bərabərdir?
2. 2000000000 və 2000000000 ədədlərinin cəmi nəyə bərabərdir? Bəs hasilləri?
3. Girişə 3.5 və 5.9 verəndə nə baş verir?

Bu hallarda, ola bilsin, gözləmədiyiniz cavablar aldınız. Gəlin bunları izah edək. C++ dilində çoxlu tip çevrilmələri avtomatik baş verir və bu proses casting (kastinq kimi oxunur) adlanır. Bu, bəzən çox yaxşıdır, bəzən isə bizi çaşdıra bilir. Bu qayda bəzən qəliz işləyir, amma yadda saxlayın ki, iki eyni tip arasında baş verən əməllər yenə həmin tiplə nəticələnir. Yəni, iki int tipi arasındakı əməldə nəticə int tipində olacaq. 10 və 4 ədədlərinin qisməti 2.5 ədədinə bərabər olsa da, orada avtomatik olaraq int tipinə çevrilmə baş verir və nəticə 2 olur. Qeyd edin ki, bu çevrilmə yuvarlaqlaşdırmır, sadəcə, nöqtədən sonrakı hissəni silir. Sonrakı hal da maraqlıdır. Dediyimiz kimi, nəticə int tipində olmalıdır, amma cavab bu tipin dəyərləri aralığına yerləşmir. Ona görə də, cəm üçün çıxışa -294967296 kimi qəribə ədəd verilir. Bu xətaya overflow (overflou kimi oxunur) deyilir. Sonuncu hal isə ən qəribəsidir. Ədədlərin cəmi olaraq 3 görəcəksiniz, amma o ədədlərin int tipinə çevrilməsində belə cəm 3 olmur. Koda həmin girişə verilən ədədlərin özlərini çıxışa verən sətir də artırın (mən dəyişənlərimi a və b adlandırmışam):

cout << a << " " << b << endl;

Girişə 3.5 və 5.9 verdikdə, yuxarıdakı sətir çıxışa 3 və 0 verir. Axı 0 haradan gəldi? Bu gözlənilməz xətanın səbəbi odur ki, girişə verilən tiplər int olduqda, cin də o tipləri daxil etmək üçün "hazırlaşır". Amma biz girişə başqa tiplər veririk, onda da cin onları başa düşə bilmir və işləmə prinsipi pozulur.

Bəs bu tipli xətalardan necə qorunaq? Tiplərin olmağı pisdirmi? İlk öncə, bizə verilmiş məsələnin şərtlərinə baxmaq lazımdır. Bütün olimpiada məsələlərində girişə veriləcək hər şeyin tipi və ölçüləri haqqında yazılır, biz də ona uyğun tiplər seçməliyik. Məsələn, girişə verilənlər 1-dən 2 milyarda qədər tam ədədlərdirsə, biz onda int tipindən onları saxlamaq üçün istifadə edə bilərik. Amma bu, hər şey demək deyil. Məsələdə bizə o ədədlərin cəmini və hasilini çıxışa vermək tələb olunursa, biz analiz etməliyik ki, bu tiplər bizə yetəcəkmi. Məsələn, bayaq gördüyümüz kimi, iki sayda 2 milyard ədədinin nə cəmi, nə də hasili int tipinə uyğun gəlir. Onda, belə bir kod yazmağı yoxlaya bilərik:

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int a, b;
  cin >> a >> b;
  long long cem = a + b;
  long long hasil = a * b;
  cout << cem << " " << hasil << endl;
  return 0;
}

Bəs bu kod işləyirmi? Yoxlasaq, görürük ki, bu kod da eyni nəticələnir. Bunun səbəbi isə odur ki, ifədənin sağ tərəfində tip dəyişməsi baş vermir, yəni, məsələn a+b ifadəsi int kimi hesablanır, onun dəyəri isə long long tipinə yazılır. Yaxşı, bəs onda biz nə edək? Belə hallarda, mən sizə 2 yol göstərəcəm. Biri ən asanıdır: elə girişə verilən tiplər üçün də long long istifadə etmək. Əgər biliriksə ki, bizə long long tipi həmişə yetərli olacaq, onu hər şey üçün istifadə etmək bizim problemi aradan götürər. Bu, həqiqətən də çox vaxt kömək olur (ilk olaraq elə bunu yoxlamağı tövsiyə edirəm), amma yadda saxlayın ki, 2 dəfə çox yaddaş və 2 dəfəyə qədər çox zaman istifadə edir. Adətən, məsələdə verilən yaddaş limiti çox olur, amma zaman limiti önəmlidir. Əgər həllinizin düzgün olduğunu düşünürsünüzsə, amma zaman limitinə uyğun gəlmirsə, bu, tipləri səmərəsiz istifadə etməkdən baş verə bilər. Bu halda biraz daha çox diqqət və zəhmət lazımdır.

C++-da avtomatik çevrilmə qaydaları var. Məsələn, cəm əməlini etdikdə, C++ nəticəni avtomatik olaraq oradakı "ən böyük" tipə saxlayır. Yəni, məsələn, long long və int üzərində cəm etsək, nəticə long long olacaq. Eyni qayda hasil, qismət və çıxma əməliyyatları üçün də keçərlidir. Onda biz istədiyimiz nəticələri düzgün almaq üçün tipləri "məcbur edə" bilərik.

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int a, b;
  cin >> a >> b;
  long long cem = (long long)a + b;
  long long hasil = (long long)a * b;
  cout << cem << " " << hasil << endl;
  return 0;
}

Bu kod a dəyişənini hər iki sətirdə long long tipinə keçirir. Bu, dəyişənin öz tipini dəyişmir, sadəcə, həmin ifadəni hesablamazdan əvvəl, long long-a çevrilmiş a hesablayır və onu istifadə edir. İndi isə, dediyimiz kimi, o ifadələrdə avtomatik çevrilmə baş verir. Amma bir şeyə də diqqət etməliyik. Bu çevrilməni biz həmişə ən əvvəldə etməliyik, çünki C++ ifadələri başdan əvvələ hesablaya-hesablaya gedir. Məsələn, bu kod düzgün işləmir:

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int a, b;
  cin >> a >> b;
  long long cem = a + b + (long long)2;
  long long hasil = a * b * (long long)2;
  cout << cem << " " << hasil << endl;
  return 0;
}

Bunun səbəbi isə cəmli ifadə long long tipinə çevrilməzdən əvvəl overflow baş verməsidir. Bu, həqiqətən də, başağrıdan və qəliz mövzudur, amma əmin olun ki, çoxlu məsələ həlli ilə artıq bunlara öyrəşəcəksiniz. Bu tip çevrilməsi, əslində, bəzən bizə kömək də ola bilir. Burada ən çox char və bool çevrilmələri maraqlıdır. Gəlin biraz da char tipi haqqında da danışaq.

Özünü yoxla
Girişə 3 int tipli ədəd verilir, onların hasilinin milyard ədədinə böldükdə alınan qalığı tapın. Əmin olun ki, kodunuzda overflow xətası yoxdur. Yoxlamaq üçün girişə üç ədədi də 1000000001 olaraq verin, çıxışa kodunuz 1 verməlidir.

C++ dilində char tipi ASCII (aski kimi oxunur) sistemindən istifadə edir. Bu sistemdə ingilis dilindəki bütün hərflər və bəzi simvollar var. Olimpiadada yalnız hərflər haqqında öyrənmək bəsdir. Yadda saxlayın ki, 26 hərf var. Bu cədvəldə onların hərəsini bir ədəd göstərir (həm böyük, həm kiçik hərflər üçün ayrı bir ədəd var). Bu ədədlərə biz ASCII kodu deyirik. Məsələn, A hərfinin kodu 65, a hərfinin kodu isə 97-dir. Yəni, əslində, char tipi ilə ədəd kimi də işləyə bilərik. Bayaq gördüyümüz kimi, özümüz bu çevrilməni apara bilərik. Gəlin C++-da iki hərfi int tipinə çevirək:

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  char a = 'a', A = 'A';
  cout << (int)a << " " << (int)A << endl;
  return 0;
}

Yadda saxlayın ki, bu kodlamada kiçik hərflər də, böyük hərflər də əlifba sırası ilə ardıcıl gəlirlər (kiçik hərflər 97-dən 122-ə qədər, böyük hərflər isə 65-dən 90-a qədər).

Özünü yoxla
Girişə hərf verilir, əlifbada ondan sonra gələn hərfi müəyyən edən kod yazın (girişə z və ya Z verilmir).

Özünü yoxla
Girişə böyük hərf verilir, çıxışa o hərfin kiçiyini verən kod yazın.

İndi isə biraz da bool tipinə baxaq. C++-da bu tipin aldığı dəyərlər true və false ola bilir, amma onları 1 və 0 ilə də əvəz etmək olar. Bu məntiqlə, biz bu tipin əvəzinə həmişə int istifadə edə bilərdik, amma burada int və long long arasındakı problem yenə yaranır: bool 4 dəfə daha az yaddaş tutur və 32 (bəzi kompilyatorlarda 64) dəfəyə qədər sürətli işləyə bilir (təbii ki, burada söhbət bütün kodun işləmə zamanından getmir. ciddi sürətlənməni ancaq çoxlu bool tiplərlə işləyəndə ala bilərsiniz).

Güclülər üçün tövsiyə
bitset tipi haqqında öyrənin və məsələlər edin. Piazza-da bu haqda soruşmaqdan çəkinməyin.

Sadə tiplər haqqında söhbəti avtomatik və əl-ilə çevrilməni daha da aydın etməklə bitirək. Qısaca, qayda belədir ki, ifadəni dəyişənə saxlamaq istəyəndə, o ifadə dəyişənin tipinə avtomatik çevrilməyə çalışacaq. Həm təəssüflə, həm də sevinərək deyirəm ki, yuxarıda öyrəndiyimiz tiplərdə avtomatik çevrilmələr mümkündür, yəni, 97.5 ədədini char tipinə çevirə bilərik. Bu bizə bəzən kod yazanda kömək edir, bəzən isə səhvlərə yol açmağa kömək edir. Məsələn, yuxarıda gördüyümüz kimi, double tipi nəzərdə tutduğumuz halda int yazsaq da, kod çalışacaq, amma səhv çalışacaq. Bir də onu yadda saxlayın ki, dəyişənlərə yazılmada sağ tərəf müstəqil olaraq hesablanır, yəni, öyrəndiyimiz kimi, long long cem = a + b; kodunda sağ tərəf avtomatik olaraq long long tipinə çevrilmir (birinci öz tipində hesablanır, sonra isə həmin nəticə çevrilir, amma artıq həmin nəticə səhvdir), biz onu əl-ilə çevirməliyik. Bunun üçün isə, dəyişənin və ya ifadənin soluna tipi mötərizədə yaza bilərik.

Sən də yaz
Əgər bilirsinizsə, danışdığımız tiplərin yaddaşda necə saxlanıldığı haqqında Piazza-da qeyd (Note) yazın. İzahı yaxşı etmək üçün şəkillər də çəkə bilərsiniz. Ən aydın bir və ya bir neçə izahı gələn dərsin qeydlərində müəllif(lər)in adı ilə paylaşacam.

Ümid edirəm, tiplər haqqında bunları öyrənmək maraqlı oldu. Onlarla bağlı çoxlu xətalar etmək olur və olimpiadalarda xətalar acımasız şəkildə çox vaxt 0 balı ilə nəticələnir, ona görə də, diqqətli olmalıyıq. İndi isə bool tipi haqqında yox, amma o tipli ifadələr haqqında danışaq. Sonra isə şərtlərə keçid edəcəyik. Şərtlər yaratmaq üçün ən çox istifadə etdiyimiz əməllər bunlardır:

• Bərabərlik: ==
• Bərabərsizlik: !=
• Böyüklük: >
• Böyük-bərabərlik: >=
• Kiçiklik: <
• Kiçik-bərabərlik: <=
• "Və" əməli: &&
• "Və ya" əməli: ||
• "Yox" əməli: ! (bu, şərtin əksini göstərir. bəzən istəmədiyimiz halı, yəni, şərtin əksini yazmaq daha asandır.)

Bu əməllərin hamısının istifadəsi bizə bool tipində nəticələr verir. Onda biz belə ifadə yaza bilərik:

bool z = (a < b) && (c >= d || e == f);

Bu dəyişənin nəticəsini belə də anlaya bilərik: z o vaxt true dəyəri alır ki, a b-dən kiçikdir və növbəti iki şərtdən ən azı biri ödənir: ya c d-dən böyükdür, ya da e və f bərabərdirlər. Düzünü desəm, bu cümləni yazanda çoxlu çətinliklərlə qarşılaşdım, çünki və və və ya ifadələrini dildə bir-birindən ayırmaq çətindir. C++ bunu danışdığımız dillərdən yaxşı bacarır. Bu mövzuda ən çox gördüyüm 2 səhv var: mötərizələrin istifadə olunmaması və == əvəzinə = yazılması. İlk səhvi araşdıraq. Məsələn, tutaq ki, bayaqkı ifadəni belə yazdıq:

bool z = a < b && c >= d || e == f;

Düzünü desəm, heç bilmirəm ki, bu bayaqkı ilə eyni nəticəni verir ya yox, amma bu kod tamamilə anlaşılmazdır. Bilinmir ki, burada ilk iki şərt qruplaşmaq istənilib (bunun kimi: (a < b && c >= d) || (e == f)), yoxsa əvvəl yazdığım kimi qruplaşma gedir. Ona görə də, && və || əməllərindən istifadə etdikdə, mütləq mötərizələrdən lazımi gəldiyi qədər bol istifadə edin. Digər səhv isə adətən diqqətsizlikdən əmələ gəlir, məsələn belə şərtlər yazılır:

bool z = (a = b);

Çalışın ki, bərabərlik üçün həmişə (xüsusən də birazdan danışacağımız if şərtli ifadələrinin içində) düzgün əməldən istifadə edin.

İndi isə keçək şərtli ifadələrə. Necə edək ki, kodumuz fərqli şərtlər altında fərqli davransın? Burada köməyə if çatır. Onun daxilinə yuxarıda öyrəndiyimiz ifadələr ilə yaratdığımız şərt yaza bilərik, sonra isə onlar üçün kod blokları açırıq. Məsələn:

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << "Yaşınızı yazın: ";
  int age;
  cin >> age;
  cout << endl; // özünü yoxla: bu sətri yazmasaq nə baş verər?
  if (age < 18) {
    cout << "Siz sürücülük vəsiqəsi ala bilməzsiniz!";
  } else {
    cout << "Siz sürücülük vəsiqəsi ala bilərsiniz!";
  }
  cout << endl; // sonda yeni sətir qoymaq adətən yaxşıdır.
  return 0;
}

else (els kimi oxunur) ifadəsi isə şərtin əksi halında baş verir. Yəni, yaşın ən azı 18 olduğunu yoxlamaq üçün if (age >= 18) yazmağa ehtiyac yoxdur. Şərtləri daha da uzatmaq mümkündür. Məsələn, belə bir qayda olsa idi ki, yaş 70-i keçdikdə yalnız əvvəllər sürücülük vəsiqəsi olanlara yenisi verilir (təzələmək məqsədi ilə), onda kodu belə dəyişə bilərdik:

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << "Yaşınızı yazın: ";
  int age;
  cin >> age;
  cout << endl; // özünü yoxla: bu sətri yazmasaq nə baş verər?
  if (age < 18) {
    cout << "Siz sürücülük vəsiqəsi ala bilməzsiniz!";
  } else if (age > 70) {
    cout << "Siz sürücülük vəsiqəsini yalnız yeniləyə bilərsiniz!";
  } else {
    // burada yaş 18 və 70 arasındadır
    cout << "Siz sürücülük vəsiqəsi ala bilərsiniz!";
  }
  cout << endl; // sonda yeni sətir qoymaq adətən yaxşıdır.
  return 0;
}

İç-içə şərtləri də yazmaq mümkündür, amma kodu sadə tutmaq üçün bundan çəkinmək lazımdır. Məsələn, yuxarıdakı eyni kodu belə də yaza bilərik:

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << "Yaşınızı yazın: ";
  int age;
  cin >> age;
  cout << endl; // özünü yoxla: bu sətri yazmasaq nə baş verər?
  if (age < 18) {
    cout << "Siz sürücülük vəsiqəsi ala bilməzsiniz!";
  } else {
    if (age > 70) {
      cout << "Siz sürücülük vəsiqəsini yalnız yeniləyə bilərsiniz!";
    } else {
      // burada yaş 18 və 70 arasındadır
      cout << "Siz sürücülük vəsiqəsi ala bilərsiniz!";
    }
  }
  cout << endl; // sonda yeni sətir qoymaq adətən yaxşıdır.
  return 0;
}

Görə bilərik ki, bu kodda "dərinlik" daha çoxdur və anlamağı daha çətindir. Düzdür, olimpiadalarda çalışmalıyıq ki, sürətli yazaq, amma yaxşı kod yazmaq da önəmlidir ki, sonra səhvləri tapmağa vaxt itirməyək.

Özünü yoxla
Girişə iki int tipində ədəd verilir, onların böyüyünü çıxışa verən proqram yazın.

Özünü yoxla
Girişə char tipində simvol verilir, onun kiçik hərf olub olmadığını yoxlayan kod yazın.

Özünü yoxla
Girişə int tipində 3 ədəd verilir, onların hasilinin mənfi, sıfır və ya müsbət olduğunu müəyyən edən kod yazın. Nəzərə alın ki, bu hasili hesablamaq long long tipi ilə mümkün olmaz.

Özünü yoxla
Girişə dörd həqiqi ədəd verilir, həmin ədədləri düzbucaqlının tərəfləri kimi istifadə edə bilərikmi sualına cavab verən proqram yazın.

Özünü yoxla
Turist məsələsini həll edin.

Əla, artıq proqramın axını üçün ən əsas şeylərdən birini öyrəndik. İndi isə marağı daha da artıracağıq. İlk olaraq while, sonra isə for dövrlərinə baxaq. Dövrlərin məqsədi işimizi ümumiləşdirməkdir. Məsələn, hansısa şeyi "n sayda ədəd üçün" və ya "ədədin bütün rəqəmləri üçün" ediriksə, deməli, dövr istifadə etməliyik. while (vayl kimi oxunur) sözünün tərcüməsi "nə qədər ki" deməkdir. Yəni, nə qədər ki, verilmiş şərt ödənir, hansısa kodu icra edəcəyik. Gəlin, müsbət ədədin rəqəmləri cəmini tapmaq üçün dövrdən istifadə edək. Bilirik ki, onluq say sistemindəki ədədi mərtəbələrə bölə bilərik, məsələn:$$21805 = 2\cdot 10^4 + 1\cdot 10^3 + 8\cdot 10^2 + 0\cdot 10^1 + 5\cdot 10^0$$ Bu ədədin son rəqəmini tapmaq üçün 10 ədədinə böldükdə alınan qalığa baxa bilərik. Həqiqətən də, 21805 ədədini 10-a böldükdə qalıq 5-dir. Digər rəqəmə keçmək üçün isə, 10-a bölmə edə bilərik. Axı C++-da tip dəyişməyəcək, ona görə də, tam ədədi 10-a böldükdə onun tam hissəsi qalacaq. Bu da son rəqəmi silmək kimidir. Onda belə bir proses yaranır: $$21805 \mod 10 = \fbox{5}, \ 21805/10 = 2180\\2180 \mod 10 = \fbox{0}, \ 2180/10 = 218\\218 \mod 10 = \fbox{8}, \ 218/10 = 21\\21 \mod 10 = \fbox{1}, \ 21/10 = 2\\2 \mod 10 = \fbox{2}, \ 2/10 = \red{0}\\ \text{davamı varmı?}$$ Gördüyümüz kimi, burada eyni prosesi təkrarlayırıq və ədədin rəqəmlərini bir-bir oxuya bilirik. Dövr məsələlərində ən diqqətli olmalı olduğumuz şeylərdən biri isə dövrün sonluğudur. Burada görürük ki, proses ədəd 0 olanda bitməlidir. Bir şeyi də nəzərə alın ki, bu rəqəmləri biz əvvəldən-başa oxuyuruq, amma cəm üçün bunun fərqi yoxdur. Kodu isə belə yaza bilərik:

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  int sum = 0;
  while (n != 0) {
    sum += n % 10; // += üstünə gəlmək əməlidir
    n /= 10; // oxşar şəkildə, /= bölmək əməlidir
  }
  cout << sum << endl;
  return 0;
}

Bir daha deyək: "Nə qədər ki, n ədədi sıfır deyil, onun son rəqəmini cəmə əlavə et və n-i 10-a böl". Çox rast gəlinən səhvlərdən biri n /= 10 əvəzinə n / 10 yazmaqdır. Birincisi n-i 10-a bölür, ikincisi isə n/10 ifadəsinin dəyərini hesablayır (amma onunla heç nə etmir).

Özünü yoxla
Sonu sıfırla bitməyən ədədin rəqəmlərini tərsinə çevrilmiş ədədi çıxışa verən kod yazın.

Özünü yoxla
Sonu sıfırla bitməyən ədədin palindrom olub-olmadığını yoxlayan kod yazın.

while dövründən istifadə edərək girişə bildiyimiz sayda ədəd də verə bilərik. Məsələn, n ədədi və ondan sonra n sayda ədəd girişə verilsə, həmin ədədlərin cəmini tapmaq üçün belə kod yaza bilərik:

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  int x, i = 0;
  long long sum = 0; // cəm böyük ola bilər
  while (i < n) {
    cin >> x;
    sum += x;
    i++; // bu, i-nin dəyərini bir ədəd artırır
  }
  cout << sum << endl;
  return 0;
}

Burada başda 0 olan i dəyişəni götürürük, sonra isə nə qədər ki, n-dən kiçikdir, ədəd daxil edib onu cəmə əlavə edirik və i-ni artırırıq. Nəzərə alın ki, burada i-nin aldığı dəyərlər 0, 1, 2, ..., n-1 ədədləridir. Bəs niyə saymağa sıfırdan başladıq? Proqramlaşdırmada adətən massivlərdə ilk ədədin indeksi (sırası) sıfır olur, ona görə də, çox vaxt proqramımızda sıra saylarını 0 üzərindən götürürük. İlk yazdığımız məsələdə ədədin ixtiyari sayda rəqəmi ola bilərdi, amma ikinci məsələdə girişə verəcəyimiz sayı bilirik. Belə hallarda, for dövrü daha əlverişlidir. Yaddan çıxarmayın ki, iki cür dövrün işləmə prinsipi eynidir, amma təxmini qayda belədir: dövr hansısa şərt üzərində qurulanda while, hansısa say üzrə qurulduqda isə for işlənir. Eyni kodu belə də yaza bilərik:

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  int x;
  long long sum = 0; // cəm böyük ola bilər
  for (int i = 0; i < n; i++) {
    cin >> x;
    sum += x;
  }
  cout << sum << endl;
  return 0;
}

while dövründə ancaq şərt yazırıq, amma for dövrü bizə dəyişən yaratmaqla və dəyişənin üzərində əməl etməyə kömək edir. Nəzərə alın ki, yaratdığımız i dəyişəni bu halda yalnız dövrün kod blokunda istifadə oluna bilər (bu, dəyişənlərin əhatəsi mövzusuna aiddir, amma suallarınız olsa, Piazza-da soruşun).

Özünü yoxla
Girişə n və sonra n tam ədəd verilir, onlardan cütlərin sayını çıxışa verən proqram yazın.

Özünü yoxla
Girişə a və b tam ədədləri verilir, $a^b$ ədədinin 1000000009 ($10^9+7$) ədədinə qalığını tapın.

Əla, artıq şərtləri və dövrləri də öyrəndik. Narahat olmayın, sonda ev tapşırığında praktika üçün çoxlu məsələlər olacaq. Sonra isə massivlərə və onların üzərindəki əməllərə baxacağıq. Amma ondan öncə kiçik bir tövsiyəm var. C++ dilində biraz təcrübəsi olanlar bilir ki, kod blokları bir sətir olduqda, çox hallarda mötərizələri silmək olar, məsələn, bu da düzgün koddur:

if (age < 18) cout << "Siz sürücülük vəsiqəsi ala bilməzsiniz!";
else if (age > 70) cout << "Siz sürücülük vəsiqəsini yalnız yeniləyə bilərsiniz!";
else cout << "Siz sürücülük vəsiqəsi ala bilərsiniz!";

Mənim tövsiyəm odur ki, belə yazmayın. Çox vaxt şərtlərə əlavə kodlar yazmaq lazım olur, məsələn, səhv axtardıqda cout sətirləri. Bu isə vaxt qazanmaq əvəzinə itirməyə səbəb olur. Həm də, diqqətsiz istifadə olunduqda başqa səhvlərə də yol aça bilər. İndi isə keçək massivlərə, hələ qarşımızda bir neçə daha mövzu var.

İndiyə kimi məsələlərdə girişə çoxlu ədədlər verdikdə onları yaddaşda saxlamağa ehtiyac qalmayıb. Bəzən isə bu bizə lazımdır. Məsələn, girişə n və n tam ədəd verilir, onları verilmiş sıranın tərsində çıxışa vermək lazımdır. Burada biz massiv adlandırdığımız data strukturundan istifadə edirik. Bu, əslində xüsusi bir tip deyil, hansısa tipin ardıcıllığıdır. Massivlərin ölçüsü statik olur, yəni, yaradılanda bilinməlidir. Buna görə də, massiv yaratdıqda, məsələdəki şərtlərə baxmaq lazımdır. Tutaq ki, tərsinə çevirmə məsələsində n ədədi ən çoxu 1000-dir. Onda, massivin ölçüsünü də ona uyğun götürməliyik. Burada tövsiyə edirəm ki, həmişə lazım olandan 5 sayda artıq ölçü götürün. Bunun iki səbəbi var: ola bilsin, indeksləri 1-dən başlatmaq daha asandır və yaxud məsələdə massivin sonuna 1-2 sayda əlavə ədəd artırmaq istəyirsiniz (bəzən, lazım olur). Onda tərsinə çıxış etmə məsələsini belə yaza bilərik:

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1005; // const yazmasaq nə baş verər?
int arr[MAX_N]; // massivə çalışın ki, bir-hərfli adlar verməyin
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  for (int i = n-1; i >= 0; i--) { // özünü yoxla: niyə n-1 ilə başlayırıq? niyə >=0 yazırıq?
    cout << arr[i] << " "; // boşluq ilə çıxışa veririk
  }
  cout << endl;
  return 0;
}

Bayaq dediyimiz kimi, massivlərin ölçüsü statik olmalıdır, ona görə də, const yazmaqla kompilyatora demiş oluruq ki, MAX_N dəyişəninin dəyəri dəyişməyəcək. Sonra isə massivin elementlərini adi dəyişən kimi istifadə edirik, sadəcə düzbücaqlı mötərizələr ilə istədiyimiz indeksə baxırıq. Çıxışa verdikdə isə, sonuncu ədəddən başlayırıq və ilk ədəd daxil olmaqla, ona qədər indeksimizi azaldırıq. Biz burada 0 indesklə başladıq, amma bəzi məsələlərdə 1 indekslə başlamaq daha asan ola bilir. Əgər belə xüsusi ehtiyac yoxdursa, mən 0 indekslə işləməyi tövsiyə edirəm. Amma ikisi ilə də işləməyi bilmək lazımdır.

Özünü yoxla
Yuxarıdakı kodun eynisinin 1 indekslə başlamaqla yazın və yoxlayın ki, işləyir.

İndi isə iki balaca tövsiyə. Niyə MAX_N dəyişəni istifadə etdik birbaşa 1005 yazmaq yerinə? Çox vaxt bizə bir neçə massiv ilə işləmək lazım olur, ona görə də, hər dəfə 1005 yazmaq xətalara yol aça bilər. Orada səhvən 105 yaza bilərik, amma MAX_N yazanda hərf səvhi etsək, kod çalışmayacaq. Bir də, çoxlu for dövrü yazanda əlimiz i++ yazmağa öyrəşir. Burada nəzərə alın ki, i-- olmalıdır, çünki tərsinə baxırıq. Səhvən i++ yazsaq, kod sonsuz işləməyə davam edərdi və konsol donardı. Belə halla üzləşsəniz, dövrlərinizi yoxlayın.

Çalışın ki, massivləri həmişə "qlobal" əhatədə qeyd edin (yəni, int main funksiyasından və ya başqa bütün funksiyalardan kənarda). Bunun səbəbi kampımızın əhatəsindən çıxır, amma maraqlananlar bu linkə baxa bilər.

Sən də yaz
C++-da i++ və ++i əməlləri arasında kiçik bir fərq var. Bu fərq haqqında yaxşı bilirsinizsə və başqası artıq yazmayıbsa, Piazza-da qeyd (Note) yaradın və paylaşın. İzahı gələn dərsin qeydlərində müəllifin adı ilə paylaşacam.

Özünü yoxla
Ən kiçik leksikoqrafik sürüşmə məsələsini həll edin.

İndi isə keçək massivin ən çox istifadə olan alternativinə: vector tipinə. Bu tip dinamik ölçülüdür, yəni, massivlər kimi statik ölçüsü olmur. Onların ölçüsünü istədiyimiz vaxt dəyişə bilərik (məsələn, element artırmaq və ya silməklə). vector tipini adətən 2 cür istifadə edirik: ya əvvəlcədən ölçü verməklə, ya da boş başlayıb ədəd əlavə etməklə. Əvvəlcədən ölçü versək, bu, daha çox massivə oxşayır, amma belə bir üstünlük var ki, başlanğıcda vector-u istədiyimiz ədədlərlə doldura bilərik (məsələn, bütün ədədlər 1 ilə). Tutaq ki, girişə verilən ədədlər arasında cüt ədədləri tapıb, onları tərsinə sırada çıxışa vermək istəyirik (məsələn, n=7 və ədədlər 1 2 6 3 5 9 4 olsa, çıxışa 4 6 2 veririk). Burada vector tipini belə istifadə edə bilərik:

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, x;
  cin >> n;
  vector<int> v(n, 1); // bu vector-da n sayda 1 ədədi ilə başlayırıq
  // bu halda v-ni 1 ədədləri ilə dolduqmağın mənası yoxdur, çünki daxil etdiyimiz ədədlər onların üzərinə yazılacaq
  vector<int> evens; // bu isə boş vector-dur
  for (int i = 0; i < n; i++) {
    cin >> v[i];
    if (x % 2 == 0) { // 2-ə bölündükdə qalıq sıfır olarsa, cüt ədəddir
      evens.push_back(x); // push_back ədədi sona əlavə edir
    }
  }
  for (int i = n - 1; i >= 0; i--) {
    cout << v[i] << " ";
  }
  cout << endl;
  int sz = evens.size();
  for (int i = sz - 1; i >= 0; i--) {
    cout << evens[i] << " ";
  }
  cout << endl;
  return 0;
}

vector tipi ilə işləyəndə ehtiyatlı olmaq lazımdır. İlk olaraq, nəzərə alın ki v[i] kimi kodu yalnız vector-un kifayət qədər yeri olduqda yazmaq olar, yoxsa proqram çalışacaq, amma xəta verəcək. Yəni, boş vector ilə başlasaq, girişə vermək üçün v[i] yazmaq düz deyil. Nümunələrə baxdıq, amma gəlin vectorun ən çox istifadə olunan əməllərini də öyrənək.

// boş vector yaratmaq üçün:
vector<tip> v; // tipi istədiyimiz tiplə əvəzləyə bilərik.

// ölçüsü n, bütün elementləri x olan vector yaratmaq üçün:
vector<tip> v(n, x);

// vectorun ölçüsünü tapmaq üçün:
v.size();

// vectorun sonuna x elementini artırmaq üçün:
v.push_back(x);

// vectorun sonuncu elementini silmək üçün:
v.pop_back();

// vectorun i indeksində olan elementi:
v[i];

// vectorun sonuncu elementi (əgər boşdursa, bu, xəta verəcək):
v.back();

// vectoru təmizləmək üçün (bütün elementləri silmək):
v.clear();

Özünü yoxla
Massiv və ya vectorda sondan k-cı elementi çıxışa verən proqram yazın.

Sən də yaz
Piazza-da qeyd (Note) yaradaraq vector üçün erase və insert metodlarını izah edin. Gələn dərsin qeydlərində yaxşı izahları müəlliflərin adı ilə bir yerdə paylaşacam.

İndi isə biraz iki-ölçülü massivlərdən danışaq. Əslində, onlar xüsusi bir şey deyillər: 1-ölçülü massivdə hər element məsələn, int olur, 2-ölçülü massivdə isə hər element int[] (yəni, int massivi olur). Yəni, 2-ölçülü massiv "massivlərin massivi" deməkdir. Belə bir məsələyə baxaq. Girişə n, m, sonra isə sətir sayı n, sütun sayı m olan iki-ölçülü massiv verilir. Fərz edək ki, $n, m \leq 1000$. Biz bu iki-ölçülü massivdə hər sütunun ən böyük ədədini taparaq onları çıxışa vermək istəyirik. Nəzərə alın ki, çıxışa m sayda ədəd veriləcək.

Nümunə giriş:
3 5
1 5 2 3 9
2 4 5 1 4
6 2 3 8 3

Yuxarıdakı test üçün çıxış:
6 5 5 8 9

Bu məsələ üçün belə bir həll yaza bilərik:

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1005;
int arr[MAX_N][MAX_N];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> arr[i][j]; // i-ci sətir, j-ci sütundakı element
    }
  }
  // indi isə hər sütuna baxaq
  for (int j = 0; j < m; j++) {
    int column_max = arr[0][j]; // j sütunundakı ilk ədədlə başlayaq
    for (int i = 0; i < n; i++) {
      if (arr[i][j] > column_max) {
        column_max = arr[i][j]; // daha böyük ədəd tapsaq, onunla əvəzləyək
      }
    }
    cout << column_max << " ";
  }
  cout << endl;
  return 0;
}

Mən sətirləri i, sütunları j adları ilə indeksləməyi sevirəm. Nəzərə alın ki, məcbur deyil ki, iç-içə dövrlər olanda içdə j, çöldə isə i işlənsin. Sütunlara baxırıq deyə ilk olaraq j adlanan dövrü yazdım. Gəlin eyni məsələni biraz daha maraqlı edək. Yalnızca, n və m üzərindəki şərti dəyişirəm: indi $n, m \leq 10^5$, amma $n\times m \leq 10^6$. Gəlin nəyin dəyişdiyini anlamağa çalışaq. Əvvəlki məsələdə n və m ədədləri ən çoxu 1000 ola bilərdi, yəni, onların hasili ən çoxu $10^6$ olur. İndi isə, n və m ədədləri çox daha böyük ola bilərlər, amma onların hasili yenə ən çoxu milyon olacaq. Məsələn, indi giriş 10 sətirli, 100000 sütunlu ola bilər. Burada massiv istifadə edə bilərikmi?

Özünü yoxla
int arr[MAX_N][MAX_N] massivi MAX_N = 100005 olduqda təxminən nə qədər yaddaş tutur? Bəs 1 milyon int üçün əslində nə qədər yaddaş lazımdır? (kömək: tipləri müzakirə edəndə, int tipinin yaddaşı haqqında danışmışdıq)

Belə hallarda köməyimizə iki-ölçülü vector çatır. Bu da massivlərdə olduğu kimi vector-ların vector-udur. Onu, hətta bir sətirlə də belə qeyd edə bilərik:

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  // hər sətiri ölçüsü m olan vector kimi düşünün
  vector<vector<int>> arr(n, vector<int>(m));
  // ... qalan kod tamamilə eynidir
  return 0;
}

Gəlin daha dərindən anlayaq. Dediyimiz kimi, n sətir var, m sütun. Bu o deməkdir ki, hər sətiri ölçüsü m olan vector kimi düşünmək olar. Ümumi isə n sətir var. Yəni vector-umuzda n element olacaq, onların hər biri isə ölçüsü m olan vector olacaq. vector<int>(m) həmin iç vector-lardır, onların sayını isə arr(n, [ölçüsü m olan vector]) yazmaqla qeyd etmişik. Ümumi tip isə vector<vector<int>> olur. İlk gördükdə biraz qəliz hiss oluna bilər, amma biraz praktikadan sonra təbii gələcək!

İndi isə string tipi haqqında danışaq. Bu tipi ona görə axıra yaxın saxladım ki, onun vector ilə oxşarlıqları çoxdur. Bu tip də dinamik ölçülü tipdir, hətta, onu char tiplərinin vector-u kimi düşünmək də olar. Amma string tipinin bir çox üstünlükləri var. Onların ilki cin ilə birbaşa işləməsidir. Yəni, girişə söz verilsə, onu rahatlıqla oxuya bilərik, hətta, ölçüsünü əvvəlcədən bilməsək belə. Əlavə olaraq, iki string-i birləşdirmək üçün toplaya da bilərik. Yenə də, kod nümunələri ilə öyrənək:

string s; // boş bir string yaratmaq üçün

string s(n, 'a'); // bütün simvolları a hərfi olan və ölçüsü n olan string

s.size(); // ölçüsünü tapmaq üçün

s += 'a'; // sonuna simvol (char) artırmaq üçün
s += "salam"; // sonuna başqa string artırmaq üçün
s += t; // əgər t string-dirsə, sonuna artırmaq üçün

s.pop_back(); // sonuncu simvolu silmək üçün

s[i]; // i-ci indeksdəki simvol

s.back(); // sonuncu simvol

s = ""; // string-i sıfırlamaq üçün (başqa stringə də bərabər edə bilərdik)

Sən də yaz
Piazza-da qeyd (Note) yaradaraq string üçün erase, insert, substr, replace metodlarını izah edin (hamısını etməyə ehtiyac yoxdur, bir-ikisini də etmək olar). Gələn dərsin qeydlərində yaxşı izahları müəlliflərin adı ilə bir yerdə paylaşacam.

İndi isə gəlin maraqlı məsələyə baxaq. Kiçin hərflərdən ibarət string-də ən çox rast gəlinən hərfi tapmaq istəyirik. Bunun üçün bütün hərfləri saya bilərik. İdeya belədir ki, 26 kiçik hərf var deyə ölçüsü 26 olan vector bizə bəs edər. Hər hərf üçün isə onları 0-dan 25-ə qədər ədədlərdə əvəz edək (ASCII kodlamanı yada gətirin). Onda bu məsələni belə edə bilərik:

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  string s;
  cin >> s;
  vector<int> cnt(26, 0); // başda bütün saylar 0-dır
  for (int i = 0; i < s.size(); i++) {
    cnt[s[i] - 'a']++; // s[i]='a' olduqda, indeks 0 olur, 'b' olduqda 1 və sair
  }
  char freq = 'a'; // tutaq ki, a hərfi ən çox rast gəlinir
  int max_cnt = cnt[0]; // bu, a hərfinin sayıdır
  for (int i = 0; i < 26; i++) {
    if (cnt[i] > max_cnt) { // i-ci hərf daha çox rast gəlinir
      freq = i + 'a';
      max_cnt = cnt[i];
    }
  }
  cout << freq << endl;
  return 0;
}

Bu məsələdən xoşum gəlir, çünki avtomatik çevrilmənin də istifadəsini göstərir. s[i] və 'a' char tipləri olsalar da, onları bir-birindən çıxa bilirik. Sonra isə int tipi olan i və char tipi olan 'a' üzərində də toplama edirik. Mütləq bu kodu tam başa düşməyə çalışın, lazım gəlsə isə Piazza-da sual verin.

Özünü yoxla
Çəyirtkə və zəncir məsələsini həll edin.

Əla! Bu dərsin "rəsmi" hissəsi bura qədər. İndi isə bonuslar!

Önəmli tövsiyə (+sən də yaz)
max və min funksiyaları haqqında öyrənin. Bilirdinizmi ki, onları 2-dən artıq ədəd üzərində də istifadə etmək olar? max({1, 2, 3, 10}) kimi.

Önəmli tövsiyə (+sən də yaz)
ceil funksiyası haqqında öyrənin. Bu funksiyanı tam ədədlərə necə tətbiq edə bilərik ki, double tipindən istifadə etməyək?

Sən də yaz
Piazza-da qeyd (Note) yaradaraq mənim vector və string tiplərini izah etdiyim kimi deque tipini izah edin. Niyə həmişə ondan istifadə etmirik haqqında da araşdırın. Gələn dərsin qeydlərində yazılarınızı müəlliflərin adları ilə birlikdə paylaşacam.

Sən də yaz
Piazza-da qeyd (Note) yaradaraq C++-dakı makroları, yəni, #define ifadələrini izah edin. Gələn dərsin qeydlərində yazılarınızı müəlliflərin adları ilə birlikdə paylaşacam.

Sən də yaz
Piazza-da qeyd (Note) yaradaraq pair tipini izah edin. Gələn dərsin qeydlərində yazılarınızı müəlliflərin adları ilə birlikdə paylaşacam.

Sən də yaz
Piazza-da qeyd (Note) yaradaraq həm massivlər, həm vector/string kimi tiplər üçün sort və reverse funksiyalarını izah edin. Gələn dərsin qeydlərində yazılarınızı müəlliflərin adları ilə birlikdə paylaşacam.

Sən də yaz
Piazza-da qeyd (Note) yaradaraq ixtiyari sayda giriş olan məsələləri izah edin (while(cin >> x) tipli giriş.) Gələn dərsin qeydlərində yazılarınızı müəlliflərin adları ilə birlikdə paylaşacam.