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

 » JWorld@TW » Java 程式分享區    列印話題    寄給朋友    訂閱主題
 本主題所含的標籤 無標籤

T55555

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

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.

 `1234567891011121314151617181920212223242526272829303132333435363738394041424344` ```//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 :
 `12` ```7/68 + 5/34 + 9/12 = 1 Total check: 60480 ```

 話題樹型展開
 人氣 標題 作者 字數 發文時間 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 程式分享區

 已讀文章  新的文章  被刪除的文章

JWorld@TW 本站商標資訊