程序代写代做代考 algorithm scheme data structure PowerPoint Presentation

PowerPoint Presentation

1
a + b
infix form
+ a b
prefix form
a b +
postfix form

2
Postponement

Reverse Polish Notation

1. Infix to postfix transformation
–   Manual transformation
–   Algorithmic transformation

2. Evaluating postfix expressions

3
Infix to Postfix
Manual Transformation
a + 5 * b

4
Infix to Postfix: Manual Transformation
a +
5 * b

5
a +
5 b *
Infix to Postfix: Manual Transformation

6
a +
5 b *
Infix to Postfix: Manual Transformation

7
a + 5 * b
a +
5 * b
a +
5 b *
a +
5 b *
Infix to Postfix: Manual Transformation

8
Infix to Postfix
Manual Transformation
a + b * c – d / e

9
a + b * c – d / e
a b c * + d e / –
Infix to Postfix: Manual Transformation

10
Postponement

Reverse Polish Notation

1. Infix to postfix transformation
–   Manual transformation
–   Algorithmic transformation

2. Evaluating postfix expressions

11
Infix to Postfix
Algorithmic Transformation
a + 5 * b

12
Infix to Postfix: Algorithmic Transformation (STACK)

a + 5 * b
a

13
push

+
Infix to Postfix: Algorithmic Transformation (STACK)
a + 5 * b
a

14

+
Infix to Postfix: Algorithmic Transformation (STACK)
a + 5 * b
a 5

15
push
*

+
Infix to Postfix: Algorithmic Transformation (STACK)
a + 5 * b
a 5

16
*

+
Infix to Postfix: Algorithmic Transformation (STACK)
a + 5 * b
a 5 b

17
*

+
Infix to Postfix: Algorithmic Transformation (STACK)
a + 5 * b
a 5 b *

18
a + 5 * b
a 5 b *
pop

+

Infix to Postfix: Algorithmic Transformation (STACK)

19
a + 5 * b
a 5 b * +

Infix to Postfix: Algorithmic Transformation (STACK)

20
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

