Ich schreibe ein Computerprogramm/einen Algorithmus, um die Anzahl der ganzzahligen Punkte innerhalb einer Kugel mit Radius R und D am Ursprung zu zählen . Im Wesentlichen, wenn wir eine Sphäre der Dimension 2 (Kreis) und Radius 5 haben, ermittle ich alle ganzzahligen Lösungen für die Ungleichung X^2 + Y^2 ≤ 25. Gibt es einen effizienten Weg, statt jeden möglichen ganzzahligen Punkt zu zählen die Punkte zählen? Symmetrie verwenden?Ermitteln der Anzahl der ganzzahligen Punkte in einer Kugel mit Radius R und Dimension D zentriert am Ursprung
Antwort
Angenommen, die Dimension ist 3 und R ist der Radius. Für z = 0 sind die möglichen x, y Koordinaten die Punkte innerhalb eines Kreises mit dem Radius R, und für jedes z sind die x, y die Punkte innerhalb eines Kreises mit dem Radius sqrt (R * R - z * z); die möglichen Werte von z sind -r, .. 0, 1, .. r wobei r die kleinste ganze Zahl kleiner als R ist. Beachten Sie, dass die Anzahl für z und -z gleich ist.
Wenn wir zu Dimension 1 kommen, fragen wir, wie viele ganze Zahlen ich | i | < R, und dies ist 1 + 2 * r
So:
int ncip(int dim, double R)
{
int i;
int r = (int)floor(R);
if (dim == 1)
{ return 1 + 2*r;
}
int n = ncip(dim-1, R); // last coord 0
for(i=1; i<=r; ++i)
{ n += 2*ncip(dim-1, sqrt(R*R - i*i)); // last coord +- i
}
return n;
}
Nun, mit Symmetrie können Sie immer nur alle Ganzzahllösungen auf der positiven Seite zählen und dann die Komponenten invertieren. Also, im Falle Ihres Kreises (D = 2, R = 5), müssen Sie nur
{X, Y ∈ N: X² + Y² ≤ R} finden. Dann erstellen Sie die Kombinationen (X, Y), (X, -Y), (-X, Y), (-X, -Y)
Dies lässt Sie mit nur (1/2) D Lösungen zu finden.
Sie können auch einen Kreis mit dem Radius R als Quadrat mit dem Radius R/√ 2 annähern, sodass alle Kombinationen von Ganzzahlen, die kleiner oder gleich sind, automatisch hinzugefügt werden können.
- 1. Plot Punkte auf einer Kugel in R
- 2. Konzentrische Kreise wie ein Gitter, zentriert am Ursprung
- 3. Der beste Weg, um alle Punkte des Gitters in der Kugel zu finden
- 4. Mit Fibonacci-Gittern gleichmäßig Punkte auf einer Kugel anordnen
- 5. Erzeugen Sie Punkte auf einer Kugel innerhalb eines bestimmten Radius von einem Punkt aus
- 6. Ermitteln der Anzahl der printf-Argumente
- 7. Zählen der Anzahl der Punkte in einer Zeichenfolge
- 8. Punkte Hinzufügen in R filled.contour - am richtigen Ort
- 9. Anzahl der Vektorwerte im Bereich mit R
- 10. affine Transformation auf der Kugel
- 11. Anzahl der Daten in R
- 12. Das Volumen einer Kugel?
- 13. Anzahl der Punkte in einem Bild
- 14. R, wie bewegt man den Ursprung der Zeichnungsachse in ggplot2?
- 15. Anzahl der in Java erstellten Objekte ermitteln
- 16. Ermitteln der Dimension mit der höchsten Varianz mit scikit-learn PCA
- 17. Ermitteln der Anzahl der GDI-Handles und USER-Objekte
- 18. Finden Sie alle Punkte mit ganzzahligen Koordinaten im Tetraeder
- 19. Anzahl der Zeilen in JTextPane ermitteln
- 20. Ermitteln der Anzahl der Zeilen in einem Textfeld in VBA
- 21. Steuern der Anzahl der Panels in einem Gitterplot mit R
- 22. Ermitteln der Anzahl der Frames in einem Core Audio AudioBuffer
- 23. r Punkte in Polygonen
- 24. Anzahl der Punkte innerhalb einer Gruppe außerhalb eines Schwellenwerts suchen
- 25. Anzahl der Zeilen in einer Java-Ergebnismenge ermitteln
- 26. Drehen einer Kugel von Punkt zu Punkt
- 27. Würfel in Kugel verwandeln
- 28. Ermitteln der Entfernung mit Mapkit
- 29. R findet die nächsten Punkte in der Matrix
- 30. Anzahl der Zeilen in Matrix mit doppelten Zeilen ermitteln
@Sean Cline: Die Frage _all_ ganzzahligen Punkten innerhalb der Kugel REGARDS zählen, etwa gleich sein Volumen. Ich sollte denken, dass es eher eine Frage der (diskreten) Mathematik ist. Ich wäre nicht überrascht, wenn es dafür eine clevere analytische Formel ("O (1)") gäbe. – doynax
Warum brauchen Sie eine neue Frage ähnlich der bestehenden? Bearbeiten Sie alte Fragen, fügen Sie neue Gedanken und Tags hinzu, wenn Sie möchten. – MBo