Hvordan finne største felles-nevner på 3 integer?

[arna]

Det jeg ønsker å gjøre er å skrive inn 3 tilfeldige tall, og så finne ut hvilket tall som er det høyeste felles delelige med alle tallene. Som f.eks

 

203, 91, 77 = 7

30, 10, 5 = 5

 

Det finnes allerede en ganske kjent algoritme for dette med 2 integer's. Også kallt Euclid's algorithm på fag-språket. Primært med denne koden (med og uten rekursjon) Les mer om denne på Wikipedia

 

function gcd(a, b)
    if b = 0 return a
    else return gcd(b, a mod b)

int gcd(int a, int b) {
 int t;
 while (b != 0) {
   t = b;
   b = a % b;
   a = t;
 }
 return a;
}

 

Forøvrig må jeg nevne at etter uttallige sjekker på google->søk fant jeg bl.annet dette utdraget: (Har hjulpet meg litt, men sliter litt med å skrive en kort og konsis kode uten ett utall av if og elser....

Another approach is to start with three numbers x, y, and z.  Label

them so that z is the smallest.  Divide

 

  x = Q1*z + R1,  0 <= R1 < z,

  y = q1*z + r1,  0 <= r1 < z.

 

Then replace x and y by R1 and r1, relabel the numbers x, y, and z, so

that the new z is the smallest nonzero number of the three, and

repeat.  Continue until both remainders are zero.  Then the last z

will be the GCD of all three numbers.

 

Example:  Find the GCD of 203, 91, and 77.

 

  original {x,y,z} = {203,91,77}

  203 = 2*77 + 49,

    91 = 1*77 + 14,

 

  new {x,y,z} = {77,49,14},

  77 = 5*14 + 7,

  49 = 3*14 + 7,

 

  new {x,y,z} = {14,7,7},

  14 = 2*7 + 0,

    7 = 1*7 + 0,

 

Both remainders are 0, so GCD = last z = 7.

 

GCD is 7.

 

 

Noen som har tips på å løse denne problemstillingen?

[lnostdal]

gcd er assosiativ, noe som vil si:

 

SWGtk> (defun my-gcd (a b)
         (if (zerop b)
             a
             (my-gcd b (mod a b))))
my-gcd
SWGtk> (my-gcd (my-gcd 203 91) 77)
7
SWGtk> (my-gcd 203 (my-gcd 91 77))
7
SWGtk> (my-gcd 30 (my-gcd 10 5))
5
SWGtk> (my-gcd (my-gcd 30 10) 5)
5

 

Common Lisp har allerede en funksjon `gcd' som tar et vilkårlig antall argumenter - derfor navnet `my-gcd'.

 

edit: rettet på indenteringen - som dette forumet fortsatt klusser til ... :|

 

edit2: en iterativ versjon, bare for morro:

(defmacro while (pred &body body)
  (let ((result (gensym)))
    `(let ((,result nil))
       (do () ((not ,pred) ,result)
         (setf ,result (progn ,@body))))))

(defun my-gcd2 (a b)
  (let ((tmp b))
    (while (not (zerop b))
      (setf b (mod a b))
      (setf a tmp))))

Endret 2. september 2006 av lnostdal

[arna]

gcd er assosiativ, noe som vil si:

 

SWGtk> (defun my-gcd (a b)
         (if (zerop b)
             a
             (my-gcd b (mod a b))))
my-gcd
SWGtk> (my-gcd (my-gcd 203 91) 77)
7
SWGtk> (my-gcd 203 (my-gcd 91 77))
7
SWGtk> (my-gcd 30 (my-gcd 10 5))
5
SWGtk> (my-gcd (my-gcd 30 10) 5)
5

 

Common Lisp har allerede en funksjon `gcd' som tar et vilkårlig antall argumenter - derfor navnet `my-gcd'.

 

edit: rettet på indenteringen - som dette forumet fortsatt klusser til ... :|

 

edit2: en iterativ versjon, bare for morro:

(defmacro while (pred &body body)
  (let ((result (gensym)))
    `(let ((,result nil))
       (do () ((not ,pred) ,result)
         (setf ,result (progn ,@body))))))

(defun my-gcd2 (a b)
  (let ((tmp b))
    (while (not (zerop b))
      (setf b (mod a b))
      (setf a tmp))))

6788222[/snapback]

 

 

Har virklig lyst til å komme med masse banneord nå ettersom det bare var å putte uttrykket inni det andre uttrykket

 

Men da et annet spørsmål; Hvordan vet man om en funksjon er 'assosiativ' ?

[lnostdal]

når man setter inn tall for x, y og z og konstanterer at (x * y) * z = x * (y * z) er sannt så er * en assosiativ funksjon/operatør

Endret 2. september 2006 av lnostdal

[lnostdal]

så noe slikt da:

 

cl-user> (defun associativep (operation &optional (x 1) (y 2) (z 3))
           (flet ((opr (p q) (funcall operation p q)))
             (= (opr x (opr y z))
                (opr (opr x y) z))))
associativep
cl-user> (associativep #'+)
t
cl-user> (associativep #'-)
nil
cl-user> (associativep #'*)
t
cl-user> (associativep #'/)
nil

 

regner med at du ser hva som foregår - ta dette som pseudokode; jeg gidder ikke rote med C ATM :}

 

edit: forumet ødlegger indenteringen igjen

Endret 2. september 2006 av lnostdal