Расставьте скобки всеми возможными способами

При любой расстановке скобок данное выражение можно представить в виде дроби. Тогда, так как все данные числа — простые, результат вычислений будет однозначно определяется тем, куда «попало» каждое из этих чисел: в числитель или в знаменатель. Очевидно, что независимо от расстановки скобок, число 2 попадает в числитель, а число 3 — в знаменатель. Каждое из следующих чисел может «попасть» как в числитель, так и в знаменатель, например, при такой расстановке скобок 2 : (3 : 5) $\cdots$ число 5 окажется в числителе дроби, а если скобки поставить так (2 : 3) : 5 $\cdots$ — в знаменателе.

Докажем, что существуют расстановки скобок, при которых каждое из чисел 5, 7, 11, 13, 17, 19, 23, 29 «попадает» как в числитель, так и в знаменатель, независимо от расположения остальных чисел. Для этого, например, разобьем все данные числа, начиная с числа 3, на группы следующим образом: каждая группа начинается с числа, которое должно «попасть» в знаменатель, и может содержать еще несколько (в том числе, и ноль) чисел, идущих следом за ним, которые все должны «попасть» в числитель. Эти группы заключаем в скобки и больше нигде скобок не ставим. Тогда первое число каждой группы попадет в знаменатель, так как на него непосредственно делится двойка, а остальные числа группы «попадут» в числитель, так как на них делится первое число из этой группы, «попавшее» в знаменатель.

Таким образом, количество чисел, которые могут являться значением данного выражения при всех возможных расстановках скобок, равно $2^ <8>= 256$.

Эту задачу можно обобщить для любого количества чисел, причем они не обязательно должны быть простыми. Расставляя всеми возможными способами скобки в выражении $a_ <1>: a_ <2>: \cdots : a_$, где каждые два числа взаимно просты, можно получить $2^$ различных значения.
Ответ: 256.

Источник

Как расставить скобки в выражении всеми возможными способами? какова сложность оптимального алгоритма?

Есть арифметическое выражение состоящее из целых чисел, и операций +,-,*,\ к примеру 1+2-3*4. Надо найти множество всех уникальных результатов данного выражения при всевозможных расстановках скобок в выражении:
(1+2)-(3*4); (1+2-3)*4 и т.д.

я придумал 3 алгоритма, но все они имею в худшем случае O(n!). Есть ли более оптимальные алгоритмы?

Для простоты, давайте считать, что есть два массива nums и ops — чтобы не вдаваться в детали разбора выражения.

Мои решения:
Вариант 1
1. определяем рекурсивную функцию на вход которой подается два массива ops и nums и третий массив, куда будем складывать результаты
2. Если ops пустой, или ops содержит одну операцию, или ops содержит операции одного приоритета, вычисляем знаечение выражения, т.к. его результат не зависит от расстановки скобок, добавляем этот результат в массив с результатами и возвращаемся из функции.
3. Цикл по всем операциям из массива ops
4. для выбранной операции — считаем что она будет первой, выбираем соответствующие ей операнды из nums выполняем операцию
5. обновляем массив nums заменяя два операнда на результат выполнения операции и удаляя операцию из массива ops
6. рекурсивно вызываем функцию для новых массивов nums и ops меньшего размера
7. продолжаем цикл
8. в результирующем массиве удаляем стандартными функциями все дубли

Вариант 2.
1. определяем рекурсивную функцию с таким же входом как и в первом варианте
2. Если ops пустой, или ops содержит одну операцию, или ops содержит операции одного приоритета, вычисляем значение выражения, т.к. его результат не зависит от расстановки скобок, добавляем этот результат в массив с результатами и возвращаемся из функции.
3. цикл по всем операциям
4. выбранную операцию будем считать последней при вычислении
5. Формируем два подвыражения, все что стоит слева от выбранной операции и все что стоит справа
6. Рекурсивно вычисляем результат выполнения функции на 2-х подвыражениях, получаем два массива с уникальными результатами.
7. делаем декартово произведение этих массивов — выполняя для каждой пары выбранную операцию, заносим ее в результирующий массив
8. Удаляем из результирующего массива дубли

Третий вариант совсем плохой —
ставим в соответствие массиву операций массив [1. n] если n количество операций. И более менее стандартными алгоритмами получаем все возможные перестановки этого массива
потом считаем выражение с учетом последовательности выполнения операций в соответствии с очередной перестановкой.

Анализ все алгоритмы имеют сложность O(n!) но второй алгоритм, уменьшает сложность за счет того что:
1. (1+1-4+6) — такого рода подвыражения считает сразу не пытаясь расставить скобки разными вариантами
2. (1-2)-(3*4) — вычисляет один раз т.к. нам неважно что будет сосчитано в первую очередь (1-2) или (3*4). В первом алгоритме такое выражение получится и при выборе в качестве первой операции первый минут и при выборе в качестве первой операции умножения.

