Algorithmen II

def max2(a, b):
    if a > b:
        return a
    else:
        return b
 
def max3(a, b, c):
    return max2(max2(a, b), c)
 
print(max3(int(input('a')), int(input('b')), int(input('c'))))

def sort(a, b, c):
    if a > b:
        if b > c:
            print(a, b, c)
        elif a > c:
            print(a, c, b)
        else:
            print(c, a, b)
    elif b > c:
        if a > c:
            print(b, a, c)
        else:
            print(b, c, a)
    else:
        print(c, b, a)
 
sort(input(), input(), input())

def multiply(a, b):
    """Multipliziert zwei natürliche Zahlen ohne Verwendung der Python-Multiplikation."""
    result = 0  # Null ist das neutrale Element bezüglich der Addition.
    while b > 0:
        result = result + a
        b = b - 1
    return result
 
def exponentiate(a, b):
    """Berechnet a hoch b nur mit Addition."""
    result = 1  # Eins ist das neutrale Element bezüglich der Multiplikation.
    while b > 0:
        result = multiply(result, a)
        b = b - 1
    return result
 
def divide(dividend, divisor):
    """Berechnet die Ganzzahldivision mit Rest nur mit Addition & Subtraktion."""
    quotient = 0
    while dividend >= divisor:
        dividend = dividend - divisor
        quotient = quotient + 1
 
    # Jetzt ist dividend kleiner als divisor - dividend ist nun der Rest.
 
    # In Python können wir mehrere Werte zurückgeben, durch Komma getrennt:    
    return quotient, dividend
 
def is_power_of_2(n):
    """Gibt True zurück, falls n eine Zweierpotenz ist, sonst False."""
    test = 1
    while test < n:
        test = multiply(test, 2)
    return test == n
 
a = input("a")
b = input("b")
print(str(a) + " * " + str(b) + " = " + str(multiply(a, b)))
print(str(a) + " ^ " + str(b) + " = " + str(exponentiate(a, b)))
 
quotient, rest = divide(a, b)
print(str(a) + "/" + str(b) + " = " + str(quotient) + " Rest " + str(rest))
 
print(str(a) + " ist eine Zweierpotenz: " + str(is_power_of_2(a)))
print(str(b) + " ist eine Zweierpotenz: " + str(is_power_of_2(b)))

def quersumme(x):
    summe = 0
    while x > 0:
        ziffer = x % 10
        summe = summe + ziffer
        x = x // 10
    return summe
 
print(quersumme(413))

import math
 
def is_divisor(dividend, divisor):
    """Gibt True zurück, wenn divisor ein ganzzahliger Teiler von dividend ist, sonst False."""
    return dividend % divisor == 0
 
def is_prime(n):
    """Gibt True zurück, falls n eine Primzahl ist, sonst False."""
    if n < 2:
        return False
    i = 2
    # Es reicht, bis zur Wurzel von n zu testen - gäbe es einen grösseren Teiler t so dass
    # t*x == n, dann müsste x kleiner sein als Wurzel(n) und wir hätten x bereits gefunden.
    while t <= math.sqrt(n):
        if is_divisor(n, t):
            # Wir haben einen Teiler gefunden -> keine Primzahl, beenden.
            return False
        t = t + 1
    # Keinen Teiler gefunden -> wir haben eine Primzahl!
    return True

Mit den Funktionen is_prime und is_divisor von oben:

def next_prime(n):
    """Gibt die nächstgrössere Primzahl grösser als n zurück."""
    next = n + 1
    while not is_prime(next):
        next = next + 1
    return next
 
def prime_factors(n):
    """Gibt die Prim-Faktoren von n in aufsteigender Folge zurück."""
    factor = 2  # first prime
    remainder = n
    # Divide n by the increasing prime numbers until we reach 1.
    while remainder > 1:
        # For each prime, divide the remainder as long as the prime is
        # a divisor.
        while is_divisor(remainder, factor):
            remainder = remainder / factor
            print(factor)
            # yield factor
 
        # remainder can no longer be divided by factor -> try with the next prime.
        factor = next_prime(factor)
 
prime_factors(int(input()))

def ggt(a, b):
    """Berechnet den grössten gemeinsamen Teiler von a und b."""
    while b > 0:
        rest = a % b
        a = b
        b = rest
    return a
 
print(ggt(544, 391))

def wurzel(n, precision=0.0001):
    """Quadratwurzel nach Heron."""
    # Grundidee: Ein Rechteck mit Fläche n
    # wird schrittweise in ein Quadrat transformiert.
    # Invariante: a * b == n
    # Die wahre Quadratwurzel liegt zwischen a und b.
    a = n
    b = 1
    while a - b > precision:
        a = (a + b) / 2  # Mittelwert der beiden Seiten.
        b = n/a
    return a
 
print(wurzel(225))