Hier mal was für Mathematiker :D

Ich habe eine unbestimmte Anzahl von Zahlen und muss deren kleinstes gemeinsames Vielfaches und grössten gemeinsamen Teiler
errechnen. Klar steht die Formel in jedem Mathebuch und ist Niveau Klasse 5 oder so, aber irgendwie steh ich auf dem Schlauch einen ordentlichen Algorithmus zu finden der nicht einfach x1 * x2 *x3 etc
auswirft

Zum Hintergrund: Es geht um ausgewogene symmetrische Tabellen mit unbestimmter Anzahl von Spalten / Zeilen

Jemand ne Idee

ganz spontan: schleifen...

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


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.

@ 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!

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.

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

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

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

@ 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) == ...

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.

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.!

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-darmstadt.de/icpcSem/web/standardcode/java/math/SpecialMath.html oder http://www.php-resource.de/forum/showthread.php?s=&threadid=10918&highlight=ggT


harry

@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

Lösungen stehen ja schon da.

im übrigen sehe ich keinen grund :motz: ig zu werden.

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.

sorry, sollte nicht :motz: ig sein

nur ist das problem eben nicht gelöst:

Nochmal eine längere Erklrung
1.) aus einer csv kommen y Zeilen mit jeweils unterschiedlich vielen Spalten (x) mit Zahlen
2.) diese Zahlen sollen nun symmetrisch in einer Tabelle dar gestellt werden Bsp:

<csv>
1,4,7,23,456
3,6
3456,567,34576,123
123,454,2
</csv>

das soll nun so dargestellt werden, dass auf jeder zeile nur x Spalten sind, die allerdings gleich gross sind (geändert : alle spalten einer Zeile sind gleichgross also symmetrisch).

was hat es dann mit den zahlen auf sich, wenn sowieso alle spalten gleich breit dargestellt werden sollen.. :confused:

da würde es ja meiner meinung nach reichen, die gesamtbreite durch die anzahl der zahlen zu dividieren, um die breite zu erhalten oder sehe ich da jetzt etwas falsch..?!


mfg.- harry d.

Beim nochmal drüber nachdenken:

Habe wahrscheinlich falsch gedacht,

danke für die Posts löse jetzt das problem in dem ich das Reihenprodukt p bilde und den Wert (p/xk) als spaltenbasis nehme


danke nochmal

es ging nie um die Zahlen sondern um die Anzahl der Zahlen je Reihe.

Alle spalten einer Zeile sind gleichgross also symmetrisch

die einfache division (maximale Anzahl/ Anzahl in Reihe k) würde zu unsymmetrischen Tabellen führen!

Danke trotzdem

weiss zwar immer noch nicht was du damit genau meinst, aber hauptsache du hast die lösung und wirst glücklich damit.. ;)


lg, harry d.

hmm,

irgendwie erkenne ich das problem nicht?!

du mußt doch nur jede zahl in ihre primfaktoren zerlegen, wobei du jeden faktor pro zahl in ein array tust, array_intersect leifert dir ein UND über alle arrays ... ggT?

und wenn ich mich richtig erinnern mußt du fürs kgV alle werte, die nur in einem array vorkommen + die werte, die mehrfach vorkommen einmal verwenden ...

etwas kompliziert, aber:

4 6 7 9

2 2 7 3
2 3 1 3

hier also
3 * 3 * 2 * 2 * 7 = kgV ?

fürs ggT auch noch, weils so schön ist :)

27 36 16 48
03 02 02 02
03 02 02 02
03 03 02 03
01 03 02 02
01 01 01 02

keines

28 36 16 48
02 02 02 02
02 02 02 02
07 03 02 03
01 03 02 02
01 01 01 02

4 ....