-
Книги, журналы, Алфутова Н.Б., Устинов А.В., Алгебра и теория чисел, глава 1. Метод математической индукции, параграф 1. Аксиома индукции
Книги, журналы, Алфутова Н.Б., Устинов А.В., Алгебра и теория чисел, глава 1. Метод математической индукции, параграф 2. Тождества, неравенства и делимость
Книги, журналы, Алфутова Н.Б., Устинов А.В., Алгебра и теория чисел, глава 1. Метод математической индукции, параграф 3. Индукция в геометрии и комбинаторике
Фильтр
Выбрана 1 задача Убрать все задачи
Задано арифметическое выражение, содержащее операции сложения, умножения, круглые скобки и операнды, которыми являются буквы английского алфавита. Нас будет интересовать скорость вычисления таких выражений на многопроцессорной машине, поэтому скобки в них будем расставлять в обязательном порядке для указания порядка проведения операций.
Известно, что сложение двух чисел занимает время p, а умножение – время
q. Время, необходимое для вычисления сложного выражения
AoB, равно времени, затрачиваемому на выполнение операции
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
Решение
Задачи
Задача 98129 |
|
|
Пусть m, n и k – натуральные числа, причём m > n. Какое из двух чисел больше:
или
(В каждом выражении k знаков квадратного корня, m и n чередуются.)
|
|
Решение |
Задача 30794 |
|
|
В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от каждого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать во всех городах, совершив не более а) 198 перёлетов; б) 196 перелётов.
|
|
|
Решение |
Задача 30824 |
|
|
На ребрах связного графа расставлены стрелки так, что для каждой вершины числа входящих и выходящих рёбер равны.
Докажите, что двигаясь по стрелкам, можно добраться от каждой вершины до любой другой.
|
|
|
Решение |
Задача 32896 |
|
|
Сто мудрецов хотят проехать на электричке из 12 вагонов от первой до 76-й станции. Они знают, что на первой станции в два вагона электрички сядут два контролёра. После четвёртой станции на каждом перегоне один из контролёров будет переходить в соседний вагон, причём они "ходят" по очереди. Мудрец видит контролёра, только если он в соседнем вагоне или через вагон. На каждой станции каждый мудрец может перебежать по платформе не далее чем на три вагона (например, из 7-го вагона мудрец может добежать до любого вагона с номером от 4 до 10 и сесть в него). Какое максимальное число мудрецов сможет ни разу не оказаться в одном вагоне с контролёром, как бы контролёры ни перемещались? (Никакой информации о контролёрах, кроме указанной в задаче, мудрец не получает. Мудрецы договариваются о стратегии заранее.)
|
|
|
Решение |
Задача 35154 |
|
|
Докажите, что при умножении многочлена (x + 1)n–1 на любой многочлен, отличный от нуля, получается многочлен, имеющий не менее n отличных от нуля коэффициентов.
|
|
|
Решение |
Страница: << 41 42 43 44 45 46 47 >> [Всего задач: 332]
