Грокаем а Иллюстрированное пособие для программистов и любопытствующих

def sum(list): if list == []: return 0
return list[0] + sum(list[l:])

2. 
   Напишите рекурсивную функцию для подсчета элементов в списке. Ответ-.
   

def count(list): if list == []: return 0
return 1 + count(list[1:])

3. 
   Найдите наибольшее число в списке.
   

Ответ-.
def max(list):
if len(list) == 2:
return list[0] if list[0] > list[l] else list[l] subjnax = max(list[l: ])
return list[0] if list[0] > sub_max else sub_max

4. 
   Помните бинарный поиск из главы 1? Он тоже относится к классу ал­горитмов «разделяй и властвуй». Сможете ли вы определить базовый и рекурсивный случай для бинарного поиска?
   

Ответ: Базовым случаем для бинарного поиска является массив, содержащий всего один элемент. Если искомый элемент совпадает с элементом массива - вы нашли его! В противном случае элемент в массиве отсутствует.
В рекурсивном случае для бинарного поиска массив делится пополам, одна половина отбрасывается, а для другой половины проводится бинарный поиск.
Запишите «О-болыпое» для каждой из следующих операций.

5. 
   Вывод значения каждого элемента массива.
   

Ответ: 0(п).

6. 
   Удвоение значения каждого элемента массива.
   

Ответ: 0(п).

7. 
   Удвоение значения только первого элемента массива.
   

Ответ: 0(1).

8. 
   Создание таблицы умножения для всех элементов массива. Например, если массив состоит из элементов [2, 3, 7, 8, 10], сначала каждый эле­мент умножается на 2, затем каждый элемент умножается на 3, затем на 7 и т. д.
   

Ответ: 0(п²).
Глава 5
Какие из следующих функций являются последовательными? 5.1 f(x) = 1 < Возвращает "1" для любых входных значений
Ответ: Функция последовательна.
5.2 f(x) = rand() < Возвращает случайное число
О
5.3


f(х) = next empty_slot() <
Ответ: Функция непоследовательна.