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

» JWorld@TW » Java 程式分享區  

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

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2004-02-28 04:26 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
轉自己的貼...
http://www.ownsky.org/cgi-bin/ut/topico_show.cgi?id=64408&h=1#630253

Someone asked me this question:

Given 1, 2, ..., 9 (nine numbers)
How do u fill the numbers and let the equation (see below) equals 1
1
2
3
   X       X       X
 ----- + ----- + -----  =  1
   XX      XX      XX


For example:
1/23 + 4/56 + 7/89 ?= 1

Each number occurs once and only once,
Write a program to solve this.

OK, now write your own java version, do not look my answers yet.
Then compare yours and mine, please post your version if yours is faster (or shorter) than mine.
Post your, if you have an other solution, or you just want to share.
(All are welcome)


caterpillar edited on 2004-03-04 12:30
reply to postreply to post
作者 Re:Quiz [Re:T55555]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2004-02-28 04:33 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
My first answer are like:

Mmmm...
I like brain exercice.

There are 9 casese to hold 9 digits.
So the total combination possible are
9! = 362880

The program consists of find all possible
combinations then check the equation.

BTW: It is better do not use floating division operation,
that may be will lose precision. (==> incorrect result)

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
45
//Author: T55555 
//Date: 2002-12-31 
 
public class Test { 
 
  public static int COUNT = 0; 
 
  public static void check(int[] t) { 
    COUNT++; 
    int denominator1 = t[1]*10 + t[2]; 
    int denominator2 = t[4]*10 + t[5]; 
    int denominator3 = t[7]*10 + t[8]; 
    if ( (t[0] * denominator2 * denominator3 + 
          t[3] * denominator1 * denominator3 + 
          t[6] * denominator1 * denominator2) == 
         (denominator1 * denominator2 * denominator3) ) { 
      System.out.println(t[0] + "/" + t[1] + t[2] + " + " + 
                         t[3] + "/" + t[4] + t[5] + " + " + 
                         t[6] + "/" + t[7] + t[8] + " = 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++) { 
      // check the value already used 
      for (int i = position-1; i >= 0; i--) { 
        if (t[ i ] == v) { 
          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); 
  } 
} 


After compile and run the program, here is the result:

1
2
3
4
5
6
7
5/34 + 7/68 + 9/12 = 1  
5/34 + 9/12 + 7/68 = 1  
7/68 + 5/34 + 9/12 = 1  
7/68 + 9/12 + 5/34 = 1  
9/12 + 5/34 + 7/68 = 1  
9/12 + 7/68 + 5/34 = 1  
Total check: 362880 


Still not fast enough...
See my second answer ...


T55555 edited on 2004-02-28 07:40
reply to postreply to post
作者 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
作者 Re:Quiz [Re:T55555]
sungo

瘋狂口罩大盜



發文: 822
積分: 17
於 2004-02-28 06:05 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
5/50 + 6/10 + 3/10 = 1 Big Smile


reply to postreply to post
作者 Re:Quiz [Re:sungo]
T55555

Java, Ruby, Haskell

版主

發文: 1026
積分: 24
於 2004-02-28 06:14 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
sungo wrote:
5/50 + 6/10 + 3/10 = 1 Big Smile


StupidStupid
Do you read the :
(1) Given 1, 2, ..., 9 (nine numbers)
(2) Each number occurs once and only once


reply to postreply to post
作者 Re:Quiz [Re:T55555]
sungo

瘋狂口罩大盜



發文: 822
積分: 17
於 2004-02-28 06:25 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
T55555 wrote:
StupidStupid
Do you read the :
(1) Given 1, 2, ..., 9 (nine numbers)
(2) Each number occurs once and only once

If each number occurs once and only once
and use numbers 1 to 9 .
The answer is only :
7/68 + 5/34 + 9/12

Sorry.Don't particularity read.. Cool


reply to postreply to post
作者 Re:Quiz [Re:T55555]
worookie

Small Ship

版主

發文: 2092
積分: 21
於 2004-02-28 08:36 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static void rookie() {
  for (int i1=1; i1<=7; i1++)
    for (int i2=i1+1; i2<=8; i2++)
      for (int i3=i2+1; i3<=9; i3++)
        if (i3!=i1)
        for (int i4=1; i4<=9; i4++)
          if (i4!=i1 && i4!=i2 && i4!=i3)
          for (int i5=1; i5<=9; i5++)
            if (i5!=i1 && i5!=i2 && i5!=i3 && i5!=i4)
            for (int i6=1; i6<=9; i6++)
              if (i6!=i1 && i6!=i2 && i6!=i3 && i6!=i4 && i6!=i5)
              for (int i7=1; i7<=9; i7++)
                if (i7!=i1 && i7!=i2 && i7!=i3 && i7!=i4 && i7!=i5 && i7!=i6)
                for (int i8=1; i8<=9; i8++)
                  if (i8!=i1 && i8!=i2 && i8!=i3 && i8!=i4 && i8!=i5 && i8!=i6 && i8!=i7)
                    check(new int [] {i1, i2, i3, i4, i5, i6, i7, i8,
                          45 - i1 - i2 - i3 - i4 - i5 - i6 - i7 - i8});
}


我測了一下, 好像又可以節省一半的時間 Big Smile


worookie edited on 2004-02-28 10:02
reply to postreply to post
作者 Re:Quiz [Re:worookie]
jini

SoftLeader Taiwan

版主

發文: 1266
積分: 23
於 2004-02-28 12: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
worookie wrote:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static void rookie() {
  for (int i1=1; i1<=7; i1++)
    for (int i2=i1+1; i2<=8; i2++)
      for (int i3=i2+1; i3<=9; i3++)
        if (i3!=i1)
        for (int i4=1; i4<=9; i4++)
          if (i4!=i1 && i4!=i2 && i4!=i3)
          for (int i5=1; i5<=9; i5++)
            if (i5!=i1 && i5!=i2 && i5!=i3 && i5!=i4)
            for (int i6=1; i6<=9; i6++)
              if (i6!=i1 && i6!=i2 && i6!=i3 && i6!=i4 && i6!=i5)
              for (int i7=1; i7<=9; i7++)
                if (i7!=i1 && i7!=i2 && i7!=i3 && i7!=i4 && i7!=i5 && i7!=i6)
                for (int i8=1; i8<=9; i8++)
                  if (i8!=i1 && i8!=i2 && i8!=i3 && i8!=i4 && i8!=i5 && i8!=i6 && i8!=i7)
                    check(new int [] {i1, i2, i3, i4, i5, i6, i7, i8,
                          45 - i1 - i2 - i3 - i4 - i5 - i6 - i7 - i8});
}


我測了一下, 好像又可以節省一半的時間 Big Smile


哇 這個我佩服


reply to postreply to post
» JWorld@TW »  Java 程式分享區

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

JWorld@TW 本站商標資訊

Powered by Powerful JuteForum® Version Jute 1.5.8