Suche einen Algorithmus...

03.08.2005, 16:58

atmosfear

Auf diesen Beitrag antworten »

Suche einen Algorithmus...

Hallo!

Ich möchte eine Strecke von der Mitte aus in beide Richtungen (also nach links und nach rechts) in gleiche Teile aufteilen.

Man muss sich das Ganze folgendermassen vorstellen...

1. Man nimmt ein Balkongeländer das eine bestimmte Länge L hat
2. Nun hat man Steher die eine gewisse Breite B haben
3. Ausserdem braucht man einen Spaltabstand S zwischen den einzelnen Stehern

Den ersten Steher möchte ich in der Mitte plazieren, die anderen sollten automatisch nach rechts bzw. links gesetzt werden. Die Strecken nach links und rechts können unterschiedlich sein, d.h. wenn sich die Aufteilung bei einer der beiden Seiten "ausgeht" muss das nicht gleich zwingend für die andere Seite zutreffen!

Nehmen wir folgendes Beispiel:

Die Strecke lässt sich nach links hin genau aufteilen, d.h. dass die gewünschte Spaltbreite nicht angepasst werden muss um zu einer geradzahligen Steheranzahl zu gelangen. Die Strecke rechts ist aber kürzer und die Aufteilung geht sich nicht aus.

Nun muss ein Weg gefunden werden, der ermöglicht einen "Einstellung" zu finden, die für beiden Seiten zu verwenden ist, es kann natütrlich aber auch passieren, dass die Aufteilung überhaupt nicht möglich ist!?!

-------------------------------------------------

Anderes Beispiel:

Sagen wir mal wir haben einen Raum, in dem die Decke mit Stehern gestützt werden soll/muss.

Wenn man immer die "Mitte der Strecke(!)" nimmt ist das Ganze natürlich kein Problem da hast du schon Recht, da die Rechnung dann immer aufgeht und für beide Seiten zutrifft.

Wenn du aber von der Raummitte(!) ausgehst und sagen wir mal auf der linken Seite einen Mauervorsprung hast, dann kannst du links nicht gleich viele Steher unterbringen als rechts!

Von der "Mitte aus" heisst also, dass du den ersten Steher an einer bestimmen Position haben willst, und dann nach rechts und links gehst. Würde man immer von links ausgehen hätte man auch kein Problem, aber wie gesagt der "mittlere" Steher sollte immer an einer bestimmten Position stehen!

DANKE
atmosfear

L R
:<------>:<---------->:
| : : | : : : :|
| : : | : : : :|
| : : | : : : :|
:--: :--:
L/m R/n

Geg: L, R
Ges: m, n

L/m = R/n
m = ganzzahlig
n = ganzzahlig

3 Gleichungen für 2 Unbekannte m, n

03.08.2005, 17:19

AD

Auf diesen Beitrag antworten »

Zitat:

Original von atmosfear
Den ersten Steher möchte ich in der Mitte plazieren

Gibt es einen besonderen Grund dafür? Bei ungeradzahlig vieln Stehern ist das ja vernünftig; bei geradzahlig vielen widerspricht das deiner anfänglichen Forderung:

Zitat:

Original von atmosfear
Ich möchte eine Strecke von der Mitte aus in beide Richtungen (also nach links und nach rechts) in gleiche Teile aufteilen.

Wenn du $\begin{eqnarray*} n \end{eqnarray*}$ gleichabständige Steher haben willst, dann ist die Gesamtlänge des Geländers

$\begin{eqnarray*} L = nB+(n-1)S \end{eqnarray*}$

Mit gegebenen $\begin{eqnarray*} L,B,n \end{eqnarray*}$ kannst du den richtigen Spaltabstand $\begin{eqnarray*} S \end{eqnarray*}$ ausrechnen - wozu also das ganze Brimborium?

04.08.2005, 08:03

atmosfear

Auf diesen Beitrag antworten »

Hallo Arthur,

Zitat:

Gibt es einen besonderen Grund dafür? Bei ungeradzahlig vieln Stehern ist das ja vernünftig; bei geradzahlig vielen widerspricht das deiner anfänglichen Forderung:

Tut mir leid, da habe ich mich wohl etwas falsch ausgedrückt!