Буду благодарен если кто- пришлет более интересные решения или поможет доказать что второйвариант оптимальное решение.

Источник

Олимпиада по математике школьный этап 2021 ВОШ задания и ответы для 4-11 класса

ПОДЕЛИТЬСЯ

Задания и ответы школьного этапа 2021 олимпиады по математике для 4-11 класса всероссийской олимпиады школьников 2021-2022 учебного года, официальная дата проведения олимпиады в Омске: 06.10.2021 (6 октября 2021 года)

Задания и ответы для 4 класса: скачать

Задания и ответы для 5 класса: скачать

Задания и ответы для 6 класса: скачать

Задания и ответы для 7 класса: скачать

Задания и ответы для 8 класса: скачать

Задания и ответы для 9 класса: скачать

Задания и ответы для 10 класса: скачать

Задания и ответы для 11 класса: скачать

Интересные задания и ответы олимпиады:

1)Ваня представил число 100 в виде суммы 14 слагаемых, имеющих одинаковую сумму цифр: 100=20+20+20+20+2+2+2+2+2+2+2+2+2+2 (сумма цифр числа 20 равна 2+0=2). Вася смог представить число 100 в виде суммы 11 слагаемых, имеющих одинаковую сумму цифр. Как он это сделал? Достаточно привести один пример такого представления.

Ответ: 100=50+5+5+5+5+5+5+5+5+5+5.

2)Вера, накопив 200 рублей, хотела купить пенал, но этих денег ей не хватило. Через несколько дней пенал уценили, и он стал стоить в два раза меньше. Теперь Вера смогла его купить и даже получила сдачу 15 рублей. Сколько стоил пенал первоначально? Ответ нужно подтвердить вычислениями и объяснениями.

Ответ: 370 р.

3)Фермер огородил снаружи участок земли и разделил его на квадратики со стороной 3 м. В пяти квадратиках он разместил гусятники (обозначены «Г»), а в других пяти – будки со сторожевыми собаками (обозначены «С»). Но гуси нападают на собак, а собаки могут загрызть гусей. Помогите фермеру построить по линиям сетки дополнительные заборы общей длины 30 м, чтобы защитить собак от гусей и гусей от собак.

Ответ: например, так, как на рисунке справа.

4)По кругу стоят 10 сорочат. Мама–сорока кормит их кашей: первому – 1 ложку, второму – 2 ложки, следующему – 1, потом – 2 и так далее. Всего она раздала 55 ложек каши, и на этом каша закончилась. Сколько сорочат получили ровно 4 ложки каши? Ответ нужно обосновать.

Ответ: 4 птенца

5)Никита записал два нечётных числа, а потом заменил в них разные цифры разными буквами, а одинаковые – одинаковыми. У Никиты получились два слова: УЧИТЕЛЯ и МЕЧТАТЕЛИ. Известно, что произведение цифр числа УЧИТЕЛЯ не равно нулю, а произведение цифр числа МЕЧТАТЕЛИ равно нулю. Чётной или нечётной будет сумма Я+И+МЕЧТА? Ответ нужно обосновать.

Ответ: чётная

6)В семье Веснушкиных три человека, и у каждого на лице в два раза больше веснушек, чем ему лет. Васе сейчас 11 лет. Васина мама младше Васиного папы на 3 года, и у неё на лице 66 веснушек. Сколько веснушек на лице у всех троих вместе? Ответ нужно подтвердить вычислениями и объяснениями.

Ответ: 160 веснушек.

7)Найдите какое-нибудь решение неравенства М Ответ: например, М=1, А=3, Т=2, Е=4, И=5, К=9, т.е. 1

8)Маша попросила встать 30 одноклассников по кругу и стала раздавать им шоколадные конфеты. Первому дала 1 конфету, второму – 2 конфеты, следующему – снова 1 конфету, потом – 2 конфеты и так далее. Всего она раздала 55 конфет, и на этом конфеты закончилась. Сколько Машиных одноклассников получили ровно 2 конфеты? Ответ нужно обосновать

Ответ: 16 человек

9)На рисунке слева изображена фигура на клетчатой бумаге. Сторона каждой клетки равна 1 см. Разрежьте данную фигуру по линиям сетки на фигурки, удовлетворяющие всем четырём условиям: 1) площадь каждой равна 5 см2 ; 2) периметр каждой равен 12 см; 3) все фигурки должны быть различными, т.е. не совпадать при наложении; 4) в каждой должен быть ровно один серый квадратик. Достаточно привести один вариант разрезания.

