Каталог по темам

Задачи

Страница: << 1 2 [Всего задач: 8]

Задача 98837

Темы:	[	Нерекурсивная генерация объектов	]
	[	Синтаксический разбор	]
	[	Числа Каталана	]

Сложность: 4

Перечислить все расстановки скобок в произведении n сомножителей. Порядок сомножителей не меняется, скобки полностью определяют порядок действий. Например, для n=4 есть 5 расстановок:

((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd)).

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

Решение

Задача 102789

[Параллельные вычисления ]

Темы:	[	Динамическое программирование (прочее)	]
Темы:	[	Синтаксический разбор (прочее)	]

Сложность: 4

Задано арифметическое выражение, содержащее операции сложения, умножения, круглые скобки и операнды, которыми являются буквы английского алфавита. Нас будет интересовать скорость вычисления таких выражений на многопроцессорной машине, поэтому скобки в них будем расставлять в обязательном порядке для указания порядка проведения операций.

Известно, что сложение двух чисел занимает время p, а умножение – время q. Время, необходимое для вычисления сложного выражения A^oB, равно времени, затрачиваемому на выполнение операции ^o, плюс максимальное из двух чисел – времени вычисления подвыражения A и времени вычисления подвыражения B. Время вычисления операнда полагаем равным нулю. Требуется написать программу, которая:
1. Определяет время, необходимое для вычисления заданного выражения на многопроцессорной машине.
2. Находит эквивалентное заданному арифметическое выражение с минимальным временем вычисления и само это время.

Выражения называется эквивалентными, если одно из них можно получить из другого последовательностью следующих преобразований:
    x + y → y + x ,                    x * y → y * x                    (коммутативный закон),
    x + (y + z) → (x + y) + z ,    x * (y * z) → (x * y) * z    (ассоциативный закон).

Входные данные
В первой строке входного файла содержатся два целых числа p и q (1 ≤ p,q ≤ 1000), во второй – арифметическое выражение длиной не более 200 символов.

Выходные данные
Первая строка выходного файла должна содержать ответ на первый пункт задачи. Во вторую строку выведите эквивалентное заданному выражение с минимальным временем вычисления, а в третью – само это время.

Пример входного файла
1 1
((a+(b+(c+d)))*e)*f

Пример выходного файла
5
((a+b)+(c+d))*(e*f)
3

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

Задача 102887

[Электронная таблица ]

Темы:	[	Обход графа в глубину	]
	[	Динамическое программирование (прочее)	]
	[	Синтаксический разбор (прочее)	]

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

Имеется таблица M × N, в каждой ячейке которой записано либо целое число, либо арифметическая формула. В формулах могут присутствовать целые числа, знаки *, /, +, -, (, ), пробелы и ссылки на значения из других ячеек таблицы, записываемые в виде {НомерCтроки, НомерCтолбца} (например, {1,10}). Требуется вычислить значения во всех ячейках заданной таблицы.

Входные данные:
В первой строке входного файла записаны целые числа M и N (1 ≤ M, N ≤ 20). В каждой из последующих M строк содержится описание очередной строки таблицы. Описание состоит из целых чисел и арифметических формул, разделенных символами | (ASCII-код 124). Все числа принадлежат диапазону [-32768, 32767], а длина каждой формулы не превышает 100 символов.

Выходные данные:
Выведите в выходной файл значения всех ячеек таблицы. Значения ячеек каждой строки таблицы должны быть записаны через пробел в отдельной строке выходного файла. Все значения следует выводить с точностью до двух знаков после десятичной точки. Если значение ячейки вычислить невозможно, вместо него следует вывести символ - (ASCII-код 45).

Пример входного файла
2 3
1      |    {1, 1   }*10        +3 |     -{1,2}/{2,2}
{2,3} |             0                     |           {2,1}

Пример выходного файла
1.00 13.00 -
- 0.00 -

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

Страница: << 1 2 [Всего задач: 8]