"离散数学及其应用（第8版）奇数题答案总结"

5星 · 超过95%的资源需积分: 0 86 浏览量更新于2024-01-09 44 收藏 6.34MB PDF 举报

离散数学及其应用是一门关于离散结构、数理逻辑和集合论等领域的数学课程。它广泛应用于计算机科学、电子工程、通信工程和数学等学科。本书《离散数学及其应用》是Kenneth H. Rosen所著的第8版教材。本书提供了大量的习题，包括奇数题和偶数题。本文主要总结了书中奇数题的答案，以帮助学生更好地学习和理解离散数学的概念和原理。第一章是对离散数学基础知识的介绍。在第1.1节中，我们回答了一些关于命题逻辑的问题。例如，我们证明了命题"A或非A"永远是真的，并证明了命题"非A且非非A"永远是假的。这些问题旨在帮助学生理解命题逻辑的基本概念。在第1.3节中，我们继续介绍了命题逻辑的推理法则。我们证明了一些常用的推理法则，如析取析取律、蕴含蕴含律和双条件双条件律。这些推理法则在离散数学和计算机科学中经常被使用，因此学生应该牢记它们。第一个习题是关于逻辑运算的性质。在这个习题中，我们需要判断一些命题的真假。有些命题可以通过直接判断真值来解答，而有些命题需要使用逻辑运算的特性来判断。例如，对于命题“Linda比Sanjay年长”，我们可以通过直接比较他们的年龄来判断真假。而对于命题“Mei比Isabella赚的钱多”，我们需要使用否定运算来判断。在第1.5节中，我们学习了集合论的基础知识。我们回答了一些关于集合交集、并集和差集的问题。例如，在习题5中，我们需要判断一些集合关系的真假。这些问题考察了学生对集合运算的理解和掌握程度。在本章的最后一节中，我们学习了关系和函数的基本概念。我们回答了一些关于关系和函数性质的问题。例如，在习题7中，我们需要判断一些关系和函数的存在性。这些问题帮助学生巩固了关系和函数的定义和性质。总的来说，本章的习题答案涵盖了离散数学中许多重要概念和原理。通过解答这些习题，学生可以更好地理解离散数学的核心思想和应用。希望这些答案对学生们的学习有所帮助，并激发他们对离散数学的兴趣和研究热情。

P1: 1

ANS Rosen-2311T MH03280-Rosen-v1.cls May 8, 2018 17:25

S-16 Answers to Odd-Numbered Exercises

67.

–2

–1

–1–2

231

–3

69. a)

–

2–4 2 4

–2

–3

–

–2

–3

–1

–

212

–1

–2

–3

–1

–6

–

12 –3–9 6 1239

–2

–3

–

–1

–2

–3

–4

–1

–

2–1 21

–2 –1 1 2

–2

–3

–1

–4

g) See part (a). 71. f

−1

(y) = (y − 1)

1∕3

73. a) f

A∩B

(x) =

1 ↔ x ∈ A ∩ B ↔ x ∈ A and x ∈ B ↔ f

(x) = 1andf

(x) =

1 ↔ f

(x)f

(x) = 1 b) f

A∪B

(x) = 1 ↔ x ∈ A ∪ B ↔ x ∈ A or

x ∈ B ↔ f

(x) = 1orf

(x) = 1 ↔ f

(x) + f

(x) − f

(x)f

(x) = 1

c) f

(x) = 1 ↔ x ∈ A ↔ x ∉ A ↔ f

(x) = 0 ↔ 1 − f

(x) = 1

d) f

A⊕B

(x) = 1 ↔ x ∈ A ⊕ B ↔ (x ∈ A and x ∉ B)

or (x ∉ A and x ∈ B) ↔ f

(x) + f

(x) − 2f

(x)f

(x) = 1

75. a) True; because xis already an integer, x = x.

b) False; x =

is a counterexample. c) True; if x or y is an

integer, then by property 4b in Table 1, the diﬀerence is 0. If

neither x nor y is an integer, then x = n + 𝜖 and y = m + 𝛿,

where n and m are integers and 𝜖 and 𝛿 are positive real num-

bers less than 1. Then m + n < x + y < m + n + 2, so

x + yis either m + n + 1orm + n + 2. Therefore, the given

