Информатика
>>
Книги, журналы
>>
А.Шень, Программирование: теоремы и задачи
>>
глава 1. Переменные, выражения, присваивания
Параграфы:
-
параграф 1. Задачи без массивов
(35 задач)
параграф 2. Массивы
(36 задач)
параграф 3. Индуктивные функции (по А.Г.Кушниренко)
(5 задач)
Фильтр
Задачи
Страница: << 5 6 7 8 9 10 11 >> [Всего задач: 55]
Дан массив a[1..n] и число b. Переставить числа
в массиве таким образом, чтобы слева от некоторой границы
стояли числа, меньшие или равные b, а справа от
границы — большие или равные b. Число действий
порядка n.
(Сообщил Ю. В.Матиясевич)
Дана функция
f : {1...N}
{1...N} Найти период последовательности
1, f(1), f(f(1), ... Количество действий
должно быть пропорционально суммарной длине предпериода
и периода (эта сумма может быть существенно меньше N)
Та же задача, но требуется, чтобы сначала шли элементы,
меньшие b, затем равные b, а лишь затем
большие b.
(Э. Дейкстра)
Функция f с натуральными аргументами
и значениями определена так:
f(0) = 0,
f(1) = 1,
f(2n) = f(n),
f(2n + 1) = f(n) + f(n + 1).
Составить программу вычисления
f(n) по
заданному n, требующую порядка
log n операций.
(Вариант предыдущей задачи, названный в книге Дейкстры
задачей о голландском флаге.) В массиве
длины n стоят числа 0, 1 и 2. Переставить
их в порядке возрастания, если единственной разрешённой
операцией (помимо чтения) над массивом является
перестановка двух элементов. Число действий порядка n.
Страница: << 5 6 7 8 9 10 11 >> [Всего задач: 55]
Задача 76262 (#1.2.31) |
|
|
|
|
Решение |
Задача 76228 (#1.1.32) |
|
|
|
|
|
Решение |
Задача 76263 (#1.2.32) |
|
|
|
|
|
Решение |
Задача 76229 (#1.1.33) |
|
|
|
|
|
Решение |
Задача 76264 (#1.2.33) |
|
|
|
|
|
Решение |
Страница: << 5 6 7 8 9 10 11 >> [Всего задач: 55]
