Forum: Offtopic Mathematik Optimierungsproblem


von Mario G. (mario)


Angehängte Dateien:

Lesenswert?

Ich grüble gerade an einem auf den ersten Blick einfachem 
Optimierungsproblem, folgende Situation:

Gegeben ist ein Rechteck (Kantenlängen w und h) und ausserdem ein 
Anzahl von Quadraten n. Nun soll die Seitenlänge der Quadrate s so 
bestimmt werden, das die Fläche des Rechtecks optimal ausgenutzt wird. 
n ist Ein Element natürlicher Zahlen von 1...m.

Zum Zeitpunkt der Bestimmung von s steht n natürlich fest.

Also z.B. w = 1000, h = 300, n = 7
Wie bestimmt man nun s so das der Platz im Rechteck optimal genutzt 
wird?

Wie würden die Mathe-Gurus unter euch das lösen?

von Mario G. (mario)


Angehängte Dateien:

Lesenswert?

Vielleicht ist das Bild etwas ungenau, hier nochmal ein neues...

von Purzel H. (hacky)


Lesenswert?

Naja. Wenn w/s sowie h/s ohne Rest aufgeht bekommt man den besten 
Fuellfaktor.

von Mario G. (mario)


Lesenswert?

das ist richtig aber ich möchte die Seitenlänge haben welche das 
Rechteck optimal ausfüllt, und zwar für beliebige w, h und n.

von Sam .. (sam1994)


Lesenswert?

mit s=sqrt(w*h/n) erhält man den idealen Wert wenn man die Quadrate 
teilen könnte. Damit die Quadrate passen muss man dafür sorgen, dass 
diese an einer Seite anliegen:
w/(w/s aufgerundet) ergibt s, wenn die Quadrate an der rechten Seite 
anliegen sollen. Das gleiche macht man mit h. Es kann aber vorkommen, 
dass beim größeren s keine n Quadrate ins Rechteck passen. Ob dann das 
kleinere s das optimale Ergebnis müsste man prüfen.

von Willi W. (williwacker)


Lesenswert?

Ich denke, das Problem dürfte mit vernünftigem Aufwand nur durch massive 
Rechenpower lösbar sein, immerhin kann man die Quadrate ja auch kippen 
(???), und nicht alle im selben Winkel, da hat es dann schon einige 
Freiheitsgrade

von Mario G. (mario)


Lesenswert?

Nein kippen ist nicht erlaubt ,wir bewegen uns nur in x und y-Richtung. 
Ich möchte es nicht komplizierter machen als es ist...

von Mario G. (mario)


Lesenswert?

Samuel K. schrieb:
> mit s=sqrt(w*h/n) erhält man den idealen Wert wenn man die Quadrate
> teilen könnte.

Diese Formel war auch mein Ansatz. Sie resultiert aus der Restfläche 
Arest  = w*h - s*s*n . Leider funktioniert es so nicht, ein Beispiel:

w = 1000
h = 300
n = 8

s ergibt sich zu 193.64 ~ 194. Das passt aber niemals um 8 Quadrate 
unterzubringen. Das Optimum dürfte irgend wo bei 150 liegen, damit wäre 
h optimal ausgenutzt, in x-Richtung würde allerdings eine Fläche von 
400*300 übrigbleiben...

Ich vermute mal man muß Randbedingungen festelegen, aber wie?

von Robert L. (lrlr)


Lesenswert?

ich würde es so lösen:

alle möglichen "figuren" die es gibt durchprobieren
und immer eine Seite der Figur, auf die länge der Fläche anpassen (je 
nachdem wie die "figur"  passt, ist das w oder h)


ob man dass jetzt auch "berechnen" kann, (und beweisen dass das dann 
immer stimm) wäre interessat

von Robert L. (lrlr)


Lesenswert?

edit:

>Das Optimum dürfte irgend wo bei 150

also es kann nur entweder genau 150 (also 2 reihen)
oder 125 sein (1 reihe)
(die Lösung ist also genau 150...)

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

Mario Grafe schrieb:
> Wie bestimmt man nun s so das der Platz im Rechteck
> optimal genutzt wird?
Was heisst den für dich "optimal ausgenutzt" willst du die Fläche 
einfach mit möglichst großen Rechtecken füllen? In dem Fall würde ich 
das einfach in sinnvollen Schrittgrößen mich einer ersten Schätzung 
annähern und dann in kleineren Schritten das optimum bestimmen.