(
(a – 2 *(b + c) – d * e) * f

push

21
(a – 2 *(b + c) – d * e) * f

(
a
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

22
(a – 2 *(b + c) – d * e) * f

(
a
push

Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

23
(a – 2 *(b + c) – d * e) * f

(
a 2

Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

24
(a – 2 *(b + c) – d * e) * f

(
a 2

push
*
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

25
(a – 2 *(b + c) – d * e) * f

(
a 2

push
*
(
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

26
(a – 2 *(b + c) – d * e) * f

(
a 2 b

*
(

Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

27
(a – 2 *(b + c) – d * e) * f

(
a 2 b

*
(

push
+
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

28
(a – 2 *(b + c) – d * e) * f

(
a 2 b c

*
(

+
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

29
(a – 2 *(b + c) – d * e) * f

(
a 2 b c +

*
(

+
pop

Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

30
(a – 2 *(b + c) – d * e) * f

(
a 2 b c +

*
(

pop, pop
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

31
(a – 2 *(b + c) – d * e) * f

(
a 2 b c + *

*

pop

Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

32
(a – 2 *(b + c) – d * e) * f

(
a 2 b c + * –

pop, pop

Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

33
(a – 2 *(b + c) – d * e) * f

(
a 2 b c + * –

pop, pop, push

Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

34
(a – 2 *(b + c) – d * e) * f

(
a 2 b c + * – d


Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

35
(a – 2 *(b + c) – d * e) * f

(
a 2 b c + * – d


push
*
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

36
(a – 2 *(b + c) – d * e) * f

(
a 2 b c + * – d e


*
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

37
(a – 2 *(b + c) – d * e) * f

pop

(
a 2 b c + * – d e *

*

Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

38
(a – 2 *(b + c) – d * e) * f

pop, pop

(
a 2 b c + * – d e * –

Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

39
(a – 2 *(b + c) – d * e) * f
(

pop, pop, pop

a 2 b c + * – d e * –
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

40
(a – 2 *(b + c) – d * e) * f

push
*

a 2 b c + * – d e * –
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

41
(a – 2 *(b + c) – d * e) * f

*

a 2 b c + * – d e * – f
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

42

(a – 2 *(b + c) – d * e) * f

pop
*
a 2 b c + * – d e * – f *

Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

43
(a – 2 *(b + c) – d * e) * f

a 2 b c + * – d e * – f *
Infix to Postfix: Algorithmic Transformation (STACK)
Exercise 7d, page 140

44
Postponement

Reverse Polish Notation

1. Infix to postfix transformation
–   Manual transformation
–   Algorithmic transformation

2. Evaluating postfix expressions

45
Evaluating Postfix Expressions
7 2 3 * – 4 +

46
7 2 3 * – 4 +
Evaluating Postfix Expressions (STACK)

7
push

47

7
push
7 2 3 * – 4 +

2
Evaluating Postfix Expressions (STACK)

48

7
push
7 2 3 * – 4 +

2
3
Evaluating Postfix Expressions (STACK)

49
pop
7 2 3 * – 4 +

3
*

7
2
Evaluating Postfix Expressions (STACK)

50
pop, pop
7 2 3 * – 4 +

3
*

7
2
Evaluating Postfix Expressions (STACK)

51
7 2 3 * – 4 +

6
=
3
*

7
2
Evaluating Postfix Expressions (STACK)

52
7 2 3 * – 4 +

6
push

7
Evaluating Postfix Expressions (STACK)

53
7 2 3 * – 4 +

6

7
Evaluating Postfix Expressions (STACK)

54
7 2 3 * – 4 +

6

7
Evaluating Postfix Expressions (STACK)

55
7 2 3 * – 4 +

pop

7
6

Evaluating Postfix Expressions (STACK)

56
7 2 3 * – 4 +

pop, pop

6

7
Evaluating Postfix Expressions (STACK)

57
7 2 3 * – 4 +

6

7
1
=
Evaluating Postfix Expressions (STACK)

58
7 2 3 * – 4 +

1
push
Evaluating Postfix Expressions (STACK)

59
7 2 3 * – 4 +

1

Evaluating Postfix Expressions (STACK)

60

7 2 3 * – 4 +

1
push
4
Evaluating Postfix Expressions (STACK)

61
7 2 3 * – 4 +

4

1
Evaluating Postfix Expressions (STACK)

62
7 2 3 * – 4 +

pop

1
4
+
Evaluating Postfix Expressions (STACK)

63
7 2 3 * – 4 +

pop, pop

4
+
1
Evaluating Postfix Expressions (STACK)

64
7 2 3 * – 4 +

4
+
1
5
=
Evaluating Postfix Expressions (STACK)

65
7 2 3 * – 4 +

5
push
Evaluating Postfix Expressions (STACK)

66
7 2 3 * – 4 +

5

Evaluating Postfix Expressions (STACK)

67
Backtracking
Eight Queens Problem
 
A Brief History

“The n-queens problem is an old one that has been around for more than a century. Originally known as the 8-Queens problem, it has been studied by many famous mathematicians over the years, including the great German mathematician Karl Friedrich Gauss (1777-1855). The problem was generalized to n by n boards in 1850 by Franz Nauck. Since the 1960’s, with rapid developments in computer science, this problem has been used as an example of backtracking algorithms, etc.”

68
Applications to Mathematics and other Areas

“The queens problem is really a puzzle but, surprisingly, there are some practical applications such as
parallel memory storage schemes,
VLSI testing,
traffic control, and
deadlock prevention.

The problem is also illustrative of more practical problems whose solutions are permutations, of which there are many.

Furthermore, the solution technique, backtracking is very important, and is best learnt on simple examples such as the queens problem.”

69
Figure 4-16

70

1, 1
Q

1
4
3
2
1
2
3
4

71

1, 1
Q

Q

1
4
3
2
1
2
3
4
2, 3

72

1, 1
Q

?
?
?
?

Q

1
4
3
2
1
2
3
4
2, 3

73

1, 1
Q

1
4
3
2
1
2
3
4

74
Q

Q

1
4
3
2
1
2
3
4

1, 1
2, 4

75
Q

Q

Q

1
4
3
2
1
2
3
4

1, 1
2, 4
3, 2

76
Q

Q

Q

?
?
?
?
1
4
3
2
1
2
3
4

1, 1
2, 4
3, 2

77
Q

?
?

Q

1
4
3
2
1
2
3
4

1, 1
2, 4

78
Q

1
4
3
2
1
2
3
4

1, 1

79

1
4
3
2
1
2
3
4

80

Q

1
4
3
2
1
2
3
4

1, 2

81

Q

Q

1
4
3
2
1
2
3
4

1, 2
2, 4

82

Q

Q

Q

1
4
3
2
1
2
3
4

1, 2
2, 4
3, 1

83

Q

Q

Q

Q

1
4
3
2
1
2
3
4
4, 3

1, 2
2, 4
3, 1

Data Structures: A Pseudocode Approach with C
84
Figure 4-18

/docProps/thumbnail.jpeg