expression is either (n + 1) + (m + 1) − (m + n + 1) = 1or

(n + 1) + (m + 1) − (m + n + 2) = 0, as desired. d)

False;

x =

and y = 3 is a counterexample. e) False; x =

a counterexample. 77. a) If x is a positive integer, then the

two sides are equal. So suppose that x = n

+ m + 𝜖,where

is the largest perfect square less than x, m is a nonnegative

integer, and 0 <𝜖≤ 1. Then both



x and



x=



+ m

are between n and n + 1, so both sides equal n. b) If x is

a positive integer, then the two sides are equal. So suppose

that x = n

− m − 𝜖,wheren

is the smallest perfect square

greater than x, m is a nonnegative integer, and 𝜖 is a real num-

ber with 0 <𝜖≤ 1. Then both



x and



x =



− m

are between n − 1andn. Therefore, both sides of the equa-

tion equal n. 79. a) Domain is Z; codomain is R; domain of

deﬁnition is the set of nonzero integers; the set of values for

which f is undeﬁned is {0}; not a total function. b) Domain is

Z; codomain is Z; domain of deﬁnition is Z;setofvaluesfor

which f is undeﬁned is ∅; total function. c) Domain is Z × Z;

codomain is Q; domain of deﬁnition is Z × (Z −{0}); set of

values for which f is undeﬁned is Z×{0}; not a total function.

d) Domain is Z × Z; codomain is Z; domain of deﬁnition is

Z×Z; set of values for which f is undeﬁned is ∅; total function.

e) Domain is Z × Z; codomain is Z; domain of deﬁnitions is

{(m, n) ∣ m > n}; set of values for which f is undeﬁned is

{

(m, n) ∣ m ≤ n}; not a total function. 81. a) By deﬁni-

tion, to say that S has cardinality m is to say that S has exactly

m distinct elements. Therefore we can assign the ﬁrst object

to 1, the second to 2, and so on. This provides the one-to-one

correspondence. b) By part (a), there is a bijection f from S to

{1, 2, … ,m} and a bijection g from T to {1, 2, … ,m}.Then

the composition g

−1

◦f is the desired bijection from S to T.

Section 2.4

1. a) 3 b) −1 c) 787 d) 2639 3. a) a

= 2,a

= 3,

= 5,a

= 9 b) a

= 1,a

= 4,a

= 27,a

= 256

c) a

= 0, a

= 1, a

= 1 d) a

= 0, a

= 1,

= 2,a

= 3 5. a) 2, 5, 8, 11, 14, 17, 20, 23, 26, 29

b) 1, 1, 1, 2, 2, 2, 3, 3, 3, 4 c) 1, 1, 3, 3, 5, 5, 7, 7, 9, 9

d) −1, −2, −2, 8, 88, 656, 4912, 40064, 362368,

3627776 e) 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536

f) 2, 4, 6, 10, 16

, 26, 42, 68, 110, 178 g) 1, 2, 2, 3, 3, 3, 3, 4,

4, 4 h) 3, 3, 5, 4, 4, 3, 5, 5, 4, 3 7. Each term could be

twice the previous term; the nth term could be obtained from

the previous term by adding n − 1; the terms could be the

positive integers that are not multiples of 3; there are in-

ﬁnitely many other possibilities. 9. a) 2, 12, 72, 432, 2592

b) 2, 4, 16, 256, 65, 536 c) 1, 2, 5, 11, 26 d) 1, 1, 6,

27, 204

e) 1, 2, 0, 1, 3 11. a) 6, 17, 49, 143, 421 b) 49 = 5⋅17−6⋅6,

143 = 5 ⋅ 49 − 6 ⋅ 17, 421 = 5 ⋅ 143 − 6 ⋅ 49 c) 5a

n−1

−

n−2

=5(2

n−1

+ 5⋅3

n−1

) − 6(2

n−2

+ 5⋅3

n−2

) = 2

n−2

(10−6) +

n−2

(75 − 30) = 2

n−2

⋅ 4 + 3

n−2

⋅ 9 ⋅ 5 = 2

+ 3

⋅ 5 = a

13. a) Yes b) No c) No d) Yes e) Yes f) Yes g) No

h) No 15. a) a

n−1

+ 2a

n−2

+ 2n − 9 =−(n − 1) + 2 +

