Методическое пособие по информатике:Программирование: ТЕОРЕМЫ И ЗАДАЧИ

НЕСКОЛЬКО ЗАМЕЧАНИЙ ВМЕСТО ПРЕДИСЛОВИЯ
Книга написана по материалам занятий программированием со школьниками математических классов школы N 57 (г. Москва). Книга написана в убеждении, что программирование имеет свой предмет, не сводящийся…
1.2. Массивы
      (а) Определить четность перестановки. (И в (а), и в (б) количество действий порядка n.) (б) Не используя других массивов, заменить перестановку на обратную (если до работы программы a[i]=j,…
1.3. Индуктивные функции (по А.Г.Кушниренко)
      (а) среднее арифметическое последовательности вещественных чисел; (б) число элементов последовательности целых чисел, равных ее максимальному элементу; (в) второй по величине элемент последовательности…
1.1.Задачи без массивов
1.1.1. Даны две целые переменные a, b. Составить фрагмент программы, после исполнения которого значения переменных поменялись бы местами (новое значение a равно старому значению b и наоборот).  …
2.2. Перестановки
  2.2.1. Напечатать все перестановки чисел 1..n (то есть последовательности длины n, в которые каждое из чисел 1..n входит по одному разу). Решение. Перестановки будем хранить в массиве x[1],...,…
2.1. Размещения с повторениями
  Здесь собраны задачи, в которых требуется получить один за другим все элементы некоторого множества.   2.1.1. Напечатать все последовательности длины k из чисел 1..n. Решение. Будем печатать…
2.3. Подмножества
  2.3.1. Перечислить все k-элементные подмножества множества {1..n}. Решение. Будем представлять каждое подмножество последовательностью x[1]..x[n] нулей и единиц длины n, в которой ровно k единиц.…
2.4. Разбиения
  2.4.1. Перечислить все разбиения целого положительного числа n на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно). (Пример: n=4, разбиения 1+1+1+1,…
2.5. Коды Грея и аналогичные задачи
Иногда бывает полезно перечислять объекты в таком порядке, чтобы каждый следующий минимально отличался от предыдущего. Рассмотрим несколько задач такого рода. 2.5.1. Перечислить все последовательности…
2.6. Несколько замечаний
  Посмотрим ещё раз на использованные нами приёмы. Вначале удавалось решить задачу по такой схеме: определяем порядок на подлежащих перечислению объектах и явно описываем процедуру перехода от данного…
2.7. Подсчет количеств
  Иногда можно найти количество объектов с тем или иным свойством, не перечисляя их. Классический пример: C(n,k) - число всех k-элементных подмножеств n-элементного множества - можно найти, заполняя…
Глава 3. Обход дерева. Перебор с возвратами
    3.1. Ферзи, не бьющие друг друга: обход дерева позиций В предыдущей главе мы рассматривали несколько задач одного и того же типа: "перечислить все элементы некоторого множества A". Схема решения…
4.2. Алгоритмы порядка n log n
   4.2.1. Предложить алгоритм сортировки, число действий которого было бы порядка n log n, то есть не превосходило бы C*n*log(n) для некоторого C и для всех n. Мы предложим два решения. Решение…
4.1. Квадратичные алгоритмы
  4.1.1. Пусть a[1], ..., a[n] - целые числа. Требуется построить массив b[1], ..., b[n], содержащий те же числа, для которого b[1] <= ... <= b[n]. Замечание. Среди чисел a[1]...a[n] могут быть…
4.3. Применения сортировки
  4.3.1. Найти количество различных чисел среди элементов данного массива. Число действий порядка n*log n. (Эта задача уже была в главе о массивах.) Решение. Отсортировать числа, а затем посчитать…
4.4. Нижние оценки для числа сравнений при сортировке
  Пусть имеется n различных по весу камней и весы, которые позволяют за одно взвешивание определить, какой из двух выбранных нами камней тяжелее. (В программистских терминах: мы имеем доступ к функции…
4.5. Родственные сортировке задачи
  4.5.1. Какова минимально возможная сложность (число сравнений в наихудшем случае) алгоритма отыскания самого легкого из n камней? Решение. Очевидный алгоритм с инвариантом "найден самый легкий камень…