Пусть на двух пересекающихся прямых l₁ и l₂ выбраны точки M₁ и M₂, не совпадающие с точкой пересечения M этих прямых. Поставим в соответствие им окружность, проходящую через M₁, M₂ и M.
Если (l₁, M₁), (l₂, M₂), (l₃, M₃) — прямые с выбранными точками в общем положении, то согласно задаче 2.80, а) три окружности, соответствующие парам (l₁, M₁) и (l₂, M₂), (l₂, M₂) и (l₃, M₃), (l₃, M₃) и (l₁, M₁), пересекаются в одной точке, которую мы поставим в соответствие тройке прямых с точками.
а) Пусть l₁, l₂, l₃, l₄ — четыре прямые общего положения, на каждой из которых задано по точке, причем эти точки лежат на одной окружности. Докажите, что четыре точки, соответствующие тройкам, получаемым отбрасыванием одной из прямых, лежат на одной окружности.
б) Докажите, что каждому набору из n прямых общего положения с заданными на них точками, лежащими на одной окружности, можно поставить в соответствие точку (при нечетном n) или окружность (при четном n) так, что n окружностей (точек при четном n), соответствующих наборам из n - 1 прямых, проходят через эту точку (лежат на этой окружности при четном n).

   Решение

Решить предыдущую задачу, если про массивы известно лишь, что x[1]≤...≤x[k] и  y[1]≤...≤y[l] (возрастание заменено неубыванием).

   Решение

Страница: << 1 2 3 4 5 6 >> [Всего задач: 28]      

(В. Баур, Ф.Штрассен) Дана программа вычисления значения некоторого многочлена P(x₁,..., x_n), содержащая только команды присваивания. Их правые части — выражения, содержащие сложение, умножение, константы, переменные x₁,..., x_n и ранее встречавшиеся (в левой части) переменные. Доказать, что существует программа того же типа, вычисляющая все n производных P/x₁,...,P/x_n, причём общее число арифметических операций не более чем в C раз превосходит число арифметических операций в исходной программе. Константа C не зависит от n.

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

Решение

В массивах a: array[0..k] of integer и b: array[0..l] of integer хранятся коэффициенты двух многочленов степеней k и l. Поместить в массив c: array[0..m] of integer коэффициенты их произведения. (Числа k,l,m — натуральные, m = k + l; элемент массива с индексом i содержит коэффициент при степени i.)

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

Решение

Предложенный выше алгоритм перемножения многочленов требует порядка n² действий для перемножения двух многочленов степени n. Придумать более эффективный (для больших n) алгоритм, которому достаточно порядка n^{log 4/log 3} действий.

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

Решение

Даны два возрастающих массива x: array[1..k] of integer и y: array[1..l] of integer. Найти количество общих элементов в этих массивах, то есть количество тех целых t, для которых t = x[i] = y[j] для некоторых i и j. (Число действий порядка k + l.)

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

Решение

Решить предыдущую задачу, если про массивы известно лишь, что x[1]≤...≤x[k] и  y[1]≤...≤y[l] (возрастание заменено неубыванием).

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

Решение

Страница: << 1 2 3 4 5 6 >> [Всего задач: 28]