2[−(n − 2) + 2] + 2n − 9 =−n +2 = a

b) a

n−1

n−2

+ 2n − 9 = 5(−1)

n−1

− (n − 1) + 2 + 2[5(−1)

n−2

−

(n − 2) + 2] + 2n − 9 = 5(−1)

n − 2

(−1 + 2) − n + 2 = a

c) a

n−1

+ 2a

n−2

+ 2n − 9 = 3(−1)

n−1

− (n − 1) + 2 +

2[3(−1)

n−2

+ 2

n−2

− (n − 2) + 2] + 2n − 9 = 3(−1)

n−2

(−1 + 2) + 2

n−2

(2 + 2) − n + 2 = a

d) a

n−1

n−2

+ 2n − 9 = 7 ⋅ 2

n−1

− (n − 1) + 2 + 2[7 ⋅ 2

n−2

−

(n − 2) + 2] + 2n − 9 = 2

n−2

(7 ⋅ 2 + 2 ⋅ 7) − n + 2 = a

17. a) a

= 2 ⋅ 3

b) a

= 2n + 3 c) a

= 1 + n(n + 1)∕2

d) a

= n

+ 4n + 4 e) a

= 1 f) a

= (3

n+1

− 1)∕2

g) a

= 5n! h) a

= 2

n! 19. a) a

= 3a

n−1

b) 5,904,900

21. a) a

= n + a

n−1

, a

= 0 b) a

= 78 c) a

= n(n + 1)∕2

P1: 1

ANS Rosen-2311T MH03280-Rosen-v1.cls May 8, 2018 17:25

Answers to Odd-Numbered Exercises S-17

23. B(k) = [1 + (0.07∕12)]B(k − 1) − 100, with B(0) = 5000

25. a) One 1 and one 0, followed by two 1s and two 0s, fol-

lowed by three 1s and three 0s, and so on; 1, 1, 1 b) The

positive integers are listed in increasing order with each

even positive integer listed twice; 9, 10, 10. c) The terms

in odd-numbered locations are the successive powers of 2;

the terms in even-numbered locations are all 0; 32, 0, 64.

d) a

= 3 ⋅ 2

n−1

; 384, 768, 1536 e) a

= 15 − 7(n − 1) =

22 − 7n; −34, −41, −48 f) a

= (n

+ n + 4)∕2; 57, 68,

80 g) a

= 2n

; 1024, 1458, 2000 h) a

= n!+1; 362881,

3628801, 39916801 27. Among the integers 1, 2, … ,a

where a

is the nth positive integer not a perfect square, the

nonsquares are a

, … ,a

and the squares are 1

, 2

, … ,k

where k is the integer with k

< n+k < (k+1)

. Consequently,

= n + k,wherek

< a

< (k + 1)

. To ﬁnd k,ﬁrstnote

that k

< n + k < (k + 1)

,sok

+ 1 ≤ n + k ≤ (k + 1)

− 1.

Hence, (k −

)

= k

− k + 1 ≤ n ≤ k

+ k = (k +

)

−

It follows that k −



n < k +

,sok ={



n} and

= n + k = n +{



n}. 29. a) 20 b) 11 c) 30 d) 511

31. a) 1533 b) 510 c) 4923 d) 9842 33. a) 21 b) 78

c) 18 d) 18 35.



j=1

− a

j−1

) = a

− a

37. a) n

b) n(n + 1)∕2 39. 15150 41. 34320 43.

n(n+1)(2n+1)

n(n+1)

+ (n + 1)(m − (n + 1)

+ 1), where n = 



m− 1

45. a) 0 b) 1680 c) 1 d) 1024 47. 34

Section 2.5

1. a) Countably inﬁnite, −1, −2, −3, −4, … b) Countably

inﬁnite, 0, 2, −2, 4, −4, … c) Countably inﬁnite,

99, 98, 97, … d) Uncountable e) Finite f) Countably inﬁ-

nite, 0, 7, −7, 14, −14, … 3. a) Countable: match n with

the string of n 1s. b) Countable. To ﬁnd a correspondence,

follow the path in Example 4, but omit fractions in the top

three rows (as well as continuing to omit fractions not in low-

est terms). c) Uncountable d) Uncountable 5. Suppose m

