發表文章

目前顯示的是 9月, 2008的文章

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

[發佈] werdna-feeds

圖片
上禮拜花了兩天研究google gadget 除了修改了未來圖書館可能會發表的個人化小工具外 也順手為自己打造一個專屬的RSS reader 功能其實很簡單 會自動讀取我兩個網誌和相簿的rss 所以只要有更新就可以在這個小工具上看見 這個小工具最簡便就是放在igoogle個人首頁上 網址: http://www.google.com/ig 以google帳號登入 只要在樣本圖下面找到[+google]標籤按下即可加入 320x250 420x250 目前的設定比較推薦在解析度1280以上 不然有些太長的句子可能會被截斷 螢幕解析度在1024x768的話畫面大概會像第一個圖 若是1280以上的會像第二個 (420x250那個) 不過在igoogle上不會有邊框 邊框是放在個人部落格才有的 另外對firefox支援較佳 大家趕快捨棄萬惡的ie吧 xd 另外也可以放在個人的網站部落格之類的 只要可以自己插入html或javascript就可以 這邊可以調整邊框顯示等等然後放上自己的網頁喔 取得原始碼將此小工具新增至個人網頁 喔對了其實應該也支援google desktop的 但目前捲軸功能不知道為什麼出不來 而且寬度太窄的話顯示也不好看 所以有想試的人再跟我說 不然就先以上面兩種為主囉 :p 歡迎大家來玩看看 有bug的話歡迎報修 如果有人也想玩google gadget可以找我討論 ^^