資料結構與演算法

(5 points) Consider the following randomized algorithm, which prints out some number of exclamation marks (!) and some number of asterisks (*). Assume that the size of $A$ is $n$ initially. What are the expected numbers of !s and *s that the algorithm prints out? Choose the tightest possible answers.

RandomizedPrint(A):
  n = length(A)
  if n <= 1:
    print "!"
    return
  for i in {0,...,n-1}:
    print "*"
  Choose a uniformly random integer p in {1,...,n-1}
  RandomizedPrint(A[:p])
  RandomizedPrint(A[p:])