new guests arrive at the fully occupied hotel. Move the guest

in Room n to Room m + n for n = 1, 2, 3, …; then the new

guests can occupy rooms 1 to m. 7. For n = 1, 2, 3, …, put

the guest currently in Room 2n into Room n, and the guest

currently in Room 2n − 1 into Room n of the new build-

ing. 9. Move the guest currently in Room i to Room 2i + 1

for i = 1, 2, 3, …. Put the jth guest from the kth bus into

Room 2

(2j + 1). 11. a) A = [1, 2] (closed interval of

real numbers from 1 to 2), B = [3, 4] b) A = [1, 2] ∪ Z

B = [3, 4] ∪ Z

c) A = [1, 3], B = [2, 4] 13. Suppose

that A is countable. Then either A has cardinality n for some

nonnegative integer n, in which case there is a one-to-one

function from A to a subset of Z

(the range is the ﬁrst n pos-

itive integers), or there exists a one-to-one correspondence f

from A to Z

; in either case we have satisﬁed Deﬁnition 2.

Conversely, suppose that A ≤ Z

. By deﬁnition, this

means that there is a one-to-one function from A to Z

,soA

has the same cardinality as a subset of Z

(namely the range

of that function). By Exercise 16 we conclude that A is count-

able. 15. Assume that B is countable. Then the elements of

B can be listed as b

, . … Because A is a subset of B,

taking the subsequence of {b

} that contains the terms that

are in A gives a listing of the elements of A. Because A is

uncountable, this is impossible. 17. Assume that A − B is

countable. Then, because A = (A − B) ∪ (A ∩ B), the elements

of A can be listed in a sequence by alternating elements of

A − B and elements of A ∩ B. This contradicts the uncount-

ability of A. 19. We are given bijections f from A to B and g

from C to D. Then the function from A × C to B × D that sends

(a, c)to(f (a),g(c)) is a bijection. 21. By the deﬁnition of

A≤ B, there is a one-to-one function f : A → B. Similarly,

there is a one-to-one function g : B → C.ByExercise33

in Section 2.3, the composition

g◦f : A → C is one-to-one.

Therefore, by deﬁnition A ≤ C. 23. Using the Axiom

of Choice from set theory, choose distinct elements a

, a

, ...of A one at a time (this is possible because A is inﬁ-

nite). The resulting set {a

, …} is the desired inﬁnite

subset of A. 25. The set of ﬁnite strings of characters over

a ﬁnite alphabet is countably inﬁnite, because we can list

these strings in alphabetical order by length. Therefore, the

inﬁnite set S can be identiﬁed with an inﬁnite subset of this

countable set, which by Exercise 16 is also countably inﬁnite.

27. Suppose that A

, … are countable sets. Because

is countable, we can list its elements in a sequence as

, … . The elements of the set



i=1

can be listed

by listing all terms a

with i + j = 2, then all terms a

with i + j = 3, then all terms a

with i + j = 4, and so

on. 29. There are a ﬁnite number of bit strings of length m,

namely, 2

. The set of all bit strings is the union of the sets

of bit strings of length m for m = 0, 1, 2, … . Because the

union of a countable number of countable sets is countable

(see Exercise 27), there are a countable number of bit strings.

31. It is clear from the formula that the range of values the

function takes on for a ﬁxed value of m + n,saym + n = x,is

(x − 2)(x − 1)∕2 + 1 through (x − 2)(x − 1)∕2 + (x − 1), be-

cause m can assume the values 1, 2, 3, … , (x − 1) under these

conditions, and the ﬁrst term in the formula is a ﬁxed positive

integer when m + n is ﬁxed. To show that this function is

one-to-one and onto, we merely need to show that the range

of values for x + 1 picks up precisely where the range of

values for x left oﬀ, i.e., that f (x − 1, 1) + 1 = f (1,x). We have

f (x − 1

, 1) + 1 =

(x−2)(x − 1)

+ (x − 1) + 1 =

− x + 2

(x − 1)x

+ 1 = f (1,x). 33. By the Schr

oder-Bernstein theo-

rem, it suﬃces to ﬁnd one-to-one functions f :(0, 1) → [0, 1]

and g :[0, 1] → (0, 1). Let f (x) = x and g(x) = (x + 1)∕3.

