99年國立嘉義大學資工所離散數學

If you have stamps of two different denominations, 5 dollars and 7 dollars, you can make up exactly any postage of n dollars or more using stamps of these two denominations.

1.

What is the minimum of n?

If you have stamps of two different denominations, 5 dollars and 7 dollars, you can make up exactly any postage of n dollars or more using stamps of these two denominations.

2.

Please prove it.

Please give a grammar that specifies each of the following languages:

3.

Please give a grammar that specifies each of the following languages:

4.

L = {x | x ∈ {a, b}* and x does not contain two consecutive a's} (Notice that the notation S* denotes the set of all sequences of letters from set S.)

5.

Determine a minimum spanning tree for the following graph.

Solve the following recurrence relations:

6.

a_n+1 − 2a_n = 5, n ≥ 0, a₀ = 1.

Solve the following recurrence relations:

7.

a_n+2 − 5a_n+1 + 6a_n = 4_n, n ≥ 0, a₀ = 5, a₁ = 10.

Write the postfix form of the following expressions:

8.

(A + B) × D + E / (F + A × D) + C

Write the postfix form of the following expressions:

9.

not (A and not ((B < C) or (C > D))) or (C < E)