Dakuan
Anmeldungsdatum: 2. November 2004
Beiträge: 6345
Wohnort: Hamburg
|
Ich suche nach einem Algorithmus, mit dem man, wenn möglich, das Verhältnis zweier Zahlen als Bruch zweier ganzer Zahlen darstellen kann, wobei das die kleinst möglichen Zahlen sein sollen. Um das zu verdeutlichen mal ein Beispiel aus der Praxis:
48000:44100 => 160:147
Gibt es so etwas?
|
Doc_Symbiosis
Anmeldungsdatum: 11. Oktober 2006
Beiträge: 4391
Wohnort: Göttingen
|
Du willst also einfach den gekürzten Bruch haben, richitg? In welcher Sprache soll's denn sein? Im Endeffekt musst Du beide Zahlen in ihre Primfaktoren zerlegen und bei beiden Zahlen vorkommende Faktoren streichen...
|
user_unknown
Anmeldungsdatum: 10. August 2005
Beiträge: 17552
Wohnort: Berlin
|
Man kann es rekursiv lösen:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | def ggt (z: Int, n: Int) : Int = {
if (n == 0) { println ("Div by zero"); ??? }
if (z == 0 || n == 1 || z == 1) z else
if (n > z) ggt (n, z) else
if (z % n == 0) n else
ggt (n, z % n)
}
def kuerzen (z: Int, n: Int) : (Int, Int) = {
val faktor = ggt (n, z)
(z/faktor, n/faktor)
}
kuerzen (196, 63)
// res9: (Int, Int) = (28, 9)
|
Hoppla - sehe, für (0/7) fehlt in kuerzen noch das Auffangen der 0 um auch dort div/0 zu verhindern.
|
MisterIgo
Anmeldungsdatum: 23. April 2009
Beiträge: 947
|
|
track
Anmeldungsdatum: 26. Juni 2008
Beiträge: 7174
Wohnort: Wolfen (S-A)
|
Dakuan schrieb: Ich suche nach einem Algorithmus, mit dem man, wenn möglich, das Verhältnis zweier Zahlen als Bruch zweier ganzer Zahlen darstellen kann, wobei das die kleinst möglichen Zahlen sein sollen. ... Gibt es so etwas?
Ja, schau mal hier → die Geschichte mit dem größten gemeinsamen Teiler. Brauchst Du gar nicht neu zu erfinden, sondern kannst du direkt dort abschreiben. (oder ggf. umschreiben) LG, track
|
Dakuan
(Themenstarter)
Anmeldungsdatum: 2. November 2004
Beiträge: 6345
Wohnort: Hamburg
|
Also das mit der Primfaktor Zerlegung ist mir auch eingefallen, aber das hätte bedeutet, dass ich auch noch einen Primzahlgenerator irgendwo abschreiben muss. Von Euklid hatte ich in meiner Schulzeit schon mal etwas gehört, aber diesen Algorithmus kannte ich noch nicht (da war ich wohl geistig abwesend). Ist aber genial einfach, genau das was ich gesucht hatte.
In C gibts das auch im FFmpeg Sourcecode:
Die wollen wohl auch Abtastraten umwandeln. Danke an alle Beteiligten!
|
MisterIgo
Anmeldungsdatum: 23. April 2009
Beiträge: 947
|
Dakuan schrieb: In C gibts das auch im FFmpeg Sourcecode:
Die wollen wohl auch Abtastraten umwandeln.
Rationale Zahlen gibts leider in wenigen Sprachen direkt eingebaut und sind in einigen Fällen deutlich komfortabler, als alles in Int umzurechnen und vor allem genauer als Float/Double. Und bei rationalen Zahlen kommt man dann automatisch zum Kürzen.
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12829
|
MisterIgo schrieb:
Rationale Zahlen gibts leider in wenigen Sprachen direkt eingebaut und sind in einigen Fällen deutlich komfortabler, als alles in Int umzurechnen und vor allem genauer als Float/Double. Und bei rationalen Zahlen kommt man dann automatisch zum Kürzen.
Ruby hat das z.B. | $ ruby -r rational -e 'p Rational(10,6)'
(5/3)
$ ruby -r rational -e 'p(10.to_r/6)'
(5/3)
|
Hatte ich schon mal erwähnt, dass Ruby die coolste Skriptsprache ist? 😉
|
user_unknown
Anmeldungsdatum: 10. August 2005
Beiträge: 17552
Wohnort: Berlin
|
Naja - wenn es nicht eingebaut ist, dann schreibt man es sich selbst. Eine praktische Übung beim Erlernen einer neuer Sprache ist es sowieso.
|
Dakuan
(Themenstarter)
Anmeldungsdatum: 2. November 2004
Beiträge: 6345
Wohnort: Hamburg
|
Hatte ich schon mal erwähnt, dass Ruby die coolste Skriptsprache ist? 😉
Nicht direkt, aber ich hatte es bereits vermutet.
|
rklm
Projektleitung
Anmeldungsdatum: 16. Oktober 2011
Beiträge: 12829
|
Dakuan schrieb: Hatte ich schon mal erwähnt, dass Ruby die coolste Skriptsprache ist? 😉
Nicht direkt, aber ich hatte es bereits vermutet.
😀
|