35. Each element A of the power set of the set of positive

integers (i.e., A ⊆ Z

) can be represented uniquely by the

bit string a

…,wherea

= 1ifi ∈ A and a

= 0

if i ∉ A. Assume there were a one-to-one correspondence

f : Z

→ (Z

). Form a new bit string s = s

… by set-

ting s

to be 1 minus the ith bit of f (i). Then because s diﬀers

in the i bit from f (i), s is not in the range of f , a contradiction.

37. For any ﬁnite alphabet there are a ﬁnite number of strings

of length n, whenever n is a positive integer. It follows by the

result of Exercise 27 that there are only a countable number

of strings from any given ﬁnite alphabet. Because the set of

P1: 1

ANS Rosen-2311T MH03280-Rosen-v1.cls May 8, 2018 17:25

S-18 Answers to Odd-Numbered Exercises

all computer programs in a particular language is a subset of

the set of all strings of a ﬁnite alphabet, which is a count-

able set by the result from Exercise 16, it is itself a countable

set. 39. Exercise 37 shows that there are only a countable

number of computer programs. Consequently, there are only

a countable number of computable functions. Because, as

Exercise 38 shows, there are an uncountable number of func-

tions, not all functions are computable. 41. a) Note that if

x is in the chain generated by y, then by the way the chains

are generated, y is in the chain generated by x,sothesetwo

chains are the same. Thus, if x is in both the chain generated

by y

and the chain generated by y

, then the chain generated

by y

and the chain generated by y

are both the same as the

chain generated by x and are therefore the same chain. b) A

moment’s reﬂection will show that by the way the chains

are constructed, this is true. c) Again, this is clear from the

construction. d) Because the chains are disjoint and every

element of A appears in exactly one chain and every element

of B appears in exactly one chain, the function h cannot map

two diﬀerent elements of A tothesameelementofB. e) If an

element b of B appears in a chain of types 1, 2, or 3, then it is

preceded by an element of A, which maps to it under h.Ifb

appears in a chain of type 4, then it is followed by an element

of A, which maps to it under h.

Section 2.6

1. a) 3 × 4 b)















2046



d) 1







121

101

143

367







3. a)



111

218









2 −2 −3

10 2

9 −44













−415−41

−310 2 −3

02−86

1 −818−13









9∕5 −6∕5

−1∕54∕5



7. 0 + A =



0 + a





+ 0



= 0 + A 9. A + (B + C) =



+ (b

+ c

)





+ b

) + c



= (A + B) + C 11. The

number of rows of A equals the number of columns of B,and

the number of columns of A equals the number of rows of B.

13. A(BC) =





































= (AB)C

15. A



1 n



17. a) Let A = [a

]andB = [b

]. Then

A + B = [a

+ b

]. We have (A + B)

= [a

+ b

] = [a

] +

] = A

+ B

. b) Using the same notation as in part (a), we

have B













= (AB)

, because

the (i, j)th entry is the (j, i)th entry of AB. 19. The result

follows because





d −b

−ca





ad −bc 0

0 ad − bc



(ad − bc)I



d −b

−ca





. 21. A

−1

)

A(A ⋯(A(AA

−1

) ⋯ A

−1

bytheassociativelaw.

Because AA

−1

= I, working from the inside shows that

−1

)

= I. Similarly (A

−1

)

= I. Therefore, (A

)

−1

)

. 23. The (i, j)th entry of A + A

is a

+ a

,which

equals a

+ a

,the(j, i)th entry of A + A

, so by deﬁnition

A + A

is symmetric. 25. x

= 1, x

=−1, x

=−2

27. a)







111

101













001

100

001













111

101







29. a)







100

110

101













100

101

110













100

111







31. a) A∨B = [a

∨ b

] = [b

∨a

] = B ∨ Ab)A∧ B =

∧ b

] = [b

∧ a

] = B ∧ A 33. a) A ∨ (B ∧ C) =

] ∨ [b

∧ c

] = [a

∨ (b

∧ c

)] = [(a

∨ b

) ∧

∨c

)] = [a

∨b

] ∧[a

∨c

] = (A∨B)∧(A∨C) b) A∧(B∨

C) = [a

]∧[b

∨c

] = [a

∧(b

∨c

)] = [(a

∧b

)∨(a

∧c

)] =

