Gegeben eine ganze Zahl N Ich möchte zwei ganze Zahlen A und B finden, die A x B ≥ N mit den folgenden Bedingungen erfüllen:
Beispiel: 23. Mögliche Lösungen 3 × 8, 6 × 4, 5 × 5. 6 × 4 ist das Beste, da es nur einen leeren Platz im Gitter übrig lässt und "weniger" rechteckig als 3 × 8 ist.
Ein anderes Beispiel: 21. Lösungen 3 × 7 und 4 × 6. 3 × 7 ist die gewünschte.
Eine Brute-Force-Lösung ist einfach. Ich würde gerne sehen, ob eine clevere Lösung möglich ist.
Einfach.
Im Pseudocode
%Vor% und es wird immer beendet, der Abstand zwischen a und b höchstens nur 1.
Es wird viel schwieriger sein, wenn Sie die zweite Einschränkung entspannen, aber das ist eine andere Frage.
Edit: Da es scheint, dass die erste Bedingung wichtiger ist, müssen Sie das Problem angehen
ein bisschen anders. Sie müssen eine Methode angeben, um die Schlechtigkeit zu messen, die nicht quadratisch genug ist = 2. Bedingung, weil sogar Primzahlen als 1*number faktorisiert werden können und wir die erste Bedingung erfüllen. Angenommen, wir haben eine Schlechtenfunktion (sagen wir a >= b && a <= 2 * b ), dann faktorisieren N und versuchen verschiedene Kombinationen, um die beste zu finden. Wenn es nicht gut genug ist, versuchen Sie mit N+1 und so weiter.
Edit2: Nachdem ich ein bisschen mehr nachgedacht habe, komme ich mit dieser Lösung in Python:
%Vor%welche Ausgaben
%Vor%Ich denke, das könnte funktionieren (Ihre Bedingungen sind etwas mehrdeutig). diese Lösung ist etwas ähnlich zu anderen, im Grunde produziert rechteckige Matrix, die fast quadratisch ist. Möglicherweise müssen Sie beweisen, dass A + 2 nicht optimal ist
%Vor%Dies ist die Lösung, wenn die erste Bedingung dominant ist (und die zweite Bedingung nicht verwendet wird)
%Vor%Andere Bedingungen variieren zwischen
Tags und Links algorithm