Полный сборник решений задач по математике для поступающих в вузы. Группа А

Полный сборник задач по математике с решениями под редакцией М.И. Сканави по всем группам сложности. Условия и нумерация всех задач полностью соответствуют изданию «Сборник задач по математике для поступающих в вузы» под редакцией М.И. Сканави, 6-е Издание (М.: Оникс, Мир и Образование). Пособия помогут при подготовке к выпускным экзаменам в средней школе, сдаче ЕГЭ и вступительным экзаменам в вуз. Книги адресованы школьникам старших классов, абитуриентам, репетиторам и преподавателям.

Полный сборник решений задач по математике для поступающих в вузы. Группа А

Полный сборник решений задач по математике

Быстрое вычисление различных мер для выпуклых многоугольников
Представляет интерес вопрос о том, как можно вычислить для данного выпуклого п—угольника такие его характеристики (измерения, меры) как введенные в предыдущих разделах величины p,s,r, h, R. Для аккуратной постановки подобных задач можно использовать две близких друг к другу, но различных формализации. Одна из них состоит в построении по данному п—угольнику (а для некоторых задач — по данным п точкам) отрезка, длина которого равна данному измерению п— угольника. Вторая состоит просто в вычислении этого измерения. В первом формализации в качестве меры сложности построения (циркулем и линейкой естественно) можно взять просто число линий (прямых и окружностей), проведенных в этом построении. Во второй формализации в качестве меры сложности естественно взять число арифметических операций, выполняемых в ходе вычисления.
В обоих случаях возникают некоторые тонкости, которые могут играть роль в дальнейшем. Например, имеется определенное различие между не ветвящимися вычислениями и вычислениями с условными переходами. В первом случае выбор очередной операции не зависит от результатов предыдущих операций. Во втором случае зависит. Например, во втором случае моделью вычислений служит так называемое алгебраическое решающее дерево. В нем на каждом шаге выполняется одна из алгебраических операций (так называемых команд, занумерованный список которых заранее составлен и образует ветвящуюся программу, которая и называется в данном случае алгебраическим решающим деревом), если полученный результат не равен нулю, то выполняется следующая по списку команда, а если результат равен нулю, то делается так называемый условный переход к другой (не обязательно следующей) команде (номер которой заранее известен).
Обычно алгебраические решающие деревья используют для решения задач распознавания (принадлежности данного объекта к данному классу или множеству), в этом случае в списке команд есть команда «Останов и выдача ответа ДА » и команда «Останов и выдача ответа НЕТ », но можно рассматривать программы (фактически это какие-то диаграммы или графы), в которых команда «Останов» только одна, а результатом работы является некоторое число, вычисленное в ходе работы программы (для хранения чисел в таких программах предусматриваются ячейки или регистры памяти, каждый из которых хранит определенное число, и среди них специально выделяют выходные регистры, в которых и будут записаны результаты работы программы; специально выделяют также входные регистры, в которых перед началом работы программы заносятся исходные данные, например координаты заданных точек). От реальных компьютерных программ такие программы отличаются тем, что работают с произвольными действительными числами (а не конечным набором специального вида рациональных чисел, как реальные компьютеры), все операции выполняются абсолютно точно, и программа может работать сколь угодно долго. Время ее работы оценивается как число всех выполненных операций (а не число команд в программе), и называется временной сложностью данной программы (мы пренебрегаем временем на выполнение команд пересылки из одного регистра в другой, которые встречаются в реальных программах).
Подобные же уточнения можно внести и в первую формализацию, хотя в ней имеются свои тонкости, которые впрочем, далее не будут играть существенную роль, более1 того, все рассматриваемые далее построения фактически не будут содержать никаких ветвлений. Не ветвящиеся геометрические построения по-существу эквивалентны не ветвящимся программам, в которых кроме арифметических операций используется еще извлечение квадратного корня (рассматриваются только такие программы, в которых операции деления и извлечения корня всегда выполнимы, не зависимо от входных данных). Эквивалентность понимается в том смысле, что меры сложности вычислений для любой данной задачи в обоих типах программ по порядку одинаковы. Здесь и далее функции (последовательности) Li(n) называются равными по порядку, если 0 < с < L/Lx < С, где константы с, не зависят от п. Будем также использовать обозначение 1*2 = O(Li), если < L2/L1 < С.
295. Докажите эквивалентность не ветвящихся геометрических построений и не ветвящихся программ в базисе {+, —, х,/, у/} в указанном выше смысле.
Указание. Примените алгебраический метод решения задач на построение.
Далее будем использовать программы без операции извлечения корня, но с ветвлениями при выполнении условий типа / > 0, / > 0, / = 0. При наличии квадратного корня сравнения вида / > 0, / > 0 фактически можно заменить на сравнения вида / = 0, так как //у/р = 1 при / > 0.
296. Укажите, как проверить со сложностью О(п), является ли данный п—угольник описанным. Если является, то центр вписанного круга и его радиус можно построить со сложностью 0(1).
Указание. Сначала проверить, является ли он выпуклым. Потом применить задачу 248.
297. Укажите, как проверить со сложностью 0(п), является ли данный п—угольник вписанным. Если является, то центр описанного круга и его радиус можно построить со сложностью 0(1).
298. Укажите, как проверить со сложностью 0(п), имеет ли данный п—угольник точку Люилье. Если имеет, то ее можно построить со сложностью 0(1).
110
Глава 2. Неравенства для выпуклых фигур и тел
299. Точку, в которой достигается минимум суммы квадратов расстояний до сторон п—угольника, можно построить со сложностью 0(п).
Указание. Примените задачу 252.

[свернуть]

Похожие страницы

Предложения интернет-магазинов