JWorld@TW the best professional Java site in Taiwan
      註冊 | 登入 | 全文檢索 | 排行榜  

» JWorld@TW » Java 程式分享區  

按列印兼容模式列印這個話題 列印話題    把這個話題寄給朋友 寄給朋友    訂閱主題
reply to postflat modego to previous topicgo to next topic
本主題所含的標籤
無標籤
作者 Re:Quiz [Re:T55555]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2004-02-28 04:41 user profilesend a private message to userreply to postreply to postsearch all posts byselect and copy to clipboard. 
ie only, sorry for netscape users:-)add this post to my favorite list
Here is my second answer:

Previous post just show you quickly to solve the problem.
Sometime, you may need spend time to think how to improve
the program or how to get the best solution.

The 9! ( 362880 ) is too many, in fact, we did not consider that
the addition operation is permutative: a + b == b + a

Because permutative, the total case to check down to :
9! / 3! = 60480 ( 6 time less then previous method! )

The esay way to make sure we consider permutative is by using equation:
denominator1 > denominator2 > denominator3
( or denominator1 < denominator2 < denominator3 )

And since we use 1 to 9 digit, no repeatly, we can say:
first digit of denominator1 > first digit of denominator 2 > first digit of denominator3

We arrange these 3 digits at beginning to save useless loop,
so finally, this time the program will faster then the previous one.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//Author: T55555 
//Date: 2002-12-31 
  
public class Test2 { 
  
  public static int COUNT = 0; 
  
  public static void check(int[] t) { 
    COUNT++; 
    int denominator1 = t[0]*10 + t[3]; 
    int denominator2 = t[1]*10 + t[4]; 
    int denominator3 = t[2]*10 + t[5]; 
    if ( (t[6] * denominator2 * denominator3 + 
          t[7] * denominator1 * denominator3 + 
          t[8] * denominator1 * denominator2) == 
         (denominator1 * denominator2 * denominator3) ) { 
      System.out.println(t[6] + "/" + t[0] + t[3] + " + " + 
                         t[7] + "/" + t[1] + t[4] + " + " + 
                         t[8] + "/" + t[2] + t[5] + " = 1"); 
    } 
  } 
  
  public static void findNext(int[] t, int position, int n) { 
    if (position == n) { 
      check(t); 
      return; 
    } 
  
    possibleValue: for (int v = 1; v <= n; v++) { 
      for (int i = position-1; i >= 0; i--) { 
        if ((t[ i ] == v) || (position <= 2 && v > t[ i ])) { 
          continue possibleValue; 
        } 
      } 
      t[position] = v; 
      findNext(t, position+1, n); 
    } 
  } 
  
  public static void main(String[] args) { 
    findNext(new int[9], 0, 9); 
    System.out.println("Total check: " + COUNT); 
  } 
} 


This time, it is faster then previous one, and the output is :
1
2
7/68 + 5/34 + 9/12 = 1  
Total check: 60480 


reply to postreply to post
話題樹型展開
人氣 標題 作者 字數 發文時間
11895 [精華] [教學]Quiz T55555 685 2004-02-28 04:26
10165 Re:Quiz T55555 1969 2004-02-28 04:33
10680 Re:Quiz T55555 2322 2004-02-28 04:41
10036 Re:Quiz sungo 26 2004-02-28 06:05
10074 Re:Quiz T55555 175 2004-02-28 06:14
10142 Re:Quiz sungo 295 2004-02-28 06:25
11049 Re:Quiz worookie 886 2004-02-28 08:36
12607 Re:Quiz jini 938 2004-02-28 12:41
» JWorld@TW »  Java 程式分享區

reply to postflat modego to previous topicgo to next topic
  已讀文章
  新的文章
  被刪除的文章
Jump to the top of page

JWorld@TW 本站商標資訊

Powered by Powerful JuteForum® Version Jute 1.5.8