什么是卡爾達諾三元組？
如果一組任意三個正整數，比方說a，b并且c滿足條件
cbrt(a b(sqrt(c)) cbrt(a - b(sqrt(c)) == 1
解釋。
如果sum of Cubic Root of a (b * square root of c) and Cubic root of a - (b * square root of c) equals 1那么 (a, b, c) 被稱為卡爾達諾三元組。
cbrt 代表立方根，sqrt 代表平方根。
n將給出一個整數，因此我們在相加時取的數字 a、b 和 c 應小于或等于 n。
總之a b c <= n。
約束：n <= 2^31 -1。
問題
我已經做了一些事情來找出正確的三元組，但是當 n 的值大于 1000 時，程式將永遠運行。
public static void cardanoTriplets(long n) {
DecimalFormat decimalFormat = new DecimalFormat("#.###");
long numberOfPairs = 0;
for (long a = 0; a <= n; a ) {
for (long b = 0; b <= n; b ) {
for (long c = 0; c <= (n - a - b); c ) {
if ((a b c) == n) {
double val = b * Math.sqrt(c);
double LHS = Double.parseDouble(decimalFormat.format(Math.cbrt(a val)));
double RHS = Double.parseDouble(decimalFormat.format(Math.cbrt(a - val)));
double addedVal = LHS RHS;
//System.out.println("RHS and LHS -: ( " RHS " , " LHS " )");
if (addedVal == 1.0d) {
numberOfPairs ;
//System.out.println(a);
//System.out.println(b);
//System.out.println(c "\n");
}
}
}
}
}
System.out.println(numberOfPairs);
}
結果
當我通過的值N作為8，平均所用的時間以找到卡爾達諾三重是31毫秒并且有時低至16毫秒。結果是準確的，結果只有一個，三元組是 (2, 1, 5)。
但是當我將n的值傳遞為 1000 時，它會增加到大約1015 毫秒并且結果不那么準確。它錯過了近 19 個三胞胎。對于 n == 1000，三元組的總數為 149。
當 n > 1000 的值時，比如說5000，它花了29271 毫秒，大約 29 秒，找到的三元組是 3364。
有什么方法可以將花費的時間減少到合理的數量，例如少于 5 秒？
如果是這樣怎么辦？
我的設備規格：
處理器：AMD Ryzen 5 3500U 四核
記憶體：8 GB
使用的IDE：IntelliJ IDEA v2021.2.3（社區版）
謝謝 ：）
uj5u.com熱心網友回復：
這是一個數論問題；使用不精確的浮點數顯然是錯誤的。
正確的解決方案需要一些數學洞察力。卡爾達諾的名字是一個很好的提示。
表達方式
cbrt(a b(sqrt(c)) cbrt(a - b(sqrt(c))
描述了某個三次方程的根。具體來說，方程的根
x^3 px - q = 0
是
cbrt(q/2 sqrt((q/2)^2 (p/3)^3)) cbrt(q/2) - sqrt(q/2)^2 (p/3)^3))
與您的問題陳述進行比較，得出結論a = q/2，并且c*b^2 = (q/2)^2 (p/3)^3
因為a是整數，所以q必須是偶數，因為b, c也是整數，所以p必須能被 整除3。因此我們對方程感興趣
x^3 3ux - 2a = 0
有1作為根。這將問題縮小到搜索u, v這樣的1 3u - 2a = 0. 在這里u^3 a^2 = b^2*c。請注意，u必須是奇數。
所有這些觀察都導致了一個（偽）代碼：
for u in range(1, n, 2)
a = (1 3u)/2
t = u^3 a^2
find the largest b such that b^2 divides t
c = t / b^2
if a b c < n
they are a Cardano triplet
uj5u.com熱心網友回復：
您的第一個問題是回圈中回圈中回圈，n=1000 需要 1.000.000.000 輪。
如您所知，n = a b c，您可以去掉一個回圈。c 回圈并重寫為：
for (long a = 0; a <= n; a ) {
for (long b = 0; b <= (n - a); b ) {
long c = n - a - b;
所以你從 n * n * n -> n * n
如果方程是 n => a b c（如你的問題陳述），你可以使用：
for (long a = 0; a <= n; a ) {
for (long b = 0; b <= (n - a); b ) {
for (long c = 0; c <= (n - a - b); c ) {
其次，您正在將格式轉換為十進制，然后轉換回雙精度，因為 Math.cbrt 已經給出了雙精度。我建議不要這樣做。
“缺少19個三胞胎”的問題與上面的一點有關。您只接受 1.0d 作為正確答案，在上一步中您對雙打進行了格式化（很可能會出現四舍五入問題）。即使你會去掉格式，我相信最好允許更多的舍入誤差..
就像是：
if (0.999 < addedVal && addedVal < 1.001)
但是，我不知道這個方程的數學原理，因為你說有 149 個三元組肯定是有原因的。根據四舍五入確定你有不同的答案......我相信有類似數學證明的三元組是 1。
最后你能做什么：我相信 Math.cbrt 的計算不是那么快。你重復了很多次。您可以通過將 Math,cbrt 的結果放在 HashSet 中來跟蹤您的計算。Key 是 Math.cbrt 的輸入，Value 是結果。
所以首先檢查你是否已經在HashSet中擁有Key，如果沒有計算cbrt并放置它，如果已經可用我們它..
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/388160.html
上一篇：最小洗掉子陣列以使陣列等于目標