Seite 1 von 1

Produkt ohne Multiplikation

Verfasst: Sonntag 7. Oktober 2012, 17:56
von Xerxes
Hallo,

ich bin ganz neu in Python und vor allem habe ich noch nie programmiert!
Nun muss ich für die Schule jedoch ein kleines Programm schreiben, in dem zwei Zahlen multipliziert werden, jedoch ohne das Multiplikationszeichen zu benutzen.
Meine Überlegung war, das z.B.
Zahl 1 so oft addiert wird wie Zahl 2 "groß" ist.
Aber ich habe nicht die leiseste Ahnung, wie das in Python zu bewerkstelligen ist? Die Zahlen können direkt im Quelltext vorgegeben werden, es ist also keine Eingaberoutine nötig.

Kann mir bitte jemand helfen? Ich muss das morgen fertig haben. Bin total am verzweifeln, weil ich noch nicht einmal weiß wie ich das ganze Anfangen soll!
Nutze übrigens Python 2.7

Re: Produkt ohne Multiplikation

Verfasst: Sonntag 7. Oktober 2012, 18:09
von cofi
Willkommen im Forum!

Hier ein paar Tipps: Du brauchst eine `for`-Schleife und `range` (oder eine `while`-Schleife und `-`) und `+` sowie `=`.

Re: Produkt ohne Multiplikation

Verfasst: Sonntag 7. Oktober 2012, 18:19
von Barabbas
Mit operator.mul kannst du das Problem elegant umschiffen - statt des Multiplikations-Operators * kannst du so eine Multiplikations-Funktion benutzen :))

Re: Produkt ohne Multiplikation

Verfasst: Sonntag 7. Oktober 2012, 18:23
von EyDu
Wo wir schon bei kreativen Lösungen sind:

Code: Alles auswählen

def mul(a, b):
    return math.exp(math.log(a) + math.log(b))
Gut, über die Wertebereiche kann man jetzt streiten ^^

Re: Produkt ohne Multiplikation

Verfasst: Sonntag 7. Oktober 2012, 18:34
von Xerxes
Hmm also vielen Dank schonmal für eure Antworten. Bei den letzten beiden verstehe ich ehrlich gesagt noch weniger ^^
Der Tipp war das wir eine Schleife nehmen sollen. Ich hab dann jetzt einfach nochmal probiert und:

Code: Alles auswählen

zahl1 = 4
zahl2 = 5
i = 0
ergebnis = 0
while i < zahl1:
      sum = ergebnis + zahl2
