Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Які бувають види алгоритмів за структурою?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)- Лінійні (послідовні) - кроки виконуються строго один за одним. - Розгалужені (з розгалуженнями) - вибір однієї з гілок виконання за умовою. - Циклічні (ітераційні) - повторення блоку дій, поки виконується умова або заданий діапазон. - Рекурсивні - алгоритм викликає сам себе до настання базового випадку (частіше розглядається як техніка організації, але виділяється окремо). - Комбіновані - поєднують перелічені структури керування в одному рішенні.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Коротка відповідь - Лінійні (послідовні) - кроки виконуються строго один за одним. - Розгалужені (з розгалуженнями) - вибір однієї з гілок виконання за умовою. - Циклічні (ітераційні) - повторення блоку дій, поки виконується умова або заданий діапазон. - Рекурсивні - алгоритм викликає сам себе до настання базового випадку (частіше розглядається як техніка організації, але виділяється окремо). - Комбіновані - поєднують перелічені структури керування в одному рішенні. ## Докладно У структурному програмуванні виділяють три базові керуючі структури: послідовність, розгалуження і цикл. Рекурсія - ключова техніка, яку часто розглядають окремо. Реальні алгоритми зазвичай комбінують кілька структур. ### 1) Лінійні (послідовні) Виконуються крок за кроком без розгалужень і повторень. Застосовні, коли порядок дій фіксований і не залежить від умов. - Переваги: простота, передбачуваність, легка перевірюваність. - Коли застосовувати: форматування даних, обчислення агрегатів, підготовка значень перед валідацією. - Типові помилки: зайві кроки, дублювання коду, відсутність обробки крайніх випадків. ```javascript function normalizeName(name) { return name.trim().toLowerCase().replace(/\s+/g, ' '); } function avg(nums) { if (!nums.length) return 0; let sum = 0; for (const n of nums) sum += n; return sum / nums.length; } const raw = " Alice Bob "; const normalized = normalizeName(raw); const mean = avg([10, 20, 30]); console.log({ normalized, mean: mean.toFixed(2) }); ``` ### 2) Розгалужені (з розгалуженнями) Вибір однієї з альтернатив за умовою. Основні конструкції: if/else, switch/case, тернарний оператор. - if / else - універсальний вибір за умовами. - switch - зручно для дискретних значень. - Тернарний ? : - для простих присвоєнь за умовою. ```javascript function grade(score) { if (score < 0 || score > 100) return "invalid"; // гвард-кейс if (score >= 90) return "A"; if (score >= 75) return "B"; if (score >= 60) return "C"; if (score >= 40) return "D"; return "F"; } console.log([95, 76, 12, 101].map(grade)); ``` 1. Слідкуйте за повнотою умов (обробіть крайні випадки). 2. Розташовуйте перевірки від більш строгих до менш строгих (або навпаки, але послідовно). 3. Уникайте "драбинок" if-else, якщо можна замінити на таблицю відповідностей/мапу. ### 3) Циклічні (ітераційні) Багаторазове виконання блоку коду. Види: for, while, do...while, а також ітеровані форми (for...of) і методи вищого порядку (forEach, map) - вони логічно теж реалізують повторення. - for - відома кількість ітерацій або перебір по колекції. - while - поки умова істинна; do...while - мінімум одна ітерація. - break/continue - керування потоком у циклі. ```javascript function sumUntilLimit(arr, limit) { let sum = 0; for (const n of arr) { if (sum + n > limit) break; // ранній вихід sum += n; } return sum; } console.log(sumUntilLimit([5, 3, 8, 2], 10)); // 8 ``` 1. Визначте інваріант - що залишається істинним на кожній ітерації. 2. Слідкуйте за зміною лічильників/умов, щоб уникнути нескінченних циклів. 3. Використовуйте ранні виходи (break/return), щоб не робити зайвих ітерацій. ### Рекурсивні алгоритми Рекурсія - спосіб розв'язання задач через розбиття на підзадачі того самого типу з базовим випадком. Особливо зручна для дерев, графів, розбиттів (divide and conquer). ```javascript const tree = { value: 1, children: [ { value: 2, children: [] }, { value: 3, children: [ { value: 4, children: [] } ] } ] }; function dfs(node, visit) { if (!node) return; // базовий випадок visit(node.value); for (const child of node.children || []) { dfs(child, visit); // рекурсивний крок } } dfs(tree, v => console.log(v)); // 1, 2, 3, 4 ``` - Обов'язково визначте базовий випадок і прогрес до нього, інакше буде переповнення стека. - Хвостова рекурсія може бути оптимізована компілятором/рушієм, але не всюди (у JS - немає гарантії). - Ітеративна версія через явний стек/чергу часто економить стек викликів і краще контролює пам'ять. ```javascript function dfsIter(root, visit) { if (!root) return; const stack = [root]; while (stack.length) { const node = stack.pop(); visit(node.value); const children = node.children || []; for (let i = children.length - 1; i >= 0; i--) { stack.push(children[i]); } } } dfsIter(tree, v => console.log(v)); // 1, 2, 3, 4 ``` ### Комбіновані алгоритми На практиці алгоритми зазвичай комбінують послідовні кроки, розгалуження і цикли. Приклад: валідація форми - лінійний прохід по полях (цикл) із перевіркою правил (розгалуження) і попередньою обробкою (послідовність). ```javascript function validateForm(fields) { const errors = []; for (const f of fields) { // цикл const value = String(f.value ?? "").trim(); // лінійна попередня обробка if (f.required && value === "") { // розгалуження errors.push(`${f.name}: required`); continue; } if (f.type === "email") { const ok = /^[^\s@]+@[^\s@]+\.[^\s@]+$/.test(value); if (!ok) errors.push(`${f.name}: invalid email`); } else if (f.type === "age") { const age = Number(value); if (!Number.isInteger(age) || age < 0 || age > 120) { errors.push(`${f.name}: invalid age`); } } } return errors; } console.log( validateForm([ { name: "email", type: "email", required: true, value: " user@example.com " }, { name: "age", type: "age", required: false, value: "200" } ]) ); ``` ## Коротка зведена таблиця | Тип | Ключова ідея | JS-конструкції | Де застосовуються | |---|---|---|---| | Лінійні | Послідовність кроків | Послідовні вирази | Форматування, агрегування | | Розгалужені | Вибір гілки за умовою | if/else, switch, ?: | Валідація, маршрутизація | | Циклічні | Повторення до умови/по діапазону | for, while, do...while, for...of | Перебір колекцій, пошук, агрегації | | Рекурсивні | Самозастосування до підзадач | Функції, що викликають самі себе | Дерева, графи, divide and conquer | | Комбіновані | Змішування структур | Комбінація вищезазначеного | Реальні застосунки і сервіси | ## Що можуть запитати на співбесіді - Наведіть приклади лінійного, розгалуженого і циклічного алгоритмів та їхню складність за часом/пам'яттю. - Коли рекурсія переважніша за ітерацію, і навпаки? Як переписати рекурсивний код ітеративно. - Намалюйте блок-схему алгоритму з розгалуженнями і циклами для заданої задачі. - Де додати ранні виходи (guard clauses) і чому це спрощує код. > Порада: перед кодом накидайте псевдокод, відзначте базові випадки та інваріанти - це знижує кількість помилок.Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.