von Mario G. (mario)


Lesenswert?

"optimal ausgenutzt" soll heissen die Restfläche soll möglichst gering 
werden

von Sam .. (sam1994)


Lesenswert?

Mario Grafe schrieb:
> Samuel K. schrieb:
>> mit s=sqrt(w*h/n) erhält man den idealen Wert wenn man die Quadrate
>> teilen könnte.
>
> Diese Formel war auch mein Ansatz. Sie resultiert aus der Restfläche
> Arest  = w*h - s*s*n . Leider funktioniert es so nicht, ein Beispiel:
>
> w = 1000
> h = 300
> n = 8
>
> s ergibt sich zu 193.64 ~ 194.

Das ist nur die Hälfte meines Beitrags:

w/s aufgerundet = 6
h/s aufgerundet = 2

sx = w/(w/s) = 166.66
sy = h/(h/s) = 150

Der größere Wert für s passt nicht. Also prüft man ob es einen besseren 
Wert für s gibt im Bereich 150 < s < 166.66:

h/s = 1000/166.66 gerundet = 1
w/n*(h/s) = 125

Dieser Wert ist kleiner als 150 -> Optimaler Wert s = 150

von Mario G. (mario)


Lesenswert?

Robert L. schrieb:
> also es kann nur entweder genau 150 (also 2 reihen)
> oder 125 sein (1 reihe)
> (die Lösung ist also genau 150...)

Für das Beispiel stimmt es, ich suche aber eine generelle Lösung für 
z.B. n = 1...1000 und für mehr oder weniger beliebige w und h.

Es durchzuprobieren ist mir auch schon in den Sinn gekommen aber es muß 
doch noch auch eine analytische Lösugn geben,oder?

von Läubi .. (laeubi) Benutzerseite


Lesenswert?

Vermutlich könnte man das sogar in eine Extremwertaufgabe überführen... 
hast du es den einfach schon mal versucht?

von Mario G. (mario)


Lesenswert?

Läubi .. schrieb:
> Vermutlich könnte man das sogar in eine Extremwertaufgabe überführen...
> hast du es den einfach schon mal versucht?

Ja habe ich aber genau da liegt der Hund begraben. Man muß geeignete 
Randbedingungen festlegen. Man könnte der Formel Arest = w*h - s*s*n 
ausgehen und entsprechend differentieren, aber ich weiß nicht wie ich 
geeigente Randbedingungen definiere.

von Robert L. (lrlr)


Lesenswert?

das (generelle) Problem ist, dass das Ergebnis (also alle quadrate) ja 
kein rechteck ergeben .. (also z.b. obiges beispiel, mit 9 quadraten)

von Sam .. (sam1994)


Lesenswert?

meine Idee in c++:
1
#include <iostream>
2
#include <math.h>
3
4
#define MAX(a,b) ((a) > (b) ? (a) : (b))
5
#define MIN(a,b) ((a) < (b) ? (a) : (b))
6
7
using namespace std;
8
9
int main(int argc, char *argv[])
10
{
11
    int w, h, n;
12
    cout << "w: "; cin >> w;
13
    cout << "h: "; cin >> h;
14
    cout << "n: "; cin >> n;
15
    
16
    double s = sqrt(w*h/n);
17
    int ws = (int)(w/s+0.99999);
18
    int hs = (int)(h/s+0.99999);
19
    double sx = (double)w / ws;
20
    double sy = (double)h / hs;
21
    
22
    if ((int)(w / sy) == 0)
23
        s = sx;
24
    else if ((int)(h / sx) == 0)
25
        s = sy;
26
    else
27
    {
28
        if (n / (int)(h / sx) > ws || n / (int)(w / sy) > hs)
29
        {
30
            double max = MAX(sx, sy);
31
            double min = MIN(sx, sy);
32
    
33
            hs = (int)(h / max);
34
            s = w/n*hs;
35
            
36
            s = MAX(min, s);
37
        }
38
        else
39
            s = MAX(sx, sy);
40
    }
41
    cout << "s = " << s << endl;
42
    
43
    system("PAUSE");
44
    return EXIT_SUCCESS;
45
}

