## 發表文章

### 623 - 500!

UVa網站題目連結 My Solved Problems Performance In these days you can more and more often happen to see programs which perform some useful calculations being executed rather then trivial screen savers. Some of them check the system message queue and in case of finding it empty (for examples somebody is editing a file and stays idle for some time) execute its own algorithm. As an examples we can give programs which calculate primary numbers. One can also imagine a program which calculates a factorial of given numbers. In this case it is the time complexity of order O ( n ) which makes troubles, but the memory requirements. Considering the fact that 500! gives 1135-digit number no standard, neither integer nor floating, data type is applicable here. Your task is to write a programs which calculates a factorial of a given number. Assumptions: Value of a number `` n " which factorial should be calculated of does not exceed 1000 (although 500! is the name of the problem, 500! is a

### 326 - Extrapolation Using a Difference Table

UVa網站題目連結 My Solved Problems Performance A very old technique for extrapolating a sequence of values is based on the use of a difference table. The difference table used in the extrapolation of a sequence of 4 values, say 3, 6, 10, and 15, might be displayed as follows: The original sequence of values appears in the first column of the table. Each entry in the second column of the table is formed by computing the difference between the adjacent entries in the first column. These values (in the second column) are called first differences. Each entry in the third column is similarly the difference between the adjacent entries in the second column; the third column entries are naturally called second differences. Computation of the last column in this example should now be obvious (but beware that this value is not always zero). Note that the last column will always contain only a single value. If we begin with a sequence of n values, the completed diffe

### 324 - Factorial Frequencies

UVa網站題目連結 My Solved Problems Performance In an attempt to bolster her sagging palm-reading business, Madam Phoenix has decided to offer several numerological treats to her customers. She has been able to convince them that the frequency of occurrence of the digits in the decimal representation of factorials bear witness to their futures. Unlike palm-reading, however, she can't just conjure up these frequencies, so she has employed you to determine these values. Recall that the definition of n ! (that is, n factorial) is just . As she expects to use either the day of the week, the day of the month, or the day of the year as the value of n , you must be able to determine the number of occurrences of each decimal digit in numbers as large as 366 factorial (366!), which has 781 digits. Input and Output The input data for the program is simply a list of integers for which the digit counts are desired. All of these input value

### 305 - Joseph

UVa網站題目連結 My Solved Problems Performance The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, ..., n , standing in circle every m th is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved. Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy. Input The input file consists of separate lines containing k . The last line in the input file contains 0. You can suppose that 0 < k < 14. Output The output file will consist of separate lines c

### 136 - Ugly Numbers

UVa網站題目連結 My Solved Problems Performance Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... shows the first 11 ugly numbers. By convention, 1 is included. Write a program to find and print the 1500'th ugly number. Input and Output There is no input to this program. Output should consist of a single line as shown below, with replaced by the number computed. Sample output The 1500'th ugly number is <number>. Solution public class Main { public static void main ( String [] args ) { int size = 1500 ; int counter = 1 ; int result = 0 ; for ( int i = 2 ; counter < size ; i ++) { int x = i ; while (( x % 5 == 0 )) { x /= 5 ; }; while (( x % 3 == 0 )) { x /= 3 ; }; while (( x % 2 == 0 )) { x /= 2 ; };

### 102 - Ecological Bin Packing

UVa網站題目連結 My Solved Problems Performance Background Bin packing, or the placement of objects of certain weights into different bins subject to certain constraints, is an historically interesting problem. Some bin packing problems are NP-complete but are amenable to dynamic programming solutions or to approximately optimal heuristic solutions. In this problem you will be solving a bin packing problem that deals with recycling glass. The Problem Recycling glass requires that the glass be separated by color into one of three categories: brown glass, green glass, and clear glass. In this problem you will be given three recycling bins, each containing a specified number of brown, green and clear bottles. In order to be recycled, the bottles will need to be moved so that each bin contains bottles of only one color. The problem is to minimize the number of bottles that are moved. You may assume that the only problem is to minimize the number of movements between boxes. For the pur

### 100 - The 3n + 1 problem

UVa網站題目連結 My Solved Problems Performance Background Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs. The Problem Consider the following algorithm: 1. input n 2. print n 3. if n = 1 then STOP 4. if n is odd then 5. else 6. GOTO 2 Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.) Given an input n , it is possible to determine the number of numbers printed (inc