Учебное пособие Москва Издательство мцнмо 2007 удк 512. 1517. 1511. 1 Ббк 22. 14122. 161 П70 Прасолов В. В
 Скачать 3.28 Mb.
|
|
33.2. Если 0 < a < 1, то 0 < a 2 < a < 1. По условию 1 > a 2 > 0,9 . . . 9 | {z Поэтому 1 > a > 0,9 . . . 9 | {z предполагается, что число a положительно. Ответ Пусть a = “ 1 − 1 10 ”“ 1 − 1 10 2 ” . . . “ 1 − 1 10 и b = “ 1 − 1 10 6 ” . . . . . . “ 1 − 1 10 99 ” . Непосредственные вычисления показывают, что + 1 10 6 < a < 0,89001 + 2 10 Ясно, что b < 1 − 1 10 6 . Кроме того, если 0 < x, y < 1, то. Поэтому b>1− 1 10 6 − 1 10 7 −. . .− 1 10 99 > 1− 2 10 6 Решения задач 465 Следовательно, ab < 0,890012 · 0,999999 < 0,890012, ab > 0,890011 · 0,999998 > 0,890009. 33.4. Мы воспользуемся тождеством arctg 1 5 − arctg 1 задача 11.11) и неравенствами для арктангенса, доказанными в задаче 29.46. Из этих неравенств следует, что p 4 > 4 “ 1 5 − 1 3 · 5 3 ” − 1 239 > 0,78514923, p 4 < 4 “ 1 5 − 1 3 · 5 3 + 1 5 · 5 5 ” − 1 239 + 1 3 · 239 Поэтому 3,1405 < p < 3,1416 и 9,862 < p 2 < 9,8698. 33.5. Пусть двоичная запись числа n имеет вид a 0 + a 1 · 2 + . . . . . . + a m · 2 m , где a m 6= 0. Тогда m 6 log 2 n < m + 1, поскольку < 2 m +1 . Числа a, a 2 , a 4 , . . . , можно вычислить, сделав умножений. Чтобы вычислить a n , нужно перемножить какой-то набор из этих чисел. Он не может включать более m + 1 чисел, поэтому достаточно m умножений. Всего получаем не более 6 2 log 2 n умножений. 33.6. Пусть b 1 = a n x 0 + a n −1 , b 2 = b 1 x 0 + a n −2 , . . . , b n = b n −1 x 0 + Тогда b n = P(x 0 ), поскольку (. . . ((a n x 0 + a n −1 )x 0 + a n −2 ) . . .)x 0 + a 0 33.7. Для вычисления разложения многочлена f с целыми коэффициентами на неприводимые множители Кронекер предложил следующий алгоритм (алгоритм Кронекера). Пусть deg f = и r = [n/2]. Если многочлен f(x) приводим, то у него есть делитель) степени не выше r. Чтобы найти этот делитель рассмотрим числа c j = f(j), j= 0, 1, . . . , r. Если c j = 0, то x−j — делитель многочлена f(x). Если же c j 6= 0, то g(j) — делитель числа Каждому набору d 0 , . . . , делителей чисел c 0 , . . . , соответствует ровно один многочлен g(x) степени не выше r, для которого d j , j = 0, 1, . . . , r. А именно k j − k ” Глава 33. Алгоритмы и вычисления Для каждого такого многочлена g(x) нужно проверить, будут ли его коэффициенты целыми числами и будет ли он делителем многочлена Сейчас известно много других, более эффективных, алгоритмов разложения многочлена на неприводимые множители. а) Будем при сравнении двух чисел выбирать наибольшее. Меньшее число будем вычёркивать из списка в дальнейших сравнениях оно участвовать не будет. Ясно, что после n − 1 сравнений в списке останется лишь одно число — наибольшее. б) Каждое сравнение отсеивает только одного претендента название наибольшего числа. Если сделано k сравнений, то остаются k претендентов название наибольшего числа. Поэтому если остался только один претендент, то k > n − 1. 33.9. Наименьшее число сравнений будет в случае, когда числа, a 2 , . . . , уже упорядочены по возрастанию. В этом случае перестановок чисел не будет вообще. Сравниваться будут числа и a 2 , и a 3 , . . . , и a n . Наибольшее число сравнений будет в случае, когда числа a 1 , a 2 , . . . , упорядочены по убыванию. В этом случае количество перестановок будет наибольшим. Количество сравнений чисел в этом случае равно + 2 + . . . + (n − 1) = n(n − 1) 2 33.10. Индукцией по m легко доказать, что для кучи из 2 m −1 + камней процесс останавливается после m шагов, поскольку после первого шага большая из куч содержит 2 m −2 + 1 камней. Ясно также, что для кучи из камней процесс тоже останавливается после m шагов. Таким образом, для кучи из n камней процесс останавливается после m шагов тогда и только тогда, когда 2 m −1 + 1 6 n 6 те. Логарифмируя эти неравенства, получаем требуемое. Согласно задаче 33.10 число m, которое определяется указанными неравенствами, это количество шагов, которые нужно сделать, чтобы завершилось деление последовательностей (имеются ввиду шаги, при которых делятся примерно пополам все последовательности, полученные на предыдущем шаге). Для слияния двух отсортированных последовательностей, состоящих из p и q чисел, требуется не более p + q − 1 сравнений пар чисел. Действительно, при каждом сравнении мы забираем одно число. Кроме того, сортировка завершается после того, как из одной последовательности забраны все числа. Но при этом в другой последовательности останется по крайней мере одно число Решения задач 467 После m делений примерно пополам мы имеем парчи- сел (некоторые пары состоят из одного числа. Для слияния этих пар нужно не более n − сравнений (для слияния пары, состоящей из одного числа, никаких сравнений не нужно, поэтому из общего количества всех чисел вычитается количество всех пар. Затем нужно слить последовательности для этого нужно не более n − сравнений и т. д. Всего получаем не более mn − 2 m −1 − 2 m −2 − . . . − 2 − 1 = mn − 2 m + 1 сравнений. а) Разобьём данные числа произвольным образом на пар. Сравнивая числа в каждой паре, выберем n наибольших чисел и n наименьших чисел в парах. Ясно, что наибольшее число нужно искать среди выбранных n наибольших чисел. Его можно найти, сделав n − 1 сравнений (задача 33.8). Аналогично можно найти наименьшее число (среди n выбранных наименьших чисел), сделав n − 1 сравнений. б) Пусть после k сравнений у насесть чисел, которые оказались меньше каких-то чисел и больше каких-то чисел, b k чисел, которые оказались меньше каких-то чисел, но пока не оказались больше каких-то чисел, чисел, которые оказались больше ка- ких-то чисел, но пока не оказались меньше каких-то чисел, и чисел, которые пока не сравнивались ни с какими числами. Первоначально и d 0 =2n. А когда после m сравнений найдены наибольшее число и наименьшее, b m =c m =1, a m =2n−2 и Рассмотрим величину f k =b k +c k + 3 2 d k . Ясно, что f 0 =3n и Будем предполагать, что если мы прямо или косвенно знаем, что > y, то числа x и y мы больше никогда друг с другом не сравниваем, потому что такое сравнение можно было бы просто пропустить. Достаточно доказать, что при сравнении любой пары чисел может случиться, что f k − f k +1 6 1. Действительно, складывая неравенства, получаем f 0 − те. Требуемое утверждение доказывается прямым перебором) Если сравниваются два числа из группы a k , то ничего не меняется f k +1 = f k 2) Пусть сравниваются число a из группы и число b из группы. Может случиться, что a<b. Тогда a k +1 = a k + 1 и b k +1 = поэтому f k − f k +1 = 1. 3) Аналогично может случиться, что a > c. Тогда a k +1 = a k + и c k +1 = c k − 1, поэтому f k − f k +1 = 1. 4) При сравнении чисел a и d одно из чисел или увеличивается на 1, а число уменьшается на 1, поэтому f k − f k +1 = 1/2. Глава 33. Алгоритмы и вычисления) При сравнении двух чисел из группы число увеличивается на 1, а уменьшается на 1, поэтому f k − f k +1 = 1. 6) Может случиться, что b < c. Тогда ничего не меняется) Может случиться, что b < d. Тогда увеличивается на а уменьшается на 1, поэтому f k − f k +1 = 1/2. 8) При сравнении двух чисел из группы число увеличивается на 1, а уменьшается на 1, поэтому f k − f k +1 = 1. 9) Может случиться, что c > d. Тогда увеличивается на а уменьшается на 1, поэтому f k − f k +1 = 1/2. 10) При сравнении двух чисел из группы оба числа и увеличиваются на 1, а уменьшается на 2, поэтому f k − f k +1 = 1. 33.13. а) Будем последовательно делить набор из n чисел примерно пополам, как это описано в задаче 33.10. Согласно решению этой задачи процесс останавливается после m шагов. Группы, полученные нам шаге, состоят из пар чисел и отдельных чисел. В каждой такой группе сравним числа и найдём среди них наибольшее (отдельные числа пока ни с чем не сравниваются. Затем аналогично найдём наибольшее число в каждой группе, полученной нам шаге, и т. д. В результате найдём наибольшее число. При этом будет сделано n − 1 сравнений. Действительно, при каждом сравнении отсеивается один кандидат название наибольшего числа, причём в результате будет отсеяно n − 1 число. Займёмся теперь поиском второго по величине числа. Ясно, что оно выбыло из дальнейшей борьбы в результате сравнения с наибольшим числом, поскольку у любого другого числа оно бы выиграло. Таким образом, второе по величине число нужно искать среди тех чисел, которые сравнивались непосредственно с самым большим числом. Таких чисел не более m. Выбрать из них наибольшее можно за m − 1 сравнений. б) Будем говорить, что число проигрывает сравнение, если оно оказывается меньше числа, с которым оно сравнивается. Пусть количество чисел, проигравших не менее i сравнений (косвенные проигрыши, когда из неравенств a < b и b < c делается вывод, что a < c, не учитывается количество всех проигрышей равно количеству всех сравнений. Тогда сумма всех чисел равна количеству всех сравнений, поскольку после каждого сравнения ровно одно из чисел увеличивается на 1. Действительно, пусть при очередном сравнении проигрывает число, которое уже проиграло сравнений. Тогда увеличивается на 1, а остальные числа не изменяются. Достаточно доказать, что при любом алгоритме сравнений может получиться так, что после того как удалось выявить наиболь- Решения задач 469 шее число и следующее за ним, будет выполняться неравенство+ k 2 > n + m − 2. Прежде всего заметим, что после того как алгоритм закончит работу, будет выполняться неравенство k 1 > n − поскольку все числа, кроме одного, должны были кому-то проиграть (если бы два числа никому не проиграли, то мы не знали бы, какое из них больше другого. Остаётся доказать, что при неудачных исходах может выполняться неравенство k 2 > m − На каждом шаге работы алгоритма будем называть лидером число, которое пока никому не проиграло. Покажем, что неравенство выполняется, если исходы сравнений следующие) при сравнении двух не лидеров результат произвольный) при сравнении лидера сне лидером всегда выигрывает лидер) при сравнении двух лидеров выигрывает тот, у кого было больше выигрышей (если выигрышей было поровну, то результат произвольный). Такие исходы сравнений возможны потому, что на лидера нет никаких ограничений сверху если его увеличить, то результат предыдущих сравнений не изменится. Введём теперь понятие подчинения лидеру. Первоначально все числа подчинены только самим себе. При сравнениях типа (1) и (подчинение лидерам не изменяется. При сравнении типа (3) проигравший и все его подчинённые переподчиняются новому лидеру. Покажем индукцией по k, что если лидер выиграл k сравнений, то ему подчинено (вместе с ним самим) не более чисел. При 0 лидеру подчинён только он сам. Пусть лидер, выигравший сравнений, выигрывает у кого-то в очередной раз. Тот, у кого он выиграл, по нашему соглашению о сравнениях типа (3) выиграл не более k сравнений. Поэтому как выигравшему, таки проигравшему подчинено не более чисел при объединении этих двух групп получается не более чисел, что и требовалось. Итак, наибольшее число выиграло по крайней мере m сравнений, поскольку ему в итоге будут подчинены все n чисел. Среди чисел, проигравших наибольшему числу, есть только одно число, которое больше никому не проиграло (иначе мы не будем знать второе по величине число. Следовательно, k 2 > m − 1. ГЛАВА ФУНКЦИОНАЛЬНЫЕ УРАВНЕНИЯ. Метод подстановки Метод подстановки позволяет решать довольно узкий класс функциональных уравнений. Он заключается в следующем. Пусть f (x) — функция, которая обладает таким свойством если) и f k +1 (x) = f ( f k (x)) при k > 1, то f n (x) = для некоторого n. Например, если f (x) = 1 − x, то f 2 (x) = Предположим, что функциональное уравнение содержит только функции f(x), f( f (x)), . . . , f( f n −1 (x)). Тогда вместо x можно подставить f 1 (x), f 2 (x), . . . , f n −1 (x) и получить систему уравнений, которую иногда удаётся решить. Найдите все функции f(x), для которых 2f(1 − x) + + 1 = xf(x). 34.2. Найдите все функции f(x), которые определены при x 6= 1 и удовлетворяют соотношению+ f 1 1 − x = x. 34.3. Найдите все функции f(x), которые определены для всех x 6= 0, ±1 и удовлетворяют соотношению+ 2f x − 1 x + 1 = 1. 34.2. Функциональные уравнения для произвольных функций. а) Предположим, что каждому рациональному числу сопоставлено действительное число f(x) так, что+ y) = f(x) + f(y) и f(xy) = f(x)f(y). Докажите, что либо x для всех x, либо f(x) = 0 для всех x. Условия задач 471 б) Решите туже самую задачу в случае, когда число сопоставляется не только рациональным числам, но и всем действительным числам. Найдите все функции f(x), которые определены для всех x и удовлетворяют соотношению+ yf(x) = (x + для всех x, y. 34.6. Найдите функцию f(x), которая определена для всех x, в некоторой точке отлична от нуля и для всех x, удовлетворяет уравнению f(x)f(y) = f(x − y). 34.7. Докажите, что не существует функции f(x), которая определена для всех x и удовлетворяет соотношению x 2 − 2. 34.3. Функциональные уравнения для непрерывных функций. Непрерывная функция f(x) определена для всех и удовлетворяет соотношению+ y) = f(x) + Докажите, что f(x) = Cx, где C = f(1). 34.9. Найдите все непрерывные функции, которые определены для всех x и удовлетворяют соотношению f(x) = = a x f(x/2), где a — фиксированное положительное число. Непрерывная функция f(x) определена для всех x, причём f(x 0 ) 6= 0 для некоторого x 0 . Докажите, что если выполнено соотношение+ y) = то f(x) = для некоторого a > 0. 34.11. Непрерывная функция f(x) определена для всех > 0 и удовлетворяет соотношению f(x) + а) Докажите, что если f(a) = 1 для некоторого a, то log a x. Глава 34. Функциональные уравнения б) Докажите, что если f(x 0 ) 6= 0 для некоторого x 0 , то 1 для некоторого a. 34.12. Найдите все непрерывные решения функционального уравнения+ y) = f(x) + f(y) + f(x)f(y). 34.13. Найдите все непрерывные решения функционального уравнения+ y)f(x − y) = Лобачевский. Функциональные уравнения для дифференцируемых функций. Найдите все дифференцируемые функции f, для которых f(x)f ′ (x) = 0 для всех x. 34.5. Функциональные уравнения для многочленов. Найдите все многочлены P(x), для которых справедливо тождество xP(x − 1) = (x − 26)P(x). 34.16. Многочлен P(x, y) обладает следующим свойством, y) = P(x + 1, y + 1) для всех x и y. Докажите, что, y) = n P k=0 a k (x − Согласно задаче 28.76 для многочлена f степени n + 1 выполняется равенство f(y) + (x − y)f ′ (y) + . . . + (x − y) n +1 f (n +1) (y) (n + При этом f (n +1) — константа, а значит y) n +1 f (n +1) (y) (n + 1)! = = (x − y) n “ −yf (n +1) (y) (n + 1)! − c ” + (x − y) n “ xf (n +1) (x) (n + 1)! + c ” Условия задач 473 Таким образом, у функционального уравнения y) k g k (y) + (x − есть решение следующего вида: (а) f — многочлен степени не выше n + б) g k (y) = f (k) (y)/k! при k = 0, 1, . . . , n − в) g n (y) = f (n) (y)/n! − yf (n +1) (y)/(n + 1)! − г) h(x) = xf (n +1) (x)/(n + 1)! + c. |