# Andras Bogdan-Andrei (CodeByAndras) > Computing student and developer: programming, cloud & infrastructure, networking, cybersecurity, automation and AI workflows. - [Counting the even elements with divide and conquer in C++](https://bogdanandras.com/algorithms/grade-10/divide-and-conquer/counting-the-even-elements-with-divide-and-conquer/): The same pattern as for the sum: the result for the portion [st, dr] is the sum of the results of the two halves. Only the base case differs: a portion with… - [GCD of an array's elements with divide and conquer in C++](https://bogdanandras.com/algorithms/grade-10/divide-and-conquer/gcd-of-an-array-s-elements-with-divide-and-conquer/): The GCD of a portion is the GCD of the left half's GCD and the right half's GCD, because gcd(a, b, c, d) = gcd(gcd(a, b), gcd(c, d)). The base case: a single… - [Divide and conquer in C++](https://bogdanandras.com/algorithms/grade-10/divide-and-conquer/): 8 C++ programs on divide and conquer (Divide et impera): recursive binary search, gCD of an array's elements with divide and conquer, maximum of an array… - [Maximum of an array with divide and conquer in C++](https://bogdanandras.com/algorithms/grade-10/divide-and-conquer/maximum-of-an-array-with-divide-and-conquer/): The three stages of the method: we split the portion [st, dr] into two halves at the middle m = (st + dr) / 2 (divide); we find the maximum of each half… - [Merge sort in C++](https://bogdanandras.com/algorithms/grade-10/divide-and-conquer/merge-sort/): We split the array into two halves, sort each half recursively, then merge them: we always compare the first remaining elements of the two halves and move… - [Quick sort in C++](https://bogdanandras.com/algorithms/grade-10/divide-and-conquer/quick-sort/): We pick a pivot (here the middle element) and rearrange the portion so that values <= pivot end up on the left and values >= pivot on the right: index i… - [Recursive binary search in C++](https://bogdanandras.com/algorithms/grade-10/divide-and-conquer/recursive-binary-search/): The array is sorted in increasing order. We compare x with the middle element: if they are equal we are done; if x is smaller, we search only the left half… - [Sum of the elements with divide and conquer in C++](https://bogdanandras.com/algorithms/grade-10/divide-and-conquer/sum-of-the-elements-with-divide-and-conquer/): The sum of the portion [st, dr] is the sum of the left half [st, m] plus the sum of the right half [m + 1, dr]. A portion with a single element has a sum… - [Towers of Hanoi in C++](https://bogdanandras.com/algorithms/grade-10/divide-and-conquer/towers-of-hanoi/): There are n disks on rod A, in decreasing order of size, and we want to move them to rod C, using rod B, without ever placing a large disk on a small one. To… - [Amicable numbers in C++](https://bogdanandras.com/algorithms/grade-10/functions/amicable-numbers/): Two numbers a and b are amicable if the sum of the proper divisors of a (the divisors smaller than a) is b and the sum of the proper divisors of b is a. The… - [Function for the sum of digits in C++](https://bogdanandras.com/algorithms/grade-10/functions/function-for-the-sum-of-digits/): The function sumaCifre(x) receives the number by value (it works on a copy, so the x in main is not destroyed) and returns the sum of its digits. In main we… - [Function returning the reverse of a number in C++](https://bogdanandras.com/algorithms/grade-10/functions/function-returning-the-reverse-of-a-number/): The function oglindit(x) builds the number with the digits of x in reverse order and returns it. With its help, the function palindrom(x) fits on one line: x… - [Function with an array parameter (the maximum) in C++](https://bogdanandras.com/algorithms/grade-10/functions/function-with-an-array-parameter-the-maximum/): An array is passed to a function together with the number of elements: int maxim(int v[], int n). The function actually receives the address of the first… - [GCD and LCM functions in C++](https://bogdanandras.com/algorithms/grade-10/functions/gcd-and-lcm-functions/): The function cmmdc(a, b) applies Euclid's algorithm by division: while b is not 0, the pair (a, b) becomes (b, a % b). The function cmmmc(a, b) reuses the… - [Global and local variables in C++](https://bogdanandras.com/algorithms/grade-10/functions/global-and-local-variables/): A global variable (declared outside the functions) is visible from the whole program, starts automatically at 0 and keeps its value between calls. A local… - [Subprograms (functions) in C++](https://bogdanandras.com/algorithms/grade-10/functions/): 11 C++ programs on subprograms (functions) (Subprograme (funcții)): gCD and LCM functions, primality function, function with an array parameter (the… - [Minimum and maximum returned by reference in C++](https://bogdanandras.com/algorithms/grade-10/functions/minimum-and-maximum-returned-by-reference/): A function can return a single value with return. When we need several results, we make them reference parameters: void minMax(int v[], int n, int &mn, int… - [Palindromes in a range in C++](https://bogdanandras.com/algorithms/grade-10/functions/palindromes-in-a-range/): A problem solved by splitting it into small functions: oglindit(x) returns the reverse of x, palindrom(x) uses the first one, and main only walks the range… - [Primality function in C++](https://bogdanandras.com/algorithms/grade-10/functions/primality-function/): We write the function estePrim(x) once, returning true if x is prime, and call it for every number read. The function looks for a divisor d between 2 and the… - [Super-prime numbers in C++](https://bogdanandras.com/algorithms/grade-10/functions/super-prime-numbers/): A number is super-prime if all its prefixes are prime. For example 239 is super-prime: 2, 23 and 239 are prime. The function estePrim(x) is reused by… - [Swapping by reference in C++](https://bogdanandras.com/algorithms/grade-10/functions/swapping-by-reference/): We compare two functions that try to swap the values of two variables. schimbaValoare(int x, int y) receives copies, so the changes are lost when the… - [Grade 10 C++ algorithms (Clasa a X-a)](https://bogdanandras.com/algorithms/grade-10/): 67 C++ algorithms for grade 10: subprograms (functions), two-dimensional arrays (matrices), character strings, the struct type, recursion, divide and… - [Bordering a matrix in C++](https://bogdanandras.com/algorithms/grade-10/matrices/bordering-a-matrix/): Bordering a matrix means adding a new row and/or column on its edge. Here we add column m + 1, holding the sum of each row, and row n + 1, holding the sum of… - [Checking a symmetric matrix in C++](https://bogdanandras.com/algorithms/grade-10/matrices/checking-a-symmetric-matrix/): A square matrix is symmetric about the main diagonal if a[i][j] == a[j][i] for every i and j (it equals its transpose). It is enough to check the elements… - [Deleting a row and a column in C++](https://bogdanandras.com/algorithms/grade-10/matrices/deleting-a-row-and-a-column/): As with arrays, deleting means moving elements over the deleted one. For row k, every row i from k to n - 1 receives row i + 1, then n decreases by 1. For… - [Generating a chessboard in C++](https://bogdanandras.com/algorithms/grade-10/matrices/generating-a-chessboard/): On a chessboard, the colour of a square depends only on the parity of i + j: squares with an even i + j have one colour (1), those with an odd i + j the… - [Generating a serpentine (zigzag) matrix in C++](https://bogdanandras.com/algorithms/grade-10/matrices/generating-a-serpentine-zigzag-matrix/): We fill the matrix with the numbers 1, 2, ..., n * m in a zigzag: odd rows from left to right, even rows from right to left. A counter val grows with every… - [Two-dimensional arrays (matrices) in C++](https://bogdanandras.com/algorithms/grade-10/matrices/): 15 C++ programs on two-dimensional arrays (matrices) (Tablouri bidimensionale (matrice)): bordering a matrix, reading and printing a matrix, main diagonal… - [Main diagonal and secondary diagonal in C++](https://bogdanandras.com/algorithms/grade-10/matrices/main-diagonal-and-secondary-diagonal/): In an n x n square matrix indexed from 1, the elements on the main diagonal have i == j, and those on the secondary diagonal have i + j == n + 1. We do not… - [Product of two matrices in C++](https://bogdanandras.com/algorithms/grade-10/matrices/product-of-two-matrices/): The product exists only if the number of columns of A equals the number of rows of B. For A (n x m) and B (m x p) the result C has n x p elements, and… - [Reading and printing a matrix in C++](https://bogdanandras.com/algorithms/grade-10/matrices/reading-and-printing-a-matrix/): A matrix with n rows and m columns is declared as int a[101][101] and traversed with two nested for loops: the first picks the row i, the second the column… - [Rotating a matrix by 90 degrees in C++](https://bogdanandras.com/algorithms/grade-10/matrices/rotating-a-matrix-by-90-degrees/): When rotating clockwise, the first column read from bottom to top becomes the first row. The result matrix b has m rows and n columns, and the element… - [Row sums and column sums in C++](https://bogdanandras.com/algorithms/grade-10/matrices/row-sums-and-column-sums/): For the sum of row i we keep i fixed and move j from 1 to m. For the sum of column j we do the opposite: j fixed in the outer loop, i varying in the inner… - [Row with the maximum sum in C++](https://bogdanandras.com/algorithms/grade-10/matrices/row-with-the-maximum-sum/): We compute the sum of every row and compare it with the largest sum found so far. The maximum starts from the sum of the first row (not from 0, because sums… - [Saddle point in C++](https://bogdanandras.com/algorithms/grade-10/matrices/saddle-point/): A saddle point is an element that is the minimum of its row and the maximum of its column. For every element a[i][j] we check the two conditions with two… - [Spiral traversal in C++](https://bogdanandras.com/algorithms/grade-10/matrices/spiral-traversal/): We keep four borders: top, bottom, left, right. On every lap we walk the top row (to the right), the right column (down), the bottom row (to the left) and… - [The four zones of a square matrix in C++](https://bogdanandras.com/algorithms/grade-10/matrices/the-four-zones-of-a-square-matrix/): The two diagonals split a square matrix into four zones (without the elements on the diagonals). With indices from 1: North: i < j and i + j < n + 1 (above… - [Transpose of a matrix in C++](https://bogdanandras.com/algorithms/grade-10/matrices/transpose-of-a-matrix/): The transpose of the matrix a (n rows, m columns) has m rows and n columns: row i of the transpose is column i of a, i.e. t[j][i] = a[i][j]. No second matrix… - [Converting to base 2, recursively in C++](https://bogdanandras.com/algorithms/grade-10/recursion/converting-to-base-2-recursively/): When converting by repeated division by 2, the remainders come out in the reverse of the order they must be written in. Recursion solves this by itself… - [Recursion in C++](https://bogdanandras.com/algorithms/grade-10/recursion/): 12 C++ programs on recursion (Recursivitate): printing the digits in order, recursively, recursive GCD, converting to base 2, recursively, recursive… - [Number of occurrences in an array, recursively in C++](https://bogdanandras.com/algorithms/grade-10/recursion/number-of-occurrences-in-an-array-recursively/): The number of occurrences of x among the first n elements is the number of occurrences among the first n - 1 elements, plus 1 if the last element v[n - 1]… - [Power of a number, recursively in C++](https://bogdanandras.com/algorithms/grade-10/recursion/power-of-a-number-recursively/): The direct version uses a^n = a * a^(n - 1) and makes n calls. The fast version halves the exponent: if n is even, a^n = (a^(n/2))^2, otherwise a^n = a *… - [Printing the digits in order, recursively in C++](https://bogdanandras.com/algorithms/grade-10/recursion/printing-the-digits-in-order-recursively/): Where we print relative to the recursive call matters. In inOrdine we print AFTER the recursive call: first the call for n / 10 finishes (printing the… - [Recursive factorial in C++](https://bogdanandras.com/algorithms/grade-10/recursion/recursive-factorial/): The mathematical definition is already recursive: 0! = 1 and n! = n * (n - 1)!. The function has a stopping condition (n == 0) and a recursive call on a… - [Recursive Fibonacci in C++](https://bogdanandras.com/algorithms/grade-10/recursion/recursive-fibonacci/): The Fibonacci sequence: F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2). The direct translation has two recursive calls, so the call tree almost doubles at… - [Recursive GCD in C++](https://bogdanandras.com/algorithms/grade-10/recursion/recursive-gcd/): Euclid's algorithm written recursively: gcd(a, 0) = a, and gcd(a, b) = gcd(b, a % b). The recursive call is the last operation in the function (tail… - [Recursive palindrome check in C++](https://bogdanandras.com/algorithms/grade-10/recursion/recursive-palindrome-check/): A word is a palindrome if its first and last characters are equal and what remains between them is also a palindrome. The function palindrom(s, st, dr) works… - [Reversing a string, recursively in C++](https://bogdanandras.com/algorithms/grade-10/recursion/reversing-a-string-recursively/): The function inverseaza(s, i) handles the characters from position i to the end. If s[i] is not '\0', it first calls itself for the rest of the string (i +… - [Sum of digits, recursively in C++](https://bogdanandras.com/algorithms/grade-10/recursion/sum-of-digits-recursively/): The digit sum of n is its last digit (n % 10) plus the digit sum of the number left after cutting it off (n / 10). Stop: a one-digit number (n < 10) has a… - [The Ackermann function in C++](https://bogdanandras.com/algorithms/grade-10/recursion/the-ackermann-function/): The Ackermann function has two arguments: A(0, n) = n + 1; A(m, 0) = A(m - 1, 1); A(m, n) = A(m - 1, A(m, n - 1)). Its values grow extremely fast (A(4, 2)… - [The Manna-Pnueli function in C++](https://bogdanandras.com/algorithms/grade-10/recursion/the-manna-pnueli-function/): The function is defined as: f(x) = x - 1 if x >= 12, otherwise f(x) = f(f(x + 2)). The inner call f(x + 2) is computed first, and its result becomes the… - [Caesar cipher in C++](https://bogdanandras.com/algorithms/grade-10/strings/caesar-cipher/): Every letter is replaced by the letter k positions further in the alphabet, circularly (after 'z' comes 'a'). We turn the letter into its position 0..25 (c… - [Checking a palindrome string in C++](https://bogdanandras.com/algorithms/grade-10/strings/checking-a-palindrome-string/): First we keep only the letters, turned into lowercase (so 'Ele fac cafele' becomes 'elefaccafele'). Then we use two indices: st starts at the beginning, dr… - [Checking anagrams in C++](https://bogdanandras.com/algorithms/grade-10/strings/checking-anagrams/): Two words are anagrams if they have the same letters, the same number of times, in a different order (for example 'roma' and 'amor'). We use a frequency… - [Converting to uppercase and lowercase in C++](https://bogdanandras.com/algorithms/grade-10/strings/converting-to-uppercase-and-lowercase/): In the ASCII table the uppercase letters 'A'..'Z' and the lowercase 'a'..'z' are a constant distance apart: 'a' - 'A' = 32. A lowercase letter becomes… - [Counting the vowels in C++](https://bogdanandras.com/algorithms/grade-10/strings/counting-the-vowels/): For every character we check whether it appears in the string "aeiouAEIOU" with the function strchr: strchr(vowels, c) returns the address of the first… - [Counting the words in C++](https://bogdanandras.com/algorithms/grade-10/strings/counting-the-words/): Without strtok: a word starts where a non-space character follows a space (or sits at the very beginning of the string). We count these 'beginnings', so… - [Extracting the numbers from a text in C++](https://bogdanandras.com/algorithms/grade-10/strings/extracting-the-numbers-from-a-text/): We walk the text; when we meet a digit, we build the number as in grade 9 (nr = nr * 10 + (s[i] - '0')) while digits follow. The expression s[i] - '0' turns… - [Character strings in C++](https://bogdanandras.com/algorithms/grade-10/strings/): 16 C++ programs on character strings (Șiruri de caractere): the longest word, caesar cipher, palindrome words in a sentence, removing the vowels, extracting… - [Letter frequency in C++](https://bogdanandras.com/algorithms/grade-10/strings/letter-frequency/): We count how many times each letter appears, without distinguishing uppercase from lowercase: tolower(c) - 'a' gives the letter's position in the frequency… - [Operations with std::string in C++](https://bogdanandras.com/algorithms/grade-10/strings/operations-with-std-string/): The string class from manages its own memory: it is assigned with =, concatenated with +, compared with == and <. getline(cin, s) reads the whole… - [Palindrome words in a sentence in C++](https://bogdanandras.com/algorithms/grade-10/strings/palindrome-words-in-a-sentence/): We combine two things learned before: strtok splits the sentence into words, and the function estePalindrom(p) checks a word with two indices moving in from… - [Removing the vowels in C++](https://bogdanandras.com/algorithms/grade-10/strings/removing-the-vowels/): We delete the vowels in the original string itself, with two indices: i reads every character, k shows where the next kept character is written. Consonants… - [Replacing one word with another in C++](https://bogdanandras.com/algorithms/grade-10/strings/replacing-one-word-with-another/): A text and two words, old and new, are read (each on its own line). We build the result in a new string: spaces are copied as they are, and every word is… - [Sorting words alphabetically in C++](https://bogdanandras.com/algorithms/grade-10/strings/sorting-words-alphabetically/): We split the sentence into words with strtok and copy them into a character matrix cuv[100][31] (every row is a string). We sort with bubble sort; two words… - [Splitting into words with strtok in C++](https://bogdanandras.com/algorithms/grade-10/strings/splitting-into-words-with-strtok/): strtok(s, separators) returns the first word of s; the following calls are made with NULL instead of s and return the other words one by one, until the… - [The longest word in C++](https://bogdanandras.com/algorithms/grade-10/strings/the-longest-word/): We split the sentence into words with strtok and keep the longest word in a separate string, copying it with strcpy (we cannot write celMaiLung = p, because… - [Walking a string and its length in C++](https://bogdanandras.com/algorithms/grade-10/strings/walking-a-string-and-its-length/): A C-style string is a char array terminated by the null character '\0'. cin.getline(s, 256) reads the whole line, spaces included (cin >> s would stop at the… - [Adding durations (hours, minutes, seconds) in C++](https://bogdanandras.com/algorithms/grade-10/structs/adding-durations-hours-minutes-seconds/): A duration is kept in a structure with three fields. To add easily, we turn the duration into seconds (h * 3600 + m * 60 + s), add the numbers and then… - [Comparing calendar dates in C++](https://bogdanandras.com/algorithms/grade-10/structs/comparing-calendar-dates/): A calendar date has three fields: day, month, year. Two dates are compared first by year, with equal years by month, and with equal months by day; the… - [The struct type in C++](https://bogdanandras.com/algorithms/grade-10/structs/): 5 C++ programs on the struct type (Tipul struct): comparing calendar dates, adding durations (hours, minutes, seconds), students sorted by average and name… - [Operations with fractions in C++](https://bogdanandras.com/algorithms/grade-10/structs/operations-with-fractions/): A fraction has two fields, the numerator a and the denominator b, so we represent it with struct Fractie { long long a, b; }. A function can return a whole… - [Points in the plane in C++](https://bogdanandras.com/algorithms/grade-10/structs/points-in-the-plane/): A point has the coordinates x and y: struct Punct { int x, y; }. The distance between two points is sqrt((x1 - x2)^2 + (y1 - y2)^2). For comparisons we use… - [Students sorted by average and name in C++](https://bogdanandras.com/algorithms/grade-10/structs/students-sorted-by-average-and-name/): The struct type groups data of different types under a single name: struct Elev { char nume[31]; double medie; }. A field is accessed with a dot (e.medie)… - [Cartesian product in C++](https://bogdanandras.com/algorithms/grade-11/backtracking/cartesian-product/): n sets are given; set i is {1, 2, ..., a[i]}. All elements of the Cartesian product are printed, i.e. all sequences (x1, ..., xn) with 1 ≤ xi ≤ a[i]. Any… - [Generating arrangements (k-permutations) in C++](https://bogdanandras.com/algorithms/grade-11/backtracking/generating-arrangements-k-permutations/): Prints, in lexicographic order, all arrangements of n elements taken k at a time: sequences of k distinct values from {1, ..., n} where order matters. It is… - [Generating balanced parentheses in C++](https://bogdanandras.com/algorithms/grade-11/backtracking/generating-balanced-parentheses/): Prints, in lexicographic order ('(' before ')'), all balanced strings made of n pairs of round brackets. We keep the number of brackets opened and closed so… - [Generating combinations in C++](https://bogdanandras.com/algorithms/grade-11/backtracking/generating-combinations/): Prints all k-element subsets of the set {1, ..., n} (combinations of n taken k at a time). To avoid getting the same subset several times, the elements are… - [Generating permutations in C++](https://bogdanandras.com/algorithms/grade-11/backtracking/generating-permutations/): Prints, in lexicographic order, all permutations of the set {1, 2, ..., n}. The solution is built in the array x, position by position. At position k we try… - [Generating subsets in C++](https://bogdanandras.com/algorithms/grade-11/backtracking/generating-subsets/): Prints all non-empty subsets of the set {1, ..., n}, in lexicographic order. The elements of a subset are placed in strictly increasing order (as with… - [Backtracking in C++](https://bogdanandras.com/algorithms/grade-11/backtracking/): 12 C++ programs on backtracking (Metoda backtracking): generating arrangements (k-permutations), map coloring, generating combinations, paths in a maze, the… - [Map coloring in C++](https://bogdanandras.com/algorithms/grade-11/backtracking/map-coloring/): A map has n countries numbered from 1, and m pairs (a, b) say that countries a and b are neighbours. We color every country with one of the colors 1..4 so… - [Partitions of a natural number in C++](https://bogdanandras.com/algorithms/grade-11/backtracking/partitions-of-a-natural-number/): Prints all ways of writing n as a sum of non-zero natural numbers, where the order of the terms does not matter. To avoid repeating the same decomposition… - [Paths in a maze in C++](https://bogdanandras.com/algorithms/grade-11/backtracking/paths-in-a-maze/): The maze is an n × m matrix of 0 (free) and 1 (wall). We start in the top-left corner (1, 1) and want to reach the bottom-right corner (n, m), moving up… - [Paying a sum with given coins in C++](https://bogdanandras.com/algorithms/grade-11/backtracking/paying-a-sum-with-given-coins/): There are n coin types with values v[1..n], as many of each as we want. We print all ways of paying exactly the sum S. x[k] is the number of coins of type k… - [Permutations with neighbours of alternating parity in C++](https://bogdanandras.com/algorithms/grade-11/backtracking/permutations-with-neighbours-of-alternating-parity/): Prints the permutations of the set {1, ..., n} in which any two neighbouring elements have different parities (one even, the other odd). Compared with… - [The n-queens problem in C++](https://bogdanandras.com/algorithms/grade-11/backtracking/the-n-queens-problem/): We place n queens on an n × n board so that none attacks another (no pair on the same row, column or diagonal). We put one queen on every row, and x[k] is… - [In-degrees and out-degrees in C++](https://bogdanandras.com/algorithms/grade-11/directed-graphs/in-degrees-and-out-degrees/): In a directed graph the edges have a direction and are called arcs: the arc (x, y) leaves x and enters y. The out-degree d+(x) is the number of arcs leaving… - [Directed graphs and shortest paths in C++](https://bogdanandras.com/algorithms/grade-11/directed-graphs/): 6 C++ programs on directed graphs and shortest paths (Grafuri orientate și drumuri minime): strongly connected components, shortest paths from one node… - [Reachability matrix (Roy-Warshall algorithm) in C++](https://bogdanandras.com/algorithms/grade-11/directed-graphs/reachability-matrix-roy-warshall-algorithm/): The reachability matrix has d[i][j] = 1 if there is a path (of length at least 1) from i to j and 0 otherwise. We start from the adjacency matrix. For every… - [Shortest paths between all pairs of nodes (Roy-Floyd) in C++](https://bogdanandras.com/algorithms/grade-11/directed-graphs/shortest-paths-between-all-pairs-of-nodes-roy-floyd/): Every arc (x, y) has a cost c ≥ 0. The cost matrix d starts with d[i][i] = 0, d[x][y] = the arc's cost and 'infinity' where there is no arc. For every… - [Shortest paths from one node (Dijkstra's algorithm) in C++](https://bogdanandras.com/algorithms/grade-11/directed-graphs/shortest-paths-from-one-node-dijkstra-s-algorithm/): We want the minimum cost of the path from node s to every other node, when all arc costs are non-negative. d[s] = 0, the rest 'infinity'. At every step we… - [Strongly connected components in C++](https://bogdanandras.com/algorithms/grade-11/directed-graphs/strongly-connected-components/): A directed graph is strongly connected if for any two nodes x and y there is a path from x to y and a path from y to x. A strongly connected component is a… - [Topological sort in C++](https://bogdanandras.com/algorithms/grade-11/directed-graphs/topological-sort/): The arc (x, y) means 'x must be done before y'. A topological sort is an order of all nodes in which every arc goes from left to right; it exists only if the… - [Edit distance in C++](https://bogdanandras.com/algorithms/grade-11/dynamic-programming/edit-distance/): What is the minimum number of operations needed to turn the word a into the word b? An operation means inserting, deleting or replacing a letter. d[i][j] is… - [Dynamic programming in C++](https://bogdanandras.com/algorithms/grade-11/dynamic-programming/): 10 C++ programs on dynamic programming (Programare dinamică): longest common subsequence, edit distance, maximum-sum path in a matrix, number of paths in a… - [Longest common subsequence in C++](https://bogdanandras.com/algorithms/grade-11/dynamic-programming/longest-common-subsequence/): Two words a and b are given. We look for the longest sequence of letters that appears as a subsequence (letters in order, not necessarily adjacent) in both… - [Longest strictly increasing subsequence in C++](https://bogdanandras.com/algorithms/grade-11/dynamic-programming/longest-strictly-increasing-subsequence/): From a sequence of n numbers we choose a strictly increasing subsequence (elements in their order in the sequence, not necessarily adjacent) that is as long… - [Maximum sum in a number triangle in C++](https://bogdanandras.com/algorithms/grade-11/dynamic-programming/maximum-sum-in-a-number-triangle/): A triangle has n rows; row i holds i numbers. We start from the top and at every step go either straight down (a[i+1][j]) or down and to the right… - [Maximum-sum path in a matrix in C++](https://bogdanandras.com/algorithms/grade-11/dynamic-programming/maximum-sum-path-in-a-matrix/): In an n × m matrix we start from the corner (1, 1) and reach (n, m) moving only right or down. We want the maximum sum of the elements on the path. Cell (i… - [Minimum number of coins in C++](https://bogdanandras.com/algorithms/grade-11/dynamic-programming/minimum-number-of-coins/): There are n coin types (any number of each) and we want to pay exactly the sum S with as few coins as possible. Greedy can be wrong (for the coins 1, 3, 4… - [Number of partitions of a number in C++](https://bogdanandras.com/algorithms/grade-11/dynamic-programming/number-of-partitions-of-a-number/): In how many ways can n be written as a sum of non-zero natural numbers, where the order of the terms does not matter? (4 = 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1… - [Number of paths in a grid with obstacles in C++](https://bogdanandras.com/algorithms/grade-11/dynamic-programming/number-of-paths-in-a-grid-with-obstacles/): An n × m grid has free cells (0) and obstacles (1). How many paths lead from (1, 1) to (n, m) if we move only right or down and never enter obstacles? A free… - [Number of ways to climb a staircase in C++](https://bogdanandras.com/algorithms/grade-11/dynamic-programming/number-of-ways-to-climb-a-staircase/): A staircase has n steps; at every move we climb either one step or two. In how many ways can we reach the top? Step i is reached either from step i - 1 or… - [The knapsack problem (0/1 version) in C++](https://bogdanandras.com/algorithms/grade-11/dynamic-programming/the-knapsack-problem-0-1-version/): A knapsack holds at most G kilograms; there are n objects with weights g[i] and values v[i], and an object is taken whole or not at all. Here greedy by value… - [Covering a segment with the minimum number of intervals in C++](https://bogdanandras.com/algorithms/grade-11/greedy/covering-a-segment-with-the-minimum-number-of-intervals/): We want to cover the segment [A, B] using as few as possible of the n given intervals [s[i], f[i]]. We sort the intervals by their left end. We keep the… - [The greedy method in C++](https://bogdanandras.com/algorithms/grade-11/greedy/): 6 C++ programs on the greedy method (Metoda greedy): covering a segment with the minimum number of intervals, scheduling shows (activity selection), paying a… - [Maximum sum with k elements in C++](https://bogdanandras.com/algorithms/grade-11/greedy/maximum-sum-with-k-elements/): From a sequence of n integers we choose exactly k elements (on different positions) with the largest possible sum. The greedy choice is obvious: take the k… - [Minimizing the average waiting time in C++](https://bogdanandras.com/algorithms/grade-11/greedy/minimizing-the-average-waiting-time/): n customers wait at a counter; serving customer i takes t[i] minutes. A customer's waiting time is the sum of the service times of the customers served… - [Paying a sum with the minimum number of banknotes in C++](https://bogdanandras.com/algorithms/grade-11/greedy/paying-a-sum-with-the-minimum-number-of-banknotes/): n banknote values are given (we have any number of each) and a sum S. The greedy strategy: pay as much as possible with the largest banknote, then continue… - [Scheduling shows (activity selection) in C++](https://bogdanandras.com/algorithms/grade-11/greedy/scheduling-shows-activity-selection/): n shows can be held in a hall; show i starts at time s[i] and ends at time f[i]. We want to schedule as many non-overlapping shows as possible (one may start… - [The knapsack problem (fractional version) in C++](https://bogdanandras.com/algorithms/grade-11/greedy/the-knapsack-problem-fractional-version/): A knapsack holds at most G kilograms. There are n objects; object i has weight g[i] and value v[i], and we may take just a piece (a fraction) of any object… - [Grade 11 C++ algorithms (Clasa a XI-a)](https://bogdanandras.com/algorithms/grade-11/): 62 C++ algorithms for grade 11: backtracking, the greedy method, dynamic programming, dynamic allocation: lists, stacks, queues, undirected graphs, directed… - [Checking brackets with a stack in C++](https://bogdanandras.com/algorithms/grade-11/lists-stacks-queues/checking-brackets-with-a-stack/): A string made of the brackets ( ) [ ] { } is correct if every opening bracket is closed by one of the same type, in the right order. We walk the string: an… - [Deleting nodes from a singly linked list in C++](https://bogdanandras.com/algorithms/grade-11/lists-stacks-queues/deleting-nodes-from-a-singly-linked-list/): A list is built from n values, then all nodes containing the value x are deleted. Deleting the first node moves the pointer prim to the next node. For a node… - [Doubly linked list in C++](https://bogdanandras.com/algorithms/grade-11/lists-stacks-queues/doubly-linked-list/): In a doubly linked list every node stores both the address of the next node (urm) and that of the previous one (ant), so the list can be traversed in both… - [Evaluating an expression in postfix (reverse Polish) notation in C++](https://bogdanandras.com/algorithms/grade-11/lists-stacks-queues/evaluating-an-expression-in-postfix-reverse-polish-notation/): In postfix notation the operator is written after its operands: (3 + 4) * 2 becomes 3 4 + 2 *, and parentheses are no longer needed. We read the elements one… - [Dynamic allocation: lists, stacks, queues in C++](https://bogdanandras.com/algorithms/grade-11/lists-stacks-queues/): 10 C++ programs on dynamic allocation: lists, stacks, queues (Alocare dinamică: liste, stive, cozi): queue implemented with a linked list, queue implemented… - [Inserting into a sorted list in C++](https://bogdanandras.com/algorithms/grade-11/lists-stacks-queues/inserting-into-a-sorted-list/): We read n numbers and insert them one by one into a singly linked list that is always kept in increasing order. If the new value is smaller than the first… - [Queue implemented with a linked list in C++](https://bogdanandras.com/algorithms/grade-11/lists-stacks-queues/queue-implemented-with-a-linked-list/): The queue is kept as a singly linked list with two pointers: prim (where we remove) and ultim (where we add). push links a new node after ultim; pop moves… - [Queue implemented with an array in C++](https://bogdanandras.com/algorithms/grade-11/lists-stacks-queues/queue-implemented-with-an-array/): The queue is a FIFO structure (first in, first out): elements are added at the end and removed from the front, as at a ticket counter. With an array c and… - [Singly linked list: create, print, add in C++](https://bogdanandras.com/algorithms/grade-11/lists-stacks-queues/singly-linked-list-create-print-add/): Every element of the list is a dynamically allocated node (with new) that stores a value (info) and the address of the next node (urm). We keep the address… - [Stack implemented with a linked list in C++](https://bogdanandras.com/algorithms/grade-11/lists-stacks-queues/stack-implemented-with-a-linked-list/): The top of the stack is the first node of a singly linked list. push creates a new node and links it in front of the top; pop moves the top to the next node… - [Stack implemented with an array in C++](https://bogdanandras.com/algorithms/grade-11/lists-stacks-queues/stack-implemented-with-an-array/): The stack is a LIFO structure (last in, first out): elements are added and removed only at the top. With an array st and an index vf (the number of… - [Binary search tree: insert, search, sorted print in C++](https://bogdanandras.com/algorithms/grade-11/trees/binary-search-tree-insert-search-sorted-print/): In a binary search tree, for every node, all values in the left subtree are smaller than the node's value and those in the right subtree are larger… - [Checking whether a graph is a tree in C++](https://bogdanandras.com/algorithms/grade-11/trees/checking-whether-a-graph-is-a-tree/): A tree is a connected undirected graph without cycles. For a graph with n nodes the following statements are equivalent: it is a tree; it is connected and… - [Children, descendants and ancestors of a node in C++](https://bogdanandras.com/algorithms/grade-11/trees/children-descendants-and-ancestors-of-a-node/): The tree is given by its parent array (t[root] = 0). The children of x are the nodes i with t[i] = x. A node y is a descendant of x if, climbing from y from… - [Diameter of a tree in C++](https://bogdanandras.com/algorithms/grade-11/trees/diameter-of-a-tree/): The diameter of a tree is the length (number of edges) of the longest path between two nodes. The two-traversal method: we run a BFS from node 1 and find the… - [Trees in C++](https://bogdanandras.com/algorithms/grade-11/trees/): 8 C++ programs on trees (Arbori): minimum spanning tree (Kruskal's algorithm), minimum spanning tree (Prim's algorithm), binary search tree: insert, search… - [Minimum spanning tree (Kruskal's algorithm) in C++](https://bogdanandras.com/algorithms/grade-11/trees/minimum-spanning-tree-kruskal-s-algorithm/): Kruskal builds the minimum spanning tree starting from n trees with a single node each. We sort the edges by cost in increasing order (on ties they stay in… - [Minimum spanning tree (Prim's algorithm) in C++](https://bogdanandras.com/algorithms/grade-11/trees/minimum-spanning-tree-prim-s-algorithm/): In a connected undirected graph with edge costs we look for a spanning tree (n - 1 edges connecting all nodes) with the minimum total cost. Prim grows the… - [Parent array: root, leaves, levels, height in C++](https://bogdanandras.com/algorithms/grade-11/trees/parent-array-root-leaves-levels-height/): A rooted tree can be stored as a parent array: t[i] is the parent of node i, and for the root t[i] = 0. The root is the node with t = 0. The leaves are the… - [Traversals of a binary tree in C++](https://bogdanandras.com/algorithms/grade-11/trees/traversals-of-a-binary-tree/): In a binary tree every node has at most two children: a left one and a right one. We store it with the arrays st[i] and dr[i] (0 if the child is missing)… - [Adjacency lists in C++](https://bogdanandras.com/algorithms/grade-11/undirected-graphs/adjacency-lists/): For every node we store only the list of its neighbours. The edge [x, y] is added twice: y to the list of x and x to the list of y. The memory used is… - [Adjacency matrix and node degrees in C++](https://bogdanandras.com/algorithms/grade-11/undirected-graphs/adjacency-matrix-and-node-degrees/): An undirected graph with n nodes and m edges can be stored in a matrix a with n rows and n columns: a[i][j] = 1 if the edge [i, j] exists, otherwise 0. The… - [Breadth-first search (BFS) in C++](https://bogdanandras.com/algorithms/grade-11/undirected-graphs/breadth-first-search-bfs/): Breadth-first search visits the nodes 'in layers': first the start node, then all its neighbours, then the neighbours' neighbours, and so on. We use a queue… - [Checking a bipartite graph in C++](https://bogdanandras.com/algorithms/grade-11/undirected-graphs/checking-a-bipartite-graph/): A graph is bipartite if its nodes can be split into two sets A and B so that every edge has one end in A and the other in B. We color the nodes with two… - [Checking a path (chain) in C++](https://bogdanandras.com/algorithms/grade-11/undirected-graphs/checking-a-path-chain/): A sequence of nodes x1, x2, ..., xk is a path if any two consecutive nodes are joined by an edge; the length of the path is k - 1 (the number of edges). The… - [Connected components in C++](https://bogdanandras.com/algorithms/grade-11/undirected-graphs/connected-components/): A graph is connected if there is a path between any two nodes. A connected component is a maximal connected 'piece' of the graph. We take the nodes in order… - [Depth-first search (DFS) in C++](https://bogdanandras.com/algorithms/grade-11/undirected-graphs/depth-first-search-dfs/): Depth-first search goes as far as it can: from the current node it moves to the first unvisited neighbour, from there to that node's first unvisited… - [Detecting a cycle in C++](https://bogdanandras.com/algorithms/grade-11/undirected-graphs/detecting-a-cycle/): A cycle is a simple path whose first node is also its last. We run a DFS traversal and keep for every node its parent (the node we came from). If from node x… - [Undirected graphs in C++](https://bogdanandras.com/algorithms/grade-11/undirected-graphs/): 10 C++ programs on undirected graphs (Grafuri neorientate): connected components, detecting a cycle, shortest path between two nodes (BFS), checking a… - [Isolated nodes and the complete graph in C++](https://bogdanandras.com/algorithms/grade-11/undirected-graphs/isolated-nodes-and-the-complete-graph/): An isolated node has degree 0. A graph is complete if any two distinct nodes are joined by an edge; the complete graph with n nodes has n · (n - 1) / 2 edges… - [Shortest path between two nodes (BFS) in C++](https://bogdanandras.com/algorithms/grade-11/undirected-graphs/shortest-path-between-two-nodes-bfs/): The length of a path is its number of edges. Breadth-first search started from x discovers the nodes in order of their distance from x, so the first time it… - [2D prefix sums in C++](https://bogdanandras.com/algorithms/grade-12/advanced-techniques/2d-prefix-sums/): s[i][j] = the sum of the elements in the rectangle with corners (1, 1) and (i, j). It is computed once: s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1]… - [Binary search on the answer in C++](https://bogdanandras.com/algorithms/grade-12/advanced-techniques/binary-search-on-the-answer/): We have n chapters with a[i] pages, in order, and k proofreaders. Every proofreader gets a run of consecutive chapters. We want the busiest proofreader to… - [Generating subsets with bitmasks in C++](https://bogdanandras.com/algorithms/grade-12/advanced-techniques/generating-subsets-with-bitmasks/): A subset of {a[0], ..., a[n-1]} can be encoded as a number masca between 0 and 2^n - 1: bit i of the mask is 1 if a[i] belongs to the subset. Bit i is tested… - [Advanced techniques: two pointers, binary search on the answer, monotonic stacks in C++](https://bogdanandras.com/algorithms/grade-12/advanced-techniques/): 7 C++ programs on advanced techniques: two pointers, binary search on the answer, monotonic stacks (Tehnici avansate: doi pointeri, căutare binară pe… - [Majority element (Boyer-Moore) in C++](https://bogdanandras.com/algorithms/grade-12/advanced-techniques/majority-element-boyer-moore/): The majority element appears more than n / 2 times. The voting algorithm keeps a candidate and a counter: a value equal to the candidate increases the… - [Monotonic stack: the next greater element in C++](https://bogdanandras.com/algorithms/grade-12/advanced-techniques/monotonic-stack-the-next-greater-element/): For every a[i] we look for the first strictly greater value to its right (or -1). We keep a stack with the positions still 'waiting' for a greater element… - [Sliding window: the longest subarray with sum ≤ S in C++](https://bogdanandras.com/algorithms/grade-12/advanced-techniques/sliding-window-the-longest-subarray-with-sum-s/): All numbers are strictly positive. We keep a window [st, dr] and its sum. We always extend the right end by one element; while the sum exceeds S, we remove… - [Two pointers: pairs with sum x in a sorted array in C++](https://bogdanandras.com/algorithms/grade-12/advanced-techniques/two-pointers-pairs-with-sum-x-in-a-sorted-array/): The array has n distinct values in strictly increasing order. We want the position pairs i < j with a[i] + a[j] = x. Instead of trying all n * (n-1) / 2… - [File: pairs of numbers with the same digit sum in C++](https://bogdanandras.com/algorithms/grade-12/baccalaureate-review/file-pairs-of-numbers-with-the-same-digit-sum/): The task (exam part III.3 style): the file date.in holds n (2 ≤ n ≤ 10^6) on the first line, then n natural numbers with at most 9 digits. Print how many… - [File: the common values of two sorted sequences in C++](https://bogdanandras.com/algorithms/grade-12/baccalaureate-review/file-the-common-values-of-two-sorted-sequences/): The task (exam part III.3 style): the file date.in holds n and m (1 ≤ n, m ≤ 10^5) on the first line, n natural numbers in increasing order on the second… - [File: the largest and smallest number formed from given digits in C++](https://bogdanandras.com/algorithms/grade-12/baccalaureate-review/file-the-largest-and-smallest-number-formed-from-given-digits/): The task (exam part III.3 style): the file date.in holds at most 10^6 digits separated by spaces. Using all the digits, each exactly once, print on the first… - [File: the longest run of terms with the same parity in C++](https://bogdanandras.com/algorithms/grade-12/baccalaureate-review/file-the-longest-run-of-terms-with-the-same-parity/): The task (exam part III.3 style): the file date.in holds a sequence of at most 10^6 natural numbers with at most 9 digits. A parity run is a run of… - [File: the values that appear exactly once in C++](https://bogdanandras.com/algorithms/grade-12/baccalaureate-review/file-the-values-that-appear-exactly-once/): The task (exam part III.3 style): the file date.in holds at most 10^6 natural numbers with at most three digits, separated by spaces. Print on the screen, in… - [Baccalaureate exam review in C++](https://bogdanandras.com/algorithms/grade-12/baccalaureate-review/): 10 C++ programs on baccalaureate exam review (Recapitulare pentru bacalaureat): file: the largest and smallest number formed from given digits, file: pairs… - [Matrix: concentric borders in C++](https://bogdanandras.com/algorithms/grade-12/baccalaureate-review/matrix-concentric-borders/): The task (exam part III.2 style): n is read (2 ≤ n ≤ 20). Build in memory a matrix with n rows and n columns in which the elements on the outer border are 1… - [Subprogram: how many numbers in a range have an odd number of divisors in C++](https://bogdanandras.com/algorithms/grade-12/baccalaureate-review/subprogram-how-many-numbers-in-a-range-have-an-odd-number-of-divisors/): The task (exam part III.1 style): the subprogram impare has the parameters a and b (1 ≤ a ≤ b ≤ 10^12) and returns how many numbers in [a, b] have an odd… - [Subprogram: removing the elements with k digits from an array in C++](https://bogdanandras.com/algorithms/grade-12/baccalaureate-review/subprogram-removing-the-elements-with-k-digits-from-an-array/): The task (exam part III.1 style): the subprogram elimina has the parameters v (an array of n natural numbers), n and k; it deletes from v all elements that… - [Subprogram: the number formed from the even digits in C++](https://bogdanandras.com/algorithms/grade-12/baccalaureate-review/subprogram-the-number-formed-from-the-even-digits/): The task (exam part III.1 style): the subprogram pare has a parameter n (0 ≤ n ≤ 10^9) and returns the number formed from the even digits of n, in the order… - [Text: reversing the words of even length in C++](https://bogdanandras.com/algorithms/grade-12/baccalaureate-review/text-reversing-the-words-of-even-length/): The task (exam part III.2 style): a text of at most 100 characters is read, made of lowercase words separated by single spaces. Print the text in which every… - [Adding two big numbers in C++](https://bogdanandras.com/algorithms/grade-12/big-numbers/adding-two-big-numbers/): We add as on paper, from the units to the left. At position i we compute s = a[i] + b[i] + carry; the result digit is s % 10, and the new carry is s / 10 (0… - [Comparing two big numbers in C++](https://bogdanandras.com/algorithms/grade-12/big-numbers/comparing-two-big-numbers/): Without leading zeros, the number with more digits is larger. If they have the same number of digits, we compare them from the most significant digit (the… - [Dividing a big number by a small number in C++](https://bogdanandras.com/algorithms/grade-12/big-numbers/dividing-a-big-number-by-a-small-number/): Unlike addition, division starts from the most significant digit, exactly like long division on paper. We keep the remainder r; for every digit we form r = r… - [Factorial as a big number in C++](https://bogdanandras.com/algorithms/grade-12/big-numbers/factorial-as-a-big-number/): Already 21! exceeds long long, but n! = 1 * 2 * ... * n can be built by repeatedly multiplying a big number by a small one. We start from the array with a… - [Big numbers in C++](https://bogdanandras.com/algorithms/grade-12/big-numbers/): 9 C++ programs on big numbers (Numere mari): adding two big numbers, reading and printing a big number, comparing two big numbers, factorial as a big number… - [Multiplying a big number by a small number in C++](https://bogdanandras.com/algorithms/grade-12/big-numbers/multiplying-a-big-number-by-a-small-number/): The small number k (at most 10^9) fits in an int, so it does not need to be split into digits. For every digit a[i], from the units, we compute t = a[i] * k… - [Multiplying two big numbers in C++](https://bogdanandras.com/algorithms/grade-12/big-numbers/multiplying-two-big-numbers/): The digit a[i] (rank 10^i) multiplied by the digit b[j] (rank 10^j) contributes to rank 10^(i+j). We first add all the products into c[i + j], without… - [Reading and printing a big number in C++](https://bogdanandras.com/algorithms/grade-12/big-numbers/reading-and-printing-a-big-number/): A number with tens or hundreds of digits does not fit in long long, so we read it as a string and keep its digits in an array, starting with the units digit… - [Subtracting two big numbers in C++](https://bogdanandras.com/algorithms/grade-12/big-numbers/subtracting-two-big-numbers/): We compute A - B. If A < B, we compute B - A and put a minus sign in front. We subtract from the units: d = a[i] - b[i] - borrow; if d comes out negative, we… - [The n-th Fibonacci term (big number) in C++](https://bogdanandras.com/algorithms/grade-12/big-numbers/the-n-th-fibonacci-term-big-number/): The sequence is F(1) = F(2) = 1 and F(i) = F(i - 1) + F(i - 2). The terms grow exponentially (F(93) no longer fits in long long), so we keep them as big… - [deque: sliding window minimum of length k in C++](https://bogdanandras.com/algorithms/grade-12/data-structures-stl/deque-sliding-window-minimum-of-length-k/): For every run of k consecutive elements we want the minimum. We keep the 'candidate' positions in a deque, with values increasing from front to back. When… - [Disjoint-set forests (union-find) in C++](https://bogdanandras.com/algorithms/grade-12/data-structures-stl/disjoint-set-forests-union-find/): We have n elements, each initially in its own set. Operation 1 x y joins the sets of x and y, and operation 2 x y asks whether x and y are in the same set… - [Data structures and the STL in C++](https://bogdanandras.com/algorithms/grade-12/data-structures-stl/): 9 C++ programs on data structures and the stl (Structuri de date și STL): deque: sliding window minimum of length k, queue: elimination in a circle… - [pair: union of intervals in C++](https://bogdanandras.com/algorithms/grade-12/data-structures-stl/pair-union-of-intervals/): pair groups two values (first, second) and compares lexicographically: first by first, then by second. So sort on an array of pairs orders the… - [priority_queue: the k largest values in C++](https://bogdanandras.com/algorithms/grade-12/data-structures-stl/priority-queue-the-k-largest-values/): priority_queue is a heap: top() gives the 'most important' element, and push and pop cost O(log size). By default the top is the maximum; with greater keeps every word once, in alphabetical order, so size() gives the number of… - [Sorting with a comparator in C++](https://bogdanandras.com/algorithms/grade-12/data-structures-stl/sorting-with-a-comparator/): sort(begin, end, cmp) orders by our own rule: cmp(x, y) returns true if x must come before y. Here we sort the contestants of a competition by score in… - [stack: checking brackets in C++](https://bogdanandras.com/algorithms/grade-12/data-structures-stl/stack-checking-brackets/): A string with the brackets (), [] and {} is correct if every closing bracket matches the last opening bracket still left open. 'Last opened, first closed' is… - [The STL vector container in C++](https://bogdanandras.com/algorithms/grade-12/data-structures-stl/the-stl-vector-container/): vector is an array that manages its own memory: push_back adds at the end (O(1) on average), size() gives the number of elements, and v[i] accesses… - [Grade 12 C++ algorithms (Clasa a XII-a)](https://bogdanandras.com/algorithms/grade-12/): 50 C++ algorithms for grade 12: big numbers, grid algorithms: lee and flood fill, math for programming, advanced techniques: two pointers, binary search on… - [Flood fill: the largest region in C++](https://bogdanandras.com/algorithms/grade-12/lee-flood-fill/flood-fill-the-largest-region/): The same matrix of 0s and 1s, but now we want the number of cells of the largest region of 1s (adjacency through sides). This time the fill is done without… - [Flood fill: the number of regions in C++](https://bogdanandras.com/algorithms/grade-12/lee-flood-fill/flood-fill-the-number-of-regions/): The matrix has n rows and m columns, with 1 for land and 0 for water. A region is a maximal group of 1 cells connected through their sides (up, down, left… - [Grid algorithms: Lee and flood fill in C++](https://bogdanandras.com/algorithms/grade-12/lee-flood-fill/): 6 C++ programs on grid algorithms: lee and flood fill (Algoritmi pe grile: Lee și fill): flood fill: the largest region, flood fill: the number of regions… - [Islands in 8 directions in C++](https://bogdanandras.com/algorithms/grade-12/lee-flood-fill/islands-in-8-directions/): Like counting regions, but two land cells (1) belong to the same island if they touch even at a corner, i.e. the neighbourhood has 8 directions. The only… - [Lee: the shortest path in a grid in C++](https://bogdanandras.com/algorithms/grade-12/lee-flood-fill/lee-the-shortest-path-in-a-grid/): The grid has n rows and m columns: 0 = free, 1 = obstacle. We can move up, down, left, right. Lee's algorithm is a breadth-first search: d[xs][ys] = 1, then… - [Lee with multiple sources in C++](https://bogdanandras.com/algorithms/grade-12/lee-flood-fill/lee-with-multiple-sources/): The grid holds 0 (free), 1 (wall) and 2 (source, for example a well). For every free cell we want the minimum number of steps to the nearest source. Instead… - [Lee with path reconstruction in C++](https://bogdanandras.com/algorithms/grade-12/lee-flood-fill/lee-with-path-reconstruction/): After Lee has filled the distance matrix, the path is rebuilt from the end towards the start: if we are in a cell with value k, one of its neighbours… - [Combinations modulo a prime in C++](https://bogdanandras.com/algorithms/grade-12/math/combinations-modulo-a-prime/): We compute C(n, k) mod P, with P = 1,000,000,007 (prime) and n ≤ 10^6. We have C(n, k) = n! / (k! * (n-k)!), but division cannot be done directly on… - [Extended Euclidean algorithm in C++](https://bogdanandras.com/algorithms/grade-12/math/extended-euclidean-algorithm/): Besides d = gcd(a, b), we find integers x and y with a * x + b * y = d. If b = 0, then d = a, x = 1, y = 0. Otherwise we solve recursively for (b, a % b) and… - [Fast exponentiation in C++](https://bogdanandras.com/algorithms/grade-12/math/fast-exponentiation/): We compute a^n with about log2(n) multiplications instead of n. The idea: a^n = (a^2)^(n/2) if n is even and a^n = a * a^(n-1) if n is odd. The iterative… - [Math for programming in C++](https://bogdanandras.com/algorithms/grade-12/math/): 9 C++ programs on math for programming (Matematică pentru programare): smallest-prime-factor sieve and fast factorization, combinations modulo a prime… - [Modular exponentiation in C++](https://bogdanandras.com/algorithms/grade-12/math/modular-exponentiation/): We compute a^n mod m for n up to 10^18. We use the same idea as fast exponentiation, but after every multiplication we take the remainder modulo m: (x * y)… - [Number and sum of divisors from the prime factorization in C++](https://bogdanandras.com/algorithms/grade-12/math/number-and-sum-of-divisors-from-the-prime-factorization/): If n = p1^e1 * p2^e2 * ... * pk^ek, a divisor chooses for every prime an exponent between 0 and ei, so the number of divisors is (e1 + 1) * (e2 + 1) * ... *… - [Number of multiples of k in a range in C++](https://bogdanandras.com/algorithms/grade-12/math/number-of-multiples-of-k-in-a-range/): How many numbers in [a, b] are divisible by k? The numbers in [1, x] divisible by k are k, 2k, ..., (x / k) * k, i.e. x / k of them (integer division). We… - [Pascal's triangle (combinations) in C++](https://bogdanandras.com/algorithms/grade-12/math/pascal-s-triangle-combinations/): The combinations C(i, j), the number of j-element subsets of an i-element set, satisfy C(i, j) = C(i-1, j-1) + C(i-1, j): either we choose element i, or we… - [Smallest-prime-factor sieve and fast factorization in C++](https://bogdanandras.com/algorithms/grade-12/math/smallest-prime-factor-sieve-and-fast-factorization/): A variant of the Sieve of Eratosthenes: instead of only marking 'composite', we store in dp[x] the smallest prime divisor of x. For every prime p (dp[p]… - [Sum of an arithmetic progression: formula vs. loop in C++](https://bogdanandras.com/algorithms/grade-12/math/sum-of-an-arithmetic-progression-formula-vs-loop/): The progression has first term a, common difference r and n terms: a, a + r, ..., a + (n-1) * r. The loop adds the terms one by one, so it takes n steps… - [Common digits of two numbers in C++](https://bogdanandras.com/algorithms/grade-9/array-techniques/common-digits-of-two-numbers/): In two arrays of 10 positions we mark which digits appear in each number (aparA[c], aparB[c]). The common digits are the ones marked in both arrays; we print… - [Distinct values and their frequencies in C++](https://bogdanandras.com/algorithms/grade-9/array-techniques/distinct-values-and-their-frequencies/): Once the frequency array is built, the distinct values are the indices val with frecv[val] > 0. Going through them in increasing order, we print them… - [Frequency array in C++](https://bogdanandras.com/algorithms/grade-9/array-techniques/frequency-array/): For small natural values (here 0..1000), frecv[x] stores how many times the value x has appeared. The value becomes an index, so every number read is counted… - [Frequency arrays, prefix sums and the Sieve of Eratosthenes in C++](https://bogdanandras.com/algorithms/grade-9/array-techniques/): 10 C++ programs on frequency arrays, prefix sums and the sieve of eratosthenes (Frecvență, sume parțiale și ciurul lui Eratostene): common digits of two… - [Majority element in C++](https://bogdanandras.com/algorithms/grade-9/array-techniques/majority-element/): The majority element appears more than n / 2 times. The voting algorithm (Boyer-Moore) keeps a candidate and a counter: an element equal to the candidate… - [Marking ranges with a difference array in C++](https://bogdanandras.com/algorithms/grade-9/array-techniques/marking-ranges-with-a-difference-array/): We have n positions, initially 0, and m operations 'add 1 to positions a..b'. Instead of walking every range, we only note its ends: d[a]++ (it starts here)… - [Maximum subarray sum (Kadane's algorithm) in C++](https://bogdanandras.com/algorithms/grade-9/array-techniques/maximum-subarray-sum-kadane-s-algorithm/): We go through the array and keep the sum of the current subarray, which ends at position i. If the sum so far has become negative, it no longer helps: we… - [Prefix sums in C++](https://bogdanandras.com/algorithms/grade-9/array-techniques/prefix-sums/): s[i] = v[1] + v[2] + ... + v[i], with s[0] = 0, is computed in a single pass: s[i] = s[i - 1] + v[i]. Then the sum over any range [st, dr] is s[dr] - s[st… - [Sieve of Eratosthenes in C++](https://bogdanandras.com/algorithms/grade-9/array-techniques/sieve-of-eratosthenes/): Finds all prime numbers up to n. We start with all numbers unmarked; for every unmarked i (hence prime) we mark its multiples as not prime, starting from i *… - [Subarray of length k with the maximum sum in C++](https://bogdanandras.com/algorithms/grade-9/array-techniques/subarray-of-length-k-with-the-maximum-sum/): Sliding window: we compute the sum of the first k elements, then slide the window one position to the right: we add the element that enters (v[i]) and… - [The missing number in a permutation in C++](https://bogdanandras.com/algorithms/grade-9/array-techniques/the-missing-number-in-a-permutation/): n and n - 1 distinct numbers from the set {1, 2, ..., n} are given; exactly one is missing. The sum of all numbers from 1 to n is n · (n + 1) / 2 (Gauss's… - [Checking a symmetric array in C++](https://bogdanandras.com/algorithms/grade-9/arrays/checking-a-symmetric-array/): An array is symmetric (a palindrome) if v[i] = v[n - i + 1] for every i. We compare the pairs from both ends towards the middle and stop at the first pair… - [Circular shift to the left in C++](https://bogdanandras.com/algorithms/grade-9/arrays/circular-shift-to-the-left/): Every element moves one position to the left, and the first one goes to the last position. We save v[1] in a variable, shift the rest (v[i] = v[i + 1]) and… - [Circular shift to the right in C++](https://bogdanandras.com/algorithms/grade-9/arrays/circular-shift-to-the-right/): Every element moves one position to the right, and the last one goes to the first position. We save v[n], shift the rest from the end towards the beginning… - [Deleting the element at a position in C++](https://bogdanandras.com/algorithms/grade-9/arrays/deleting-the-element-at-a-position/): To delete the element at position poz, we shift the elements after it one position to the left, from left to right (v[i] = v[i + 1]), then n decreases by 1… - [One-dimensional arrays (vectors) in C++](https://bogdanandras.com/algorithms/grade-9/arrays/): 11 C++ programs on one-dimensional arrays (vectors) (Tablouri unidimensionale (vectori)): reading and printing an array, removing the even elements… - [Inserting a value after every even element in C++](https://bogdanandras.com/algorithms/grade-9/arrays/inserting-a-value-after-every-even-element/): We go through the array from the end to the beginning. When v[i] is even, we shift the elements after it one position to the right and put x at position i +… - [Inserting an element at a position in C++](https://bogdanandras.com/algorithms/grade-9/arrays/inserting-an-element-at-a-position/): To put val at position poz, we make room: we shift the elements v[poz..n] one position to the right. Shifting starts from the end (from n down to poz); going… - [Reading and printing an array in C++](https://bogdanandras.com/algorithms/grade-9/arrays/reading-and-printing-an-array/): An array stores several values of the same type, accessed by index. We declare the array with a fixed maximum size and use positions 1..n. n and the n… - [Removing the even elements in C++](https://bogdanandras.com/algorithms/grade-9/arrays/removing-the-even-elements/): Instead of deleting the even elements one by one (every deletion shifts the whole rest of the array), we make a single pass: k counts the elements kept, and… - [Reversing an array in C++](https://bogdanandras.com/algorithms/grade-9/arrays/reversing-an-array/): We swap the first element with the last, the second with the second to last, and so on: v[i] with v[n - i + 1]. We stop halfway (i <= n / 2); if we went up… - [Sum of the elements on even and odd positions in C++](https://bogdanandras.com/algorithms/grade-9/arrays/sum-of-the-elements-on-even-and-odd-positions/): Mind the difference between the position (the index i) and the value (v[i]). Parity is checked here for the index: v[2], v[4], ... are on even positions. The… - [The maximum and the positions where it appears in C++](https://bogdanandras.com/algorithms/grade-9/arrays/the-maximum-and-the-positions-where-it-appears/): Unlike a sequence read one value at a time, an array can be traversed several times: in the first pass we find the maximum, in the second we print every… - [Check digit (digital root) in C++](https://bogdanandras.com/algorithms/grade-9/digits/check-digit-digital-root/): The check digit is obtained by repeatedly replacing the number with the sum of its digits until a single digit remains (for example 99999 -> 45 -> 9). The… - [Checking for distinct digits in C++](https://bogdanandras.com/algorithms/grade-9/digits/checking-for-distinct-digits/): Checks whether all digits of n are different. We remember which digits we have already seen (vazut[c] becomes true on the first occurrence of c); if we meet… - [Doubling the odd digits in C++](https://bogdanandras.com/algorithms/grade-9/digits/doubling-the-odd-digits/): Every odd digit of n appears twice in the result. We build the result from right to left with rez = rez + digit * p; an odd digit is added twice, so p grows… - [First digit of a number in C++](https://bogdanandras.com/algorithms/grade-9/digits/first-digit-of-a-number/): The first (leftmost) digit is what remains after we cut off all the other digits: we divide by 10 while the number has at least two digits (n >= 10)… - [Digits of a number in C++](https://bogdanandras.com/algorithms/grade-9/digits/): 15 C++ programs on digits of a number (Cifrele unui număr): number of occurrences of digit k, largest number formed from the digits of n, check digit… - [Largest and smallest digit in C++](https://bogdanandras.com/algorithms/grade-9/digits/largest-and-smallest-digit/): We start with the maximum at 0 (the smallest possible digit) and the minimum at 9 (the largest possible digit), then compare every digit with them. We use… - [Largest number formed from the digits of n in C++](https://bogdanandras.com/algorithms/grade-9/digits/largest-number-formed-from-the-digits-of-n/): We count how many times each digit appears, in a frequency array with 10 positions (frecv[c] = how many times digit c appears). The largest number is… - [Number of digits of a number in C++](https://bogdanandras.com/algorithms/grade-9/digits/number-of-digits-of-a-number/): Counts the digits of n by cutting off the last digit at every step (n / 10) until the number becomes 0. We use do-while so that the number 0 is counted… - [Number of occurrences of digit k in C++](https://bogdanandras.com/algorithms/grade-9/digits/number-of-occurrences-of-digit-k/): We go through the digits of n and count how many are equal to k. With do-while, for n = 0 and k = 0 the answer is correctly 1. Complexity O(n). Original… - [Palindrome number in C++](https://bogdanandras.com/algorithms/grade-9/digits/palindrome-number/): A number is a palindrome if it reads the same from left to right and from right to left, i.e. it is equal to its reverse. We work on a copy, because the loop… - [Printing the digits in their order in the number in C++](https://bogdanandras.com/algorithms/grade-9/digits/printing-the-digits-in-their-order-in-the-number/): With n % 10 the digits come out from right to left. To print them from left to right, we first compute p = the largest power of 10 not greater than n. Then… - [Product of the digits of a number in C++](https://bogdanandras.com/algorithms/grade-9/digits/product-of-the-digits-of-a-number/): Multiplies the digits of n. The product starts from 1 (the identity element of multiplication), not from 0. With do-while, for n = 0 we correctly get the… - [Removing the even digits in C++](https://bogdanandras.com/algorithms/grade-9/digits/removing-the-even-digits/): We build a new number from the odd digits of n, keeping their order. The digits come from right to left, so every kept digit is placed in front of the ones… - [Replacing one digit with another in C++](https://bogdanandras.com/algorithms/grade-9/digits/replacing-one-digit-with-another/): Replaces every occurrence of digit x in n with digit y. We rebuild the number from right to left with rez = rez + digit * p, putting y in place of every… - [Reverse of a number in C++](https://bogdanandras.com/algorithms/grade-9/digits/reverse-of-a-number/): Builds the number made of the digits of n written in reverse order. At every step we take the last digit (n % 10), append it to the right of the reversed… - [Sum of the digits of a number in C++](https://bogdanandras.com/algorithms/grade-9/digits/sum-of-the-digits-of-a-number/): Adds up the digits of n. The last digit is obtained with n % 10, then removed with n / 10. We repeat until n becomes 0. Complexity O(n). Original: Suma… - [Coprime numbers in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/coprime-numbers/): Two numbers are coprime if their only common divisor is 1, i.e. gcd(a, b) = 1. The numbers themselves do not have to be prime: 15 and 28 are coprime… - [Divisors of a number in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/divisors-of-a-number/): Divisors come in pairs: if d divides n, then n / d divides n too, and one of them is at most the square root of n. So it is enough to try d from 1 while d *… - [Euler's totient function in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/euler-s-totient-function/): φ(n) is the number of values in 1..n that are coprime with n. If p1, p2, ... are the prime divisors of n, then φ(n) = n · (1 - 1/p1) · (1 - 1/p2) · ... For… - [GCD by repeated division (Euclid's algorithm) in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/gcd-by-repeated-division-euclid-s-algorithm/): The greatest common divisor does not change if we replace the pair (a, b) with (b, a % b). We repeat until b becomes 0; then the GCD is a. It also works when… - [GCD by repeated subtraction in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/gcd-by-repeated-subtraction/): We subtract the smaller number from the larger one until they become equal; the common value is the GCD. It only works for a, b > 0 (with a 0 the loop would… - [Divisibility and prime numbers in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/): 17 C++ programs on divisibility and prime numbers (Divizibilitate și numere prime): gCD by repeated division (Euclid's algorithm), gCD by repeated… - [Last digit of x to the power y in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/last-digit-of-x-to-the-power-y/): The last digit of a product depends only on the last digits of the factors. The last digits of powers repeat with period 4 (for example for 3: 3, 9, 7, 1, 3… - [Least common multiple in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/least-common-multiple/): We use the relation gcd(a, b) * lcm(a, b) = a * b. We compute the GCD with Euclid's algorithm on copies of a and b, then lcm = a / gcd * b (we divide first… - [Number of divisors in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/number-of-divisors/): For every d with d * d <= n that divides n we count two divisors, d and n / d, except when d * d == n, when the two coincide. Complexity O(√n). Original… - [Pairs of twin primes in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/pairs-of-twin-primes/): Two prime numbers are twins if their difference is 2 (for example 11 and 13). We print all pairs (p, p + 2) with p + 2 <= n, testing both numbers for… - [Perfect number in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/perfect-number/): A number is perfect if it equals the sum of its divisors smaller than itself (6 = 1 + 2 + 3). We compute the sum of all divisors in O(√n) and subtract n… - [Primality test in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/primality-test/): A number is prime if it has exactly two divisors: 1 and itself (so 0 and 1 are not prime). If n has a divisor d between 2 and n - 1, it also has one at most… - [Prime divisors of a number in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/prime-divisors-of-a-number/): This is the prime factorization, printing only the factors, without exponents. Every factor found is removed completely from n. Complexity O(√n). Original… - [Prime factorization in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/prime-factorization/): We try the factors d = 2, 3, 4, ... and divide n by d as many times as possible, counting how many times (the exponent). A composite d no longer divides n… - [Proper divisors of a number in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/proper-divisors-of-a-number/): Proper divisors are the divisors other than 1 and n. We use the same two passes as when printing all divisors, but start from d = 2, so 1 and its pair, n… - [Simplifying a fraction in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/simplifying-a-fraction/): A fraction a / b becomes irreducible if we divide the numerator and the denominator by gcd(a, b). We compute the GCD on copies, to keep the original values… - [Sum of divisors in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/sum-of-divisors/): We add the divisors in pairs (d and n / d) for d * d <= n; when n is a perfect square, the root is added only once. Complexity O(√n). Original: Suma… - [The first n prime numbers in C++](https://bogdanandras.com/algorithms/grade-9/divisibility-primes/the-first-n-prime-numbers/): We take the candidates 2, 3, 4, ... one by one and test them with the primality test up to √x. We stop after printing n prime numbers. Complexity Other… - [Grade 9 C++ algorithms (Clasa a IX-a)](https://bogdanandras.com/algorithms/grade-9/): 87 C++ algorithms for grade 9: digits of a number, divisibility and prime numbers, number sequences read one at a time, number bases, one-dimensional arrays… - [Checking for a power of 2 in C++](https://bogdanandras.com/algorithms/grade-9/number-bases/checking-for-a-power-of-2/): A power of 2 has a single 1 bit in base 2 (for example 64 = 1000000). Subtracting 1 turns that bit into 0 and all the bits to its right into 1 (63 =… - [Converting between any two bases in C++](https://bogdanandras.com/algorithms/grade-9/number-bases/converting-between-any-two-bases/): We go through base 10: first we convert the number from base b1 to base 10 (Horner's scheme), then from base 10 to base b2 (repeated division). The number… - [Converting from base 10 to base b in C++](https://bogdanandras.com/algorithms/grade-9/number-bases/converting-from-base-10-to-base-b/): We repeatedly divide n by b; the remainders are the digits in base b, but they come from the last to the first. That is why every new digit is placed in… - [Converting from base b to base 10 in C++](https://bogdanandras.com/algorithms/grade-9/number-bases/converting-from-base-b-to-base-10/): The number in base b is read as text (it may contain A..F), then Horner's scheme is applied: we go through the digits from left to right and do rez = rez * b… - [Converting to base 10 using powers of the base in C++](https://bogdanandras.com/algorithms/grade-9/number-bases/converting-to-base-10-using-powers-of-the-base/): The version for b <= 10, when the number can be read as an integer: its digits are extracted from the right with n % 10, and every digit is multiplied by the… - [Number bases in C++](https://bogdanandras.com/algorithms/grade-9/number-bases/): 6 C++ programs on number bases (Baze de numerație): converting from base 10 to base b, converting to base 10 using powers of the base, converting from base b… - [Number of 1 bits in binary in C++](https://bogdanandras.com/algorithms/grade-9/number-bases/number-of-1-bits-in-binary/): The base-2 digits are obtained just like the base-10 digits, except that we divide by 2: the last binary digit is n % 2. We count how many of them are 1. 13… - [Checking a non-decreasing sequence in C++](https://bogdanandras.com/algorithms/grade-9/sequences/checking-a-non-decreasing-sequence/): The sequence is non-decreasing if every number is at least equal to the one before it. We keep the previous number in the variable ant and compare every new… - [Checking an arithmetic progression in C++](https://bogdanandras.com/algorithms/grade-9/sequences/checking-an-arithmetic-progression/): A sequence is an arithmetic progression if the difference between two consecutive terms is always the same (the common difference). The difference is found… - [Counting elements with a property in C++](https://bogdanandras.com/algorithms/grade-9/sequences/counting-elements-with-a-property/): n and n natural numbers are read. We count how many of them are even and how many have the last digit equal to the first. Each property has its own counter… - [GCD of several numbers in C++](https://bogdanandras.com/algorithms/grade-9/sequences/gcd-of-several-numbers/): gcd(a, b, c) = gcd(gcd(a, b), c). We keep in rez the GCD of the numbers read so far and combine it, with Euclid's algorithm, with every new number. We start… - [Number sequences read one at a time in C++](https://bogdanandras.com/algorithms/grade-9/sequences/): 13 C++ programs on number sequences read one at a time (Șiruri de numere citite pe rând): longest run of equal elements, largest Fibonacci term not greater… - [Largest Fibonacci term not greater than n in C++](https://bogdanandras.com/algorithms/grade-9/sequences/largest-fibonacci-term-not-greater-than-n/): We generate the terms of the Fibonacci sequence (1, 1, 2, 3, 5, ...) while the next term does not exceed n. The last term kept is the answer. We assume n >=… - [Longest run of equal elements in C++](https://bogdanandras.com/algorithms/grade-9/sequences/longest-run-of-equal-elements/): A run means elements on consecutive positions. lung is the length of the current run: it grows when the new number equals the previous one and goes back to 1… - [Maximum and minimum of a sequence in C++](https://bogdanandras.com/algorithms/grade-9/sequences/maximum-and-minimum-of-a-sequence/): n is read, then n integers. The maximum and the minimum start from the first number read (not from 0, because all numbers may be negative), then every… - [Number of sign changes in C++](https://bogdanandras.com/algorithms/grade-9/sequences/number-of-sign-changes/): n non-zero numbers are read. A sign change happens between two consecutive terms with opposite signs, i.e. when their product is negative. We compare the… - [Pairs of consecutive terms with a property in C++](https://bogdanandras.com/algorithms/grade-9/sequences/pairs-of-consecutive-terms-with-a-property/): We count the pairs of adjacent terms that have the same parity. A sequence of n terms has n - 1 consecutive pairs; for every new term x, the pair is (ant… - [Reading a sequence terminated by 0 in C++](https://bogdanandras.com/algorithms/grade-9/sequences/reading-a-sequence-terminated-by-0/): We do not know in advance how many numbers follow: we read up to the first 0, which only marks the end and is not part of the sequence. The program prints… - [Sum and arithmetic mean in C++](https://bogdanandras.com/algorithms/grade-9/sequences/sum-and-arithmetic-mean/): n and n integers are read; their sum and arithmetic mean are printed, with two decimals. For the mean we divide a real number by n (1.0 * suma / n); suma / n… - [The n-th term of the Fibonacci sequence in C++](https://bogdanandras.com/algorithms/grade-9/sequences/the-n-th-term-of-the-fibonacci-sequence/): The Fibonacci sequence starts with 1, 1 and every term is the sum of the two before it: 1, 1, 2, 3, 5, 8, ... We do not need an array: we keep only the last… - [The two largest values in C++](https://bogdanandras.com/algorithms/grade-9/sequences/the-two-largest-values/): We keep the largest value (max1) and the second one (max2). If the new number exceeds max1, the old max1 moves down to second place; otherwise, if it exceeds… - [Binary search in C++](https://bogdanandras.com/algorithms/grade-9/sorting-searching/binary-search/): It only works on an array sorted in increasing order. We compare x with the middle element of the range [st, dr]: if they are equal, we are done; if x is… - [Bubble sort in C++](https://bogdanandras.com/algorithms/grade-9/sorting-searching/bubble-sort/): We go through the array and swap any two neighbouring elements that are in the wrong order (v[i] > v[i + 1]). After every pass, the largest remaining element… - [Counting sort in C++](https://bogdanandras.com/algorithms/grade-9/sorting-searching/counting-sort/): When the values are small natural numbers (here 0..10000), we do not compare elements: we count how many times each value appears in a frequency array, then… - [First position with a value greater than or equal to x in C++](https://bogdanandras.com/algorithms/grade-9/sorting-searching/first-position-with-a-value-greater-than-or-equal-to-x/): The binary search variant that does not stop at the first match: in an array sorted in increasing order, we look for the smallest position p with v[p] >= x… - [Sorting and searching in C++](https://bogdanandras.com/algorithms/grade-9/sorting-searching/): 10 C++ programs on sorting and searching (Sortare și căutare): binary search, linear search, merging two sorted arrays, first position with a value greater… - [Insertion sort in C++](https://bogdanandras.com/algorithms/grade-9/sorting-searching/insertion-sort/): Like arranging playing cards in your hand: the first i - 1 elements are already sorted, and v[i] is inserted in its place among them. We save v[i] in x and… - [Linear search in C++](https://bogdanandras.com/algorithms/grade-9/sorting-searching/linear-search/): We check the elements one by one, starting from the first, until we find the value x or reach the end of the array. It works on any array, sorted or not. The… - [Merging two sorted arrays in C++](https://bogdanandras.com/algorithms/grade-9/sorting-searching/merging-two-sorted-arrays/): From two arrays sorted in increasing order we build a third, also sorted. We compare the current elements a[i] and b[j], copy the smaller one and advance… - [Selection sort in C++](https://bogdanandras.com/algorithms/grade-9/sorting-searching/selection-sort/): For every position i, from 1 to n - 1, we look for the minimum of v[i..n] and bring it to position i with a single swap. After step i, the first i positions… - [Sorting by two criteria in C++](https://bogdanandras.com/algorithms/grade-9/sorting-searching/sorting-by-two-criteria/): We order the numbers increasingly by their last digit, and numbers with the same last digit decreasingly by value. The sorting algorithm stays the same (here… - [Sorting with std::sort in C++](https://bogdanandras.com/algorithms/grade-9/sorting-searching/sorting-with-std-sort/): The library has the sort function, which orders in O(n log n). It takes the start and the end of the range: for positions 1..n we write sort(v +… - [Counting the values in a file in C++](https://bogdanandras.com/algorithms/grade-9/text-files/counting-the-values-in-a-file/): The file date.in contains a natural number k on the first line, and on the following lines a sequence of natural numbers of unknown length. We read until the… - [Formatted writing to a file in C++](https://bogdanandras.com/algorithms/grade-9/text-files/formatted-writing-to-a-file/): n is read from date.in and the numbers from 1 to n are written to date.out, five per line. ofstream is used exactly like cout; a new line is written with… - [Text files in C++](https://bogdanandras.com/algorithms/grade-9/text-files/): 5 C++ programs on text files (Fișiere text): reading until the end of the file, counting the values in a file, processing a file line by line, formatted… - [Processing a file line by line in C++](https://bogdanandras.com/algorithms/grade-9/text-files/processing-a-file-line-by-line/): getline(fin, linie) reads a whole line, spaces included, up to '\n'. The loop while (getline(fin, linie)) stops at the end of the file. We count the lines… - [Reading until the end of the file in C++](https://bogdanandras.com/algorithms/grade-9/text-files/reading-until-the-end-of-the-file/): The file date.in contains integers, but we do not know how many. The expression fin >> x returns 'true' as long as reading succeeds and 'false' at the end of… - [Sum of the numbers on each line in C++](https://bogdanandras.com/algorithms/grade-9/text-files/sum-of-the-numbers-on-each-line/): Every line of date.in contains a few integers, an unknown number of them. We read the line with getline, then 're-read' it as a stream of numbers with… - [266 C++ algorithms for high school, explained and runnable](https://bogdanandras.com/algorithms/): Free platform with 266 elementary C++ algorithms for grades 9–12 (Romanian curriculum): explanations in English, original Romanian comments, examples, a live… - [Căutare binară recursivă în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/divide-et-impera/cautare-binara-recursiva/): Vectorul este sortat crescător. Comparăm x cu elementul din mijloc: dacă sunt egale am terminat; dacă x este mai mic, căutăm doar în jumătatea stângă, altfel… - [Cmmdc-ul elementelor unui vector prin divide et impera în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/divide-et-impera/cmmdc-ul-elementelor-unui-vector-prin-divide-et-impera/): Cmmdc-ul unei porțiuni este cmmdc-ul dintre cmmdc-ul jumătății stângi și cmmdc-ul jumătății drepte, pentru că cmmdc(a, b, c, d) = cmmdc(cmmdc(a, b), cmmdc(c… - [Divide et impera în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/divide-et-impera/): 8 algoritmi C++ rezolvați la „Divide et impera” (clasa a 10-a): căutare binară recursivă, cmmdc-ul elementelor unui vector prin divide et impera, maximul… - [Maximul unui vector prin divide et impera în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/divide-et-impera/maximul-unui-vector-prin-divide-et-impera/): Cele trei etape ale metodei: împărțim porțiunea [st, dr] în două jumătăți, la mijlocul m = (st + dr) / 2 (divide); aflăm recursiv maximul fiecărei jumătăți… - [Numărul elementelor pare prin divide et impera în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/divide-et-impera/numarul-elementelor-pare-prin-divide-et-impera/): Același tipar ca la sumă: rezultatul pentru porțiunea [st, dr] este suma rezultatelor celor două jumătăți. Diferă doar cazul elementar: o porțiune cu un… - [Sortarea prin interclasare (Merge Sort) în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/divide-et-impera/sortarea-prin-interclasare-merge-sort/): Împărțim vectorul în două jumătăți, sortăm recursiv fiecare jumătate, apoi le interclasăm: comparăm mereu primele elemente rămase din cele două jumătăți și… - [Sortarea rapidă (Quick Sort) în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/divide-et-impera/sortarea-rapida-quick-sort/): Alegem un pivot (aici elementul din mijloc) și rearanjăm porțiunea astfel încât în stânga să ajungă valori <= pivot, iar în dreapta valori >= pivot: indicele… - [Suma elementelor prin divide et impera în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/divide-et-impera/suma-elementelor-prin-divide-et-impera/): Suma porțiunii [st, dr] este suma jumătății stângi [st, m] plus suma jumătății drepte [m + 1, dr]. O porțiune cu un singur element are suma egală cu acel… - [Turnurile din Hanoi în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/divide-et-impera/turnurile-din-hanoi/): Avem n discuri pe tija A, în ordine descrescătoare a mărimii, și vrem să le mutăm pe tija C, folosind tija B, fără să punem vreodată un disc mare peste unul… - [Algoritmi C++ clasa a 10-a](https://bogdanandras.com/algoritmi/clasa-a-10-a/): 67 de algoritmi C++ rezolvați pentru clasa a 10-a: subprograme (funcții), tablouri bidimensionale (matrice), șiruri de caractere, tipul struct… - [Bordarea matricei în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/matrice/bordarea-matricei/): A borda o matrice înseamnă a-i adăuga o linie și/sau o coloană nouă pe margine. Aici adăugăm coloana m + 1, cu suma fiecărei linii, și linia n + 1, cu suma… - [Cele patru zone ale matricei pătratice în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/matrice/cele-patru-zone-ale-matricei-patratice/): Cele două diagonale împart o matrice pătratică în patru zone (fără elementele de pe diagonale). Cu indici de la 1: Nord: i < j și i + j < n + 1 (deasupra… - [Citirea și afișarea unei matrice în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/matrice/citirea-si-afisarea-unei-matrice/): O matrice cu n linii și m coloane se declară ca int a[101][101] și se parcurge cu două for-uri imbricate: primul alege linia i, al doilea coloana j. Indexăm… - [Diagonala principală și diagonala secundară în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/matrice/diagonala-principala-si-diagonala-secundara/): Într-o matrice pătratică n x n, indexată de la 1, elementele de pe diagonala principală au i == j, iar cele de pe diagonala secundară au i + j == n + 1. Nu… - [Generarea matricei în serpentină în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/matrice/generarea-matricei-in-serpentina/): Completăm matricea cu numerele 1, 2, ..., n * m „în zigzag”: liniile impare de la stânga la dreapta, liniile pare de la dreapta la stânga. Un contor val… - [Generarea tablei de șah în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/matrice/generarea-tablei-de-sah/): Pe o tablă de șah, culoarea pătratului depinde doar de paritatea sumei i + j: pătratele cu i + j par au o culoare (1), cele cu i + j impar cealaltă culoare… - [Tablouri bidimensionale (matrice) în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/matrice/): 15 algoritmi C++ rezolvați la „Tablouri bidimensionale (matrice)” (clasa a 10-a): bordarea matricei, citirea și afișarea unei matrice, diagonala principală… - [Linia cu suma maximă în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/matrice/linia-cu-suma-maxima/): Calculăm suma fiecărei linii și o comparăm cu cea mai mare sumă găsită până acum. Pornim maximul de la suma primei linii (nu de la 0, pentru că sumele pot fi… - [Parcurgerea în spirală în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/matrice/parcurgerea-in-spirala/): Ținem patru margini: sus, jos, stanga, dreapta. La fiecare tură parcurgem linia de sus (spre dreapta), coloana din dreapta (în jos), linia de jos (spre… - [Produsul a două matrice în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/matrice/produsul-a-doua-matrice/): Produsul se poate face doar dacă numărul de coloane al lui A este egal cu numărul de linii al lui B. Pentru A (n x m) și B (m x p) rezultatul C are n x p… - [Punct șa în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/matrice/punct-sa/): Un punct șa este un element care este minim pe linia lui și maxim pe coloana lui. Pentru fiecare element a[i][j] verificăm cele două condiții cu două funcții… - [Rotirea unei matrice cu 90 de grade în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/matrice/rotirea-unei-matrice-cu-90-de-grade/): La rotirea în sensul acelor de ceasornic, prima coloană citită de jos în sus devine prima linie. Matricea rezultat b are m linii și n coloane, iar elementul… - [Ștergerea unei linii și a unei coloane în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/matrice/stergerea-unei-linii-si-a-unei-coloane/): Ca la vectori, ștergerea înseamnă mutarea elementelor peste cel șters. Pentru linia k, fiecare linie i de la k la n - 1 primește linia i + 1, apoi n scade cu… - [Suma pe linii și pe coloane în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/matrice/suma-pe-linii-si-pe-coloane/): Pentru suma liniei i ținem i fix și plimbăm j de la 1 la m. Pentru suma coloanei j facem invers: j fix în bucla din afară, i variabil în bucla din interior… - [Transpusa unei matrice în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/matrice/transpusa-unei-matrice/): Transpusa matricei a (n linii, m coloane) are m linii și n coloane: linia i a transpusei este coloana i a lui a, adică t[j][i] = a[i][j]. Nu e nevoie de o a… - [Verificarea matricei simetrice în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/matrice/verificarea-matricei-simetrice/): O matrice pătratică este simetrică față de diagonala principală dacă a[i][j] == a[j][i] pentru orice i și j (este egală cu transpusa ei). Ajunge să verificăm… - [Afișarea cifrelor în ordine, recursiv în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/recursivitate/afisarea-cifrelor-in-ordine-recursiv/): Contează unde punem afișarea față de autoapel. În inOrdine afișăm DUPĂ autoapel: întâi se termină apelul pentru n / 10 (care afișează cifrele din față), abia… - [Cmmdc recursiv în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/recursivitate/cmmdc-recursiv/): Algoritmul lui Euclid scris recursiv: cmmdc(a, 0) = a, iar cmmdc(a, b) = cmmdc(b, a % b). Autoapelul este ultima operație din funcție (recursivitate „de… - [Conversia în baza 2, recursiv în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/recursivitate/conversia-in-baza-2-recursiv/): La conversia prin împărțiri repetate la 2, resturile se obțin în ordine inversă față de cum trebuie scrise. Recursivitatea rezolvă asta singură: întâi ne… - [Factorial recursiv în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/recursivitate/factorial-recursiv/): Definiția matematică este deja recursivă: 0! = 1 și n! = n * (n - 1)!. Funcția are o condiție de oprire (n == 0) și un autoapel pe o problemă mai mică (n… - [Fibonacci recursiv în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/recursivitate/fibonacci-recursiv/): Șirul lui Fibonacci: F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2). Transcrierea directă are două autoapeluri, deci arborele apelurilor se dublează aproape… - [Funcția Ackermann în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/recursivitate/functia-ackermann/): Funcția Ackermann are două argumente: A(0, n) = n + 1; A(m, 0) = A(m - 1, 1); A(m, n) = A(m - 1, A(m, n - 1)). Valorile cresc extrem de repede (A(4, 2) are… - [Funcția Manna-Pnueli în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/recursivitate/functia-manna-pnueli/): Funcția este definită astfel: f(x) = x - 1 dacă x >= 12, altfel f(x) = f(f(x + 2)). Autoapelul interior f(x + 2) se calculează primul, iar rezultatul lui… - [Recursivitate în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/recursivitate/): 12 algoritmi C++ rezolvați la „Recursivitate” (clasa a 10-a): afișarea cifrelor în ordine, recursiv, cmmdc recursiv, conversia în baza 2, recursiv, factorial… - [Inversarea unui șir de caractere, recursiv în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/recursivitate/inversarea-unui-sir-de-caractere-recursiv/): Funcția inverseaza(s, i) se ocupă de caracterele de la poziția i până la final. Dacă s[i] nu este '\0', întâi se autoapelează pentru restul șirului (i + 1)… - [Numărul de apariții într-un vector, recursiv în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/recursivitate/numarul-de-aparitii-intr-un-vector-recursiv/): Numărul aparițiilor lui x printre primele n elemente este numărul aparițiilor printre primele n - 1 elemente, la care se adaugă 1 dacă ultimul element v[n… - [Palindrom recursiv în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/recursivitate/palindrom-recursiv/): Un cuvânt este palindrom dacă primul și ultimul caracter sunt egale și ce rămâne între ele este tot palindrom. Funcția palindrom(s, st, dr) lucrează pe… - [Puterea unui număr, recursiv în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/recursivitate/puterea-unui-numar-recursiv/): Varianta directă folosește a^n = a * a^(n - 1) și face n apeluri. Varianta rapidă înjumătățește exponentul: dacă n este par, a^n = (a^(n/2))^2, altfel a^n =… - [Suma cifrelor, recursiv în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/recursivitate/suma-cifrelor-recursiv/): Suma cifrelor lui n este ultima cifră (n % 10) plus suma cifrelor numărului rămas după tăierea ei (n / 10). Oprirea: un număr cu o singură cifră (n < 10) are… - [Cel mai lung cuvânt în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/cel-mai-lung-cuvant/): Împărțim fraza în cuvinte cu strtok și păstrăm cuvântul cu lungimea cea mai mare într-un șir separat, copiindu-l cu strcpy (nu putem scrie celMaiLung = p… - [Cifrul lui Cezar în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/cifrul-lui-cezar/): Fiecare literă se înlocuiește cu litera aflată la k poziții mai departe în alfabet, circular (după 'z' urmează 'a'). Transformăm litera în poziția ei 0..25… - [Cuvintele palindrom dintr-o frază în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/cuvintele-palindrom-dintr-o-fraza/): Combinăm două lucruri învățate: strtok împarte fraza în cuvinte, iar funcția estePalindrom(p) verifică un cuvânt cu doi indici care se apropie dinspre… - [Eliminarea vocalelor în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/eliminarea-vocalelor/): Ștergem vocalele chiar în șirul inițial, cu doi indici: i citește fiecare caracter, k arată unde scriem următorul caracter păstrat. Consoanele și celelalte… - [Extragerea numerelor dintr-un text în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/extragerea-numerelor-dintr-un-text/): Parcurgem textul; când întâlnim o cifră, construim numărul ca la clasa a IX-a (nr = nr * 10 + (s[i] - '0')) cât timp urmează cifre. Expresia s[i] - '0'… - [Frecvența literelor în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/frecventa-literelor/): Numărăm de câte ori apare fiecare literă, fără să facem diferența între literele mari și cele mici: tolower(c) - 'a' dă poziția literei în vectorul de… - [Împărțirea în cuvinte cu strtok în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/impartirea-in-cuvinte-cu-strtok/): strtok(s, separatori) întoarce primul cuvânt din s; apelurile următoare se fac cu NULL în loc de s și întorc pe rând celelalte cuvinte, până când rezultatul… - [Șiruri de caractere în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/): 16 algoritmi C++ rezolvați la „Șiruri de caractere” (clasa a 10-a): cel mai lung cuvânt, cifrul lui Cezar, cuvintele palindrom dintr-o frază, eliminarea… - [Înlocuirea unui cuvânt cu altul în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/inlocuirea-unui-cuvant-cu-altul/): Se citesc un text și două cuvinte, vechi și nou (fiecare pe câte un rând). Construim rezultatul într-un șir nou: copiem spațiile așa cum sunt, iar fiecare… - [Numărarea cuvintelor în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/numararea-cuvintelor/): Fără strtok: un cuvânt începe acolo unde un caracter diferit de spațiu urmează după un spațiu (sau se află chiar la începutul șirului). Numărăm aceste… - [Numărarea vocalelor în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/numararea-vocalelor/): Pentru fiecare caracter verificăm dacă apare în șirul "aeiouAEIOU" cu funcția strchr: strchr(vocale, c) întoarce adresa primei apariții a lui c în vocale sau… - [Operații cu std::string în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/operatii-cu-std-string/): Clasa string din își gestionează singură memoria: se atribuie cu =, se lipește cu +, se compară cu == și <. getline(cin, s) citește tot rândul… - [Parcurgerea unui șir și lungimea lui în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/parcurgerea-unui-sir-si-lungimea-lui/): Un șir de caractere în stil C este un vector de char terminat cu caracterul nul '\0'. cin.getline(s, 256) citește tot rândul, cu tot cu spații (cin >> s s-ar… - [Sortarea alfabetică a cuvintelor în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/sortarea-alfabetica-a-cuvintelor/): Separăm fraza în cuvinte cu strtok și le copiem într-o matrice de caractere cuv[100][31] (fiecare linie este un șir). Sortăm cu metoda bulelor; două cuvinte… - [Transformarea în majuscule și minuscule în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/transformarea-in-majuscule-si-minuscule/): În tabelul ASCII literele mari 'A'..'Z' și cele mici 'a'..'z' sunt la distanță constantă: 'a' - 'A' = 32. O literă mică devine mare scăzând 32 (s[i] = s[i]… - [Verificarea anagramelor în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/verificarea-anagramelor/): Două cuvinte sunt anagrame dacă au aceleași litere, de același număr de ori, în altă ordine (de exemplu „roma” și „amor”). Folosim un vector de frecvență cu… - [Verificarea unui șir palindrom în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/siruri-de-caractere/verificarea-unui-sir-palindrom/): Întâi păstrăm doar literele, transformate în minuscule (așa „Ele fac cafele” devine „elefaccafele”). Apoi folosim doi indici: st pornește de la început, dr… - [Adunarea duratelor (ore, minute, secunde) în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/struct/adunarea-duratelor-ore-minute-secunde/): O durată se ține într-o structură cu trei câmpuri. Ca să adunăm ușor, transformăm durata în secunde (h * 3600 + m * 60 + s), adunăm numerele și apoi refacem… - [Compararea datelor calendaristice în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/struct/compararea-datelor-calendaristice/): O dată calendaristică are trei câmpuri: zi, luna, an. Două date se compară întâi după an, la ani egali după lună, iar la luni egale după zi; funcția… - [Elevi sortați după medie și nume în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/struct/elevi-sortati-dupa-medie-si-nume/): Tipul struct grupează sub un singur nume date de tipuri diferite: struct Elev { char nume[31]; double medie; }. Un câmp se accesează cu punct (e.medie), iar… - [Tipul struct în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/struct/): 5 algoritmi C++ rezolvați la „Tipul struct” (clasa a 10-a): compararea datelor calendaristice, adunarea duratelor (ore, minute, secunde), elevi sortați după… - [Operații cu fracții în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/struct/operatii-cu-fractii/): O fracție are două câmpuri, numărătorul a și numitorul b, deci o reprezentăm cu struct Fractie { long long a, b; }. O funcție poate întoarce o structură… - [Puncte în plan în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/struct/puncte-in-plan/): Un punct are coordonatele x și y: struct Punct { int x, y; }. Distanța dintre două puncte este sqrt((x1 - x2)^2 + (y1 - y2)^2). Pentru comparații folosim… - [Funcție care întoarce oglinditul în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/subprograme/functie-care-intoarce-oglinditul/): Funcția oglindit(x) construiește numărul cu cifrele lui x în ordine inversă și îl întoarce cu return. Cu ajutorul ei, funcția palindrom(x) se scrie într-un… - [Funcție cmmdc și cmmmc în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/subprograme/functie-cmmdc-si-cmmmc/): Funcția cmmdc(a, b) aplică algoritmul lui Euclid prin împărțiri: cât timp b nu este 0, perechea (a, b) devine (b, a % b). Funcția cmmmc(a, b) o refolosește… - [Funcție cu vector ca parametru (maximul) în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/subprograme/functie-cu-vector-ca-parametru-maximul/): Un vector se transmite unei funcții împreună cu numărul de elemente: int maxim(int v[], int n). Funcția primește de fapt adresa primului element, deci… - [Funcție de primalitate în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/subprograme/functie-de-primalitate/): Scriem o singură dată funcția estePrim(x), care întoarce true dacă x este prim, și o apelăm pentru fiecare număr citit. Funcția caută un divizor d între 2 și… - [Funcție pentru suma cifrelor în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/subprograme/functie-pentru-suma-cifrelor/): Funcția sumaCifre(x) primește numărul prin valoare (lucrează pe o copie, deci x-ul din main nu se strică) și întoarce suma cifrelor. În main citim n numere… - [Subprograme (funcții) în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/subprograme/): 11 algoritmi C++ rezolvați la „Subprograme (funcții)” (clasa a 10-a): funcție cmmdc și cmmmc, funcție de primalitate, funcție cu vector ca parametru… - [Interschimbare prin referință în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/subprograme/interschimbare-prin-referinta/): Comparăm două funcții care încearcă să schimbe între ele valorile a două variabile. schimbaValoare(int x, int y) primește copii, deci modificările se pierd… - [Minim și maxim întoarse prin referință în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/subprograme/minim-si-maxim-intoarse-prin-referinta/): O funcție poate întoarce cu return o singură valoare. Când avem nevoie de mai multe rezultate, le punem ca parametri prin referință: void minMax(int v[], int… - [Numere prietene în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/subprograme/numere-prietene/): Două numere a și b sunt prietene dacă suma divizorilor proprii ai lui a (divizorii mai mici decât a) este b și suma divizorilor proprii ai lui b este a… - [Numere superprime în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/subprograme/numere-superprime/): Un număr este superprim dacă toate prefixele lui sunt numere prime. De exemplu 239 este superprim: 2, 23 și 239 sunt prime. Funcția estePrim(x) este… - [Palindroame dintr-un interval în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/subprograme/palindroame-dintr-un-interval/): Problemă rezolvată prin descompunere în funcții mici: oglindit(x) întoarce răsturnatul lui x, palindrom(x) îl folosește pe primul, iar main doar parcurge… - [Variabile globale și variabile locale în C++](https://bogdanandras.com/algoritmi/clasa-a-10-a/subprograme/variabile-globale-si-variabile-locale/): O variabilă globală (declarată în afara funcțiilor) se vede din tot programul, pornește automat cu 0 și își păstrează valoarea între apeluri. O variabilă… - [Arbore binar de căutare: inserare, căutare, afișare sortată în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/arbori/arbore-binar-de-cautare-inserare-cautare-afisare-sortata/): Într-un arbore binar de căutare, pentru fiecare nod, toate valorile din subarborele stâng sunt mai mici decât valoarea nodului, iar cele din subarborele… - [Arborele parțial de cost minim (algoritmul lui Kruskal) în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/arbori/arborele-partial-de-cost-minim-algoritmul-lui-kruskal/): Kruskal construiește arborele parțial de cost minim pornind de la n arbori cu câte un singur nod. Sortăm muchiile crescător după cost (la egalitate rămân în… - [Arborele parțial de cost minim (algoritmul lui Prim) în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/arbori/arborele-partial-de-cost-minim-algoritmul-lui-prim/): Într-un graf neorientat conex cu costuri pe muchii căutăm un arbore parțial (n - 1 muchii care leagă toate nodurile) cu suma costurilor minimă. Prim crește… - [Diametrul unui arbore în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/arbori/diametrul-unui-arbore/): Diametrul unui arbore este lungimea (numărul de muchii) celui mai lung lanț dintre două noduri. Metoda celor două parcurgeri: facem un BFS din nodul 1 și… - [Fiii, descendenții și ascendenții unui nod în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/arbori/fiii-descendentii-si-ascendentii-unui-nod/): Arborele este dat prin vectorul de tați (t[rădăcină] = 0). Fiii lui x sunt nodurile i cu t[i] = x. Un nod y este descendent al lui x dacă, urcând din y din… - [Arbori în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/arbori/): 8 algoritmi C++ rezolvați la „Arbori” (clasa a 11-a): arborele parțial de cost minim (algoritmul lui Kruskal), arborele parțial de cost minim (algoritmul lui… - [Parcurgerile unui arbore binar în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/arbori/parcurgerile-unui-arbore-binar/): Într-un arbore binar fiecare nod are cel mult doi fii: unul stâng și unul drept. Îl memorăm prin vectorii st[i] și dr[i] (0 dacă fiul lipsește). Rădăcina… - [Vectorul de tați: rădăcină, frunze, niveluri, înălțime în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/arbori/vectorul-de-tati-radacina-frunze-niveluri-inaltime/): Un arbore cu rădăcină se poate memora prin vectorul de tați: t[i] este tatăl nodului i, iar pentru rădăcină t[i] = 0. Rădăcina este nodul cu t = 0. Frunzele… - [Verificarea că un graf este arbore în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/arbori/verificarea-ca-un-graf-este-arbore/): Un arbore este un graf neorientat conex și fără cicluri. Pentru un graf cu n noduri următoarele afirmații sunt echivalente: este arbore; este conex și are n… - [Colorarea hărților în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/backtracking/colorarea-hartilor/): O hartă are n țări numerotate de la 1, iar m perechi (a, b) spun că țările a și b sunt vecine. Colorăm fiecare țară cu una dintre culorile 1..4 astfel încât… - [Drumuri într-un labirint în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/backtracking/drumuri-intr-un-labirint/): Labirintul este o matrice n × m cu 0 (liber) și 1 (zid). Pornim din colțul stânga-sus (1, 1) și vrem să ajungem în colțul dreapta-jos (n, m), mergând sus… - [Generarea aranjamentelor în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/backtracking/generarea-aranjamentelor/): Afișează, în ordine lexicografică, toate aranjamentele de n elemente luate câte k: șiruri de k valori distincte din {1, ..., n}, în care ordinea contează… - [Generarea combinărilor în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/backtracking/generarea-combinarilor/): Afișează toate submulțimile cu k elemente ale mulțimii {1, ..., n} (combinări de n luate câte k). Ca să nu obținem aceeași submulțime de mai multe ori… - [Generarea parantezărilor corecte în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/backtracking/generarea-parantezarilor-corecte/): Afișează, în ordine lexicografică ('(' înaintea lui ')'), toate șirurile corecte formate din n perechi de paranteze rotunde. Ținem numărul de paranteze… - [Generarea permutărilor în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/backtracking/generarea-permutarilor/): Afișează, în ordine lexicografică, toate permutările mulțimii {1, 2, ..., n}. Soluția se construiește în vectorul x, poziție cu poziție. Pe poziția k… - [Generarea submulțimilor în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/backtracking/generarea-submultimilor/): Afișează toate submulțimile nevide ale mulțimii {1, ..., n}, în ordine lexicografică. Elementele unei submulțimi se pun în ordine strict crescătoare (ca la… - [Metoda backtracking în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/backtracking/): 12 algoritmi C++ rezolvați la „Metoda backtracking” (clasa a 11-a): generarea aranjamentelor, colorarea hărților, generarea combinărilor, drumuri într-un… - [Partițiile unui număr natural în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/backtracking/partitiile-unui-numar-natural/): Afișează toate modurile de a scrie n ca sumă de numere naturale nenule, fără să conteze ordinea termenilor. Ca să nu repetăm aceeași descompunere, termenii… - [Permutări cu vecini de parități diferite în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/backtracking/permutari-cu-vecini-de-paritati-diferite/): Afișează permutările mulțimii {1, ..., n} în care oricare două elemente vecine au parități diferite (unul par, celălalt impar). Față de generarea… - [Plata unei sume cu monede date în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/backtracking/plata-unei-sume-cu-monede-date/): Avem n tipuri de monede, cu valorile v[1..n], din fiecare câte vrem. Afișăm toate modurile de a plăti exact suma S. x[k] este numărul de monede de tipul k și… - [Problema celor n dame în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/backtracking/problema-celor-n-dame/): Așezăm n dame pe o tablă n × n astfel încât să nu se atace (nicio pereche pe aceeași linie, coloană sau diagonală). Punem câte o damă pe fiecare linie, iar… - [Produsul cartezian în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/backtracking/produsul-cartezian/): Se dau n mulțimi; mulțimea i este {1, 2, ..., a[i]}. Se afișează toate elementele produsului cartezian, adică toate șirurile (x1, ..., xn) cu 1 ≤ xi ≤ a[i]… - [Componentele conexe în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-neorientate/componentele-conexe/): Un graf este conex dacă între oricare două noduri există un lanț. O componentă conexă este o „bucată” conexă maximală a grafului. Luăm nodurile în ordine… - [Detectarea unui ciclu în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-neorientate/detectarea-unui-ciclu/): Un ciclu este un lanț simplu în care primul nod coincide cu ultimul. Facem o parcurgere DFS și reținem pentru fiecare nod tatăl lui (nodul din care am… - [Grafuri neorientate în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-neorientate/): 10 algoritmi C++ rezolvați la „Grafuri neorientate” (clasa a 11-a): componentele conexe, detectarea unui ciclu, lanțul de lungime minimă între două noduri… - [Lanțul de lungime minimă între două noduri (BFS) în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-neorientate/lantul-de-lungime-minima-intre-doua-noduri-bfs/): Lungimea unui lanț este numărul de muchii. Parcurgerea în lățime pornită din x descoperă nodurile în ordinea distanței față de x, deci prima dată când ajunge… - [Listele de adiacență în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-neorientate/listele-de-adiacenta/): Pentru fiecare nod reținem doar lista vecinilor lui. Muchia [x, y] se adaugă de două ori: y în lista lui x și x în lista lui y. Memoria folosită este… - [Matricea de adiacență și gradele nodurilor în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-neorientate/matricea-de-adiacenta-si-gradele-nodurilor/): Un graf neorientat cu n noduri și m muchii se poate memora într-o matrice a cu n linii și n coloane: a[i][j] = 1 dacă există muchia [i, j], altfel 0… - [Noduri izolate și graful complet în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-neorientate/noduri-izolate-si-graful-complet/): Un nod izolat are gradul 0. Un graf este complet dacă oricare două noduri distincte sunt unite printr-o muchie; graful complet cu n noduri are n · (n - 1) /… - [Parcurgerea în adâncime (DFS) în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-neorientate/parcurgerea-in-adancime-dfs/): Parcurgerea în adâncime merge cât de departe se poate: din nodul curent trece în primul vecin nevizitat, de acolo în primul vecin nevizitat al acestuia și… - [Parcurgerea în lățime (BFS) în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-neorientate/parcurgerea-in-latime-bfs/): Parcurgerea în lățime vizitează nodurile „pe straturi”: întâi nodul de start, apoi toți vecinii lui, apoi vecinii vecinilor etc. Folosim o coadă: scoatem… - [Verificarea unui graf bipartit în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-neorientate/verificarea-unui-graf-bipartit/): Un graf este bipartit dacă nodurile lui se pot împărți în două mulțimi A și B astfel încât fiecare muchie să aibă un capăt în A și celălalt în B. Colorăm… - [Verificarea unui lanț în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-neorientate/verificarea-unui-lant/): O succesiune de noduri x1, x2, ..., xk este lanț dacă oricare două noduri consecutive sunt unite printr-o muchie; lungimea lanțului este k - 1 (numărul de… - [Componentele tare conexe în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-orientate/componentele-tare-conexe/): Un graf orientat este tare conex dacă pentru oricare două noduri x și y există drum de la x la y și drum de la y la x. O componentă tare conexă este un grup… - [Drumuri minime de la un nod (algoritmul lui Dijkstra) în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-orientate/drumuri-minime-de-la-un-nod-algoritmul-lui-dijkstra/): Se cere costul minim al drumului de la nodul s la fiecare alt nod, când toate costurile arcelor sunt nenegative. d[s] = 0, restul „infinit”. La fiecare pas… - [Drumuri minime între toate perechile de noduri (Roy-Floyd) în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-orientate/drumuri-minime-intre-toate-perechile-de-noduri-roy-floyd/): Fiecare arc (x, y) are un cost c ≥ 0. Matricea costurilor d pornește cu d[i][i] = 0, d[x][y] = costul arcului și „infinit” unde nu există arc. Pentru fiecare… - [Gradele interne și externe în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-orientate/gradele-interne-si-externe/): Într-un graf orientat muchiile au sens și se numesc arce: arcul (x, y) pleacă din x și intră în y. Gradul extern d+(x) este numărul de arce care pleacă din… - [Grafuri orientate și drumuri minime în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-orientate/): 6 algoritmi C++ rezolvați la „Grafuri orientate și drumuri minime” (clasa a 11-a): componentele tare conexe, drumuri minime de la un nod (algoritmul lui… - [Matricea drumurilor (algoritmul Roy-Warshall) în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-orientate/matricea-drumurilor-algoritmul-roy-warshall/): Matricea drumurilor are d[i][j] = 1 dacă există un drum (de lungime cel puțin 1) de la i la j și 0 altfel. Pornim de la matricea de adiacență. Pentru fiecare… - [Sortarea topologică în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/grafuri-orientate/sortarea-topologica/): Arcul (x, y) înseamnă „x trebuie făcut înaintea lui y”. O sortare topologică este o ordine a tuturor nodurilor în care fiecare arc merge de la stânga la… - [Acoperirea unui segment cu număr minim de intervale în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/greedy/acoperirea-unui-segment-cu-numar-minim-de-intervale/): Vrem să acoperim segmentul [A, B] folosind cât mai puține dintre cele n intervale date [s[i], f[i]]. Sortăm intervalele după capătul stâng. Ținem punctul… - [Metoda greedy în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/greedy/): 6 algoritmi C++ rezolvați la „Metoda greedy” (clasa a 11-a): acoperirea unui segment cu număr minim de intervale, planificarea spectacolelor, plata unei sume… - [Minimizarea timpului mediu de așteptare în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/greedy/minimizarea-timpului-mediu-de-asteptare/): La un ghișeu așteaptă n clienți; servirea clientului i durează t[i] minute. Timpul de așteptare al unui client este suma duratelor clienților serviți… - [Planificarea spectacolelor în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/greedy/planificarea-spectacolelor/): Într-o sală se pot ține n spectacole; spectacolul i începe la ora s[i] și se termină la ora f[i]. Vrem să programăm cât mai multe spectacole care nu se… - [Plata unei sume cu număr minim de bancnote în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/greedy/plata-unei-sume-cu-numar-minim-de-bancnote/): Se dau n valori de bancnote (din fiecare avem oricâte) și o sumă S. Strategia greedy: plătim cât mai mult cu bancnota cea mai mare, apoi continuăm cu restul… - [Problema rucsacului (varianta fracționară) în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/greedy/problema-rucsacului-varianta-fractionara/): Un rucsac suportă cel mult G kilograme. Avem n obiecte; obiectul i are greutatea g[i] și valoarea v[i], iar din orice obiect putem lua și o bucată (o… - [Suma maximă cu k elemente în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/greedy/suma-maxima-cu-k-elemente/): Dintr-un șir de n numere întregi alegem exact k elemente (pe poziții diferite) cu suma cât mai mare. Alegerea greedy este evidentă: luăm cele mai mari k… - [Algoritmi C++ clasa a 11-a](https://bogdanandras.com/algoritmi/clasa-a-11-a/): 62 de algoritmi C++ rezolvați pentru clasa a 11-a: metoda backtracking, metoda greedy, programare dinamică, alocare dinamică: liste, stive, cozi, grafuri… - [Coada implementată cu o listă înlănțuită în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/liste-stive-cozi/coada-implementata-cu-o-lista-inlantuita/): Coada se ține ca o listă simplu înlănțuită cu doi pointeri: prim (de unde se scoate) și ultim (unde se adaugă). push leagă un nod nou după ultim; pop mută… - [Coada implementată cu un vector în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/liste-stive-cozi/coada-implementata-cu-un-vector/): Coada este o structură de tip FIFO (primul intrat, primul ieșit): se adaugă la sfârșit și se scoate de la început, ca la un ghișeu. Cu un vector c și doi… - [Evaluarea unei expresii în formă poloneză postfixată în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/liste-stive-cozi/evaluarea-unei-expresii-in-forma-poloneza-postfixata/): În forma postfixată operatorul se scrie după operanzi: (3 + 4) * 2 devine 3 4 + 2 *, iar parantezele nu mai sunt necesare. Citim elementele pe rând: un număr… - [Alocare dinamică: liste, stive, cozi în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/liste-stive-cozi/): 10 algoritmi C++ rezolvați la „Alocare dinamică: liste, stive, cozi” (clasa a 11-a): coada implementată cu o listă înlănțuită, coada implementată cu un… - [Inserarea într-o listă ordonată în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/liste-stive-cozi/inserarea-intr-o-lista-ordonata/): Citim n numere și le inserăm pe rând într-o listă simplu înlănțuită păstrată mereu în ordine crescătoare. Dacă noua valoare este mai mică decât primul… - [Lista dublu înlănțuită în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/liste-stive-cozi/lista-dublu-inlantuita/): Într-o listă dublu înlănțuită fiecare nod reține atât adresa nodului următor (urm), cât și a celui anterior (ant), deci lista se poate parcurge în ambele… - [Lista simplu înlănțuită: creare, afișare, adăugare în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/liste-stive-cozi/lista-simplu-inlantuita-creare-afisare-adaugare/): Fiecare element al listei este un nod alocat dinamic (cu new), care reține o valoare (info) și adresa nodului următor (urm). Ținem adresa primului nod (prim)… - [Ștergerea nodurilor dintr-o listă simplu înlănțuită în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/liste-stive-cozi/stergerea-nodurilor-dintr-o-lista-simplu-inlantuita/): Se creează o listă din n valori, apoi se șterg toate nodurile care conțin valoarea x. Ștergerea primului nod mută pointerul prim pe nodul următor. Pentru un… - [Stiva implementată cu o listă înlănțuită în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/liste-stive-cozi/stiva-implementata-cu-o-lista-inlantuita/): Vârful stivei este primul nod al unei liste simplu înlănțuite. push creează un nod nou și îl leagă în fața vârfului; pop mută vârful pe nodul următor și… - [Stiva implementată cu un vector în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/liste-stive-cozi/stiva-implementata-cu-un-vector/): Stiva este o structură de tip LIFO (ultimul intrat, primul ieșit): se adaugă și se scoate doar în vârf. Cu un vector st și un indice vf (numărul de… - [Verificarea parantezelor cu o stivă în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/liste-stive-cozi/verificarea-parantezelor-cu-o-stiva/): Un șir format din paranteze ( ) [ ] { } este corect dacă fiecare paranteză deschisă se închide cu una de același tip, în ordinea potrivită. Parcurgem șirul… - [Cel mai lung subșir comun în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/programare-dinamica/cel-mai-lung-subsir-comun/): Se dau două cuvinte a și b. Căutăm cel mai lung șir de litere care apare ca subșir (litere în ordine, nu neapărat alăturate) în ambele. L[i][j] este lungimea… - [Distanța de editare în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/programare-dinamica/distanta-de-editare/): Câte operații sunt necesare, minim, ca să transformăm cuvântul a în cuvântul b? O operație înseamnă inserarea, ștergerea sau înlocuirea unei litere. d[i][j]… - [Drum de sumă maximă în matrice în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/programare-dinamica/drum-de-suma-maxima-in-matrice/): Într-o matrice n × m pornim din colțul (1, 1) și ajungem în (n, m) mergând doar la dreapta sau în jos. Vrem suma maximă a elementelor de pe drum. În celula… - [Programare dinamică în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/programare-dinamica/): 10 algoritmi C++ rezolvați la „Programare dinamică” (clasa a 11-a): cel mai lung subșir comun, distanța de editare, drum de sumă maximă în matrice, numărul… - [Numărul de drumuri într-o grilă cu obstacole în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/programare-dinamica/numarul-de-drumuri-intr-o-grila-cu-obstacole/): O grilă n × m are celule libere (0) și obstacole (1). Câte drumuri duc din (1, 1) în (n, m) dacă ne mișcăm doar la dreapta sau în jos și nu intrăm în… - [Numărul de moduri de a urca o scară în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/programare-dinamica/numarul-de-moduri-de-a-urca-o-scara/): O scară are n trepte; la fiecare pas urcăm fie o treaptă, fie două. În câte moduri putem ajunge sus? Pe treapta i ajungem fie de pe treapta i - 1, fie de pe… - [Numărul minim de monede în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/programare-dinamica/numarul-minim-de-monede/): Avem n tipuri de monede (din fiecare oricâte) și vrem să plătim exact suma S cu cât mai puține monede. Greedy-ul poate greși (pentru monedele 1, 3, 4 și S =… - [Numărul partițiilor unui număr în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/programare-dinamica/numarul-partitiilor-unui-numar/): În câte moduri se poate scrie n ca sumă de numere naturale nenule, fără să conteze ordinea termenilor? (4 = 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1, deci 5.)… - [Problema rucsacului (varianta discretă) în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/programare-dinamica/problema-rucsacului-varianta-discreta/): Un rucsac suportă cel mult G kilograme; avem n obiecte cu greutățile g[i] și valorile v[i], iar un obiect se ia întreg sau deloc. Aici greedy-ul după valoare… - [Subșirul strict crescător de lungime maximă în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/programare-dinamica/subsirul-strict-crescator-de-lungime-maxima/): Dintr-un șir de n numere alegem un subșir (elemente în ordinea din șir, nu neapărat alăturate) strict crescător și cât mai lung. L[i] este lungimea celui mai… - [Suma maximă în triunghiul de numere în C++](https://bogdanandras.com/algoritmi/clasa-a-11-a/programare-dinamica/suma-maxima-in-triunghiul-de-numere/): Un triunghi are n linii; linia i conține i numere. Pornim din vârf și la fiecare pas coborâm fie drept în jos (a[i+1][j]), fie în jos și la dreapta… - [Fill — cea mai mare zonă în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/algoritmul-lee-si-fill/fill-cea-mai-mare-zona/): Aceeași matrice de 0 și 1, dar acum vrem numărul de celule al celei mai mari zone de 1 (vecinătate prin laturi). Umplerea se face de data asta fără… - [Fill — numărul de zone în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/algoritmul-lee-si-fill/fill-numarul-de-zone/): Matricea are n linii și m coloane, cu 1 pentru teren și 0 pentru apă. O zonă este un grup maxim de celule 1 legate prin laturi (sus, jos, stânga, dreapta)… - [Algoritmi pe grile: Lee și fill în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/algoritmul-lee-si-fill/): 6 algoritmi C++ rezolvați la „Algoritmi pe grile: Lee și fill” (clasa a 12-a): fill — cea mai mare zonă, fill — numărul de zone, insule în 8 direcții, lee cu… - [Insule în 8 direcții în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/algoritmul-lee-si-fill/insule-in-8-directii/): Ca la numărarea zonelor, dar două celule de uscat (1) aparțin aceleiași insule dacă se ating și pe colț, adică vecinătatea are 8 direcții. Singura schimbare… - [Lee cu mai multe surse în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/algoritmul-lee-si-fill/lee-cu-mai-multe-surse/): Grila conține 0 (liber), 1 (zid) și 2 (sursă, de exemplu o fântână). Pentru fiecare celulă liberă vrem numărul minim de pași până la cea mai apropiată sursă… - [Lee cu reconstituirea drumului în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/algoritmul-lee-si-fill/lee-cu-reconstituirea-drumului/): După ce Lee a completat matricea de distanțe, drumul se reface de la final spre start: dacă suntem într-o celulă cu valoarea k, unul dintre vecini are sigur… - [Lee — drumul minim într-o grilă în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/algoritmul-lee-si-fill/lee-drumul-minim-intr-o-grila/): Grila are n linii și m coloane: 0 = liber, 1 = obstacol. Ne putem deplasa sus, jos, stânga, dreapta. Algoritmul lui Lee este o parcurgere în lățime… - [Algoritmi C++ clasa a 12-a](https://bogdanandras.com/algoritmi/clasa-a-12-a/): 50 de algoritmi C++ rezolvați pentru clasa a 12-a: numere mari, algoritmi pe grile: Lee și fill, matematică pentru programare, tehnici avansate: doi… - [Algoritmul lui Euclid extins în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/matematica/algoritmul-lui-euclid-extins/): Pe lângă d = cmmdc(a, b), găsim numere întregi x și y cu a * x + b * y = d. Dacă b = 0, atunci d = a, x = 1, y = 0. Altfel rezolvăm recursiv pentru (b, a %… - [Ciur cu cel mai mic divizor prim și factorizare rapidă în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/matematica/ciur-cu-cel-mai-mic-divizor-prim-si-factorizare-rapida/): O variantă a ciurului lui Eratostene: în loc să marcăm doar „compus”, reținem în dp[x] cel mai mic divizor prim al lui x. Pentru fiecare prim p (dp[p] rămas… - [Combinări modulo un număr prim în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/matematica/combinari-modulo-un-numar-prim/): Calculăm C(n, k) mod P, cu P = 1 000 000 007 (prim) și n ≤ 10^6. Avem C(n, k) = n! / (k! * (n-k)!), dar împărțirea nu se poate face direct pe resturi… - [Exponențierea modulară în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/matematica/exponentierea-modulara/): Calculăm a^n mod m pentru n de până la 10^18. Folosim aceeași idee ca la exponențierea rapidă, dar după fiecare înmulțire luăm restul la m: (x * y) mod m =… - [Exponențierea rapidă în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/matematica/exponentierea-rapida/): Calculăm a^n cu aproximativ log2(n) înmulțiri în loc de n. Ideea: a^n = (a^2)^(n/2) dacă n este par și a^n = a * a^(n-1) dacă n este impar. Varianta… - [Matematică pentru programare în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/matematica/): 9 algoritmi C++ rezolvați la „Matematică pentru programare” (clasa a 12-a): ciur cu cel mai mic divizor prim și factorizare rapidă, combinări modulo un număr… - [Numărul multiplilor lui k dintr-un interval în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/matematica/numarul-multiplilor-lui-k-dintr-un-interval/): Câte numere din [a, b] se divid cu k? Numerele din [1, x] divizibile cu k sunt k, 2k, ..., (x / k) * k, adică x / k bucăți (împărțire întreagă). Scădem… - [Numărul și suma divizorilor din descompunerea în factori primi în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/matematica/numarul-si-suma-divizorilor-din-descompunerea-in-factori/): Dacă n = p1^e1 * p2^e2 * ... * pk^ek, un divizor alege pentru fiecare prim un exponent între 0 și ei, deci numărul divizorilor este (e1 + 1) * (e2 + 1) *… - [Suma unei progresii aritmetice: formulă vs. buclă în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/matematica/suma-unei-progresii-aritmetice-formula-vs-bucla/): Progresia are primul termen a, rația r și n termeni: a, a + r, ..., a + (n-1) * r. Bucla adună termenii unul câte unul, deci face n pași. Formula lui Gauss… - [Triunghiul lui Pascal (combinări) în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/matematica/triunghiul-lui-pascal-combinari/): Combinările C(i, j) — numărul de submulțimi cu j elemente ale unei mulțimi cu i elemente — respectă relația C(i, j) = C(i-1, j-1) + C(i-1, j): fie alegem… - [Adunarea a două numere mari în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/numere-mari/adunarea-a-doua-numere-mari/): Adunăm ca pe hârtie, de la unități spre stânga. La rangul i calculăm s = a[i] + b[i] + transport; cifra rezultatului este s % 10, iar noul transport este s /… - [Citirea și afișarea unui număr mare în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/numere-mari/citirea-si-afisarea-unui-numar-mare/): Un număr cu zeci sau sute de cifre nu încape în long long, așa că îl citim ca șir de caractere și îi păstrăm cifrele într-un vector, începând cu cifra… - [Compararea a două numere mari în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/numere-mari/compararea-a-doua-numere-mari/): Fără zerouri nesemnificative, numărul cu mai multe cifre este mai mare. Dacă au același număr de cifre, le comparăm de la cifra cea mai semnificativă… - [Factorialul unui număr mare în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/numere-mari/factorialul-unui-numar-mare/): Deja 21! depășește long long, dar n! = 1 * 2 * ... * n se poate construi înmulțind repetat un număr mare cu un număr mic. Pornim de la vectorul cu o singură… - [Împărțirea unui număr mare la un număr mic în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/numere-mari/impartirea-unui-numar-mare-la-un-numar-mic/): Spre deosebire de adunare, împărțirea începe de la cifra cea mai semnificativă, exact ca la împărțirea „în colțuri” de pe hârtie. Ținem restul r; la fiecare… - [Numere mari în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/numere-mari/): 9 algoritmi C++ rezolvați la „Numere mari” (clasa a 12-a): adunarea a două numere mari, citirea și afișarea unui număr mare, compararea a două numere mari… - [Înmulțirea a două numere mari în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/numere-mari/inmultirea-a-doua-numere-mari/): Cifra a[i] (rangul 10^i) înmulțită cu cifra b[j] (rangul 10^j) contribuie la rangul 10^(i+j). Adunăm întâi toate produsele în c[i + j], fără să ne ocupăm de… - [Înmulțirea unui număr mare cu un număr mic în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/numere-mari/inmultirea-unui-numar-mare-cu-un-numar-mic/): Numărul mic k (cel mult 10^9) încape într-un int, deci nu trebuie despărțit în cifre. Pentru fiecare cifră a[i], de la unități, calculăm t = a[i] * k +… - [Scăderea a două numere mari în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/numere-mari/scaderea-a-doua-numere-mari/): Calculăm A - B. Dacă A < B, calculăm B - A și punem semnul minus în față. Scădem de la unități: d = a[i] - b[i] - împrumut; dacă d iese negativ, adăugăm 10… - [Termenul n din șirul lui Fibonacci (număr mare) în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/numere-mari/termenul-n-din-sirul-lui-fibonacci-numar-mare/): Șirul este F(1) = F(2) = 1 și F(i) = F(i - 1) + F(i - 2). Termenii cresc exponențial (F(93) nu mai încape în long long), deci îi ținem ca numere mari… - [Fișier — cea mai lungă secvență de termeni cu aceeași paritate în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/recapitulare-bacalaureat/fisier-cea-mai-lunga-secventa-de-termeni-cu-aceeasi-paritate/): Cerința (tip subiectul III.3): fișierul date.in conține un șir de cel mult 10^6 numere naturale de cel mult 9 cifre. O secvență paritară este o secvență de… - [Fișier — cel mai mare și cel mai mic număr format din cifre date în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/recapitulare-bacalaureat/fisier-cel-mai-mare-si-cel-mai-mic-numar-format-din-cifre/): Cerința (tip subiectul III.3): fișierul date.in conține cel mult 10^6 cifre separate prin spații. Folosind toate cifrele, fiecare o singură dată, afișați pe… - [Fișier — perechi de numere cu aceeași sumă a cifrelor în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/recapitulare-bacalaureat/fisier-perechi-de-numere-cu-aceeasi-suma-a-cifrelor/): Cerința (tip subiectul III.3): fișierul date.in conține pe prima linie n (2 ≤ n ≤ 10^6), apoi n numere naturale de cel mult 9 cifre. Afișați câte perechi de… - [Fișier — valorile care apar o singură dată în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/recapitulare-bacalaureat/fisier-valorile-care-apar-o-singura-data/): Cerința (tip subiectul III.3): fișierul date.in conține cel mult 10^6 numere naturale de cel mult trei cifre, separate prin spații. Afișați pe ecran, în… - [Fișier — valorile comune a două șiruri ordonate în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/recapitulare-bacalaureat/fisier-valorile-comune-a-doua-siruri-ordonate/): Cerința (tip subiectul III.3): fișierul date.in conține pe prima linie n și m (1 ≤ n, m ≤ 10^5), pe a doua linie n numere naturale ordonate crescător, iar pe… - [Recapitulare pentru bacalaureat în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/recapitulare-bacalaureat/): 10 algoritmi C++ rezolvați la „Recapitulare pentru bacalaureat” (clasa a 12-a): fișier — cel mai mare și cel mai mic număr format din cifre date, fișier… - [Matrice — contururi concentrice în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/recapitulare-bacalaureat/matrice-contururi-concentrice/): Cerința (tip subiectul III.2): se citește n (2 ≤ n ≤ 20). Construiți în memorie o matrice cu n linii și n coloane în care elementele de pe conturul exterior… - [Subprogram — câte numere dintr-un interval au un număr impar de divizori în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/recapitulare-bacalaureat/subprogram-cate-numere-dintr-un-interval-au-un-numar-impar/): Cerința (tip subiectul III.1): subprogramul impare are parametrii a și b (1 ≤ a ≤ b ≤ 10^12) și întoarce câte numere din [a, b] au un număr impar de… - [Subprogram — eliminarea elementelor cu k cifre dintr-un tablou în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/recapitulare-bacalaureat/subprogram-eliminarea-elementelor-cu-k-cifre-dintr-un-tablou/): Cerința (tip subiectul III.1): subprogramul elimina are parametrii v (un tablou cu n numere naturale), n și k; șterge din v toate elementele care au exact k… - [Subprogram — numărul format din cifrele pare în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/recapitulare-bacalaureat/subprogram-numarul-format-din-cifrele-pare/): Cerința (tip subiectul III.1): subprogramul pare are un parametru n (0 ≤ n ≤ 10^9) și întoarce numărul format din cifrele pare ale lui n, în ordinea în care… - [Text — inversarea cuvintelor de lungime pară în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/recapitulare-bacalaureat/text-inversarea-cuvintelor-de-lungime-para/): Cerința (tip subiectul III.2): se citește un text de cel mult 100 de caractere, format din cuvinte de litere mici separate prin câte un spațiu. Afișați… - [Containerul vector din STL în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/structuri-de-date-stl/containerul-vector-din-stl/): vector este un tablou care își gestionează singur memoria: push_back adaugă la final (în medie O(1)), size() dă numărul de elemente, iar v[i] accesează… - [deque — minimul pe ferestre de lungime k în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/structuri-de-date-stl/deque-minimul-pe-ferestre-de-lungime-k/): Pentru fiecare secvență de k elemente consecutive vrem minimul. Ținem într-un deque pozițiile „candidate”, cu valori crescătoare de la față spre spate. Când… - [Structuri de date și STL în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/structuri-de-date-stl/): 9 algoritmi C++ rezolvați la „Structuri de date și STL” (clasa a 12-a): deque — minimul pe ferestre de lungime k, queue — eliminarea din cerc, pair… - [Păduri de mulțimi disjuncte (union-find) în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/structuri-de-date-stl/paduri-de-multimi-disjuncte-union-find/): Avem n elemente, fiecare inițial în propria mulțime. Operația 1 x y unește mulțimile lui x și y, iar operația 2 x y întreabă dacă x și y sunt în aceeași… - [pair — reuniunea intervalelor în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/structuri-de-date-stl/pair-reuniunea-intervalelor/): pair grupează două valori (first, second) și se compară lexicografic: întâi după first, apoi după second. Așadar sort pe un vector de perechi… - [priority_queue — cele mai mari k valori în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/structuri-de-date-stl/priority-queue-cele-mai-mari-k-valori/): priority_queue este un heap: top() dă elementul „cel mai important”, iar push și pop costă O(log dimensiune). Implicit vârful este maximul; cu greater păstrează fiecare cuvânt o singură dată, în ordine alfabetică, deci size() dă numărul… - [Sortare cu comparator în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/structuri-de-date-stl/sortare-cu-comparator/): sort(început, sfârșit, cmp) ordonează după regula noastră: cmp(x, y) întoarce true dacă x trebuie pus înaintea lui y. Aici sortăm participanții unui concurs… - [stack — verificarea parantezelor în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/structuri-de-date-stl/stack-verificarea-parantezelor/): Un șir cu paranteze (), [] și {} este corect dacă fiecare paranteză închisă se potrivește cu ultima paranteză deschisă rămasă neînchisă. „Ultima deschisă… - [Căutare binară pe răspuns în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/tehnici-avansate/cautare-binara-pe-raspuns/): Avem n capitole cu a[i] pagini, în ordine, și k corectori. Fiecare corector primește o secvență de capitole consecutive. Vrem ca cel mai încărcat corector să… - [Doi pointeri — perechi cu suma x într-un vector sortat în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/tehnici-avansate/doi-pointeri-perechi-cu-suma-x-intr-un-vector-sortat/): Vectorul are n valori distincte, în ordine strict crescătoare. Vrem perechile de poziții i < j cu a[i] + a[j] = x. În loc să încercăm toate cele n * (n-1) /… - [Element majoritar (Boyer-Moore) în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/tehnici-avansate/element-majoritar-boyer-moore/): Elementul majoritar apare de mai mult de n / 2 ori. Algoritmul de vot ține un candidat și un contor: o valoare egală cu candidatul crește contorul, una… - [Fereastra glisantă — cea mai lungă secvență cu suma ≤ S în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/tehnici-avansate/fereastra-glisanta-cea-mai-lunga-secventa-cu-suma-s/): Toate numerele sunt strict pozitive. Ținem o fereastră [st, dr] și suma ei. Extindem mereu capătul drept cu un element; cât timp suma depășește S, scoatem… - [Generarea submulțimilor cu măști de biți în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/tehnici-avansate/generarea-submultimilor-cu-masti-de-biti/): O submulțime a lui {a[0], ..., a[n-1]} se poate codifica printr-un număr masca între 0 și 2^n - 1: bitul i al măștii este 1 dacă a[i] face parte din… - [Tehnici avansate: doi pointeri, căutare binară pe răspuns, stive monotone în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/tehnici-avansate/): 7 algoritmi C++ rezolvați la „Tehnici avansate: doi pointeri, căutare binară pe răspuns, stive monotone” (clasa a 12-a): căutare binară pe răspuns, doi… - [Stiva monotonă — următorul element mai mare în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/tehnici-avansate/stiva-monotona-urmatorul-element-mai-mare/): Pentru fiecare a[i] căutăm prima valoare strict mai mare aflată în dreapta lui (sau -1). Ținem o stivă cu pozițiile care încă „așteaptă” un element mai mare… - [Sume parțiale pe matrice în C++](https://bogdanandras.com/algoritmi/clasa-a-12-a/tehnici-avansate/sume-partiale-pe-matrice/): s[i][j] = suma elementelor din dreptunghiul cu colțurile (1, 1) și (i, j). Se calculează o singură dată: s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1]… - [Conversia din baza 10 în baza b în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/baze-de-numeratie/conversia-din-baza-10-in-baza-b/): Împărțim repetat n la b; resturile sunt cifrele în baza b, dar obținute de la ultima spre prima. De aceea fiecare cifră nouă se lipește în fața rezultatului… - [Conversia din baza b în baza 10 în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/baze-de-numeratie/conversia-din-baza-b-in-baza-10/): Numărul în baza b se citește ca text (poate conține A..F), apoi se aplică schema lui Horner: parcurgem cifrele de la stânga la dreapta și facem rez = rez * b… - [Conversia în baza 10 cu puterile bazei în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/baze-de-numeratie/conversia-in-baza-10-cu-puterile-bazei/): Varianta pentru b <= 10, când numărul se poate citi ca întreg: cifrele lui se extrag de la dreapta cu n % 10, iar fiecare cifră se înmulțește cu puterea… - [Conversia între două baze oarecare în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/baze-de-numeratie/conversia-intre-doua-baze-oarecare/): Trecem prin baza 10: întâi transformăm numărul din baza b1 în baza 10 (schema lui Horner), apoi din baza 10 în baza b2 (împărțiri repetate). Se citesc… - [Baze de numerație în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/baze-de-numeratie/): 6 algoritmi C++ rezolvați la „Baze de numerație” (clasa a 9-a): conversia din baza 10 în baza b, conversia în baza 10 cu puterile bazei, conversia din baza b… - [Numărul de biți 1 din scrierea în baza 2 în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/baze-de-numeratie/numarul-de-biti-1-din-scrierea-in-baza-2/): Cifrele în baza 2 se obțin la fel ca cifrele în baza 10, doar că împărțim la 2: ultima cifră binară este n % 2. Numărăm câte dintre ele sunt 1. 13 = 1101 în… - [Verificarea unei puteri a lui 2 în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/baze-de-numeratie/verificarea-unei-puteri-a-lui-2/): O putere a lui 2 are în baza 2 un singur bit de 1 (de exemplu 64 = 1000000). Scăzând 1, acel bit devine 0 și toți biții din dreapta lui devin 1 (63 =… - [Afișarea cifrelor în ordinea din număr în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/cifrele-unui-numar/afisarea-cifrelor-in-ordinea-din-numar/): Cu n % 10 cifrele ies de la dreapta la stânga. Ca să le afișăm de la stânga la dreapta, calculăm întâi p = cea mai mare putere a lui 10 cel mult egală cu n… - [Cel mai mare număr format cu cifrele lui n în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/cifrele-unui-numar/cel-mai-mare-numar-format-cu-cifrele-lui-n/): Numărăm de câte ori apare fiecare cifră, într-un vector de frecvență cu 10 poziții (frecv[c] = de câte ori apare cifra c). Cel mai mare număr se obține… - [Cifra de control în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/cifrele-unui-numar/cifra-de-control/): Cifra de control se obține înlocuind numărul cu suma cifrelor lui, în mod repetat, până când rămâne o singură cifră (de exemplu 99999 -> 45 -> 9). Același… - [Cifra maximă și cifra minimă în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/cifrele-unui-numar/cifra-maxima-si-cifra-minima/): Pornim cu maximul 0 (cea mai mică cifră posibilă) și minimul 9 (cea mai mare cifră posibilă), apoi comparăm fiecare cifră cu ele. Folosim do-while pentru ca… - [Dublarea cifrelor impare în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/cifrele-unui-numar/dublarea-cifrelor-impare/): Fiecare cifră impară a lui n apare de două ori în rezultat. Construim rezultatul de la dreapta la stânga cu rez = rez + cifra * p; o cifră impară se adaugă… - [Eliminarea cifrelor pare în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/cifrele-unui-numar/eliminarea-cifrelor-pare/): Construim un număr nou din cifrele impare ale lui n, păstrând ordinea lor. Cifrele vin de la dreapta la stânga, așa că fiecare cifră păstrată se pune în fața… - [Cifrele unui număr în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/cifrele-unui-numar/): 15 algoritmi C++ rezolvați la „Cifrele unui număr” (clasa a 9-a): numărul de apariții ale cifrei k, cel mai mare număr format cu cifrele lui n, cifra de… - [Înlocuirea unei cifre cu alta în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/cifrele-unui-numar/inlocuirea-unei-cifre-cu-alta/): Înlocuiește în n fiecare apariție a cifrei x cu cifra y. Reconstruim numărul de la dreapta la stânga cu rez = rez + cifra * p, punând y în locul fiecărei… - [Număr palindrom în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/cifrele-unui-numar/numar-palindrom/): Un număr este palindrom dacă se citește la fel de la stânga la dreapta și de la dreapta la stânga, adică este egal cu oglinditul său. Lucrăm pe o copie… - [Numărul de apariții ale cifrei k în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/cifrele-unui-numar/numarul-de-aparitii-ale-cifrei-k/): Parcurgem cifrele lui n și numărăm câte sunt egale cu k. Cu do-while, pentru n = 0 și k = 0 răspunsul este corect 1. Cod C++ complet, cu exemple, rulabil… - [Numărul de cifre ale unui număr în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/cifrele-unui-numar/numarul-de-cifre-ale-unui-numar/): Numără cifrele lui n tăind la fiecare pas ultima cifră (n / 10) până când numărul devine 0. Folosim do-while ca numărul 0 să fie numărat corect: el are o… - [Oglinditul unui număr în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/cifrele-unui-numar/oglinditul-unui-numar/): Construiește numărul format din cifrele lui n scrise în ordine inversă. La fiecare pas luăm ultima cifră (n % 10), o lipim la dreapta oglinditului (ogl * 10… - [Prima cifră a unui număr în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/cifrele-unui-numar/prima-cifra-a-unui-numar/): Prima cifră (cea din stânga) rămâne după ce tăiem toate celelalte cifre: împărțim la 10 cât timp numărul are cel puțin două cifre (n >= 10). Cod C++ complet… - [Produsul cifrelor unui număr în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/cifrele-unui-numar/produsul-cifrelor-unui-numar/): Înmulțește cifrele lui n. Produsul pornește de la 1 (elementul neutru al înmulțirii), nu de la 0. Cu do-while, pentru n = 0 se obține corect produsul 0… - [Suma cifrelor unui număr în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/cifrele-unui-numar/suma-cifrelor-unui-numar/): Adună cifrele lui n. Ultima cifră se obține cu n % 10, apoi este eliminată cu n / 10. Repetăm până când n devine 0. Cod C++ complet, cu exemple, rulabil… - [Verificarea cifrelor distincte în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/cifrele-unui-numar/verificarea-cifrelor-distincte/): Verifică dacă toate cifrele lui n sunt diferite. Ținem minte ce cifre am văzut deja (vazut[c] devine true la prima apariție a lui c); dacă dăm peste o cifră… - [Cel mai mic multiplu comun în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/cel-mai-mic-multiplu-comun/): Se folosește relația cmmdc(a, b) * cmmmc(a, b) = a * b. Calculăm cmmdc-ul cu algoritmul lui Euclid, pe copii ale lui a și b, apoi cmmmc = a / cmmdc * b… - [Cmmdc prin împărțiri repetate (algoritmul lui Euclid) în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/cmmdc-prin-impartiri-repetate-algoritmul-lui-euclid/): Cel mai mare divizor comun nu se schimbă dacă înlocuim perechea (a, b) cu (b, a % b). Repetăm până când b devine 0; atunci cmmdc-ul este a. Funcționează și… - [Cmmdc prin scăderi repetate în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/cmmdc-prin-scaderi-repetate/): Scădem numărul mai mic din cel mai mare până când devin egale; valoarea comună este cmmdc-ul. Merge doar pentru a, b > 0 (cu un 0 bucla nu s-ar opri). Este… - [Descompunerea în factori primi în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/descompunerea-in-factori-primi/): Încercăm factorii d = 2, 3, 4, ... și împărțim n la d de câte ori se poate, numărând de câte ori (exponentul). Un d compus nu mai divide n, pentru că… - [Divizorii primi ai unui număr în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/divizorii-primi-ai-unui-numar/): Este descompunerea în factori primi, din care afișăm doar factorii, fără exponenți. Fiecare factor găsit este eliminat complet din n. Cod C++ complet, cu… - [Divizorii proprii ai unui număr în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/divizorii-proprii-ai-unui-numar/): Divizorii proprii sunt divizorii diferiți de 1 și de n. Folosim aceleași două treceri ca la afișarea tuturor divizorilor, dar pornim de la d = 2, deci… - [Divizorii unui număr în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/divizorii-unui-numar/): Divizorii vin în perechi: dacă d divide n, atunci și n / d divide n, iar unul dintre ei este cel mult rădăcina pătrată a lui n. Ajunge deci să încercăm d de… - [Divizibilitate și numere prime în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/): 17 algoritmi C++ rezolvați la „Divizibilitate și numere prime” (clasa a 9-a): cmmdc prin împărțiri repetate (algoritmul lui Euclid), cmmdc prin scăderi… - [Indicatorul lui Euler în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/indicatorul-lui-euler/): φ(n) este numărul valorilor din 1..n prime cu n. Dacă p1, p2, ... sunt divizorii primi ai lui n, atunci φ(n) = n · (1 - 1/p1) · (1 - 1/p2) · ... Pentru… - [Număr perfect în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/numar-perfect/): Un număr este perfect dacă este egal cu suma divizorilor săi mai mici decât el (6 = 1 + 2 + 3). Calculăm suma tuturor divizorilor în O(√n) și scădem n. Cod… - [Numărul divizorilor în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/numarul-divizorilor/): Pentru fiecare d cu d * d <= n care divide n numărăm doi divizori, d și n / d, cu excepția cazului d * d == n, când cei doi coincid. Cod C++ complet, cu… - [Numere prime între ele în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/numere-prime-intre-ele/): Două numere sunt prime între ele dacă singurul lor divizor comun este 1, adică cmmdc(a, b) = 1. Numerele nu trebuie să fie prime: 15 și 28 sunt prime între… - [Perechi de numere prime gemene în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/perechi-de-numere-prime-gemene/): Două numere prime sunt gemene dacă diferența lor este 2 (de exemplu 11 și 13). Afișăm toate perechile (p, p + 2) cu p + 2 <= n, testând primalitatea ambelor… - [Primele n numere prime în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/primele-n-numere-prime/): Luăm pe rând candidații 2, 3, 4, ... și îi testăm cu testul de primalitate până la √x. Ne oprim după ce am afișat n numere prime. Cod C++ complet, cu… - [Simplificarea unei fracții în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/simplificarea-unei-fractii/): O fracție a / b devine ireductibilă dacă împărțim numărătorul și numitorul la cmmdc(a, b). Calculăm cmmdc-ul pe copii, ca să păstrăm valorile inițiale. Cod… - [Suma divizorilor în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/suma-divizorilor/): Adunăm divizorii în perechi (d și n / d) pentru d * d <= n; când n este pătrat perfect, rădăcina se adună o singură dată. Cod C++ complet, cu exemple… - [Test de primalitate în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/test-de-primalitate/): Un număr este prim dacă are exact doi divizori: 1 și el însuși (deci 0 și 1 nu sunt prime). Dacă n are un divizor d între 2 și n - 1, are și unul cel mult… - [Ultima cifră a lui x la puterea y în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/divizibilitate-numere-prime/ultima-cifra-a-lui-x-la-puterea-y/): Ultima cifră a unui produs depinde doar de ultimele cifre ale factorilor. Ultimele cifre ale puterilor se repetă cu perioada 4 (de exemplu pentru 3: 3, 9, 7… - [Citirea până la sfârșitul fișierului în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/fisiere-text/citirea-pana-la-sfarsitul-fisierului/): Fișierul date.in conține numere întregi, dar nu știm câte. Expresia fin >> x întoarce „adevărat” cât timp citirea reușește și „fals” la sfârșitul fișierului… - [Fișiere text în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/fisiere-text/): 5 algoritmi C++ rezolvați la „Fișiere text” (clasa a 9-a): citirea până la sfârșitul fișierului, numărarea valorilor dintr-un fișier, prelucrarea unui fișier… - [Numărarea valorilor dintr-un fișier în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/fisiere-text/numararea-valorilor-dintr-un-fisier/): Fișierul date.in conține pe prima linie un număr natural k, iar pe următoarele linii un șir de numere naturale de lungime necunoscută. Citim până la… - [Prelucrarea unui fișier pe linii în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/fisiere-text/prelucrarea-unui-fisier-pe-linii/): getline(fin, linie) citește un rând întreg, cu tot cu spații, până la '\n'. Bucla while (getline(fin, linie)) se oprește la sfârșitul fișierului. Numărăm… - [Scrierea formatată într-un fișier în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/fisiere-text/scrierea-formatata-intr-un-fisier/): Se citește n din date.in și se scriu în date.out numerele de la 1 la n, câte cinci pe un rând. ofstream se folosește exact ca cout; un rând nou se scrie cu… - [Suma numerelor de pe fiecare linie în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/fisiere-text/suma-numerelor-de-pe-fiecare-linie/): Fiecare linie din date.in conține câteva numere întregi, în număr necunoscut. Citim linia cu getline, apoi o „recitim” ca pe un flux de numere cu… - [Cifrele comune a două numere în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/frecventa-sume-partiale-ciur/cifrele-comune-a-doua-numere/): Marcăm în doi vectori de 10 poziții ce cifre apar în fiecare număr (aparA[c], aparB[c]). Cifrele comune sunt cele marcate în ambii vectori; le afișăm… - [Ciurul lui Eratostene în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/frecventa-sume-partiale-ciur/ciurul-lui-eratostene/): Găsește toate numerele prime până la n. Pornim cu toate numerele nemarcate; pentru fiecare i nemarcat (deci prim) marcăm ca neprimi multiplii lui, începând… - [Elementul majoritar în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/frecventa-sume-partiale-ciur/elementul-majoritar/): Elementul majoritar apare de mai mult de n / 2 ori. Algoritmul prin vot (Boyer-Moore) păstrează un candidat și un contor: un element egal cu candidatul… - [Frecvență, sume parțiale și ciurul lui Eratostene în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/frecventa-sume-partiale-ciur/): 10 algoritmi C++ rezolvați la „Frecvență, sume parțiale și ciurul lui Eratostene” (clasa a 9-a): cifrele comune a două numere, ciurul lui Eratostene… - [Marcarea intervalelor cu vectorul de diferențe în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/frecventa-sume-partiale-ciur/marcarea-intervalelor-cu-vectorul-de-diferente/): Avem n poziții, inițial 0, și m operații „adună 1 pe pozițiile a..b”. În loc să parcurgem fiecare interval, notăm doar capetele: d[a]++ (de aici începe) și… - [Numărul lipsă dintr-o permutare în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/frecventa-sume-partiale-ciur/numarul-lipsa-dintr-o-permutare/): Se dau n și n - 1 numere distincte din mulțimea {1, 2, ..., n}; unul singur lipsește. Suma tuturor numerelor de la 1 la n este n · (n + 1) / 2 (formula lui… - [Secvența de lungime k cu suma maximă în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/frecventa-sume-partiale-ciur/secventa-de-lungime-k-cu-suma-maxima/): Fereastra glisantă: calculăm suma primelor k elemente, apoi mutăm fereastra cu câte o poziție la dreapta: adăugăm elementul care intră (v[i]) și scădem… - [Secvența de sumă maximă (algoritmul lui Kadane) în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/frecventa-sume-partiale-ciur/secventa-de-suma-maxima-algoritmul-lui-kadane/): Parcurgem vectorul și păstrăm suma secvenței curente, care se termină la poziția i. Dacă suma de până acum a devenit negativă, nu ne mai ajută: începem o… - [Sume parțiale în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/frecventa-sume-partiale-ciur/sume-partiale/): s[i] = v[1] + v[2] + ... + v[i], cu s[0] = 0, se calculează într-o singură trecere: s[i] = s[i - 1] + v[i]. Apoi suma pe orice interval [st, dr] este s[dr]… - [Valorile distincte și frecvențele lor în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/frecventa-sume-partiale-ciur/valorile-distincte-si-frecventele-lor/): După ce am construit vectorul de frecvență, valorile distincte sunt indicii val cu frecv[val] > 0. Parcurgându-i crescător, le afișăm direct în ordine… - [Vectorul de frecvență în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/frecventa-sume-partiale-ciur/vectorul-de-frecventa/): Pentru valori naturale mici (aici 0..1000), frecv[x] reține de câte ori a apărut valoarea x. Valoarea devine indice, așa că fiecare număr citit se numără… - [Algoritmi C++ clasa a 9-a](https://bogdanandras.com/algoritmi/clasa-a-9-a/): 87 de algoritmi C++ rezolvați pentru clasa a 9-a: cifrele unui număr, divizibilitate și numere prime, șiruri de numere citite pe rând, baze de numerație… - [Al n-lea termen al șirului lui Fibonacci în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/siruri-de-numere/al-n-lea-termen-al-sirului-lui-fibonacci/): Șirul lui Fibonacci începe cu 1, 1 și fiecare termen este suma celor doi dinaintea lui: 1, 1, 2, 3, 5, 8, ... Nu avem nevoie de vector: păstrăm doar ultimii… - [Cea mai lungă secvență de elemente egale în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/siruri-de-numere/cea-mai-lunga-secventa-de-elemente-egale/): O secvență înseamnă elemente aflate pe poziții consecutive. lung este lungimea secvenței curente: crește când numărul nou este egal cu cel anterior și revine… - [Cel mai mare termen Fibonacci cel mult egal cu n în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/siruri-de-numere/cel-mai-mare-termen-fibonacci-cel-mult-egal-cu-n/): Generăm termenii șirului lui Fibonacci (1, 1, 2, 3, 5, ...) cât timp următorul termen nu depășește n. Ultimul termen păstrat este răspunsul. Se presupune n… - [Cele mai mari două valori în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/siruri-de-numere/cele-mai-mari-doua-valori/): Ținem minte cea mai mare valoare (max1) și a doua (max2). Dacă numărul nou depășește max1, vechiul max1 coboară pe locul doi; altfel, dacă depășește max2, îl… - [Citirea unui șir terminat cu 0 în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/siruri-de-numere/citirea-unui-sir-terminat-cu-0/): Nu știm dinainte câte numere urmează: citim până la primul 0, care doar marchează sfârșitul și nu face parte din șir. Se afișează câte numere s-au citit și… - [Cmmdc-ul mai multor numere în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/siruri-de-numere/cmmdc-ul-mai-multor-numere/): cmmdc(a, b, c) = cmmdc(cmmdc(a, b), c). Păstrăm în rez cmmdc-ul numerelor citite până acum și îl combinăm, cu algoritmul lui Euclid, cu fiecare număr nou… - [Șiruri de numere citite pe rând în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/siruri-de-numere/): 13 algoritmi C++ rezolvați la „Șiruri de numere citite pe rând” (clasa a 9-a): cea mai lungă secvență de elemente egale, cel mai mare termen Fibonacci cel… - [Maximul și minimul unui șir în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/siruri-de-numere/maximul-si-minimul-unui-sir/): Se citesc n și apoi n numere întregi. Maximul și minimul pornesc de la primul număr citit (nu de la 0, pentru că toate numerele pot fi negative), apoi… - [Numărarea elementelor cu o proprietate în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/siruri-de-numere/numararea-elementelor-cu-o-proprietate/): Se citesc n și n numere naturale. Numărăm câte dintre ele sunt pare și câte au ultima cifră egală cu prima. Fiecare proprietate are contorul ei, pornit de la… - [Numărul de schimbări de semn în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/siruri-de-numere/numarul-de-schimbari-de-semn/): Se citesc n numere nenule. O schimbare de semn are loc între doi termeni consecutivi de semne opuse, adică atunci când produsul lor este negativ. Comparăm… - [Perechi de termeni consecutivi cu o proprietate în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/siruri-de-numere/perechi-de-termeni-consecutivi-cu-o-proprietate/): Numărăm perechile de termeni aflați unul după altul care au aceeași paritate. Un șir de n termeni are n - 1 perechi consecutive; pentru fiecare termen nou x… - [Suma și media aritmetică în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/siruri-de-numere/suma-si-media-aritmetica/): Se citesc n și n numere întregi; se afișează suma și media lor aritmetică, cu două zecimale. La medie împărțim un număr real la n (1.0 * suma / n); suma / n… - [Verificarea unei progresii aritmetice în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/siruri-de-numere/verificarea-unei-progresii-aritmetice/): Un șir este progresie aritmetică dacă diferența dintre doi termeni consecutivi este mereu aceeași (rația). Rația se află din primii doi termeni, apoi fiecare… - [Verificarea unui șir crescător în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/siruri-de-numere/verificarea-unui-sir-crescator/): Șirul este crescător dacă fiecare număr este cel puțin egal cu cel dinaintea lui. Păstrăm numărul anterior în variabila ant și comparăm fiecare număr nou cu… - [Căutarea binară în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/sortare-si-cautare/cautarea-binara/): Funcționează doar pe un vector sortat crescător. Comparăm x cu elementul din mijlocul zonei [st, dr]: dacă e egal, am terminat; dacă x e mai mic, căutăm în… - [Căutarea secvențială în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/sortare-si-cautare/cautarea-secventiala/): Verificăm elementele pe rând, de la primul, până găsim valoarea x sau terminăm vectorul. Merge pe orice vector, sortat sau nu. Se afișează poziția primei… - [Sortare și căutare în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/sortare-si-cautare/): 10 algoritmi C++ rezolvați la „Sortare și căutare” (clasa a 9-a): căutarea binară, căutarea secvențială, interclasarea a doi vectori sortați, prima poziție… - [Interclasarea a doi vectori sortați în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/sortare-si-cautare/interclasarea-a-doi-vectori-sortati/): Din doi vectori sortați crescător construim un al treilea, tot sortat. Comparăm elementele curente a[i] și b[j], îl copiem pe cel mai mic și avansăm doar în… - [Prima poziție cu valoare mai mare sau egală cu x în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/sortare-si-cautare/prima-pozitie-cu-valoare-mai-mare-sau-egala-cu-x/): Varianta de căutare binară care nu se oprește la prima potrivire: într-un vector sortat crescător, căutăm cea mai mică poziție p cu v[p] >= x. Dacă v[mij] >=… - [Sortarea cu std::sort în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/sortare-si-cautare/sortarea-cu-std-sort/): Biblioteca are funcția sort, care ordonează în O(n log n). Primește începutul și sfârșitul zonei: pentru pozițiile 1..n scriem sort(v + 1, v + n… - [Sortarea după două criterii în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/sortare-si-cautare/sortarea-dupa-doua-criterii/): Ordonăm numerele crescător după ultima cifră, iar numerele cu aceeași ultimă cifră descrescător după valoare. Algoritmul de sortare rămâne același (aici… - [Sortarea prin inserție în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/sortare-si-cautare/sortarea-prin-insertie/): Ca la aranjarea cărților de joc în mână: primele i - 1 elemente sunt deja sortate, iar v[i] este inserat la locul lui printre ele. Salvăm v[i] în x și mutăm… - [Sortarea prin metoda bulelor în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/sortare-si-cautare/sortarea-prin-metoda-bulelor/): Parcurgem vectorul și interschimbăm oricare două elemente vecine aflate în ordine greșită (v[i] > v[i + 1]). După fiecare parcurgere, cel mai mare element… - [Sortarea prin numărare în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/sortare-si-cautare/sortarea-prin-numarare/): Când valorile sunt numere naturale mici (aici 0..10000), nu comparăm elemente: numărăm de câte ori apare fiecare valoare într-un vector de frecvență, apoi… - [Sortarea prin selecție în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/sortare-si-cautare/sortarea-prin-selectie/): Pentru fiecare poziție i, de la 1 la n - 1, căutăm minimul din v[i..n] și îl aducem pe poziția i printr-o singură interschimbare. După pasul i, primele i… - [Citirea și afișarea unui vector în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/vectori/citirea-si-afisarea-unui-vector/): Un vector păstrează mai multe valori de același tip, accesate prin indice. Declarăm vectorul cu o dimensiune maximă fixă și folosim pozițiile 1..n. Se citesc… - [Eliminarea elementelor pare în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/vectori/eliminarea-elementelor-pare/): În loc să ștergem elementele pare unul câte unul (fiecare ștergere mută tot restul vectorului), facem o singură trecere: k numără elementele păstrate, iar… - [Tablouri unidimensionale (vectori) în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/vectori/): 11 algoritmi C++ rezolvați la „Tablouri unidimensionale (vectori)” (clasa a 9-a): citirea și afișarea unui vector, eliminarea elementelor pare, inserarea… - [Inserarea unei valori după fiecare element par în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/vectori/inserarea-unei-valori-dupa-fiecare-element-par/): Parcurgem vectorul de la sfârșit spre început. Când v[i] este par, mutăm elementele de după el cu o poziție la dreapta și punem x pe poziția i + 1. Mergând… - [Inserarea unui element pe o poziție în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/vectori/inserarea-unui-element-pe-o-pozitie/): Ca să punem val pe poziția poz, facem loc: mutăm elementele v[poz..n] cu o poziție la dreapta. Mutarea începe de la capăt (de la n spre poz); de la stânga… - [Inversarea unui vector în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/vectori/inversarea-unui-vector/): Interschimbăm primul element cu ultimul, al doilea cu penultimul și așa mai departe: v[i] cu v[n - i + 1]. Ne oprim la jumătate (i <= n / 2); dacă am merge… - [Maximul și pozițiile pe care apare în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/vectori/maximul-si-pozitiile-pe-care-apare/): Spre deosebire de un șir citit pe rând, un vector poate fi parcurs de mai multe ori: la prima parcurgere aflăm maximul, la a doua afișăm toate pozițiile pe… - [Permutarea circulară la dreapta în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/vectori/permutarea-circulara-la-dreapta/): Fiecare element se mută cu o poziție la dreapta, iar ultimul ajunge pe prima poziție. Salvăm v[n], mutăm restul de la capăt spre început (v[i] = v[i - 1]) și… - [Permutarea circulară la stânga în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/vectori/permutarea-circulara-la-stanga/): Fiecare element se mută cu o poziție la stânga, iar primul ajunge pe ultima poziție. Salvăm v[1] într-o variabilă, mutăm restul (v[i] = v[i + 1]) și punem… - [Ștergerea elementului de pe o poziție în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/vectori/stergerea-elementului-de-pe-o-pozitie/): Ca să ștergem elementul de pe poziția poz, mutăm elementele de după el cu o poziție la stânga, de la stânga spre dreapta (v[i] = v[i + 1]), apoi n scade cu… - [Suma elementelor de pe pozițiile pare și impare în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/vectori/suma-elementelor-de-pe-pozitiile-pare-si-impare/): Atenție la diferența dintre poziție (indicele i) și valoare (v[i]). Paritatea se verifică aici pentru indice: v[2], v[4], ... sunt pe poziții pare. Se… - [Verificarea unui vector simetric în C++](https://bogdanandras.com/algoritmi/clasa-a-9-a/vectori/verificarea-unui-vector-simetric/): Un vector este simetric (palindrom) dacă v[i] = v[n - i + 1] pentru orice i. Comparăm perechile de la capete spre mijloc și ne oprim la prima pereche… - [Algoritmi elementari în C++ pentru liceu](https://bogdanandras.com/algoritmi/): 266 de algoritmi C++ rezolvați și explicați pentru clasele 9–12: cifre, vectori, matrice, recursivitate, backtracking, grafuri, programare dinamică. Rulezi… - [Andras Bogdan-Andrei](https://bogdanandras.com/): Andras Bogdan-Andrei — computing student and developer. Programming, cloud and infrastructure, networking, cybersecurity and AI-driven automation, with real… - [Elementary Algorithms in C++](https://bogdanandras.com/projects/algoritmi-elementari-cpp/): 266 high-school algorithms, explained, verified — and now online. The complete collection of high-school algorithms in C++, organised by curriculum — now… - [CodePrepper](https://bogdanandras.com/projects/codeprepper/): High-school computer science in one app. Lessons, step-by-step algorithm animations, multiple-choice tests and C++ problems with automatic grading for grades… - [EdgePilot](https://bogdanandras.com/projects/edgepilot/): Let AI agents drive Microsoft Edge — safely. An MCP server and Edge extension that give AI agents labelled workspaces, a profile per chat, a side-panel chat… - [Projects](https://bogdanandras.com/projects/): 7 public projects by Andras Bogdan-Andrei: desktop apps, AI agent tools, browser automation, a self-hosted price tracker and a learning platform with 266… - [ManyAgentsAI](https://bogdanandras.com/projects/manyagentsai/): A whole AI team, not a single chatbot. 62 agents, 10 teams and 44 skills running on the Claude, Gemini or ChatGPT subscription you already have. English and… - [MocaLLM](https://bogdanandras.com/projects/mocallm/): Free LLMs, one endpoint, a whole team of agents. Dozens of free LLM providers behind one OpenAI- and Anthropic-compatible endpoint, with smart routing and… - [Photorunner](https://bogdanandras.com/projects/photorunner/): The photo editor that grows with you. Fast on-the-spot editing, watermark removal, filters, an AI assistant and LAN collaboration — on desktop and in the… - [PriceSentinel](https://bogdanandras.com/projects/pricesentinel/): Finds the cheapest store, in real time, and tells you. A self-hosted, multi-store price tracker with scheduled checks, cheapest-store alerts, AI link…