Анализ арифметических выражений.
Преамбула
В задачах этого листка:
- Использование вышеописанной процедуры и, таким образом, всех ее подпрограмм обязательно.
- Рекурсия запрещена.
- Для хранения комбинаций используется глобальный массив и соответствующие константы; данные с клавиатуры не вводятся.
- Время выполнения процедуры получитьСледующуюКомбинацию, по умолчанию не более Cn.
1. В этой задаче требуется написать функцию, возвращающую значение целого арифметического выражения по представляяющей его строке. Допустимые операции: сложение, вычитание, умножение ('*'), деление ('/'), остаток ('%'), степень ('^').
- строка состоит из 3-х символов и имеет формат <цифра> <оператор> <цифра>.
- строка состоит имеет формат <цифра> {<оператор> <цифра>}. (часть, заключенная в фигурные скобки может неограниченно повторяться или быть пустой)
- строка имеет формат <натуральное число> <оператор> <натуральное число>.
- те и только те, у которых i-ый член не превосходит i.
- так, чтобы соседние последовательности (а также первая и последняя) отличались бы только в одной позиции и только на единицу.
2. Напечатать все подмножества множества 1 .. k.
3.
- Напечатать все перестановки чисел 1 .. n. (то есть последовательности длины n, в которые каждое из этих чисел входит по одному разу).
- То же, так, чтобы соседние последовательности (а также первая и последняя) получались бы друг из друга обменом лишь двух элементов
4. Перечислить все возрастающие последовательности длины k из чисел 1 .. n в лексикографическом порядке.
пример: при n=5, k=2 получаем 12 13 14 15 23 24 25 34 35 45)
5.
- Перечислить все разбиения целого положительного числа n на целые положительные слагаемые (разбиения, отличающиеся лишь порядком слагаемых, считаются за одно). разбиения представляются как невозрастающие последовательности, порядок перечисления – лексикографический.
пример: для n = 4, разбиения 1+1+1+1, 2+1+1, 2+2, 3+1, 4.)
- Представляя по-прежнему разбиения как невозрастающие последовательности, переписать их в порядке, обратном лексикографическому.
пример: для n = 4, должно быть 4, 3+1, 2+2, 2+1+1, 1+1+1+1).
- Представляя разбиения как неубывающие последовательности, перечислить их в лексикографическом порядке.
пример: для n = 4: 1+1+1+1, 1+1+2, 1+3, 2+2, 4;
6. Перечислить все вложения (т. е. функции, переводящие разные элементы в разные) множества {1..k} в {1..n}, где k не превышает n.
7. Перечислить все последовательности нулей и единиц длины 2n, содержащие n нулей и n единиц, и такие, что в любом начальном отрезке число единиц не превосходит числа нулей.
8. Перечислить все способы расстановки скобок в произведении n сомножителей. Порядок сомножителей не меняется, скобки полностью определяют порядок действий.
пример: для n = 4 существует 5 расстановок:
- ((a...b)..c)..d
- .(a..(b...c)).d
- .(a...b).(c...d)
- ..a.((b...c)..d)
- ..a..(b..(c...d))
9. На окружности задано 2n пронумерованных точек Перечислить все способы провести nнепересекающихся хорд, с вершинами в этих точках.
10. Перечислить все способы разрезать выпуклый n–угольник на треугольники, проведя n–3 его диагонали.