von Robert L. (lrlr)


Lesenswert?

das ganze zu "Lösen" (mittels Software) ist jetzt glaub ich nicht so das 
Problem..

in der Überschrift vom Thread steht "Mathematik"
deshalb GLAUBE ist, dass es nicht darum geht das "irgendwie" zu lösen, 
sonder mit einer Formel..

von Sam .. (sam1994)


Lesenswert?

Falls du den Code angeschaut hättest, wüsstest du, dass dieser eine 
Formel mit ein paar Bedingungen enthält. Ich habe diesen Code 
geschrieben um meine Idee zu testen, die ich oben erklärt habe. Bisher 
habe ich keinen Fehler gefunden.

von D. I. (Gast)


Lesenswert?

Bevor man sich Gedanken zum Algorithmus macht:

Erstmal Rahmenbedingungen: wie groß können w,h,n werden? Arbeiten wir im 
ganzzahligen Bereich, oder im realen?

Und dein Code ist glaube ich nicht optimal Samuel. Es gibt Fälle wo ein 
bisschen Verschnitt auf beiden Achsen besser ist als nur ein Verschnitt 
auf einer Achse.

von Robert L. (lrlr)


Lesenswert?

>. Es gibt Fälle wo ein
>bisschen Verschnitt auf beiden Achsen besser ist als nur ein Verschnitt
>auf einer Achse.

wie ?
beispiel?

von Sam .. (sam1994)


Lesenswert?

D. I. schrieb:
> Und dein Code ist glaube ich nicht optimal Samuel. Es gibt Fälle wo ein
> bisschen Verschnitt auf beiden Achsen besser ist als nur ein Verschnitt
> auf einer Achse.

Ich denke man kann die Quadrate solange vergrößeren, bis sie an einer 
Seite anliegen.

von D. I. (Gast)


Lesenswert?

mh stimmt, bin gerade von ganzzahligen S ausgegangen, dann ja, dann hast 
du recht.

von Mario G. (mario)


Lesenswert?

also ich habe jetzt folgenden Algorithmus als Lösung, er funktioniert, 
aber ist sicher noch verbesserbar:
Das Problem ist das w,h,s und auch n ganze Zahlen (integer) sind. Daher 
muß man den Wertebereich für s einschränken:

