Results 1 to 3 of 3

Math Help - Algorithm

  1. #1
    Senior Member
    Joined
    Apr 2006
    Posts
    401

    Algorithm

    Suppose that you're given a 3 by 3 table of pos. integers. For any step, you are either able to double each of the #s in any 1 row (horizontal), or you are able to subtract 1 from each of the #s in any 1 column (vertical). Come up with an algorithm that transforms the orig. table into a table of all 0's.

    Note: need this explained in words how it works (not any pseudocode or programming), and showing an example of how this works.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Glaysher's Avatar
    Joined
    Aug 2006
    From
    Newton-le-Willows
    Posts
    224
    Start with first column

    Keep subtracting 1 from each entry in the column until one of the entries is 1 then

    i) Double the entries in the row the 1 is in
    ii) Subtract one from each entry in the first column

    Do this until you have two entries in the column that are 1 then

    i) Double the entries in the rows the 1s are in
    ii) Subtract one from each entry in the first column

    Do this until all entries in the first column are 1 then

    i) Subtract one from each entry in the first column

    The frst column's entries are now all zeroes.

    You can now repeat this procedure for the second and third columns as doubling zeroes will not change the number
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Glaysher's Avatar
    Joined
    Aug 2006
    From
    Newton-le-Willows
    Posts
    224
    Can improve the efficiency of the algorithm by targeting the column with the highest entry at each stage
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. algorithm
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: January 19th 2010, 02:46 AM
  2. Algorithm
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: November 22nd 2009, 07:11 AM
  3. algorithm
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: July 16th 2008, 01:29 PM
  4. Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 27th 2008, 01:02 PM
  5. gcd algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 4th 2007, 11:47 PM

Search Tags


/mathhelpforum @mathhelpforum