Nehmen wir folgendes Beispiel an:
Wie du meiner Skizze entnehmen kannst kann in einem Raum auf einer Seite ein Mauervorsprung sein, der die Strecke in eine Richtung verringert. Der Steher in der "Mitte" muss aber an einem bestimmten Platz stehen! (ist halt so gefordert) Diese bedeutet, dass die restlichen Steher "von der Mitte aus" aufgeteilt werden müssen, also nach links und rechts hin. Würde man links oder rechts anfangen könnte man ja nicht gerade garantieren, dass der Steher in der Mitte an die gewünschte Stelle kommt.
Nun kann ich den Spaltabstand nach z.B.: links so anpassen, dass der letzte bzw. der erste Steher links an der Wand steht und kein Spiel hat. Dieser Spaltabstand muss aber nicht für die rechte Seite zutreffen, da die Strecke eine andere Länge hat. So kann es passieren, dass rechts ein Spalt zwischen dem letzten Steher und der Wand bleibt (siehe wiederum meine Skizze)

Nun sollte ein Weg gefunden werden mit dem festgestellt werden kann, welcher Spaltabstand zwischen den Steher verwendet werden muss, damit beide "Abschlusssteher" links und rechts ganz an der Wand stehen!
Ich weiss, das kann sich nicht immer ausgehen, aber dann muss halt die Steherbreite angepasst werden...

Vielen Dank für jede Hilfe!
atmosfear

04.08.2005, 10:24

jovi

Auf diesen Beitrag antworten »

Zitat:

1. Man nimmt ein Balkongeländer das eine bestimmte Länge L hat
2. Nun hat man Steher die eine gewisse Breite B haben
3. Ausserdem braucht man einen Spaltabstand S zwischen den einzelnen Stehern

4. nun sei noch N die Anzahl der Steher und
5. A der Abstand vom linken Rand des mittleren Stehers zum linken Ende und Z der Abstand vom rechten Rand des mittleren Stehers zum rechten Ende

Meine Frage nun: welche der Parameter sind nun gegeben und welche sollen bestimmt werden ?

04.08.2005, 11:23

atmosfear

Auf diesen Beitrag antworten »

Hallo!

Also hier eine Zusammenfassung:

1. L = Gesamtlänge des Geländers (Raums)
2. B = Breite der einzelnen Steher
3. S = Spaltabstand zwischen den einzelnen Stehern
4. N = Anzahl der Steher
5. A = Abstand vom linken Rand des mittleren Stehers zum linken Ende
5. Z = Abstand vom rechten Rand des mittleren Stehers zum rechten Ende

Gegeben ist die Gesamtlänge L, die Breite der Steher B, die Abstände der einzelnen Ränder, also A und Z, sowie der gewünschte Spaltabstand S.

Unbekannt ist somit die Anzahl der Steher N

Zur Vereinfachung sollten wir ein Beispiel nehmen:

L = 6000 mm
B = 150 mm
S = 200 mm
A = 300 mm
Z = 0 mm

Details bitte meiner angehängten Skizze entnehmen...

Vielen Dank!
atmosfear

04.08.2005, 11:44

kurellajunior

Auf diesen Beitrag antworten »

Vervollständigung:

L = Gesamtlänge des Geländers (Raums)
B = Breite der einzelnen Steher
S = Spaltabstand zwischen den einzelnen Stehern
N = Anzahl der Steher
A = Abstand vom linken Rand des mittleren Stehers zum linken Ende
Z = Abstand vom rechten Rand des mittleren Stehers zum rechten Ende
M = Breite des Mauervorsprungs

Ich fasse mal in Gleichung zusammen, was ich der Skizze entnehmen kann:
$\begin{eqnarray*} M+N\cdot B+(N-1)S=&M+A+Z+B&=L\\ N\cdot B+(N-1)S=&A+Z+B&=L-M\\ (N-1)(B+S)=&A+Z&=L-M-B \end{eqnarray*}$
und
$\begin{eqnarray*} A+M=Z \end{eqnarray*}$
Du suchst eine Lösung für
$\begin{eqnarray*} A&=N_l\cdot B+(N_l-1)\cdot S\\ Z&=N_r\cdot B+(N_r-1)\cdot S \end{eqnarray*}$
bei der $\begin{eqnarray*} N=N_l+N_r+1 \end{eqnarray*}$ ganzahlig sein muss, $\begin{eqnarray*} S \end{eqnarray*}$ frei variabel ist und $\begin{eqnarray*} B \end{eqnarray*}$ im Notfall angepasst werden kann.

Stimmt das soweit?

Anzeige

04.08.2005, 12:00

