Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 157
Текст из файла (страница 157)
а) ь (~ ~ ~Я (у е ~~е Раэдел 4.4. 1. а)7; 3. 1 2 3 — 1 — 2 — 3 а(и) = -и 5. 1 2 3 ( ) ( -10 -9 -8 а(и) = и — 11 О 1 О О О 1 О 1 1 О О 1 О О О О О О О 1 О О О О 1 О 1 1 О О 1 1 1 О О 1 1 О О О О О О 1 О О О О О 1 в) (7; б) С~.ь 0ф О)О О О О О О О О О)О О О 1 О О О)О О О О О О О О О1ОО 616 О Ответы к упражнениям 879 Раздел 5.7. 1.
Процедура Транспонироваиие матрицы (А, гп, и): Цикл посот1дот: Цикл по У от 1 до и: Тсн = Аб; Конец цикла; Конец цикла; Конец процедуры 3 а) 4 1 -4 5' ') [ -14 -12 ~ Ц-И 5 — 15 — 30 бб б) 29 23 -17 23 51 5 -17 5 11 в) 11 -16 -15 с 3 11 6 -8 -16 0 5 — 15 -30 в) г)~ 2.0 д) е) 7. Процедура Наименьшее целое число(аз, аз, аз,..., а ) (находнт наименьшее значение аь): Положить /с = 1; Цикл по б от 2 до гм Если а, ( аь, то положить /с = с; Конец цикла', Конец процедуры.
9. Процедура Проверка симметричности матрицы (А, п): Положить Т = 1, Цикл по с от 1 до и: Цикл по У от б до и. Если АО ~ А,» то положить Т = 0; Конец цикла; Конец цикла; Конец процедуры. Раздел 4.5. 1. (2,4). 3. 9. 5. Согласно теореме 4.51 множество положительных рациональных чисел счетно бесконечное. Поскольку существует взаимно однозначное соответствие между положительными рациональными числами и отрицательными рациональными числами, то множество отрицательных рациональных чисел счетно. Поэтому по теореме 4.52 их объединение счетно.
Поскольку множество (О) счетно, то его объединение с ненулевыми рациональными числами счетно. Поэтому множество рациональных чисел счетно. 7. Используя индукцию, покажем сначала, что если А счетно, то Ах Ах Ах хА, декартово произведение и копий множества А, счетно. Существует взаимно однозначное соответствие между многочленами пятой степени с целыми коэффициентами и Я х л х Я х Я х а х Я, где аззз+абх +азз +азх +оба+по соответствует (аз,а4,аз,аз,а„ао). следовательно, 4 3 2 множество многочленов пятой степени с целыми коэффициентами счетно.
880 Ответы к упражнениям Раздел Б.2. 1. а) У(1) = б) 7"(1) = в) 7'(1) = г) 7'(1) = д) 7'(1) = 3. а) 7'(2) = б) 7'(2) = в) з'(2) = г) 7'(2) = д) 7'(2) = 9 з'(2) = 27 з'(3) = 81 з(4) = 243; 5 7'(2) = 16 7'(3) = 41 з (4) = 94; 4 У(2) = 16 У(3) = 256 У(4) = 65536; 1 У(2) = 4 У(3) = 36 У(4) = 576; 2 Д2) = 4 У(3) = 16 У(4) = 65536. 5 г(3) = 7 з'(4) = 9 з'(5) = 11; 1 У(3) = 0 У(4) = -1 У(5) = 1' 7 /(3) = 56 7'(4) = 3145 1(5) = 9890994; 2 з(3) = 0 г"(4) = -48 г'(5) = -5760; — 1 У(3) = — 1 У(4) = 1 У(5) = -1.
1 в) 7'(п) = —, 5. а) 7(п) = 2"; б) 1(п) = п + 1; г) з'(и) = 1 + 2п; д) 7'(п) = 5". 7. ао = 7 — 2е+' = 5. Требуется показать, что 7 — 2ь ы = 2(7 — 2") — 7. Подставляя в рекурсивную функцию, имеем 2(7 — 2 ) — 7 = 7 — 2 2" = 7 — 2"~~. 11. Процедура Среднее арифметическое (аз, аз, аз, °, а„): Положить Я = 0; Цикл по 1 от 1 до и: Заменить Я иа Я + а,; Конец цикла; Я Положить Л = —; и Конец процедуры. 13. Следующая процедура вычитает Ь из а, где Ь имеет размерность гп, а имеет размерность п, ти < п и Ь < а. Предположим, что Ь = Ь,ЬзЬз .. Ь„и а = а1азаз.
а„, где Ь, = 0 для 1 < и — т. Кроме того, предположим, что у нас имеется процедура Сложение (а, Ь), построенная в предыдущей задаче, которая складывает числа а и Ь. Пусть ЬОО = ЬгЬзЬз . Ью Процедура Вычитание (а,Ь,пз,п); Цикл по з от 1 до и: Условие: если Ь„гег < а оьи то положить с;+з = а„,ег — Ь„;+~', Условие: если Ь вЂ”,+1 ) а,+и то положить с;+1 = 10+ а -*+1 — Ь вЂ” еы заменить ЬГ" ~ на Сложение (Ьг" *1, 1); Конец цикла; Конец процедуры.
15. Следующая процедура делит а на Ь, определяя частное 9 и остаток г. Процедура Деление (а,Ь): Если Ь > а, положить 9 = 0 и т = а; Положиты = 1; Условный цикл: до тех пор, пока г > Ь, положить т = а — (з . Ь); положить 9 = К положиты = з -'г 1; Конец условного цикла; Конец процедуры. Ответы к упражнениям 881 9. ао = — 1 — 2 + = -3. ас = — 1 — 2 т = — 5. Подставляя в рекурсивную функцию, имеем о.н тес -1 — 2~+' = 6(-1 — 2 ) — 8(-1 — 2ь ') — 3. Но 6( — 1 — 2 ) — 8( — 1 — 2 ') — 3 = — 1-6 2 +8.2 ' = — 1 — 3 2 ~'+2 2 +' = — 1-2 +'.
И. ат = 1 + 1 Ч- 1 = 3. ПодставлЯЯ в РекУРсивнУю фУнкцию, имеем ((с — 1) + !с — 1 + 1 + 2/с = !с — 2!с + 1 + Зк = !с + !с Ч- 1. 13. ао = — 2( — 1) +2 3 = О, а, = — 2(-1)'+2.3' = 8. Подставляя в рекурсивную функцию, имеем 2(-2(- 1) ' + 2 3 ') + 3(-2(-1) з + 2 3 з) = = — 4(-Ц"-' — 6( — П"-' 4.з"-'+6.з"-' = = 4(-1) — 6(-1) + 4 Зь ~ + 2 Зе ' = -2(-1) + 2 Зь. 15. ао = 3( — 2) Ч-2 3 — 3 2 = 2, ат = 3( — 2) + 2 3 — 3 2' = — 6. Подставляя в рекурсивную функцию, имеем 3(-2) + 2 3" — 3 2" = 3(-2)ь ' + 2 3" ' — 3. 2 '+ +6(3(-2)" з+2 3 — 3 2 )+3 2 = (3 — 9)(-2) ' + (2 + 4)3 ' + (-3 — 9)2 + 3 2 =3(-2) 4-2.3 — 6 2 ч-з 2 =3(-2) ч-2 3 — 3 2 .
17. = 5.8 х 16ю лет. Раздел 6.3. 1 2в 1 255 3. а) (а) 5 (б) 4; б) (а) 14 (б) 8; в) (а) 18 (б) 9. 5. (5), (в), (г). 7. Для и = 1 имеем 1! = 1 = 1', поэтому утверждение истинно, Предположим, что утверждение истинно для и = )с, т.е. !с! < !с" < ()с Ч- 1)" поскольку разложение (к Ч- 1)" включает к" как один из множителей. Умножая обе части неравенства !с! < (!с+ 1)" на (к + 1), получаем (!с + 1)! < (!с+ 1)"+'. 9.
Если Дп) = 0(д(и)), то существуют !ситпз такие, что 1(п) < !с,д(п) для п > ти Если д(п) = 0(!с(п)), то сусцествуют )сз,тз такие, что д(п) < )сз)с(п) для п > тиз. Полагая М = таах(пс„,тз), получаем 7(п) < lссд(п) < к,)сз!с(п) для и > М, поэтому Дп) = О(!с(п)). 11. Пусть Р(тп) является утверждением "Если т и ти — положительные целые числа, т < ти и п > 1, то и" < и ".
Утверждение несомненно истинно, если тп = 1. Предположим, что Р(к) истинно, так что если т < !с, то п" < и". Нужно доказать, что Р(к) истинно, так что если т < !с -!- 1, то и" < тспт'. Поскольку 1 < и, то п" 1 < п" п. Следовательно, и" < и"+'. Предположим, что т < й+1. Если т < к+1, то т < )с, поэтому и" < и" < и"+'. Если т = !с+ 1, то и' < пь+'. Таким образом, Р(к+ 1) истинно. количество сравнений всегда одинаково); количество сравнений всегда одинаково); и — !ойа 2+ А) + Рп = п — 1 + А) + Рп = Рп(!ойа п + А).
(с)з !Ва, е с ((2) 2 ) 2Р ыкз ' 2Р А+ + п 2 — с и 2 — с Я„и' зт ' 2Р Следовательно, —" = А+— п п 2 — с 882 Ответы к упражнениям Раздел 5.4. 1. О, 1, 2, 3, 4, 5, 7, 8, 9, 11. 3. а,б,с,Н,У,1,т,п,р,г,з,г,и,з,у,з. 5. а) 9,8,7,6,5,4,3,2,1 (для и объектов б) 9,8,7,6,5,4,3,2, 1 (для п объектов в) 1,2,3,4,5,6,7,8,9; г) 5, 3, 1, 2, 4, 3, 7; д) 1, 2, 3, 4, 5, 6, 7, 8, 9. 7.
2Р( — )(!ойа( — ) + А) + Рп = Рп(!ойз 2 2 = Рп(!об 9. — = +Р= Гвз сыа -г 2 2.2 (2) ((2) (2) 2 ) ((-;) '. (2) 2 ) '' ° + ' 3 гв'+ с рекурсивная формула, деленная пап = 2 повторное применение рекурсивной формулы повторное применение рекурсивной формулы повторное применение рекурсивной формулы гп !О82 п' поскольку и = 2 сумма геометрической прогрессии поскольку с *а' " = и *а" (возьмите !о8 от обеих частей) подставьте значение Я1 2Р ' аз' ьзтк 2Р А+ —. 2 — с и п 2 — с и !в'„=п'зт'А+ — и !оз 2 — с Ошаеты к упражнениям 883 б) (а + Ь 2) х (с + д 2) г) (а + Ь) 2 + (с + д); 6) (а 2-Ь <Г2) + (с"2+еГ2) г) (а "2+ Ь 2+ с"2) "3; г) 59; д) 53. г) 2ВЕ; д) 147Е.
г) 16893; д) 53731 в) 10111010.001; в) 4.5625 б) 3858.6796875; г) 12971.75415039 б) 111110010.101000111100; г) 1010000100101110.000100011100 Раздел 5.7. 1. а) 10001010; в) 11001001; 6) 01001011; г) 00010101. Раздел Б.Б. 1. а) а2" Ь2" +; 6) аЗ" За2" х -Ь7+; в) а2 Ь+ сд2" +; г) а2" ЬЗ" + 4; д) а2"Ьс + х. 3. а) (а + Ь) + (с — д), в) 3 х а х Ь + 4 х с х д 2; д) (а" 2+ Ь) х (с+ сГ2). 5. а) +" а2 Ь2; 6) ++ "аЗ х 3 "а27; в) х + "а2Ь+ с" д2; г) "-Ь "а2 "Ь34; д) х "а2 + Ьс.
7. а) (а + Ь) + (с — д) в) ЗаЬ+ 4сд+ 5ад; д) (а" 2+ Ь)(с+ сГ2). 9. 1. Добавлять скобки в выражение, пока оно не станет полноскобочным. 2. Начиная с самых внутренних скобок, удалить пару скобок и поместить находящийся внутри скобок оператор на место соответствовавшей ему левой скобки. При наличии более чем одной самой внутренней пары скобок начинать с правой пары. 3. Перемещаясь к следующей паре скобок, снова удалить их и поместить оператор, находившийся внутри скобок, на место соответствовавшей ему левой скобки. 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
