Каталог по источникам

Задачи

Страница: << 10 11 12 13 14 15 16 >> [Всего задач: 78]

Задача 98833

Тема:

[

Нерекурсивная генерация объектов

]

Сложность: 3+

Представляя разбиения как неубывающие последовательности, перечислить их в порядке, обратном лексикографическому. Пример для n=4: 4, 2+2, 1+3, 1+1+2, 1+1+1+1.

Прислать комментарий Решение

Задача 76206

Темы:	[	Числа Фибоначчи	]
Темы:	[	Линейная алгебра	]

Сложность: 4

Та же задача, если требуется, чтобы число операций было пропорционально log n. (Переменные должны быть целочисленными.)

Прислать комментарий Решение

Задача 76245

Тема:

[

Многочлены

]

Сложность: 4

(В. Баур, Ф.Штрассен) Дана программа вычисления значения некоторого многочлена P(x₁,..., x_n), содержащая только команды присваивания. Их правые части — выражения, содержащие сложение, умножение, константы, переменные x₁,..., x_n и ранее встречавшиеся (в левой части) переменные. Доказать, что существует программа того же типа, вычисляющая все n производных $\partial$ P/ $\partial$ x₁,..., $\partial$ P/ $\partial$ x_n, причём общее число арифметических операций не более чем в C раз превосходит число арифметических операций в исходной программе. Константа C не зависит от n.

Прислать комментарий Решение

Задача 76247

Тема:

[

Многочлены

]

Сложность: 4

Предложенный выше алгоритм перемножения многочленов требует порядка n² действий для перемножения двух многочленов степени n. Придумать более эффективный (для больших n) алгоритм, которому достаточно порядка n^{log 4/log 3} действий.

Прислать комментарий Решение

Задача 98834

Тема:

[

Нерекурсивная генерация объектов

]

Сложность: 4

Перечислить все последовательности длины n из чисел 1..k в таком порядке, чтобы каждая следующая отличалась от предыдущей в единственной цифре, причём не более, чем на 1.

Прислать комментарий Решение

Страница: << 10 11 12 13 14 15 16 >> [Всего задач: 78]