Homework #1 (deadline: 10/13)

張貼日期：Sep 10, 2016 2:27:29 AM

Consider the following three problems and write Python programs to solve them. Your programs should be named as "學號_題號.py" and pack them into a compression file. Then submit your file to the elearning platform (教學平台).

1. Monte Carlo method. The Monte Carlo method is a method for finding approximate solution to problems that cannot be precisely solved. An example to compute the number pi is given as follows:

  • Simulate shooting a dart into a square surrounding a circle of radius 1. That can be done by generating random x and y coordinates between -1 and 1. If the generated point lies inside the circle, we count it as a hit. That is the case when x*x + y*y <= 1. Because our shots are entirely random, we expect that the ratio of hits/ tries is approximately equal to the ratio of the areas of the circle and the square, that is, pi/4. Therefore, our estimate for pi is 4*hits/tries.

Write a program to output the estimated value for pi based on the above Monte Carlo method. To generate a random, you can call the function random().

2. The game of Nim. This is a well-known game with a number of variants. Two players alternately take marbles from a pile. In each move, a player chooses how many marbles to take. The player must take at least one but at most half of the marbles. Then the other player takes a turn. The player who takes the last marble loses.

Write a program in which the computer plays against a human opponent. Generate a random integer between 10 and 100 to denote the initial size of the pile. Generate a random integer between 0 and 1 to decide whether the computer or the human takes the first turn. The human can decide whether the computer plays smart or stupid. In stupid mode the computer simply takes a random legal value (between 1 and n/2) from the pile whenever it has a turn. In smart mode the computer takes off enough marbles to make the size of the pile a power of two minus 1 - that is, 3, 7, 15, 31, or 63. That is always a legal move, except when the size of the pile is currently one less than a power of two. In that case, the computer makes a random legal move.

3. Credit Card Number Check. The last digit of a credit card number is the check digit, which protects against transcription errors such as an error in a single digit or switching two digits. The following method is used to verify actual credit card numbers bu, for simplicity, we will describe it for numbers with 8 digits instead of 16:

  • Starting from the rightmost digit, form the sum of every other digit. For example, if the credit card number is 43589795, then you form the sum 5+7+8+3 = 23.

  • Double each of the digits that were not included in the preceding step. Add all digits of the resulting numbers. For example, with the number given above, doubling the digits, starting with the next-to-last one, yields 18 18 10 8. Adding all digits in these values yields 1+8+1+8+1+0+8 = 27.

  • Add the sums of the two preceding steps. If the last digit of the result is 0, the number is valid. In our case, 23+27 = 50, so the number is valid.

Write a program that implements this algorithm. The user should supply an 8-digit number without spacing (your program has to validate the input), and you should print out whether the number is valid or not.