∧ b

] ∨ [a

∧ c

] = (A ∧ B) ∨ (A ∧ C) 35. A ⊙ (B ⊙ C) =





∧







∧ c











∧ b

∧c











∧b

∧c















∧ b





∧ c



(A ⊙ B) ⊙ C

Supplementary Exercises

1. a) A b) A ∩ B c) A − B d) A ∩ B e) A ⊕ B

3. Yes 5. A − (A −B) = A−(A ∩

B) = A ∩ (A∩B) = A ∩

(

A ∪ B) = (A ∩ A) ∪ (A ∩ B) =∅∪(A ∩ B) = A ∩ B 7. Let

A ={1}, B =∅, C ={1}.Then(A − B) − C =∅, but

A − (B − C) ={1}. 9. No. For example, let A = B =

{a, b}, C =∅,andD ={a}.Then(A − B) − (C − D) =

∅−∅=∅, but (A − C) − (B − D) ={a, b}−{b}={a}.

11. a) ∅ ≤ A ∩ B ≤ A ≤ A ∪ B ≤ U b) ∅ ≤

A − B ≤ A ⊕ B≤ A ∪ B≤ A+ B 13. a) Yes, no

b) Yes, no c) f has inverse with f

−1

(a) = 3,f

−1

(b) = 4,

−1

(d ) = 1; g has no inverse. 15. If f is one-to-

one, then f provides a bijection between S and f (S), so they

have the same cardinality. If f is not one-to-one, then there ex-

ist elements x and y in S such that f (x) = f (y). Let S ={x, y}.

Then S = 2 but f (S) = 1. 17. Let x ∈ A.Then

({x}) ={f (y) ∣ y ∈{x}} = {f (x)}. By the same reasoning,

({x}) ={g(x)}. Because S

= S

, we can conclude that

{f (x)}={g(x)}, and so necessarily f (x) = g(x). 19. The

equation is true if and only if the sum of the fractional parts

of x and y is less than 1. 21. The equation is true if and only

if either both x and y are integers, or x is not an integer but the

sum of the fractional parts of x and y is less than or equal to 1.

23. If x is an integer, then x+ m − x= x + m − x = m.

Otherwise, write x in terms of its integer and fractional parts:

x = n + 𝜖,wheren = xand 0 <𝜖<1. In this case x+

P1: 1

ANS Rosen-2311T MH03280-Rosen-v1.cls May 8, 2018 17:25

Answers to Odd-Numbered Exercises S-19

m − x=n + 𝜖+ m − n − 𝜖= n + m − n − 1 = m − 1.

25. Write n = 2k+1 for some integer k.Thenn

= 4k

+4k+1,

so n

∕4 = k

+ k +

. Therefore, n

∕4= k

+ k + 1. But

+ 3)∕4 = (4k

+ 4k + 1 + 3)∕4 = k

+ k + 1. 27. Let

x = n + (r∕m) + 𝜖,wheren is an integer, r is a nonnegative

integer less than m,and𝜖 is a real number with 0 ≤ 𝜖<1∕m.

The left-hand side is nm + r + m𝜖= nm + r. On the right-

hand side, the terms xthrough x + (m + r − 1)∕mare all

just n and the terms from x + (m − r)∕mon are all n + 1.

Therefore, the right-hand side is (m − r)n + r(n + 1) = nm + r,

as well.

29. 101 31. a

= 1; a

2n+1

= n ⋅ a

for all

n > 0; and a

= n + a

2n−1

for all n > 0. The next

four terms are 5346, 5353, 37, 471, and 37, 479. 33. If each

−1

(j) is countable, then S = f

−1

(1) ∪ f

−1

(2) ∪ ⋯ is the

countable union of countable sets and is therefore countable

by Exercise 27 in Section 2.5. 35. Because there is a one-

to-one correspondence between R and the open interval (0, 1)

(given by f (x) = 2 arctan(x)∕𝜋), it suﬃces to shows that

(0, 1) × (0, 1)= (0, 1). By the Schr

oder-Bernstein theorem

it suﬃces to ﬁnd injective functions f :(0, 1) → (0, 1) × (0, 1)

and g :(0, 1) × (0, 1) → (0, 1). Let f (x) = (x,

). For g we

