Mid-term Exam (2)

Introduction to Computer Science
NCNU CSIE

Date:  December 6, 2013
Time: 08:10-11:00
Open book; turn off computer & mobile phone

  1. (5%) Listen to the melody played by the TA, and identify the title of this overture and the name of the composer.
    1. Mozart: The Marriage of Figaro - Overture
    2. Tchaikovsky : The Nutcracker Suite - Russian Dance
    3. Mozart: The Magic Flute - Overture
    4. Bizet: Carmen - Overture
  2. (5%) Listen to the melody played by the TA, and identify the title of this overture and the name of the composer.
    1. Mozart: The Marriage of Figaro - Overture
    2. Tchaikovsky : The Nutcracker Suite - Russian Dance
    3. Bizet: Carmen - Overture
    4. Rossini: William Tell - Overture
  3. (5%) Listen to the melody played by the TA, and identify the title of this overture and the name of the composer.
    1. Mozart: The Magic Flute - Overture
    2. Bizet: Carmen - Overture
    3. Rossini: La scala di seta - Overture
    4. Rossini: William Tell - Overture
  4. (5%) Listen to the melody played by the TA, and identify the title of this overture and the name of the composer.
    1. Tchaikovsky : The Nutcracker Suite - Russian Dance
    2. Mozart: The Magic Flute - Overture
    3. Bizet: Carmen - Overture
    4. Rossini: La scala di seta - Overture
    1. (5%) Listen to the melody played by the TA, and identify the title of this overture and the name of the composer.
      1. Mozart: The Marriage of Figaro - Overture
      2. Tchaikovsky : The Nutcracker Suite - Russian Dance
      3. Bizet: Carmen - Overture
      4. Rossini: William Tell - Overture

    2. (20%) Consider the following code which simulates the Drunken Man Walking problem in Ex9-12.  With the input 5, 100000, the program estimates the ratio for the drunken man to get home safely is 54.6%, which is slightly higher than 50% that we expect.  Try to modify the code so that it can calculate the probability correctly.  Leave a comment with the pound sign (#) on the line which you modified.

      from random import randrange

      def main():
          position, n = eval(
            input("Input the initial position and number of iterations (p, n) -- "))
          home, river = simNIteration(position, n)
          printProb(home, river)

      def simNIteration(p, n):
          home = river = 0
          for i in range(n):
              s = simOneIteration(p)
              if s == 0:
                  home = home + 1
              else:
                  river = river + 1
          return home, river

      def printProb(h, r):
          print("============")
          print("Probability:")
          print("============")
          print("{0}\t{1}\t{2:0.1%}".format("Home", h, h/(h+r) ))
          print("{0}\t{1}\t{2:0.1%}".format("River", r, r/(h+r) ))

      def endIteration(p):
          return p == 0 or p == 11

      def simOneIteration(p):
          while not endIteration(p):
              coin = randrange(1, 3)
              if coin == 1:
                  p = p - 1
              else:
                  p = p + 1
          return p

      main()

    3. (20%) Based on the GCD function, design a Python program to calculate the LCM (lowest common multiplier) of two numbers.
      The program may run as follows.

      Please input two positive numbers -- 33, 90
      LCM(33,90) = 990

    4. (20%) Consider the following Python program.  It is expected to run 10 multiplication tests and measure how long it takes for a user to finish the 10 test.  However, the program could not run successfully. Try to modify the code so that it can run correctly.  Be sure to truncate the fractional portion of the measured time, because the precision of seconds is good enough for us.  Leave a comment with the pound sign (#) on the line which you modifed.

      import random
      import time

      def main():

          count = 0

          for num in range (10):
              m1 = random.randint(0,99)
              m2 = random.randint(0,99)
              print(m1,"*",m2,"=",end="")

              start = time.time.now()

              user = eval(input(" "))
              ans = m1 * m2

              if user != ans:
                  print("Wrong! ",m1,"*",m2,"=",ans)
                  count = count + 1

          end = time.time.now()
          time = end - start

          print("You made ",count,"mistake today.",end="\t")
          print("You spend",time,"seconds in this exercise.")

      main()

    5. (20%) Please write a Python program to factorize a positive integer to prime numbers.  Make sure that your program will check the validity of the input value.
      The program may run as follows.

      Please input a number to factorize -- 34.5
      Please input a number to factorize -- 69.77
      Please input a number to factorize -- -6
      Please input a number to factorize -- 38
      2 * 19

      Please input a number to factorize -- 97
      97

      Please input a number to factorize -- 72
      2 * 2 * 2 * 3 * 3

      Please input a number to factorize -- 64
      2 * 2 * 2 * 2 * 2 * 2

    6. (20%) Let a, b, c, d, denote different numeric digits (0 .. 9).  Design a Python program to list all combinations that will look like ab*aa=cddc.  In this example, a and c are leading digits, so they cannot be zero.  (Hint: one solution is 78*77=6006.)