print sum
Nach rumprobieren bekomme ich inzwischen wenigstens keinen Error mehr, aber ein Ergebnis wird so auch nicht ausgespuckt :-(

Die Zeile mit sum ist eingerückt.

MfG

Re: Produkt ohne Multiplikation

Verfasst: Sonntag 7. Oktober 2012, 18:41
von BlackJack
Ist immer wieder nützlich sich mal mit dem C64 beschäftigt zu haben, dessen Prozessor keine Multiplikation kennt:

Code: Alles auswählen

def mul(a, b):
    result = 0
    
    while True:
        if b & 1:
            result += a
        if not b:
            return result
        b >>= 1
        a <<= 1
(Die doofe Forensoftware macht aus einem `&` ein `&` :-()

@Xerxes: Was sagt denn die Bedingung von der Schleife? Wann wird die jemals unwahr? Und welche Anweisung sorgt Deiner Meinung nach dafür?

Statt zu sagen was eingerückt ist, könntest Du auch einfach Code-Tags benutzen, am besten die für Python. Es gibt da so eine Schaltfläche über dem Texteditorfeld wenn man einen Beitrag schreibt, da steht Python drauf.

Re: Produkt ohne Multiplikation

Verfasst: Sonntag 7. Oktober 2012, 18:48
von Xerxes

Code: Alles auswählen

zahl1 = 4
zahl2 = 6
i = 0
ergebnis = 0
while i < zahl1:
    ergebnis = ergebnis + zahl2
    i+=1
print ergebnis
Danke, jetzt geht es. Hab jetzt das mit sum rausgenommen und den Teil mit der Anweisung bedacht ;-)

Der von dir genannte Code gibt bei mir übrigens eine Fehlermeldung?!

Re: Produkt ohne Multiplikation

Verfasst: Sonntag 7. Oktober 2012, 18:59
von microkernel
Wenn du es wirklich kompliziert machen willst kannst du dir auch das hier mal anschauen Karatsuba Algorithmus :D

Re: Produkt ohne Multiplikation

Verfasst: Sonntag 7. Oktober 2012, 19:18
von BlackJack
@Xerxes: Hast Du den Quelltext auch entsprechend des Kommentars darunter geändert?

Re: Produkt ohne Multiplikation

Verfasst: Sonntag 7. Oktober 2012, 19:50
von EyDu
Da bereits vor dem Betreten der Schleife feststeht, wie oft die Schleife durchlaufen wird, solltest du eine for-Schleife statt einer while-Schleife verwenden. Und wie sieht es bei der Aufgabenstellung mit negativen Zahlen aus? Bei deiner Version würde man die Schleife niemals verlassen

Außerdem solltest du noch bedenken, welchen der beiden Summanden du zum Zählen verwendest. Starte dein Programm mal mit zahl1 =2, zahl2 = 1000000000000 und zahl1=1000000000000, zahl2 = 2. Du wirst in der Dauer deiner Berechnung einen kleinen Unterschied festellen. Es bietet sich daher an, die kleinere Zahl zum Zählen zu verwenden.

Re: Produkt ohne Multiplikation

Verfasst: Sonntag 7. Oktober 2012, 20:34
von Hyperion
Ich schlage noch dieses vor:

Code: Alles auswählen

from itertools import repeat

def mul(a, b):
    count = min(a, b)
    value = max(a, b)
    return sum(repeat(value, count))

mul(4, 5)
>>> 20

Re: Produkt ohne Multiplikation

Verfasst: Sonntag 7. Oktober 2012, 23:59
von EyDu
@BlackJack: Dein Ansatz ist ja sogar eine sinnvolle Lösung, so geht das nicht :D Gibt es einen Grund, warum du die Abbruchbedingung in die Schleife gezogen hast, statt einem einfachem ``while b`` und dem return nach der Schleife?

Code: Alles auswählen

import itertools

def mul(a, b):
    return sum(1 for _ in itertools.product(range(a), range(b))))

Re: Produkt ohne Multiplikation

Verfasst: Montag 8. Oktober 2012, 07:04
von BlackJack
@EyDu: Kein Grund, ich hab's einfach ohne nachzudenken runtergehackt. Für das sinnvoll entschuldige ich mich hiermit. :-D

Hier die Lösung in Haskell — da hat man das Problem mit dem & nicht. :-)

Code: Alles auswählen

import Data.Bits

mul :: Int -> Int -> Int
mul a b = mul' a b 0
    where mul' _ 0 r = r
          mul' a b r =
              mul' (shiftL a 1) (shiftR b 1) (if odd b then r + a else r)

Re: Produkt ohne Multiplikation

Verfasst: Montag 8. Oktober 2012, 13:36
von EyDu
@BlackJack: Hab ich auch vermutet, allerdings wollte ich meiner Müdigkeit kein Vertrauen mehr schenken. Die Entschuldigung wird natürlich angenommen :D

Ich hätte da noch etwas Triviales in C++:

Code: Alles auswählen

#include <iostream>

template <size_t x, size_t y>
struct mul {
    enum { value = x + mul<x, y-1>::value };
};


template<size_t x>
struct mul<x, 0> {
    enum { value = 0 };
};


int main(const int argc, char **argv) {
    std::cout << mul<5, 3>::value << std::endl;
    
    return 0;
}

Re: Produkt ohne Multiplikation

