Anzahl der Möglichkeiten N Kreise unterschiedlicher Radius können in einer Linie angeordnet werden

Question

Frage: Gegeben M Punkte auf einer Linie durch 11 Einheiten getrennt. Finde die Anzahl der Möglichkeiten, wie N Kreise mit verschiedenen Radien gezogen werden können, so dass sie sich nicht schneiden oder überlappen oder ineinander liegen ?? Vorausgesetzt, dass die Kreismittelpunkte jene MM-Punkte sein sollten.

Beispiel 1: N = 3, M = 6, r1 = 1, r2 = 1, r3 = 1 Antwort: 24 Wege.

Beispiel 2: N = 2, M = 5, r1 = 1, r2 = 2 Antwort: 6 Möglichkeiten.

Beispiel 3: N = 1, M = 10, r = 50. Antwort = 10 Wege.

Ich habe diese Frage online gefunden und konnte sie bis jetzt nicht lösen. Bis jetzt konnte ich nur so viel aufarbeiten, dass jeder Kreis Räume von n-rn-r bis n-2rn-2r nehmen kann. Aber unter anderem wie kann ich für Kantenfälle anpassen, in denen ein Kreis mit dem Radius 33 den Punkt n-4n-4 hat, jetzt wird der letzte Punkt unberührt bleiben, aber ich kann keinen Kreis mit einem Radius größer als 1 platzieren in der Lage, irgendeine verallgemeinerte mathematische Lösung dafür zu sehen.

Answer 1

Wenn der Mittelpunkt der Kreise auf nicht-ganzzahlige X- und Y-Koordinaten platziert werden kann, ist dies entweder unmöglich, weil die Länge zu kurz ist, oder unendlich viele, da die Länge ausreicht und unendlich viele Übersetzungen vorhanden sind.

Also, da Sie die Ergebnisse berechnen müssen, werde ich annehmen, dass die Koordinaten von (M, M) sind ganze Zahlen.

Wenn es einen einzelnen Kreis gibt, dann ist die Lösung die Anzahl der Punkte, die der Kreis legal platzieren kann.

Wenn es mindestens zwei Kreise gibt, dann müssen Sie die Summe der Durchmesser berechnen und wenn das größer ist als die Gesamtlänge der Linie, über die wir sprechen, dann haben Sie keine Lösung. Wenn dies nicht der Fall ist, müssen Sie die Summe der Durchmesser von der Gesamtlänge subtrahieren, um Complementer zu erhalten. Du hast auch N! Permutationen, um die Reihenfolge der Kreise zu berechnen. Und Sie haben Complementer - 1 mögliche Standorte, wo Sie die Lücken zwischen den Kreisen verteilen können. Die Längen der Lücken G1, ..., Gn-1

Wir wissen, dass G1 + ... + Gn-1 = Komplementierers

Die Anzahl der möglichen Verteilungen von G1, ..., Gn -1 ist D. Die Formel wäre daher

N! * D

Die verbleibende Frage ist: Wie können wir D berechnen?

Lösung:

function distr(depth, maxDepth, amount) 
    if (depth = maxDepth) then 
     return 1 //we need to put the remaining elements on the last slot 
    end if 
    sum = 1 //if we put amount here, that is a trivial case 
    for i = amount - 1 to 0 do 
     sum = distr(depth + 1, maxDepth, amount - i) 
    end for 
    return sum 
end distr 

Sie müssen sich mit Tiefe distr nennen = 1, maxDepth = N-1, amout = Komplementierers