Tham khảo tài liệu 'thuật toán algorithms (phần 6)', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | RANDOM NUMBERS 43 Exercises 1. Write a program to generate random four-letter words collections of letters . Estimate how many words your program will generate before a word is repeated. 2. How would you simulate generating random numbers by throwing two dice and taking their sum with the added complication that the dice are nonstandard say painted with the numbers 1 2 3 5 8 and 13 3. What is wrong with the following linear feedback shift register 4. Why wouldn t the or or and function instead of the exclusive or function work for linear feedback shift registers 5. Write a program to produce a random two dimensional image. Example generate random bits write a when 1 is generated when 0 is generated. Another example use random numbers as coordinates in a two dimensional Cartesian system write a at addressed points. 6. Use an additive congruential random number generator to generate 1000 positive integers less than 1000. Design a test to determine whether or not they re random and apply the test. 7. Use a linear congruential generator with parameters of your own choosing to generate 1000 positive integers less than 1000. Design a test to determine whether or not they re random and apply the test. 8. Why would it be unwise to use for example b 3 and c 6 in the additive congruential generator 9. What is the value of the x2 statistic for a degenerate generator which always returns the same number 10. Describe how you would generate random numbers with m bigger than the computer word size. 4. Polynomials The methods for doing arithmetic operations given in Chapter 2 are simple and straightforward solutions to familiar problems. As such they provide an excellent basis for applying thinking to produce more sophisticated methods which are substantially more efficient. As we ll see it is one thing to write down a formula which implies a particular mathematical calculation it is quite another thing to write a computer program which performs the calculation efficiently. .