Ответ: например, как на рисунке ниже.

10)Винни-Пух, Пончик и Карлсон приняли участие в турнире обжор. По результатам трёх туров судья заполнил таблицу, где указал, сколько пирогов в каждом туре съел каждый участник. Оказалось, что все числа в таблице различны. Ночью каждый из участников увеличил только один из своих результатов в таблице на 1. Утром все увидели следующую таблицу.

Ответ: см. файл выше

11)На клетчатой бумаге нарисован прямоугольник 3х4 клетки. Разрежьте его по сторонам клеток на 3 части так, чтобы из них можно было сложить фигуру, изображенную справа.

Ответ: вариант разрезания приведен: 1-я часть с цифрами «1», 2-я часть – «2» и 3-я часть – «3». Из них легко складывается нужная фигура.

12)Мальвина написала на доске выражение М+А = Т+Е = М+А+Т = И+К+А и попросила Буратино заменить все буквы цифрами так, чтобы равенства оказались верными. Причем разные буквы нужно заменять разными цифрами, а одинаковые буквы ‒ одинаковыми цифрами. Помогите Буратино справиться с задачей. Достаточно привести хотя бы один пример.

Ответ: пусть М=5, А=2, Т=0, Е=7, И=1, К=4. Тогда получим верные равенства: 5+2=0+7=5+2+0=1+4+2.

13)Семи детям раздали 55 конфет. После этого первыйсказал, что по крайней мере 1 конфета у него имеется. «А у меня ровно на две больше!» — сказал второй. «А у меня ровно на две больше, чем у тебя!» — сказал третийвторому, затем такую же фразу произнес четвертый— третьему, пятый – четвертому, шестой— пятому. А седьмой заявил: «А у меня конфет больше всех!». Сколько конфет получил седьмой ребенок? Найдите все варианты и докажите, что других нет.

Ответ: 13 или 19

14)У Алисы есть три деревянных кубика. Длина ребра меньшего кубика равна 1 дм, среднего — 2 дм, большего — 3 дм. На покраску меньшего кубика ей потребовалось на 120 г краски меньше, чем на покраску среднего кубика. Сколько граммов краски ей потребуется на покраску большего кубика?

Ответ: 360 г.

15)Чтобы насытиться, голодному кролику нужно съесть ровно три каких-нибудь различных овоща. Какое наибольшее количество голодных кроликов можно накормить досыта, если в запасах имеется 5 кукуруз, 8 огурцов, 11 морковок и 17 перцев? Ответ нужно обосновать.

Ответ: 12

16)На клетчатой бумаге нарисован прямоугольник 3х4 клетки. Разрежьте его по сторонам клеток на 3 части так, чтобы из них можно было сложить фигуру, изображенную справа.

Ответ: вариант разрезания приведен: 1-я часть с цифрами «1», 2-я часть – «2» и 3-я часть – «3». Из них легко складывается нужная фигура.

17)Замените буквы A, B, C, D, E, F, G, K цифрами от 1 до 8 без повторений так, чтобы числа 6, 11, 16, 21 в серых треугольниках являлись суммами цифр, стоящих в трёх белых треугольниках, соседствующих по сторонам с серым.

Ответ: подходящие значения букв: А=2, В=3, С=5, D=1, Е=8, F=4, G=6, К=7. Легко проверить, что условие задачи выполняется.

18)Рыбак поймал 6 кг рыбы. Часть приготовил себе, остальное отдал трём котам. Каждый кот съедает в 2 раза больше рыбы, чем рыбак за одно и то же время. Сколько килограммов рыбы было отдано котам, если есть все начали одновременно, а коты съели свою часть в 2 раза быстрее, чем рыбак?

Ответ: 4,5 кг.

19)Три одинаковых кубика приставлены друг к другу гранями с одинаковым числом очков. Найдите сумму чисел на трёх нижних гранях кубиков данной конструкции, на верхних гранях которых числа 3, 5 и 6.

Ответ: 7

20)Лиса Алиса, Буратино и Пьеро нашли 110 золотых монет. Алиса предложила разложить их на три кучки и сказала: «Пусть жребий определит, кому какая достанется!» Чтобы мальчики не расстраивались, они договорились уравнять свои кучки по меньшей, а лишнее отдать Алисе. (Например, если Буратино достанется 10 монет, Пьеро – 15, а Алисе – 85 монет, то Пьеро отдаст Алисе 5 монет, чтобы у него с Буратино стало поровну). Алисе необходимо разложить все монеты на три кучки так, чтобы в результате ей наверняка досталось не меньше 100 золотых монет. Сколько у нее есть вариантов?

Ответ: 15