atmosfear

Auf diesen Beitrag antworten »

Hallo!

Zitat:

M = Breite des Mauervorsprungs

Braucht man meiner Meinung nach nicht, da der Vorsprung ohnehin nicht wichtig ist, sondern lediglich der Abstand vom mittleren zum äußeren Balken, also A oder Z, oder sehe ich das falsch?

Ich meine man muss halt immer von der "echten" Raumlänge, also inklusive des Mauervorsprungs ausgehen, sonst könnte man den Steher ja nicht "in Raummitte" plazieren...

Alles in allem stimmt das soweit, ja

DANKE
atmosfear

04.08.2005, 12:56

kurellajunior

Auf diesen Beitrag antworten »

Aha, also oben ergänzt um
$\begin{eqnarray*} A+M=Z \end{eqnarray*}$ ?

Mal sehen wer sich wann damit beschäftigt, ich guck heute abend nochmal drauf

Jan

04.08.2005, 13:26

atmosfear

Auf diesen Beitrag antworten »

Also, eigentlich sollte

$\begin{eqnarray*} A + M = Z \end{eqnarray*}$

gleichzusetzen sein, zumindest ist das so in meiner angefertigten Skizze zu sehen.

Warum dachtest du eigentlich, dass ein zusätzlicher Parameter M gebraucht wird?

Ansonsten hast du ALLES richtig verstanden, auch dass die Spaltbreite und notfalls sogar die Steherbreite angepasst werden muss.
Es kann durchaus passieren, dass sich eine Seite mit einer Steherbreite/Spaltbreite perfekt aufteilen lässt und die andere eben nicht...

Danke
atmosfear

04.08.2005, 15:39

jovi

Auf diesen Beitrag antworten »

Zitat:

Original von atmosfear

Zur Vereinfachung sollten wir ein Beispiel nehmen:

L = 6000 mm
B = 150 mm
S = 200 mm
A = 300 mm
Z = 0 mm

also irgendwie verstehe ich dein Beispiel trotzdem nicht.

Es muss doch immer A+B+Z = L gelten !

04.08.2005, 15:54

atmosfear

Auf diesen Beitrag antworten »

1. L = Gesamtlänge des Geländers (Raums)
2. B = Breite der einzelnen Steher
3. S = Spaltabstand zwischen den einzelnen Stehern
4. N = Anzahl der Steher
5. A = Abstand vom linken Rand des mittleren Stehers zum linken Ende
6. Z = Abstand vom rechten Rand des mittleren Stehers zum rechten Ende
7. M = Breite des Mauervorsprungs

$\begin{eqnarray*} A+B+Z = L \end{eqnarray*}$ ???

Warum sollte Obiges gelten, wenn B die Steherbreite darstellt!?

RICHTIG WÄRE
$\begin{eqnarray*} A + M + Z = L \end{eqnarray*}$

atmosfear

04.08.2005, 17:46

jovi

Auf diesen Beitrag antworten »

M interessiert nicht, ist irrelevant, steht nichts von in der ursprünglichen Aufgabe, ist ja nur die Differenz von A und Z, also bereits festgelegt.
Deshalb habe ich L auch aufgefasst als das was du unter L-M verstehst.
Wenn ich also den linken Teil der Strecke (A) und den mittleren Teil der Strecke (B) und den rechten Teil der Strecke (Z) addiere, dann sollte schon die Länge der Strecke (L) rauskommen oder ?

05.08.2005, 01:14

kurellajunior

Auf diesen Beitrag antworten »

Wenn ich jovis Einwand mal ignoriere (schließlich scheint er meine Posts auch nicht gelesen zu haben Augenzwinkern

Augenzwinkern

), Sind wir immer noch bei
$\begin{eqnarray*} A&=N_l\cdot B+(N_l-1)\cdot S\\ Z&=N_r\cdot B+(N_r-1)\cdot S \end{eqnarray*}$
bei der $\begin{eqnarray*} N=N_l+N_r+1 \end{eqnarray*}$ ganzahlig sein muss, $\begin{eqnarray*} S \end{eqnarray*}$ frei variabel ist und $\begin{eqnarray*} B \end{eqnarray*}$ im Notfall angepasst werden kann.

Also ein lGS mit 3 unbekannten, von denen 2 ganzzahlig sein sollen. Leider steh ich mit der ganzzahlarithmetik etwas auf Kriegsfuß, da müssen andere ran?
Hilfe