Schritt 1:
Bestimmen aller möglichen s für die x- und y-Richtung mit Hilfe der 
Formeln sx[i=0..n-1] = w/i und sy[[i=0..n-1] = h/i

Schritt 2:
Gegencheck für die jeweils andere Richtung welche sx und sy gültig (d.h. 
w udn h nicht überschreiten) sind mit Hilfe von hx[i=0..n-1]=(n/i)*sx 
und wx[i=0..n-1]=(n/i)*sy, dabei fallen einige Werte schonmal raus. Der 
Trick ist hierbei, das auch der Term (n/i) auf ganze Zahlen gerundet 
werden muß, aber immer aufgerundet (falls bei (n/i) ein Rest bleibt.

Schritt 3:
Jetzt haben wir die "möglichen" s (sx und sy) ausgerecht und können die 
gültigen Werte in die Formel für die Restflächenberechnung A = w*h - 
s*s*n einsetzen. Der Wert s bei dem die Fläche minimal ist ist der 
gesuchte Wert s!
Neben bei kann man noch die Anzahl der Elemente in x-Richtung (nx = w/s) 
ausrechnen.

von Sam .. (sam1994)


Lesenswert?

Naja, das ist jetzt wirklich Bruteforce und in dem Sinne kein wirklicher 
Algorithmus. Wenn du ihn in c-ähnlichen Code fasst, könnte man ihn mit 
meinem in einem bestimmten Wertebereich vergleichen.

von Mario G. (mario)


Lesenswert?

Hier noch ein Beispiel:
w = 1000
h = 300
n = 8

S-Werte:
sx[0..7] = 1000, 500, 333.33, 250, 200, 166.66, 142.85, 125
sy[0..7] = 300, 150, 100, 75, 60, 50, 42.85, 37.5

Gegencheck für sx mit auf Ganzahl gerundeten (n/i):
hx[0..7] = 8000, 2000, 1000, 500, 400, 333.32, 285.7, 125

Gegencheck für sy:
wx[0..7] = 2400, 600, 300, 150, 120, 100, 85.7, 37.5

Übrig bleiben insgesamt:
s[..] = 142.85, 125, 150, 100, 75, 60, 50, 42.85, 37.5

Restflächen:
A[..] =136751, 175000, 120000, 220000, 255000, 271200, 280000, 285311, 
288750

Ich sehe gerade das man die Restfläche gar nicht ausrechnen muß, es ist 
immer der größte möglich s-Wert...w.z.b.w.

von Mario G. (mario)


Lesenswert?

Samuel K. schrieb:
> Naja, das ist jetzt wirklich Bruteforce und in dem Sinne kein wirklicher
> Algorithmus. Wenn du ihn in c-ähnlichen Code fasst, könnte man ihn mit
> meinem in einem bestimmten Wertebereich vergleichen.

Ja ein echter analytischer Ansatz wäre mir auch lieber, aber man muß die 
Randbedingungen beachten.

von Mario G. (mario)


Lesenswert?


von D. I. (Gast)


Lesenswert?

Wenn deine Zielfunktion eine Parabel ist (ist sie das wirklich?) dann 
kannst du ternäre Suche anwenden um das Optimum zu finden. Dann muss man 
auch nichts brute-forcen

von Mario G. (mario)


Lesenswert?

D. I. schrieb:
> Wenn deine Zielfunktion eine Parabel ist (ist sie das wirklich?) dann
> kannst du ternäre Suche anwenden um das Optimum zu finden. Dann muss man
> auch nichts brute-forcen

Nun ja, so einfach ist das nicht, da für s nur bestimmte Werte 
zugelassen werden. Die Extremwerte der parabel bestimmen sich einfach, 
aber man muß noch das nächstmöglich s finden.

Mir ist noch eine andere Lösung eingefallen, welche sich aus dem 
Verhältnis von w und h ableitet.
Folgendes kann angenommen werden:
w   nx
- ~ --
h   ny

nx, ny ... Anzahl der Quadrate in x und y-Richtung

Schritt 1: Verhältnis von v = w/h ausrechnen
Schritt 2: nx = sqrt(v*n) und ny = sqrt(n/v) ausrechnen und aufrunden
Schritt 3: das jeweilige nx bzw. ny für beide Lösungen ausrechnen, 
also nxy = n/nx und nyx = n/ny
Schritt 4: Für beide Fälle s ausrechnen, als sxx=w/nx, sxy=h/nxy, 
syx=w/nyx, syy=h/ny
Schritt 5: für alle vier s... überprüfen ob die jeweilige Grenze (w, h) 
überschritten wird.
Schritt 6: Den maximalen übrigbleibenden s-Wert nehmen

von Nils P. (ert)


Lesenswert?

So in der Art würde ich es auch angehen

optimales N berechnen : x=abrunden(lange_seite/kurze_seite)

x>=N --> optimales s ist die kurze seite

x<N --> kurze_seite_neu=kurze_seite/2
        x_neu=abrunden(2*(lange_seite/kurze_seite_neu)

x_neu>=N --> optimales s ist kurze_seite/2

usw und so fort...

Grüße Ert

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Mario Grafe schrieb:
> Ich grüble gerade an einem auf den ersten Blick einfachem
> Optimierungsproblem, folgende Situation:
>
> Gegeben ist ein Rechteck (Kantenlängen w und h) und ausserdem ein
> Anzahl von Quadraten n. Nun soll die Seitenlänge der Quadrate s so
> bestimmt werden, das die Fläche des Rechtecks optimal ausgenutzt wird.
>
> [...]
>
> Wie würden die Mathe-Gurus unter euch das lösen?

Wenn ich's recht sehe ist das Euklid'scher Algorithmus aka. einfache 
Kettenbruckentwicklung für das Seitenverhältnis w/l:

Zunächst bestimmt man

Q wird nicht sonderlich groß sein; zB ist
Q(200) = { 1, 2, 5, 10 }

Dann führt man den Euklid'schen Algorithmus für das Seitenverhältnis 
durch und erhält damit eine rationale, teilerfremde (und in gewissem 
Sinne optimale) Annäherung für das Seitenverhältnis, sei diese a:b.

Dann prüft man für alle q in Q, ob a·b <= n/q²

Ist das der Fall, berechnet man den Verschnitt
und sucht den besten Verschnitt v(q) über aller so gefunden q.

Da a und b geometrisch wachsen, ist entweder recht bald a·b > n und man 
kann aufhören.

Oder w und h sind kommensurabel und die Kettenbruchentwicklung von w/h 
also endlich. Hier kann der Fall auftreten, daß die 
Kettenbruckentwicklung von w/h abbricht bevor a·b > n ist. In diesem 
Fall hört man auch auf weiter zu entwickeln.

Beachte, daß Q nie leer ist und mindestens immer die 1 enthält.

Man setzt dann s(n) = a·b/q für die Seitenlänge und ist fertig.

von Mario G. (mario)


Lesenswert?

Johann L. schrieb:
> Wenn ich's recht sehe ist das Euklid'scher Algorithmus aka. einfache
> Kettenbruckentwicklung für das Seitenverhältnis w/l:
>

q ist also 0....n, aber was ist n', soll es das Seitenverhältnis w/h 
sein?

von Hagen R. (hagen)


Lesenswert?

Johann L. schrieb:
> Oder w und h sind kommensurabel und die Kettenbruchentwicklung

Danke Johann, wieder was gelernt: inkommensurabel = teilerfremd

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Hagen Re schrieb:

> Danke Johann, wieder was gelernt: inkommensurabel = teilerfremd

Nicht ganz, e und 1 sind inkommensurabel "teilerfremd" für reelle Zahlen 
passt nicht wirklich. Am ehensten passt zu kommensurabel "stehen in 
rationalem Verhältnis zueinander" oder "mit gleichem Maß messbar".

2.8 und 35 können zB beide mit einem Maß der Länge 0.7 (ganzzahlig) 
ausgemessen werden; bei 1 und e geht das nicht.

von Michael L. (Firma: Desert Irrigation Systems) (overingenieur)


Lesenswert?

Das ist doch eine Variationsaufgabe und zwar genau ein allgemeines 
isoperimetrisches Problem. Die Randbedingungen sind die beiden 
Längenparameter der xy-Achsen und die Anzahl der Quadrate, die 
Extremwerte sind die Flächen. Wurde so schon im 9. Jh. v. Chr. gelöst 
von Königin Dido bei der Landnahme von Karthago.

Damit sollte man das jetzt im 2. Semseter locker lösen können.

Also ein echt alter Hut welcher mathematisch richtig dann irgendwann von 
Euler formuliert wurde.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Michael Lieter schrieb:
> Das ist doch eine Variationsaufgabe

Sehe ich hier nicht. Das Problem ist doch diskret.

von Michael L. (Firma: Desert Irrigation Systems) (overingenieur)


Lesenswert?

Johann L. schrieb:
> Sehe ich hier nicht. Das Problem ist doch diskret.

Spielt keine Rolle - ist eben ein Spezialfall.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Michael Lieter schrieb:
> Johann L. schrieb:
>> Sehe ich hier nicht. Das Problem ist doch diskret.
>
> Spielt keine Rolle - ist eben ein Spezialfall.

Das ist doch so, als wollte man eine Diophantische Gleichung oder ein 
Faktorisierungproblem mittels Techniken der Differntial-, Integral- oder 
Variationsrechnung lösen...

von Michael L. (Firma: Desert Irrigation Systems) (overingenieur)


Lesenswert?

Es handelt sich aber um ein triviales Problem - welches natürlich mit 
verschieden Verfahren lösbar ist - selbst in einem Vektorraum ist eine 
Lösung formulierbar - ich rede mit Anfängern...

2. Semester?

von Simon K. (simon) Benutzerseite


Lesenswert?

Michael Lieter schrieb:
> Es handelt sich aber um ein triviales Problem - welches natürlich mit
> verschieden Verfahren lösbar ist - selbst in einem Vektorraum ist eine
> Lösung formulierbar - ich rede mit Anfängern...
>
> 2. Semester?

Also so hat den Georg Johann auch noch keiner angefahren, wenn es um 
Mathematik geht.

Du scheinst dir deiner Sache ja sicher zu sein.

von Michael L. (Firma: Desert Irrigation Systems) (overingenieur)


Lesenswert?

Natürlich, ich unterrichte höhere Mathematik für Informatiker.

von Simon K. (simon) Benutzerseite


Lesenswert?

Oh Gott! Die armen, ich nenne sie mal "Teilnehmer".

von D. I. (Gast)


Lesenswert?

Ich habe praktisch schon darauf gewartet wann unser Überingenieur 
endlich auftaucht ;)

von Michael L. (Firma: Desert Irrigation Systems) (overingenieur)


Lesenswert?

Eure begrenzte Vorstellung der Mathematik erstaunt mich.

Ich stelle meinen Studenten in der 1. Vorlesung folgende Frage:

Was ist e?

Nur die Studenten welche im Geiste wie Euler sind, können über ihre 
Beschreibung mitteilen das sie überhaupt nach dem verstehen dieser 
Eintrittskarte die Befähigung besitzen sich selbst mit der Fähigkeit des 
Nachdenkens die höheren Ebenen der Mathematik erschliessen können.

Es sind sehr Wenige.

von Winfried J. (Firma: Nisch-Aufzüge) (winne) Benutzerseite


Lesenswert?

o weh


s ist der gröste gemeinsame teiler von w und und h

http://de.wikipedia.org/wiki/Gr%C3%B6%C3%9Fter_gemeinsamer_Teiler

von Michael L. (Firma: Desert Irrigation Systems) (overingenieur)


Lesenswert?

Nein - e ist eine Grenzwertbetrachtung - in Worten: ?

von D. I. (Gast)


Lesenswert?

Michael Lieter schrieb:
> Was ist e?

Offensichtlich der 4. Buchstabe in unserem Alphabet

von Johann L. (gjlayde) Benutzerseite


Angehängte Dateien:

Lesenswert?

Für einen Ingenieur mit einem Hammer besteht die Welt aus lauter Nägeln 
;-)

Wie auch immer, da hier weniger Rumtheoretisieren denn eine praxisnahe 
Antwort gefragt ist, anbei eine Lösung in C, bzw. genauer C99.

Kettenbrüche braucht man übrigens nicht; das Problem ist viel einfacher. 
Um ein Variationsproblem reinzuprügeln muss man sich auch ziemlich 
anstrengen; macht sich aber bestimmt ganz chic und beeindruckend ;-)