21)Сколько раз в последовательности из 12 чисел: 2, _, _, _, _, _, _, _, _, _, _,1 (на первом месте стоит 2, на последнем месте 1) встретится цифра 2, если известно, что сумма любых трех чисел, идущих подряд, равна 5?

Ответ: 8 раз

22)На турнир «рыцарей и лжецов» математического кружка ребята мастерили из квадратного листа картона размером 150см×150см стену рыцарского замка. По краям и в середине было вырезано три одинаковых квадрата. Петя заметил, что при этом периметр первоначального листа увеличился на 8%. Найдите площадь получившейся «стены».

Ответ: 20772 см2

23)Петя и Вася живут в одном доме и выходят в школу одновременно. Петя сначала считает ворон и идет со скоростью 4 км/ч, но ровно на середине пути на парковке пересаживается на велосипед и едет со скоростью 12 км/ч. Вася идет в школу с постоянной скоростью и приходит в школу одновременно с Петей. Учитель Степан Иванович на середине пути обгоняет Петю на мопеде, так как его скорость в 5 раз больше скорости Васи, он приезжает в щколу на 3 минуты раньше мальчиков. Найдите расстояние от дома мальчиков до школы.

Ответ: 2км

24)По данным, изображенным на рисунке справа, найти длину катета BC прямоугольного треугольника АВС.

Ответ: 12

25)Какое наибольшее число «тетраминошек» (как на рисунке) можно разместить внутри квадрата 6×6 без наложений? Фигурки можно как угодно поворачивать и переворачивать.

Ответ: 8

26)Назовем прямоугольник «симпатичным», если его длинная сторона меньше удвоенной короткой. (В частности, квадрат является симпатичным прямоугольником). Разрежьте квадрат площади 100 на четыре симпатичных прямоугольника с площадями 10, 20, 30 и 40.

27)В системе координат изобразили графики функций y x a , y ax b и y bx . Причем ось Оу, идущую, как обычно, «снизу вверх» перпендикулярно оси Ох, стерли. Восстановите ось Оу.

28)Винни-Пух заготовил мёд на зиму в нескольких полных горшочках по 5 литров каждый. Если бы он свои запасы мёда разлил в 4-литровые горшочки, то их потребовалось бы на четыре больше, правда, один горшочек оказался бы неполным. А если разлить весь мёд в горшочки по 7 литров, то их потребовалось бы на четыре меньше первоначального количества. Но один горшочек снова оказался бы неполным. Сколько горшочков мёда заготовил Винни-Пух?

29)Из вершин А, В и С треугольника АВС провели соответственно медиану АМ, биссектрису ВK и высоту СH. Оказалось, что середина отрезка ВK совпадает с серединой отрезка MH. Найдите углы треугольника АВС.

30)На каникулах для всех желающих провели турнир по шашкам. Каждый сыграл с каждым ровно одну партию. За победу в партии участник турнира получал 2 очка, за ничью – 1 очко, за проигрыш – 0 очков. Известно, что среди участников мальчиков было в десять раз больше, чем девочек, и они вместе набрали в 4,5 раза больше очков, чем девочки. Сколько очков набрала самая успешная девочка?

31)Девятиклассник Дима выписывает ряд последовательных трёхзначных чисел так, чтобы каждое число делилось нацело на свою последнюю цифру. Какое наибольшее количество чисел могло быть в этом ряду?

32)Имеется сталь двух сортов с содержанием никеля 55% и 12%. Сколько нужно взять металла каждого из сортов, чтобы получить 2021 т стали с содержанием 32% никеля?

33)Вася выписывает последовательность из 2021 натуральных чисел, начиная с некоторого числа, так, чтобы сумма любых трех подряд идущих чисел была равна 5. Какое наибольшее количество двоек у него может получиться?

34)На стороне ВС треугольника АВС выбрана точка F. Оказалось, что отрезок AF пересекает медиану BD в точке Е так, что АЕ = ВС. Докажите, что BF = FE.

35)Имеются две бочки с водой бесконечной вместимости и два ковшика объемами 2 и 2 2 литров. Можно ли, пользуясь этими ковшиками, перелить из одной бочки в другую ровно 1 литр?

36)От 2 кусков сплавов с разным содержанием свинца массой 6 кг и 12 кг отрезали по куску равной массы. Каждый из отрезанных кусков сплавили с остатком другого сплава, после чего процентное содержание свинца в обоих сплавах стало одинаковым. Каковы массы отрезанных кусков?

37)Художник Петров красит плоскость в два цвета произвольным образом, а геометр Васильев утверждает, что сможет построить треугольник с вершинами одного цвета, величины углов которого относятся как 4:2:1. Прав ли он?

Источник