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

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

T55555   於 2004-02-28 04:41       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*10 + t; int denominator2 = t*10 + t; int denominator3 = t*10 + t; if ( (t * denominator2 * denominator3 + t * denominator1 * denominator3 + t * denominator1 * denominator2) == (denominator1 * denominator2 * denominator3) ) { System.out.println(t + "/" + t + t + " + " + t + "/" + t + t + " + " + t + "/" + t + t + " = 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, 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 本站商標資訊