follow the hint. Suppose (x, y) ∈ (0, 1) × (0, 1), and represent

x and y with their decimal expansions x = 0.x

… and

y = 0. y

…, never choosing the expansion of any number

that ends in an inﬁnite string of 9s. Let g(x, y) be the decimal

expansion obtained by interweaving these two strings, namely

0.x

…. 37. A





, A

4n+1



−10



4n+2



−10

0 −1



, A

4n+3



0 −1



, for n ≥ 0

39. Suppose that A =





. Let B =





. Be-

cause AB = BA, it follows that c = 0anda = d.Let

B =





. Because AB = BA, it follows that b = 0.

Hence, A =



a 0

0 a



= aI. 41. a) Let A ⊙ 0 =





.Then

= (a

∧0) ∨ ⋯ ∨(a

∧0) = 0. Hence, A⊙0 = 0. Similarly,

0⊙A = 0. b) A∨0 =



∨ 0







= A. Hence, A∨0 = A.

Similarly, 0 ∨ A = A. c) A ∧ 0 =



∧ 0



= [0] = 0. Hence,

A ∧ 0 = 0. Similarly, 0 ∧ A = 0.

CHAPTER 3

Section 3.1

1. max := 1, i := 2, max := 8, i := 3, max := 12, i := 4,

i := 5, i := 6, i := 7, max := 14, i := 8, i := 9, i := 10, i := 11

3. procedure AddUp(a

, … ,a

: integers)

sum : = a

for i :=2to n

sum := sum + a

return sum

5. procedure duplicates(a

, … ,a

: integers in

nondecreasing order)

k := 0 {this counts the duplicates}

j := 2

while j ≤ n

if a

= a

j−1

then

k := k + 1

:= a

while j ≤ n and a

= c

j := j + 1

, … ,c

is the desired list}

7. procedure last even location(a

, … ,a

: integers)

k := 0

for i := 1 to n

if a

is even then k := i

return k {k = 0 if there are no evens}

9. procedure palindrome check(a

… a

: string)

answer := true

for i := 1 to n∕2

if a

≠ a

n+1−i

then answer := false

return answer

11. procedure interchange(x, y: real numbers)

z := x

x := y

y := z

The minimum number of assignments needed is three.

13. Linear search: i := 1, i := 2, i := 3, i := 4, i := 5, i := 6,

i := 7, location := 7; binary search: i := 1, j := 8, m := 4,

i := 5, m := 6, i := 7, m := 7, j := 7, location := 7

15. procedure insert(x, a

, … ,a

: integers)

{the list is in order: a

≤ a

≤ ⋯ ≤ a

}

n+1

:= x + 1

i := 1

while x > a

i := i + 1

for j := 0 to n − i

n−j+1

:= a

n−j

:= x

{x has been inserted into correct position}

17. procedure ﬁrst largest(a

, … ,a

: integers)

max := a

location := 1

for i := 2 to n

if max < a

then

max := a

location := i

return location

19. procedure mean-median-max-min(a, b, c: integers)

mean := (a + b + c)∕ 3

{the six diﬀerent orderings of a, b, c with respect

to ≥ will be handled separately}

P1: 1

ANS Rosen-2311T MH03280-Rosen-v1.cls May 8, 2018 17:25

S-20 Answers to Odd-Numbered Exercises

if a ≥ b then

if b ≥ c then median := b; max := a; min := c

⋮

(The rest of the algorithm is similar.)

21. procedure ﬁrst-three(a

, … ,a

: integers)

if a

> a

then interchange a

and a

if a

> a

then interchange a

and a

if a

> a

then interchange a

and a

23. procedure onto( f : function from A to B,where

A ={a

, … ,a

}, B ={b

, … ,b

}, a

, … ,a

, … ,b

are integers)

for i := 1 to m

hit(b

):= 0

count := 0

for j := 1 to n

if hit( f (a

)) = 0 then

hit( f (a

)) := 1

count := count + 1

if count = m then return true else return false

25. procedure ones(a: bit string, a = a

… a

)

count:= 0

for i := 1 to n

if a

:= 1 then

count := count + 1

return count

27. procedure ternary search(s: integer, a

, … ,a

increasing integers)

i := 1

j := n

while i < j − 1

l := (i + j)∕3

u := 2(i + j)∕3

