Entwickler-Ecke

Basistechnologien - Größte Teiler einer Zahl


GURKE deluxe - Mi 13.10.10 03:28
Titel: Größte Teiler einer Zahl
Hallo,
Ich habe ein Text mit einer bestimmen Länge. Nun stelle man sich vor, jedes Zeichen vom Text entspricht ein Pixel eines Bildes.
Nun weiß ich aber nicht wie groß das Bild werden soll. Soll heißen wie breit und wie hoch es sein muss.

Ich habe dazu ein Code geschrieben der die Zahlen ausrechnet, die multipliziert die Textlänge ergeben und dessen Differenz die geringste ist:

C#-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
 
int kleinstedifferenz = Convert.ToInt16(tbPasswort.Text);
int[] Teiler = new int[2];

for (int i = Convert.ToInt32(tbPasswort.Text); i > 0; i--)
{
    for (int j = Convert.ToInt32(tbPasswort.Text); j > 0; j--)
    {
        if ((i * j == Convert.ToInt32(tbPasswort.Text)) && (Math.Abs(i-j) < kleinstedifferenz))
        {
            kleinstedifferenz = Math.Abs(i - j);
            Teiler[0] = i;
            Teiler[1] = j;
        }
    }
}


Nun ist bei mir die Textlänge gerne mal so bei 50.000 Zeichen, folglich bearbeitet er 50000² ->2.500.000.000 Kombinationen! Das dauert natürlich viel zu lange.

Habt ihr eine gute Idee, wie ich schneller an die beiden Teiler ran komme?



GURKE


GURKE deluxe - Mi 13.10.10 04:29
Okay, habs rausbekommen:

C#-Quelltext 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
 
int Zahl = 100;
    int x = Convert.ToInt32(Math.Round(Convert.ToDouble(Math.Sqrt(Convert.ToDouble(Zahl)))));
    int y = x;

    for (; x * y != Zahl; )
    {
        if (x * y == Zahl)
            return;
        if (x * y < Zahl)
            x++;
        if (x * y > Zahl)
            y--;
    }


Zahl ist die Zahl dessen Teiler gesucht werden. x und y sind die Teiler. Bei 25000 hat er knapp ne Sekunde gerechnet.



GURKE


Kha - Mi 13.10.10 18:04
Du kannst auch x von 2 ab hochzählen, falls Zahl % x == 0 ist dann Zahl / x der größte echte Teiler.
Und mit dem Convert hast du dich ein bisschen übernommen :) , es gibt immer direktere Varianten der Methoden dieser Klasse.

C#-Quelltext 
1:
 
int x = (int)Math.Sqrt(Zahl); // abrunden


GURKE deluxe - Do 14.10.10 03:14
Stimmt, an die %-Methode habe ich gar nicht gedacht, war wohl schon zu spät :D

user profile iconKha hat folgendes geschrieben Zum zitierten Posting springen:
Du kannst auch x von 2 ab hochzählen, falls Zahl % x == 0 ist dann Zahl / x der größte echte Teiler.
Und mit dem Convert hast du dich ein bisschen übernommen :) , es gibt immer direktere Varianten der Methoden dieser Klasse.

C#-Quelltext 
1:
 
int x = (int)Math.Sqrt(Zahl); // abrunden


Rundet er dann durch das "(int)" ab?


Gurke


DuxGladii - Do 14.10.10 08:53

C#-Quelltext 
1:
 
int x = (int)Math.Round(Math.Sqrt(Zahl));


wäre einfacher zu lesen :)


Kha - Do 14.10.10 09:33
user profile iconDuxGladii hat folgendes geschrieben Zum zitierten Posting springen:

C#-Quelltext 
1:
 
int x = (int)Math.Round(Math.Sqrt(Zahl));


wäre einfacher zu lesen :)
Und macht etwas anderes :gruebel: ?

Dass ein Cast nach int abrundet, ist eine Eigenschaft aller C-artigen Sprachen, sodass die meisten Programmierer das als bekannt (bzw. nachschlagbar) voraussetzen und ohne groß zu überlegen einsetzen :) .


DuxGladii - Do 14.10.10 10:07

C#-Quelltext 
1:
 
int x = Convert.ToInt32(Math.Round(Convert.ToDouble(Math.Sqrt(Convert.ToDouble(Zahl)))));


ist unnötig kompliziert, macht aber das gleiche wie meine Variante. Wieso also nicht die weniger komplizierte benutzen?


Ralf Jansen - Do 14.10.10 10:49
Zitat:
Und macht etwas anderes :gruebel: ?


Natürlich. Der Cast rundet ab (oder genauer rundet nach 0). Math.Round rundet zur nächsten Zahl und nicht grundsätzlich ab. (Beispiel z.B. Sqrt von 8, abrunden würde 2 ergeben mit runden aber natürlich 3) Ich habe den Thread jetzt aber nicht soweit verfolgt welches der beiden Version richtiger/gewünschter ist.


Kha - Do 14.10.10 16:57
user profile iconDuxGladii hat folgendes geschrieben Zum zitierten Posting springen:
[...]ist unnötig kompliziert, macht aber das gleiche wie meine Variante. Wieso also nicht die weniger komplizierte benutzen?
Du hast dich also auf den originalen Code bezogen, es sah aber so aus, als würdest du dich auf meinen beziehen. Deshalb meine rhetorische Frage, dass das weder äquivalent noch einfacher aussieht ;) .
Und im Bezug zu Teilertests schadet Aufrunden zwar nichts, aber striktes Abrunden genügt.


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!