Hilfe

Jan

05.08.2005, 10:02

jovi

Auf diesen Beitrag antworten »

Nun ich will zuerst mal die Aufgabe verstehen und atomsfear dazu bringen Unklarheiten zu klären -
was mir zugegebenermassen noch nicht gelungen ist.

Zitat:

Gegeben ist die Gesamtlänge L, die Breite der Steher B, die Abstände der einzelnen Ränder, also A und Z, sowie der gewünschte Spaltabstand S.
Unbekannt ist somit die Anzahl der Steher N

Danach und nach seinem Beispiel wäre nur N gesucht.
Aber das Beispiel ist ,ob nun mit oder ohne M (ich verzichte lieber auf überflüssige Parameter), völlig unmöglich weil widersprüchlich.

05.08.2005, 16:46

atmosfear

Auf diesen Beitrag antworten »

@jovi

Zitat:

M interessiert nicht, ist irrelevant, steht nichts von in der ursprünglichen Aufgabe, ist ja nur die Differenz von A und Z, also bereits festgelegt.

Da hast du Recht!

Zitat:

Wenn ich also den linken Teil der Strecke (A) und den mittleren Teil der Strecke (B) und den rechten Teil der Strecke (Z) addiere, dann sollte schon die Länge der Strecke (L) rauskommen oder ?

Das ist richtig, da B die Steherbreite darstellt, und natürlich zur Gesamtlänge L addiert werden muss

Es gilt also Folgendes:

$\begin{eqnarray*} L = A + B + Z + M \end{eqnarray*}$

wobei M zu ignorieren ist, da wenn M schon vorher von L subtrahiert wird, Folgendes gilt:

$\begin{eqnarray*} L = A + B + Z \end{eqnarray*}$

Fakt ist, dass A und Z nicht gleich sein müssen, das bedeutet, dass die Steher nicht immer von links oder rechts beginnend aufgeteilt werden sollen, sondern dass ich mit einem Steher an einer bestimmten Position starten möchte (und dies muss ja nicht immer unbedingt die Mitte sein)

Beispiel:

A = 2990 mm
B = 20 mm
Z = 4990 mm
L = 8000 mm

Also ergibt

$\begin{eqnarray*} A + B + Z = L \end{eqnarray*}$

Die Schwierigkeit besteht nun darin herauszufinden, welcher Spaltabstand auf beiden Seite zu einer ganzzahligen Steheranzahl führt, wobei der "abschließende" Steher auf beiden Seiten genau an der Wand anzubringen ist.

So, ich hoffe nun alle Ungereimtheiten geklärt zu haben und bedanke im voraus für die großartige Unterstützung!

atmosfear

05.08.2005, 18:12

jovi

Auf diesen Beitrag antworten »

Ich fürchte, die Aufgabe ist mit den meisten zufällig in der Praxis vorkommenden Startbedingungen für A,B,Z,L nicht lösbar.
Ich komme auf folgende Formeln:
$\begin{eqnarray*} N_l(B+S) = A \end{eqnarray*}$
$\begin{eqnarray*} N_r(B+S) = Z \end{eqnarray*}$
und daraus folgt:
$\begin{eqnarray*} (B+S) = \frac{A}{N_l} = \frac{Z}{N_r} \end{eqnarray*}$
Das bedeutet, wir brauchen 2 möglichst kleine Teiler von A und Z damit noch etwas rauskommt, das (B+S) ergibt, also grösser ist als B.
Die kleinsten Teiler in deinem Bsp. , die ich finden konnte waren
$\begin{eqnarray*} N_l = 299 \end{eqnarray*}$ und $\begin{eqnarray*} N_r = 499 \end{eqnarray*}$ was zu B+S = 10mm führt. Da aber B bereits 20mm ist ...

Also falls die Teiler $\begin{eqnarray*} N_l \end{eqnarray*}$ von $\begin{eqnarray*} A \end{eqnarray*}$ und $\begin{eqnarray*} N_r \end{eqnarray*}$ von $\begin{eqnarray*} Z \end{eqnarray*}$ existieren, für die gilt:
$\begin{eqnarray*} \frac{A}{N_l} = \frac{Z}{N_r} \ge B \end{eqnarray*}$
dann existiert die Lösung $\begin{eqnarray*} S = \frac{A}{N_l} - B \end{eqnarray*}$
Evtl. sogar mehrere.

07.08.2005, 09:05

