Clasa a X-a

10 capitole · 76 lecții disponibile

Șiruri de caractere

Șiruri de caractereBază

Tipul string — text ca un vector de caractere

Șiruri de caractereBază

Funcții specifice — uneltele clasei string

Șiruri de caractereBază

Parcurgeri — citește fiecare caracter o dată

Șiruri de caractereBază

Frecvențe — câte de fiecare caracter

Șiruri de caractereMediu

Prefixe și sufixe — începuturi și finaluri

Șiruri de caractereMediu

Palindroame — citit la fel în ambele sensuri

Șiruri de caractereMediu

Căutări în șiruri — unde apare un tipar

Structuri de date liniare

Structuri de date liniareBază

Stiva — ultimul intrat, primul ieșit

Structuri de date liniareBază

Coada — primul intrat, primul ieșit

Structuri de date liniareMediu

Algoritmul lui Lee — drumul minim în labirint

Structuri de date liniareMediu

Deque — coadă cu două capete

Structuri de date liniareMediu

Liste simplu înlănțuite — noduri legate prin pointeri

Structuri de date liniareMediu

Liste dublu înlănțuite — legături în ambele sensuri

Structuri de date liniareMediu

Lecție-punte: când folosim fiecare structură

STL

pair — două valori legate într-una

vector — tabloul care crește singur

list — lista dublu înlănțuită din STL

deque — container cu acces la ambele capete

queue — adaptorul FIFO din STL

priority_queue — mereu cel mai prioritar primul

stack — adaptorul LIFO din STL

set — mulțime ordonată fără duplicate

multiset — mulțime ordonată cu duplicate

unordered_set — mulțime rapidă pe hash

map — dicționar ordonat cheie-valoare

multimap — o cheie cu mai multe valori

unordered_map — dicționar rapid pe hash

bitset — tablou compact de biți

Lecție-punte: complexitățile structurilor STL

Numere mari

Numere mariMediu

Reprezentarea numerelor mari — un vector de cifre

Numere mariMediu

Adunarea numerelor mari — cifră cu cifră, cu transport

Numere mariMediu

Scăderea numerelor mari — cu împrumut

Numere mariMediu

Înmulțirea unui număr mare cu un număr natural

Numere mariGreu

Împărțirea unui număr mare la un număr natural

Combinatorică și modulară

Combinatorică și modularăMediu

Numărarea submulțimilor — 2 la puterea n

Combinatorică și modularăMediu

Numărarea permutărilor — n factorial

Combinatorică și modularăMediu

Numărarea aranjamentelor — alegi și ordonezi

Combinatorică și modularăMediu

Numărarea combinărilor — alegi fără ordine

Combinatorică și modularăGreu

Parantezări — numerele lui Catalan

Combinatorică și modularăGreu

Partiții — sume fără să conteze ordinea

Combinatorică și modularăGreu

Număr de ordine — rangul unei permutări

Combinatorică și modularăMediu

Aritmetică modulară — calcule fără overflow

Combinatorică și modularăGreu

Invers modular — împărțirea modulo un prim

Combinatorică și modularăMediu

Lecție-punte: de ce lucrăm modulo

Recursivitate

RecursivitateMediu

Funcții recursive — o funcție care se apelează pe sine

RecursivitateMediu

Caz de bază — unde se oprește recursivitatea

RecursivitateMediu

Apel recursiv — coborâre și urcare

RecursivitateMediu

Stiva apelurilor — memoria recursivității

RecursivitateMediu

Relații de recurență — un termen din cei dinainte

RecursivitateMediu

Lecție-punte: desenarea arborelui de recursie

Divide et Impera

Divide et ImperaMediu

Ideea Divide et Impera — împarte, rezolvă, combină

Divide et ImperaMediu

Împărțirea problemei — unde tai la mijloc

Divide et ImperaMediu

Rezolvarea subproblemelor — recursie până la bază

Divide et ImperaGreu

Combinarea rezultatelor — pasul care decide viteza

Divide et ImperaGreu

Exemple clasice — Merge Sort și prietenii

Geometrie

Etapa națională

Sistemul cartezian — puncte și vectori în plan

Distanța dintre două puncte — Pitagora în plan

Ecuația dreptei — forma generală ax + by + c = 0

Panta unei drepte — cât de abruptă urcă

Distanța de la punct la dreaptă — cea mai scurtă cale

Intersecții de drepte și segmente — testul cu orientare

Arii — produsul vectorial și formula shoelace

Algoritmi de baleiere — o linie care mătură planul

Înfășurătoarea convexă — elasticul din jurul punctelor

Backtracking

Etapa națională

BacktrackingMediu

Backtracking elementar — încearcă, dă înapoi, repetă

BacktrackingGreu

Backtracking în plan — problema damelor

BacktrackingGreu

Generarea soluțiilor — permutări, combinări, aranjamente

BacktrackingGreu

Tăierea ramurilor inutile — oprește-te din timp

Programare dinamică

Etapa națională

Programare dinamicăMediu

Ideea programării dinamice — nu recalcula niciodată

Programare dinamicăMediu

Stări — ce descrie o subproblemă

Programare dinamicăMediu

Tranziții — cum legi o stare de cele dinainte

Programare dinamicăMediu

Inițializare — cazurile de bază ale tabelului

Programare dinamicăGreu

Probleme de numărare — în câte moduri

Programare dinamicăGreu

Probleme de optimizare — rucsacul 0/1

Programare dinamicăMediu

Memoizare — recursie cu memorie (top-down)

Programare dinamicăGreu

Lecție-punte: cum alegi starea într-un DP