Урок 5 класу 39 - 26 травня 2015 р. - Альгопедія

Зміст

Ми обговоримо деякі класичні проблеми, з векторами чи без них.

Потужність

Обчисліть n якомога ефективніше (a та n натуральних чисел). Проблема також відома як логарифмічне зростання. Ідея цього рішення полягає в наступному:

Якщо n парне, то a n = a 2 * n/2 = (a 2) n/2
Якщо n непарне, то n-1 парне і маємо an = a * a n-1 = a * a 2 * (n-1)/2 = a * (a 2) (n-1)/2 = a * (a 2) n/2

У наведених вище формулах ми врахували, що/- це цілочисельний поділ мови C. Тому, коли n непарне (n-1)/2, це те саме, що n/2. Спостерігається, що незалежно від парності n, на кожному кроці ітерації ми можемо перетворити a на a * a, а потім поділити n на 2. Лише у випадках, коли n непарне, ми будемо накопичувати поточне значення a у розрахунковому добутку. Ось рішення, засноване на цій ідеї:

Монотонна послідовність

Скажіть, чи послідовність чисел одноманітна. Послідовність є монотонною, якщо її номери знаходяться у порядку зростання або зменшення. Послідовність має щонайменше два числа. Вам заборонено використовувати масиви (вектори або матриці).

дужки

Враховуючи послідовність 0 і 1, де 0 означає відкриту дужку '(', а 1 означає закриту дужку ')', скажіть, чи є послідовність правильним вираженням дужок, і якщо це так, обчисліть максимальну кількість дужок одна в одній. Приклад: 0 1 0 0 1 0 1 1 є правильним і має коефіцієнт вкладеності 2, тоді як послідовність 0 0 0 1 1 1 0 є неправильною. Вам заборонено використовувати масиви (вектори або матриці).

Ми можемо вирішити проблему, дотримуючись наступних правил, що діють для будь-якого правильного виразу:

скрізь, де ми "розбиваємо" вираз, ліворуч матимемо число відкритих дужок, більших або рівних закритим
в кінці кількість закритих дужок має дорівнювати замкнутим

Якщо виконуються обидві умови, вираз правильний. Перша умова повинна бути виконана для кожного положення розриву.

Тема домашнього завдання: як узагальнити? У нас є круглі дужки, квадрати та брекети, однакові вимоги.