Algorithmus gesucht: 'abstand von intervallen'

Wissenschaft Informatik
#1

hallo.

ich habe fünf intervalllängen zwischen 0 und 100.
diese intervalle möchte ich auf einem zahlenstrahl mit der schrittweite „1“ plazieren.

beginn bzw. ende jedes intervalls darf nicht mit beginn bzw. ende aller anderen intervalle zusammenfallen.
außerdem soll ein bestimmter abstand „min“ zwischen start- bzw. endpunkten aller intervalle untereinander eingehalten werden.

d.h. am ende möchte ich zehn natürliche zahlen auf dem zahlenstrahl von 0 bis 100 haben, von denen jede zahl entweder einen start- oder einen endpunkt eines der intervalle darstellt.
der abstand von jedem punkt zum nächsten soll mindestens „min“ sein (z.b. 5).

unelegante lösungen dazu fallen mir schon ein, aber ich hätte gern was schönes… :smile:

wie könnte ich beweisen, daß sich unter bestimmten bedingungen der geforderte abstand „min“ nicht einhalten läßt?

gruß

michael

#2

Moin, Michael,

unelegante lösungen dazu fallen mir schon ein, aber ich hätte
gern was schönes… :smile:

Gesamtlänge minus Summe der n Intervalle / (n-1) = Zwischenraum. Auch nicht elegant, aber notwendig; Ganzzahligkeit wird dann das nächste Problem.

wie könnte ich beweisen, daß sich unter bestimmten bedingungen
der geforderte abstand „min“ nicht einhalten läßt?

die mathematische Schreibweise ist mir hier zu mühsam, deshalb in Worten:

Die Summe der n Intervalle plus der (n-1) Zwischenräume ist größer als die Gesamtlänge.

Gruß Ralf

#3

Hallo Michael,

deine Problembeschreibung lässt viel Interpretationsspielraum. Je nachdem, welche stillschweigenden Annahmen man macht, kann ein Algorithmus einfacher oder komplizierter aussehen:

diese intervalle möchte ich auf einem zahlenstrahl mit der
schrittweite „1“ plazieren.

Sind Überlappungen der Intervalle zugelassen? (Z.B. erstes Intervall [0,10], zweites Intervall [3,17]?)

beginn bzw. ende jedes intervalls darf nicht mit beginn bzw.
ende aller anderen intervalle zusammenfallen.

Was genau soll das „bzw.“ bedeuten? Beginn darf nicht mit Beginn eines anderen Intervalls zusammenfallen und Ende nicht mit Ende, oder werden einfach alle Intervallgrenzen gemeinsam betrachtet? Das hieße, jeder Punkt des Zahlenstrahls darf von den Grenzen höchstens eines Intervalls belegt sein (bei der Intervalllänge 0 könnten Beginn und Ende desselben Intervalls zusammenfallen).

außerdem soll ein bestimmter abstand „min“ zwischen start-
bzw. endpunkten aller intervalle untereinander eingehalten
werden.

Gleiche Frage hier: Abstände zwischen beliebigen Paaren von (verschiedenen) Intervallgrenzen? Oder nur von einem Intervall zum nächsten? Nur von Beginn zu Ende oder auch Beginn zu Beginn …?

d.h. am ende möchte ich zehn natürliche zahlen auf dem
zahlenstrahl von 0 bis 100 haben, von denen jede zahl entweder
einen start- oder einen endpunkt eines der intervalle
darstellt.

Es müssen aber nicht notwendigerweise 10 unterschiedliche Zahlen sein (im Extremfall 10-mal dieselbe).

der abstand von jedem punkt zum nächsten soll mindestens „min“
sein (z.b. 5).

Von jedem? Das hieße auch, alle Intervalllängen müssten größergleich „min“ sein. (Soll der Algorithmus dann feststellen, dass es keine Lösung gibt?)

unelegante lösungen dazu fallen mir schon ein, aber ich hätte
gern was schönes… :smile:

Es wäre gut, wenn du eine solche unelegante Lösung hier zur Diskussion stellen würdest.

wie könnte ich beweisen, daß sich unter bestimmten bedingungen
der geforderte abstand „min“ nicht einhalten läßt?

Durch die Angabe eines einzigen Beispiels.

Viele Grüße,

Andreas