Brute Force

This is a discussion on Brute Force within the C Programming forums, part of the General Programming Boards category; Hi, I'm new to Algorithm And Analysis, I just started and found some problem, that is Brute Force, In the ...

  1. #1
    Registered User
    Join Date
    Sep 2010
    Posts
    3

    Smile Brute Force

    Hi, I'm new to Algorithm And Analysis, I just started and found some problem, that is Brute Force,

    In the Example,

    GCD(m,n)

    Brute Force - Consecutive Integer Checking
    Step 1 - Assign the value of min {m,n} to t

    Step 2 - Divide m by t. If the remainder of this division is 0, go Step 3, otherwise Step 4

    Step 3 - Divide n by t. If the remainder of this division is 0, return the value of t as the answer and stop. Otherwise go Step 4

    Step 4 - Decrease the value of t by 1. Go to Step 2

    My Question is: I completely don't understand this clearly, Can someone help explain to me? Thanks for the help...

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    What part don't you understand?

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Sep 2010
    Posts
    3
    Thanks for replying!

    Lets use this example GCD(60,24)

    Step 1 - What is min {m,n} ? after get the value assign to t, what is "t" ? Remainder?

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,442
    Try min stands for minimum.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by 123sample View Post
    Thanks for replying!

    Lets use this example GCD(60,24)

    Step 1 - What is min {m,n} ? after get the value assign to t, what is "t" ? Remainder?
    You're looking for the greatest common denominator, and 24 is the minimum of the set with {60, 24}.

    Clearly, the gcd can not be larger than 24, so that's your starting point.

    With C, if you want to check just the remainder first, I might use the modulus operator: %.

    So m=60, n=24, and t=24, we want to know if m%t==0. And we need to make that check in a loop:


    Code:
    while (t > 1) {
      if(m % t == 0) {  //got one denominator
        //repeat with n 
            //if t is common to m and n, that's the gcd - break here
      }
      decrement t;
    }
    
    //print out the gcd you found

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Running a Brute Force Attack Simulation...
    By Junior89 in forum C++ Programming
    Replies: 31
    Last Post: 02-13-2011, 07:52 PM
  2. 2d array Brute force test
    By grimuth in forum C++ Programming
    Replies: 5
    Last Post: 04-08-2010, 10:01 AM
  3. Brute Force
    By swgh in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 08-16-2007, 01:41 AM
  4. Replies: 2
    Last Post: 03-21-2004, 07:21 PM
  5. Help : Brute Force String KeyGen
    By Tangy in forum C++ Programming
    Replies: 11
    Last Post: 03-11-2002, 08:01 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21