if x > a

then i := u + 1

else if x > a

then

i := l + 1

j := u

else j := l

if x = a

then location := i

else if x = a

then location := j

else location := 0

return location {0 if not found}

29. procedure ﬁnd a mode(a

, … ,a

: nondecreasing

integers)

modecount := 0

i := 1

while i ≤ n

value := a

count := 1

while i ≤ n and a

= value

count := count + 1

i := i + 1

if count > modecount then

modecount := count

mode := value

return mode

31. Assume the input is strings a

…a

and b

…b

where each character is a letter, A through Z. Assume also

that a function index is available, such that index(x)isthe

position of the letter x in the alphabet (index(‘A’) = 1, ...,

index(‘Z’) = 26). a) Initialize a-count and b-count to be

lists of length 26 with all values equal to 0. For i from 1

to n increment a-count(index(a

)) and b-count(index(b

)). If

a-count(i) = b-count(i)foralli from 1 to 26, then return

“true”; otherwise return “false.” b) Sort both strings into al-

phabetical order. Then the two original strings were anagrams

if and only if the sorted strings are identical.

33. procedure ﬁnd duplicate(a

, … ,a

: integers)

location := 0

i := 2

while i ≤ n and location = 0

j := 1

while j < i and location = 0

if a

= a

then location := i

else j := j + 1

i := i + 1

return location

{location is the subscript of the ﬁrst value that

repeats a previous value in the sequence}

35. procedure ﬁnd decrease(a

, … ,a

: positive

integers)

location := 0

i := 2

while i ≤ n and location = 0

if a

< a

i−1

then location := i

else i := i + 1

return location

{location is the subscript of the ﬁrst value less than

the immediately preceding one}

37. At the end of the ﬁrst pass: 1, 3, 5, 4, 7; at the end of the

second pass: 1, 3, 4, 5, 7; at the end of the third pass: 1, 3, 4,

5, 7; at the end of the fourth pass: 1, 3, 4, 5, 7

39. procedure better bubblesort(a

, … ,a

: integers)

i : = 1; done : = false

while i < n and done = false

done : = true

for j : = 1 to n − i

if a

> a

j+1

then

interchange a

and a

j+1

done : = false

i : = i + 1

, … ,a

is in increasing order}

41. At the end of the ﬁrst, second, and third passes: 1, 3, 5, 7, 4;

at the end of the fourth pass: 1, 3, 4, 5, 7 43. a) 1, 5, 4, 3, 2;

1, 2, 4, 3, 5; 1, 2, 3, 4, 5; 1, 2, 3, 4, 5 b) 1, 4, 3, 2, 5; 1,

2, 3, 4, 5; 1, 2, 3, 4, 5; 1, 2, 3, 4, 5 c) 1, 2, 3, 4, 5; 1, 2, 3,

4, 5; 1, 2, 3, 4, 5; 1, 2, 3, 4, 5 45. We carry out the linear

search algorithm given as Algorithm 2 in this section, except

that we replace x ≠ a

by x < a

, and we replace the else

clause with else location := n + 1. 47. 2 + 3 + 4 + ⋯ + n =

+n−2)∕2 49. Find the location for the 2 in the list 3 (one

剩余97页未读，继续阅读

Y3210100085

粉丝: 1
资源: 2

"离散数学及其应用（第8版）奇数题答案总结"

离散数学及应用

离散数学及其应用奇数题答案

离散数学及其应用 全部答案包括偶数题 Kenneth.H.Rosen

离散数学及其应用（原书第8版） (Kenneth H.Rosen) 偶数题目答案

离散数学及其应用_本科教学版_第6版_Kenneth H. Rosen_课后答案[1-10章]

初等数论及其应用 第五版 Kenneth H.Rosen著 夏鸿刚译 含书签

初等数论及其应用【美】Kenneth.H．Rosen

离散数学及其应用（第七版）Rosen 奇数题答案（英文）

"离散数学及应用电子版：Kenneth H. Rosen著作第八版全新展望

《初等数论及其应用》第五版-Kenneth H. Rosen-数论基础与现代应用

最新资源

离散数学及其应用全部答案包括偶数题 Kenneth.H.Rosen

初等数论及其应用第五版 Kenneth H.Rosen著夏鸿刚译含书签