Рекурсия: как ею пользоваться
- Понятие рекурсии (прямой и косвенной)
Лаконичность и ресурсоёмкость рекурсии на примере задачи «f(2n)=f(n); f(2n+1)=f(n)+f(n+1)»
- Задачи, для решения которых рекурсия не требуется (вычисление факториала и пр.)
- Логарифмическая глубина — признак допустимости рекурсии
- на примере алгоритма быстрой сортировки
- Переход от рекурсии к циклу с отслеживанием состояния
на примере решения задачи о разложении на слагаемые
Изготовление файла со случайным содержимым, склеивание и сравнение файлов на примене задачи о разбиении файлов
Домашнее задание
Прочитать о рекурсии в Википедии - Составить программу для вычисления суммы: 2! + 4! + 6! + ... + п!
- Рекурсивную
- Нерекурсивную
Эффективно работающую на относительно больших числах, например, n==10000
Решить-таки задачу о сортировке строк в файле с помощью сортировки слиянием
«Лобовой» вариант (отдельный файл на каждую упорядоченную последовательность строк): 2012-12-14.joinsort.py
Вариант с созданием только двух временных файлов: joinsort.py
Генератор тестового файла: 2012-12-14.joinsort.gen.py
(MCCME) Радиолюбитель Петя решил собрать детекторный приемник. Для этого ему понадобился конденсатор емкостью C мкФ. В распоряжении Пети есть набор из n конденсаторов, емкости которых равны c1, c2, ..., cn, соответственно. Петя помнит, как вычисляется емкость параллельного соединения двух конденсаторов (Cnew = C1 + C2) и последовательного соединения двух конденсаторов (Cnew = (C1*C2)/(C1+C2)). Петя хочет спаять некоторую последовательно-параллельную схему из имеющегося набора конденсаторов, такую, что ее емкость ближе всего к искомой (то есть абсолютная величина разности значений минимальна). Разумеется, Петя не обязан использовать для изготовления схемы все конденсаторы. (Напомним определение последовательно-параллельной схемы. Схема, составленная из одного конденсатора, – последовательно-параллельная схема. Любая схема, полученная последовательным соединением двух последовательно-параллельных схем, – последовательно-параллельная, а также любая схема, полученная параллельным соединением двух последовательно-параллельных схем, – последовательно-параллельная).
Формат входных данных: В первой строке входных данных содержатся числа n и C. Во второй строке задается последовательность емкостей имеющихся в наличии конденсаторов с1, с2, ..., сn. Значения всех емкостей – вещественные числа. Для всех наборов входных данных n < 7.
Формат выходных данных: Выведите минимально отличающуюся от C емкость последовательно-параллельной схемы из имеющихся конденсаторов. Результат выводите с шестью знаками после запятой.
Вот интересно, почему у авторов эта задача называется «Резисторы»? -- FrBrGeorge 2012-12-22 16:16:15
(генератор тестовых данных 2012-12-14.yomkosti.gen.py
Условные обозначения
- — тема по Linux
- — тема повышенной сложности
- — теоретическое задание
— тема для самостоятельного изучения