Mit GCC übersetzt man das Programm zB mit

> gcc quadrate.c -o quadrate.exe -std=c99 -Os -lm

> .\quadrate.exe 1000 300 7
> S = 150.00 (4 x 2, Verschnitt: 142500.0 = 47.50%, #Extra=5

> .\quadrate.exe 1000 300 8
> S = 150.00 (4 x 2, Verschnitt: 120000.0 = 40.00%, #Extra=4

"4 x 2" ist der Raster, in dem die Quadrate angeordnet werden.
"Extra" ist die Anzahl der Bonus-Quadrate, die man gratis aus dem 
Verschnitt erhalten kann.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Winfried J. schrieb:
> o weh
>
> s ist der gröste gemeinsame teiler von w und und h

Nein, ist es nicht. Beispiel: w = 1024, h = 1000 und n = 1200.
Lösung ist s = 200/7 ≈ 28.57 aber ggT (1024,1000) = 8

von Winfried J. (Firma: Nisch-Aufzüge) (winne) Benutzerseite


Lesenswert?

Johann L. schrieb:
> Winfried J. schrieb:> o weh>> s ist der gröste gemeinsame teiler von w und und 
hNein, ist es nicht. Beispiel: w = 1024, h = 1000 und n = 1200.Lösung ist s = 
200/7 ≈ 28.57 aber ggT (1024,1000) = 8

Das ist ja wohl Blödsinn!

200/7  ist ein nichtperiodischer unendlicher Bruch (Teilbarrkeitsregeln) 
es bleibt also ein wenn auch sehr kleiner Rest. Schon bei "≈" hättest du 
drauf kommen sollen.




Mit GGT=8 125*128 = 16000 Einzelflächen bleibt Rest Null, also optimal 
ausgenutzt bei gröstmöglicher Einzelfläche.

von Johann L. (gjlayde) Benutzerseite


Lesenswert?

Winfried J. schrieb:
> Johann L. schrieb:
>> Winfried J. schrieb:
>>> o weh
>>> s ist der gröste gemeinsame teiler von w und und h
>> Nein, ist es nicht. Beispiel: w = 1024, h = 1000 und n = 1200.
>> Lösung ist s = 200/7 ≈ 28.57 aber ggT (1024,1000) = 8
>
> Das ist ja wohl Blödsinn!
>
> 200/7 ist ein nichtperiodischer unendlicher Bruch (Teilbarrkeitsregeln)

Das ist auf jeden Fall Blödsinn

> es bleibt also ein wenn auch sehr kleiner Rest. Schon bei "≈" hättest du
> drauf kommen sollen.
>
> Mit GGT=8 125*128 = 16000 Einzelflächen bleibt Rest Null, also optimal
> ausgenutzt bei gröstmöglicher Einzelfläche.

Enstpann dich erst mal und lies die Aufgabenstellung dann gaaanz 
entspannt durch.

Mit den Zahlen von oben sind 1200 möglichst große Quadrate auf einem
1024 × 1000 großen Rechteck unterzubringen, und die Frage ist die nach 
der besten Kantenlänge der Quadrate.

Ich behaupte immer noch: Diese Kantenlänge ist 200/7.

200/7 hat übrigens periodische Dezimalentwicklung:

von Yalu X. (yalu) (Moderator)


Lesenswert?

@Samuel:

Für w=1, h=3 und n=5 liefert dein Programm s=0, was nicht sein kann.
Grund dafür ist die Integer-Division in
1
    double s = sqrt(w*h/n);

Wenn man sie durch eine Float-Division ersetzt, kommt s=0,5 heraus, was
aber immer noch nicht stimmt. Die richtige Lösung wäre s=0,6.


@Johann:

Auch dein Verfahren liefert für obige Eingabe s=0,5. Der Hund liegt hier
begraben:
1
    a = sqrt ((double) N*H/W);
2
    b = sqrt ((double) N*W/H);
3
    
4
    for (int ia = -1; ia <= 1; ia++)
5
        for (int ib = -1; ib <= 1; ib++)
6
        {
7
            double sa, sb, s, v;
8
            int aa = a + ia;
9
            int bb = b + ib;
10
            ...

Es genügt nicht, nur die nächsten Nachbarn von a und b zu untersuchen.


Wenn ich mich nicht verrechnet habe, müsste folgende Formel das
Problem lösen:

von Johann L. (gjlayde) Benutzerseite


Angehängte Dateien:

Lesenswert?

Yalu X. schrieb:

> @Johann:
>
> Auch dein Verfahren liefert für obige Eingabe s=0,5

Grrr. Danke für den Hinweis; lag aber an einem Denkfehler, nicht an 
einem Rundungsfehler. Die Suche geht jetzt nur noch über 6 Kachelungen 
anstatt über 9 wie zuvor.

>> quadrate.exe 1 3 5
>> S = 0.60 (1 x 5, Verschnitt: 1.2 = 40.00%, #Extra=0

> Wenn ich mich nicht verrechnet habe, müsste folgende Formel das
> Problem lösen:

Sieht gut aus :-) Die gleiche Idee in eine Formel wo ich nur 
durchprobiere...

von Yalu X. (yalu) (Moderator)


Lesenswert?

Johann L. schrieb:
> lag aber an einem Denkfehler, nicht an einem Rundungsfehler.

Ja, der Rundungsfehler war nur in Samuels Programm (zusätzlich zu einem
Denkfehler).

Dein jetziges Programm liefert aber immer noch Fehler, wenngleich
deutlich weniger als vorher. Beispiele:
1
 H   W   N  dein S  mein S
2
——————————————————————————
3
 3   1   5  0,5000  0,6000
4
 5   3  29  0,6000  0,6250
5
19   6   5  3,1667  3,8000
6
——————————————————————————

Die Fehler scheinen aber nur noch für H>W aufzutreten.

von Yalu X. (yalu) (Moderator)


Lesenswert?

Fehler gefunden: Ersetze in Zeile 40
1
        a = W / b;

durch
1
        a = N / b;

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.