Verfasst: Montag 8. Oktober 2012, 14:14
von pillmuncher
Und endrekursiv in Prolog:

Code: Alles auswählen

bmul(A, B, R) :-
    A >= 0,
    B >= 0,
    C is A mod 2,
    bmul_(C, A, B, 0, T),
    R is T.

bmul_(0, 0, _, T, T) :- !.
bmul_(0, A, B, S, T) :- !, bmul_(A, B, S, T).
bmul_(1, A, B, S, T) :- !, bmul_(A, B, S + B, T).

bmul_(A, B, S, T) :-
    X is A >> 1,
    Y is B << 1,
    C is X mod 2,
    bmul_(C, X, Y, S, T).

Re: Produkt ohne Multiplikation

Verfasst: Montag 8. Oktober 2012, 14:26
von /me
Ich habe da noch eine Lösung in Oracles PL/SQL.

Zu Beginn definieren wir zwei Tabellen.

Code: Alles auswählen

CREATE TABLE FACTOR_1 (id  NUMBER(10));
CREATE TABLE FACTOR_2 (id  NUMBER(10));
Und schon können wir auf simpelste Art und Weise mit einem Kreuzprodukt die Berechnung durchführen.

Code: Alles auswählen

declare
    val1  NUMBER(10) := 3;
    val2  NUMBER(10) := 4;
    result NUMBER(10);
    
    i     NUMBER(10);
begin
    DELETE FROM FACTOR_1;
    DELETE FROM FACTOR_2;

    i := 0;
    loop
        if i < val1 then
            INSERT INTO FACTOR_1 VALUES(i);
        end if;
        if i < val2 then
            INSERT INTO FACTOR_2 VALUES(i);
        end if;
        if i >= val1 AND i >= val2 then
            exit;
        end if;
        i := i + 1;
    end loop;
    
    SELECT COUNT(*) 
      INTO result
      FROM factor_1, factor_2;
      
   dbms_output.put_line(result);
end;
Die einfach durchzuführende Anpassung an die Verwendung nur einer Tabelle überlasse ich dem geneigten Leser.

Re: Produkt ohne Multiplikation

Verfasst: Montag 8. Oktober 2012, 14:42
von BlackJack
``:=`` für Zuweisungen erinnert mich so an Pascal

Code: Alles auswählen

Program Multiplikation;

Var i, j: Word;

Function Mul(a: Word; b: Word): Word;
Begin
  Mul := 0;
  While b <> 0 Do
    Begin
      If b And 1 = 1 Then Mul := Mul + a;
      a := a SHL 1;
      b := b SHR 1;
    End;
End;

Begin
  For i := 0 To 10 Do
    For j := 0 To 10 Do
      WriteLn(Mul(i, j));
End.

Re: Produkt ohne Multiplikation

Verfasst: Montag 8. Oktober 2012, 19:00
von EyDu
Und die gruselige Zuweisung an den Funktionsnamen um den Rückgabewert zu erstellen.

Um den Bitshifting-Trend zu unterstützen, habe ich mal das C++-Template-Äquivalent umgesetzt. Ist ja nicht besonders viel zu ändern und sieht schon beinahe wie Haskell aus. Wenn man sich weit genug entfernt :)

Code: Alles auswählen

template<size_t x, size_t y>
struct mulShift {
    enum { value = (x & -(y&1)) + mulShift<x<<1, y>>1>::value };
};


template <size_t x>
struct mulShift<x, 0> {
    enum { value = 0 };
};

Edit: Grmpf. & und &

Re: Produkt ohne Multiplikation

Verfasst: Montag 8. Oktober 2012, 19:37
von BlackJack
In JavaScript sehr ähnlich. Besonderheit im Gegensatz zu Python kann man den eingebauten Zahlentyp um die Methode erweitern.

Code: Alles auswählen

Number.prototype.mul = function(other) {
    var result = 0, self = this;
    while (other) {
        if (other & 1) result += self;
        self <<= 1;
        other >>= 1;
    }
    return result;
}