Größte Teiler einer Zahl

GURKE deluxe · Verfasst: Mi 13.10.10 03:28

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:

markieren

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 · Verfasst: Mi 13.10.10 04:29

Okay, habs rausbekommen:

markieren

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 · Verfasst: 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.

markieren

C#-Quelltext

1:	int x = (int)Math.Sqrt(Zahl); // abrunden

_________________
>λ=

GURKE deluxe · Verfasst: Do 14.10.10 03:14

Stimmt, an die %-Methode habe ich gar nicht gedacht, war wohl schon zu spät

Kha hat folgendes geschrieben :

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.

markieren

C#-Quelltext

1:	int x = (int)Math.Sqrt(Zahl); // abrunden

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

Gurke

DuxGladii · Hält's aus hier Beiträge: 8 Win7 VS2010, C#

markieren

C#-Quelltext

1:	int x = (int)Math.Round(Math.Sqrt(Zahl));

wäre einfacher zu lesen

Kha · Verfasst: Do 14.10.10 09:33

DuxGladii hat folgendes geschrieben :

markieren

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 · Hält's aus hier Beiträge: 8 Win7 VS2010, C#

markieren

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 · Verfasst: 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 · Verfasst: Do 14.10.10 16:57

DuxGladii hat folgendes geschrieben :

[...]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.

_________________
>λ=

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme