Rechnnung

CStoll

Such mal nach "kleinstes gemeinsames Vielfaches" - das hilft sicher weiter

C++ Forumbot

Dieser Thread wurde von Moderator/in CStoll aus dem Forum C++ in das Forum Mathematik verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

Bashar

Versuch dich der Frage zu nähern, indem du erstmal das kleinste gemeinsame Vielfache nur der Zahlen von 1 bis 4 oder so bestimmst.

Whtthfck*

Hab mich auch mal an die Aufgabe gemacht.
Ich habe es mit lauter if-Abfragen versucht, sprich:

if((zahl * multi) % (zahl - 1) == 0)
    {
    if((zahl * multi) % (zahl - 2) == 0)
        { 
         ...

Das muss doch kürzer und eleganter gehen, aber ich check gerade nicht wie genau.
Brauche einen kleinen Denkanstoß.

CStoll

Schau mal in der Wikipedia unter kgV nach, dort findest du einen Algorithmus zur Berechnung (Euklid) - den kannst du Stück für Stück auf alle benötigten Zahlen anwenden:

kgV(1,2) = 2
kgV(2,3) = 6
kgV(6,4) = 12
...

(PS: Denk dir bitte einen brauchbaren Usernamen aus ;))

Whtthfck*

thx CStoll, hab mir da mal ne kleine Funktion geschrieben:

int kgV(int a,int b)
{
    int c = a*b;
    while(b != 0)
    {
        if(a > b)
        a = a - b;
        else b = b - a;
    }
    return c/a;
}

int ggT(int a,int b)
{
    while(b != 0)
    {
        if(a > b)
        a = a - b;
        else b = b - a;
    }
    return a;
}

PS: Was hast du gegen meinen Usernamen ?

Jester

wie wär's mit

ing kgV(int a, int b)
{
  return (a/ggT(a,b)) * b;
}

Dann hast Du a) den Code nicht zweimal dastehen und b) bist du besser gegen Überläufe abgesichert: a*b könnte sehr viel größer sein als kgV(a,b). Also erst dividieren und dann multiplizieren.

CStoll

Das sieht schonmal nicht schlecht aus, allerdings könntest du das Verfahren noch etwas beschleunigen ("moderner" Euklid-Algorithmus). Und redundante Berechnungen sind immer ungünstig:

int ggT(int a,int b)
{
  int h;
  while(b!=0)
  {
    h=a%b;
    a=b;
    b=h;
  }
  return a;
}

int kgV(int a,int b)
{
  return a*b/ggT(a,b);
}

PS: Was ich gegen deinen Namen habe? Den kann doch kein Mensch aussprechen - und wenn doch, denk mal über die Bedeutung nach

hmm....
9*8*7*5 = 2520.

alles zurückgeführt auf die Primzahlen von 1-10
(3*3) * (2*2*2) * 7 * 5

würde heissen, man müsste mindestens alle Pfzs zusammen multiplizieren.
2 * 3 * 5 * 7 * 11 * 13 * 17 * 19

Wäre aber schon 9699690.. Is das nich ein bischen zu hoch? Oo
Ausserdem kann man das auch nicht überall durch teilen.. o_O

Jester

Jo, du hast in Deinem Produkt eine 3 vergessen. Und die 11,13,17 und 19 haben dadrin nix verloren. 2520 ist das kgv(5,7,8,9)

life

Das sieht schonmal nicht schlecht aus, allerdings könntest du das Verfahren noch etwas beschleunigen (Steinscher Algorithmus).

public static boolean isEven(int a) {
		return (a & 1) == 0;
	}

	public static int computeGGT(int... params) {
		if (params.length == 1) {
			return params[0];
		}
		else if (params.length == 2) {
			int a = params[0];
			int b = params[1];
			int k = 0;
			while (isEven(a) && isEven(b)) {
				a >>= 1;
				b >>= 1;
				++k;
			}
			int t;
			if (!isEven(a)) {
				t = -b;
			} else {
				t = a;
			}
			while (t != 0) {
				while (isEven(t)) {
					t >>= 1;
				}
				if (t > 0) {
					a = t;
				} else {
					b = -t;
				}
				t = a - b;
			}
			return a << k;
		}
		else {
			int ggt = computeGGT(params[0], params[1]);
			for(int i = 2; i < params.length; i++) {
				ggt = computeGGT(ggt, params[i]);
			}
			return ggt;
		}
	}

	public static int computeKGV(int... params) {
		if(params.length == 1)
			return params[0];
		else if(params.length == 2) {
			return (params[0]/computeGGT(params[0], params[1]))*params[1];
		}
		else {
			int kgv = computeKGV(params[0], params[1]);
			for(int i = 2; i < params.length; i++) {
				kgv = computeKGV(kgv, params[i]);
			}
			return kgv;
		}
	}

	public static void main(String[] args) {
		int[] params = new int[10];
		for(int i = 0; i < params.length; i++) {
			params[i] = i+1;
		}
		System.out.println(computeKGV(params));
	}

@Jester:
die 11,13,17 und 19 waren natürlich für die aufgabe mit allen zahlen bis 20.

Jester

Achso, dann fehlen aber noch ein paar Faktoren.

Die 3 muß zweimal ins Produkt, da sie in der 9 zweimal drin ist. Die 2 muß sogar vier mal rein (wegen der 16).