kgV und ggT von x Zahlen

**TobiaZ** · 13.05.2004, 13:18

ganz spontan: schleifen...

**icon** · 13.05.2004, 13:20

so berechnet man das ggt (ist ein methode aus java -> musst du noch auf php umbauen)

Code:

public int ggt (int a, int b)
	{
		do
		{
			while (a>b)
			{
				a=a-b;
			}

			while (b>a)
			{
				b=b-a;
			}
		}
		while (a!=b);

		return b;	
	}

lg, harry d.

**chansel0049** · 13.05.2004, 13:22

@ Tobiaz
Das wäre nicht gerade effektiv, oder ? Schliesslich hätte ich dann so was wie x^x-1 schleifendurchläufe für ein unbekanntes x!

**icon** · 13.05.2004, 13:26

Original geschrieben von chansel0049
@ Tobiaz
Das wäre nicht gerade effektiv, oder ? Schliesslich hätte ich dann so was wie x^x-1 schleifendurchläufe für ein unbekanntes x!

und will soll man so etwas sonst realisieren

ich glaube ich habe den oben genannten algorithums aus dem adim-scriptum für standard c und ich habe bis jetzt noch keinen anderen gefunden, der es besser, schnell oder effizienter schafft das ggt zu ermitteln..

naja.. mach damit was du willst..

mfg.- harry d.

**chansel0049** · 13.05.2004, 13:27

@icon: selbe problem, selbst bei kleinem x habe ich bereits enorme Schleifendurchläufe um den einen gemeinsamen kgv von x zahlen zu berechnen

**Abraxax** · 13.05.2004, 13:29

dann nimm doch das ding aus dem mathebuch der klasse 5 ...

**icon** · 13.05.2004, 13:30

ich verstehe dein problem echt nicht..

entwerder du willst das ggt ermitteln oder nicht..

wenn ja dann NUR mit schleifen und wenn nein, dann lass es doch einfach..

und noch etwas: für einen normalen server (ich nehme einmal an er hat über 200mhz und 16mb speicher..*gg*) ist so etwas eine spielerei die ihn eigentlich nicht belastet außer du führst das script 50 mal pro sekunde aus..

harry

**chansel0049** · 13.05.2004, 13:32

@ icon

Klar ist der Code richtig und sicher auch der effektivste aber das für ! zwei ! Zahlen,

aber mein problem ist wie mache errechne ich das für 3, 5, 7, 10 oder X zahlen wenn ich das eine Ergebnis haben will, dass gilt für
x1 und x2 und x3 und x4 ....

also y == ggt(x1,x2) == ggt(x2,x3) == ggt(x1,x3) == ...

**icon** · 13.05.2004, 13:38

Original geschrieben von chansel0049

also y == ggt(x1,x2) == ggt(x2,x3) == ggt(x1,x3) == ...

das wäre sicher eine möglichkeit

eine andere:

wieder eine schleife nehmen

und die beste:

das codeschnipsel von mir einfach modifizieren

lg, harry d.

**chansel0049** · 13.05.2004, 13:41

das wäre sicher eine möglichkeit

Nein man wärs nicht! Sondern eine Bedingung!

Die bedingung ist dass y der ggt aller beliebiger Zahlenpaare der Reihe ist.!

**icon** · 13.05.2004, 13:46

habe damit gemeint, dass es eine möglichkeit der programmiertechnischen umsetztung wäre.- den mathematischen background habe ich da gar nicht gemeint..

und noch etwas:

manchmal kann die suche auch hilfreich sein:

zb: http://www.pi.informatik.tu-darmstad...ecialMath.html oder http://www.php-resource.de/forum/sho...&highlight=ggT

harry

**chansel0049** · 13.05.2004, 13:57

@icon

Danke für die Tipps, nur helfen die kein bischen! Ist schliesslich auch nicht so als ob ich

1.) nicht suchen könnte
2.) nicht diese funktionen kennen würde

Mein Problem:

Das problem is das ich auf der such bin nach einer Lösung,
die das ggT einer ganzen Reihe berechnet:

3, 15, 18, 9

das Ergebnis hier ist 3 denn 3 teilt jede der Zahlen 3,15,18,9

Wenn ich hier einfach auf dem langen Draht stehe tuts mir leid! Aber ich glaube du hast nicht mein Prolem verstanden

**TobiaZ** · 13.05.2004, 14:02

Lösungen stehen ja schon da.

im übrigen sehe ich keinen grund

ig zu werden.

**icon** · 13.05.2004, 14:04

Aber ich glaube du hast nicht mein Prolem verstanden

habe dir meine lösungsvorschläge zwar schon ~4 post vorher mitgeteilt aber naja..

noch einmal:

entweder du baust den algorithmus in eine weitere schleife:

[CODE]

for ($i=0;$i<=count[$values]-2;i++)
{
if ($ggt >= ggt($i,($i+1))) ggt = ggt($i,($i+1));
}

[CODE]

die in etwa so irgendwie ausschauen könnte

oder du baust die funktion einfach auf deine bedürfnisse um..!- da wirst du zwar ein weilchen brauchen, aber es ist mit sicherheit auch schaffbar..

mfg.- harry d.

kgV und ggT von x Zahlen