Results 1 to 6 of 6
  1. #1
    Join Date
    Jan 2011
    Posts
    2
    Rep Power
    0

    Default Program Question

    I do not want to seem as if I just want an answer to a homework problem. But I just want to know what exactly I could do to write code to accomplish the task.

    I am in a Java with Data Structures course and my professor gave me this:

    Solve A/BC + D/EF + G/HI = 1 where A, B,C,... I are {1,2,3,...9} and each digit is used exactly once. Here BC, EF, HI are concatenations rather than multiplications. e.g. If B = 3 and C = 5, BC would be the number 35 (not the product 3x5 = 15). (The solution is unique up to ordering of the fractions.)


    I would really appreciate some help.

    Thanks,

    Jim

  2. #2
    Join Date
    Jan 2011
    Posts
    2
    Rep Power
    0

    Default

    this is what i have so far:
    Java Code:
    public class StringProblem {
      public static void main(String[] args) {
        double a = 1;
        double d = 4;
        double g = 7;
        String b = "2";
        String c = "3";
        String e = "5";
        String f = "6";
        String h = "8";
        String i = "9";
        String first = b+c;
        String second = e+f;
        String third = h+i;
        double bc = Integer.parseInt(first);
        double ef = Integer.parseInt(second);
        double hi = Integer.parseInt(third);
        double answer = (a/bc) + (d/ef) + (g/hi);
        System.out.println(answer);
      }
    }

  3. #3
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,000
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by WickedBetrayal View Post
    I do not want to seem as if I just want an answer to a homework problem. But I just want to know what exactly I could do to write code to accomplish the task.

    I am in a Java with Data Structures course and my professor gave me this:

    Solve A/BC + D/EF + G/HI = 1 where A, B,C,... I are {1,2,3,...9} and each digit is used exactly once. Here BC, EF, HI are concatenations rather than multiplications. e.g. If B = 3 and C = 5, BC would be the number 35 (not the product 3x5 = 15). (The solution is unique up to ordering of the fractions.)


    I would really appreciate some help.

    Thanks,

    Jim
    First let's get rid of those ugly divisions: your problem is equvalent to the problem: A*EF*HI+D*BC*HI+G*BC*EF == BC*EF*HI. Variables A .. I are a permutation of the values 1 ... 9. We have to find a permutation such that the equality holds. The equation makes sense in mathematical notation as:

    A*(10*E+F)*(10*H+I)+D*(10*B+C)*(10*H+I)+G*(10*B+C) *(10*E+F) ==
    (10*B+C)*(10*E+F)*(10*H+I)

    (I hope I got that right ;-)

    Finding permutations isn't a trivial task but very well doable. The next method finds a next permutation (if there is one) given a current permutation in lexicographical order. Let a current permutation be P0 P1 P2 ... Pn;

    the steps are:

    Java Code:
    1) find a largest i such that Pi < P(i+1)
    2) if no such i exists there is no next permutation
    3) find a largest j such that j > i and Pj > Pi (such a value j always exists)
    4) swap values Pi and Pj
    5) reverse the subsequence P(i+1) .. Pn
    Those five steps produce a next permutation given a curent one: P1 ... Pn.

    You have to check all permutations starting at permutation 1, 2, 3 ... 9 and evaluate the equality above. If it holds you have found values for A ... I.

    kind regards,

    Jos
    Last edited by JosAH; 01-09-2011 at 09:54 AM.
    cenosillicaphobia: the fear for an empty beer glass

  4. #4
    nve5009 is offline Member
    Join Date
    Jan 2011
    Posts
    9
    Rep Power
    0

    Default

    I'm also having problems with this. I understand doing the A*EF*HI+D*BC*HI+G*BC*EF == BC*EF*HI to get ride of the divisions. Could you explain how A*(10*E+F)*(10*H+I)+D*(10*B+C)*(10*H+I)+G*(10*B+C) *(10*E+F) ==
    (10*B+C)*(10*E+F)*(10*H+I) is equal to the other equation.

    Also, the first step you said to do is find a largest i such that Pi < P(i+1). Does that mean I must increase all the variables by 1? How am I supposed to set up the first permutation? Do I just set A to 1, B to 2, and so on?

    Sorry I'm very confused. I'd appreciate any help. Thank You.

  5. #5
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,000
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by nve5009 View Post
    I'm also having problems with this. I understand doing the A*EF*HI+D*BC*HI+G*BC*EF == BC*EF*HI to get ride of the divisions. Could you explain how A*(10*E+F)*(10*H+I)+D*(10*B+C)*(10*H+I)+G*(10*B+C) *(10*E+F) ==
    (10*B+C)*(10*E+F)*(10*H+I) is equal to the other equation.
    If e.g. BC == 12 then B == 1 and C == 2; so mathemaTically 10*B+C == 10*1+2 == 12. The first notation is a symbolic notation, while the second is a methematical notation.

    Quote Originally Posted by nve5009 View Post
    Also, the first step you said to do is find a largest i such that Pi < P(i+1). Does that mean I must increase all the variables by 1? How am I supposed to set up the first permutation? Do I just set A to 1, B to 2, and so on?

    Sorry I'm very confused. I'd appreciate any help. Thank You.
    If you have a permutation, say, 14532, finding a largest i such that Pi < P(i+1) results in i == 1 because 4 < 5 and 4 is located at position 1. Next you have to find a largest j such that Pj > Pi. Pi == 4 and if j == 2 then Pj == 5 and 5 > 4. Swap Pi and Pj, so we get 15432 and next we have to reverse the subsequence starting at position i+1: 432, reversed we get 15234. Got it?

    You do have to set up the first permutation yourself, which is easy: 123456789

    kind regards,

    Jos

    edit: After rereading my own pseudo code I noticed that it was quite terse, so here is a Java implementation. This class permutes a char array with five elements:

    Java Code:
    import java.util.Arrays;
    
    public class T {
    
    	private static void swap(char[] s, int i, int j) {
    		char t = s[i];
    		s[i] = s[j];
    		s[j] = t;
    	}
    
    	public static char[] permute(char[] s) {
    
    		int i, j;
    
    		for (i = s.length - 1; --i >= 0;)
    			if (s[i] < s[i + 1])
    				break;
    
    		if (i < 0)
    			return null;
    
    		for (j = s.length; --j > i;)
    			if (s[i] < s[j])
    				break;
    
    		swap(s, i, j);
    
    		for (j = s.length; ++i < --j;)
    			swap(s, i, j);
    
    		return s;
    	}
    
    	public static void main(String[] args) {
    
    		char[] names = "ABCDE".toCharArray();
    
    		do {
    			System.out.println(Arrays.toString(names));
    		} while (permute(names) != null);
    	}
    }
    Last edited by JosAH; 01-13-2011 at 07:57 AM.
    cenosillicaphobia: the fear for an empty beer glass

  6. #6
    nve5009 is offline Member
    Join Date
    Jan 2011
    Posts
    9
    Rep Power
    0

    Default

    thanks for the response. I think I understand what to do now. I'll post again if I have anymore problems but thanks a lot

Similar Threads

  1. Database/Program Question PLEASE HELP
    By MacnCheese in forum JDBC
    Replies: 1
    Last Post: 12-01-2010, 06:49 AM
  2. Question about the program
    By mingming88 in forum New To Java
    Replies: 9
    Last Post: 08-25-2010, 03:45 PM
  3. question in java program
    By Moiz in forum New To Java
    Replies: 1
    Last Post: 09-13-2009, 11:33 PM
  4. Simple Paint program question
    By StressaJune in forum New To Java
    Replies: 1
    Last Post: 03-30-2009, 08:46 PM
  5. Question/Java Program
    By icedragon770 in forum Java Applets
    Replies: 7
    Last Post: 10-13-2008, 06:12 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •