Archiv der Kategorie: Programmieren (allgemein)

Division mit Rest: Modulo und Divisor

Modulo

Ein oft gebrauchtes Instrument in der Programmierung ist Modulo, der Rest einer Division. Bei einer Division zweier Zahlen (Divident : Divisor) erhält man oft ein Ergebnis (Quotient), bei der keine glatte Ganzzahl herauskommt, also einen Bruchwert. Dies ist der Rest der Division, und man bekommt den ganzzahligen Restwert so heraus: Weiterlesen

Euklidischer Algorithmus

Den größten gemeinsamen Teiler (ggT) von zwei Zahlen, findet man mit dem Euklidischen Algorithmus.

am einfachsten verdeutlicht an diesem Beispiel:
Gegeben sind die beiden Ganzzahlen:

    a = 24
    b = 14

Die jeweiligen Teilermengen sind (Ganzzahlen):

24: 1,2,3,4,6,8,12,24
14: 1,2,7,14

Es finden sich hier 2 Zahlen, die in beiden Reihen vorkommen: 1,2. Dies sind die gemeinsamen Teiler von 24 und 14.

Wie sieht nun der Algorithmus aus, um den größten gemeinsamen Teiler zu finden?

1. wenn (a == b) dann {ggT = a}
2. wenn (a < b)  dann {b=b-a und Goto 1.} 
3. wenn (a > b)  dann {a=a-b und Goto 1.}

Schreibtischtest:

┌─────────────┬───────────────────────────────┐
│ Variablen   │  Vergleich und Operation      │
╞═════════════╪═════════╪═════╪═══════════════╡
│ a=24, b=14  |  a == b |  n  |               │
│             |  a < b  |  n  |               │
│             |  a > b  |  j  |  a= 24-14 =10 │
│ a=10, b=14  |  a == b |  n  |               │
│             |  a < b  |  j  |  b= 14-10 = 4 │
│ a=10, b= 4  |  a == b |  n  |               │
│             |  a < b  |  n  |               │
│             |  a > b  |  j  |  a= 10-4  = 6 │
│ a= 6, b= 4  |  a == b |  n  |               │
│             |  a < b  |  n  |               │
│             |  a > b  |  j  |  a=  6-4  = 2 │
│ a= 2, b= 4  |  a == b |  n  |               │
│             |  a < b  |  j  |  b=  4-2  = 2 │
│ a= 2, b= 2  |  a == b |  j  |  ggT=2        │
└─────────────┴─────────┴─────┴───────────────┘