atmosfear

Auf diesen Beitrag antworten »

Hallo!

Ist es nicht so, dass die Strecke A wie folgt definiert werden muss?!

$\begin{eqnarray*} A = Nl*B + (Nl - 1)*S \end{eqnarray*}$

sowie die Strecke Z wie folgt:

$\begin{eqnarray*} Z = Nr*B + (Nr - 1)*S \end{eqnarray*}$

da die Anzahl der Spalte um 1 weniger sein muss als die der Steher?

--------------------------------------------------------

kurellajunior hat das denke ich schon richtig aufgeschrieben

$\begin{eqnarray*} N = Nl + Nr + 1 \end{eqnarray*}$ -> muss ganzzahlig sein

und

$\begin{eqnarray*} S \end{eqnarray*}$ kann variabel sein...

Danke
atmosfear

07.08.2005, 12:52

jovi

Auf diesen Beitrag antworten »

Das verstehe ich nun nicht - ich habe mich an deiner Zeichnung orientiert.
Die Anzahl der Spalten ist $\begin{eqnarray*} N_l+N_r \end{eqnarray*}$ und damit um 1 kleiner als die der Steher.
Und $\begin{eqnarray*} N, N_l, N_r \end{eqnarray*}$ müssen natürlich ganzzahlig sein, deshalb findet man ja auch meistens keine Lösung,
so wie bei deinem Beispiel.
Man kann natürlich leicht Aufgaben mit dazugehörigen Lösungen konstruieren. Bei :
A = 1600
Z = 2400
B = 100
L = 4100
gibt es für N die Lösungen 6, 11 und 21 mit jeweils (beliebig) vielen Möglichkeiten für S
Also müssen die Aufgaben so aussehen, ggt(A,Z) > B

07.08.2005, 14:58

atmosfear

Auf diesen Beitrag antworten »

Zitat:

Das verstehe ich nun nicht - ich habe mich an deiner Zeichnung orientiert.

Tut mir leid, da hast du natürlich Recht!

Zitat:

Deshalb findet man ja auch meistens keine Lösung

Dann müsste man gegebenfalls eben die auch noch die Steherbreite anpassen...

Okay wir wissen nun wie man die Rechnung grundsätzlich aufstellt, die Frage ist nun wie man am schnellsten zu einer Lösung kommt, die sich IMMER ausgeht!

Ich denke wenn auch die Steherbreite variabel gehalten wird, müsste es doch möglich sein, immer auf eine ganzzahlige Anzahl zu kommen, oder?

Das Ziel ist es ein Programm zu erstellen, das die Eingabe von L, A, Z und B ermöglicht und die restlichen Unbekannten dann automatisch berechnen kann.
Zuerst soll versucht werden auf eine ganzzahlige Steheranzahl bei angegebenen Spaltabstand zu kommen. Dann wird die Spaltbreite in einem vorher definierten Toleranzbereich nach oben und unten korrigiert.
Gibt es dann noch immer kein Ergebnis, so sollte auch die Steherbreite (und natürlich gegebenenfalls auch wieder die Spaltbreite) so lange angepasst werden bis eine Lösung gefunden wird.

Vielen Dank
atmsfear

07.08.2005, 15:37

kurellajunior

Auf diesen Beitrag antworten »

sollte genauso beschrieben ein kleiner bruteforce algorithmus tun. Beschrieben hast Du ihn selber, müsste nur noch umgesetzt werden. Dieser sollte Dir dann in Abhängigkeit von Säulen und Abstandsbreite alle ganzzahligen Lösungen ausspucken.

Jan

07.08.2005, 17:04

jovi

Auf diesen Beitrag antworten »

Zitat:

Dann müsste man gegebenfalls eben die auch noch die Steherbreite anpassen...

Achtung: dann ist nur noch L und der Mittelpukt gegeben !
Da wenn du B veränderst auch A und Z sich ändern

08.08.2005, 07:41

atmosfear

Auf diesen Beitrag antworten »

Zitat:

Achtung: dann ist nur noch L und der Mittelpukt gegeben !

Genau, und dann wird's kompliziert!

Habe gestern wieder einige Stunden mit dem Problemchen verbracht, werde heute mal ein Stückchen von meinem Code posten, damit man die Berechnung besser nachvollziehen kann...

Vielleicht kommen wir dann ja doch noch auf einen grünen Zweig smile

smile

DANKE
atmosfear

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »