Урок от 5 клас 39 - 26 май 2015 г. - Алгопедия
Съдържание
Ще обсъдим някои класически проблеми, със или без вектори.
Мощност
Изчислете a 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 е неправилна. Нямате право да използвате масиви (вектори или матрици).
Можем да разрешим проблема, като спазваме следните правила, валидни за всеки правилен израз:
- където и да „счупим“ израза, вляво ще имаме брой отворени скоби, по-големи или равни на затворените
- в края броят на затворените скоби трябва да бъде равен на затворените
Ако и двете условия са изпълнени, изразът е правилен. Първото условие трябва да бъде изпълнено за всяка позиция на счупване.
Тема на домашната работа: как да обобщим? Имаме кръгли скоби, квадратчета и скоби, същото изискване.