Алгоритмдер: циклдер, рекурсия, издөө

Программаны кол менен аткаруу

«Программа эмнени чыгарат?» деген маселеде өзгөрмөлөрдүн таблицасын түзүп, ар бир кадамда алардын маанилерин жазып отуруңуз. `range(a, b)` — $a$дан $b - 1$ге чейинки сандар экенин унутпаңыз.

```python s = 0 for i in range(1, 5): s += i * i print(s) # 1 + 4 + 9 + 16 = 30 ```

Рекурсия жана рекурренттик формулалар

Рекурсивдүү функциянын маанисин кичине аргументтерден баштап удаалаш эсептеген ыңгайлуу. Санап чыгуу маселелеринде да ушундай: $a_n$ ди мурунку мүчөлөр аркылуу туюнтуп алсак, жоопту таблица менен табабыз.

Мисалы, $1$ жана $2$ кадам менен $n$ тепкичке чыгуунун жолдорунун саны $a_n = a_{n-1} + a_{n-2}$ (Фибоначчи сандары).

Экилик издөө

Иреттелген массивде издөө аймагын ар бир кадамда эки эсе кичирейтебиз. $k$ салыштыруу менен узундугу $2^k - 1$ге чейинки массивди текшерсе болот, ошондуктан $n$ элемент үчүн эң начар учурда $\lfloor \log_2 n \rfloor + 1$ салыштыруу керек. $1000$ элемент үчүн — $10$, миллион үчүн — $20$.