有人可以幫我解決這個問題嗎？
陳述： - 我們可以在 K 步中僅使用 2 次運算從 0 開始的最大可能 n 位數是多少：-乘以 3 或增加 2。
示例：N = 2 K = 5；-> (0->2->6->8->24->72) 72 是答案
N = 2 ，K = 51 -> (0->2->6->8->10->30->32->96->98)。98 是我們可以獲得的最大值，因此需要檢查其余的動作。
我的 2 狀態遞回解決方案：-
public static void largestNDigitNumber(long[] highest, long maxValue, long k, long currentValue) {
if (highest[0] == (maxValue - 2)) return; //no need to do anything as we get 98 as highest.
if (k < 0) return; //checking for steps
if (highest[0] < currentValue && currentValue <= (maxValue - 2)) {
highest[0] = currentValue;
}
largestNDigitNumber(highest, maxValue, (k - 1), (currentValue * 3));
largestNDigitNumber(highest, maxValue, (k - 1), (currentValue 2));
}
public static void main(String[] args) {
int n = 2;
long k = 51;
long maxValue = (long) Math.pow(10, n);
long[] highest = new long[1];
largestNDigitNumber(highest, maxValue, (k - 1), 2);
if (highest[0] < (long) Math.pow(10, (n - 1))) {
System.out.println("-1"); // if it is not possible to make n digit in given steps
} else System.out.println(highest[0]);
}
當“k”很小時，它給出了正確的答案，但對于較大的“k”值，它不顯示任何輸入。對于 n=2 和 k = 51，它不顯示任何內容。
請幫助我改進此代碼
uj5u.com熱心網友回復：
這個問題相當于問什么是小于 10^n/2 且數位和加長度小于或等于 k 1 的最大基數為 3 的數。（答案是基數為 3 的數字的兩倍）。
例如，N=2 K=5。小于50，長度加數和小于等于6的3進制最大數是多少。答案：1100（十進制36），所以原題答案是36*2=72。
對于 N=2，K=51，小于 50 的最大基數為 3 的數字是 2001（十進制 49）并且長度總和加數字總和 = 7，這遠小于 K 1。
鑒于這種表示，很容易在 O(n) 時間內解決問題（實際上，您可以使用鉛筆和紙解決它）。基數為 3 的數字的長度 d 盡可能大，使得 3^d < 10^n/2 且 d<=K。然后從最重要的開始貪婪地填寫數字的數字，直到您有數字和 K 1-d （或者您用完數字）。
等價
首先請注意，在不失一般性的情況下，您可以假設您永遠不會 2連續進行三個操作，因為通過 2在最近的操作之前插入單個操作*3（或者 2 * 3如果沒有*3操作，則簡單地替換它）可以更有效地完成。假設您已將當前數字表示為以 3 為底的雙倍數字。一個 2操作對應于將 1 添加到底部數字（由于上面的觀察，這永遠不會溢位到下一列）。甲*3操作移動所有的數字向上一列，引入0作為底數字。請注意，由于數字翻了一番，因此該 2操作僅將 1 加到以 3 為底的數字上！
由此可以看出，可以通過觀察加倍的 base-3 數字來計算操作次數。因為*3引入了一個新的數字，并且 2把數字和加1，所以運算次數等于數字加1，再加上數字和。
舉個例子。假設您有兩倍的 base-3 數字 2 * 2101，那么這等效于2 * (1 3*3*(1 3*(1 1)))) = (2 3*3*(2 3*(2 2)))。
uj5u.com熱心網友回復：
我試過這樣的事情。它似乎作業正常。
getMaxNumber(2, 5) ==> 72
getMaxNumber(2, 51) ==> 98
private int getMaxNumber(int n, int k){
int N = 0;
for (int i = 0; i < n; i ) {
N = N * 10 9;
}
int[] result = new int[1];
helper(N, k, 0, 0, result);
return result[0];
}
private void helper(int N, int K, int n, int k, int[] result){
if(n > N) return;
if(k <= K){
result[0] = Math.max(result[0], n);
}
if(n > 0)
helper(N, K, n * 3, k 1, result);
helper(N, K, n 2, k 1, result);
}
uj5u.com熱心網友回復：
保持原始遞回方法的風格。我對其進行了一些修改以產生一個有效的解決方案：
public static long largestNDigitNumber(int n, long currentK, long maxK, long currentValue) {
if (currentK > maxK || n < 1 || maxK < 1) return 0;
if (currentValue >= Math.pow(10, n))
return 0;
long c1 = largestNDigitNumber(n, currentK 1, maxK, currentValue * 3);
long c2 = largestNDigitNumber(n, currentK 1, maxK, currentValue 2);
if (c1 == 0 && c2 == 0)
return currentValue;
return c1 > c2 ? c1 : c2;
}
public static void main(String[] args) {
int n = 2;
long k = 51;
long largest = largestNDigitNumber(n, 0, k, 0);
System.out.println(largest); //98
}
這種遞回方法在這里回傳值而不是使用陣列。因此，在回傳之前檢查一個回傳值是否大于另一個或它們都為 0。
uj5u.com熱心網友回復：
2 和 *3 操作都保持奇偶校驗，所以從 0 開始我們只能達到偶數。我們可以從最高的偶數開始搜索：8、98、998、9998 等，看看到 0 的最短距離是多少。
如果我們正在尋找最短距離，那么可以做出的選擇就更少了。如果當前數字是 3 的倍數，那么有兩種選擇，要么除以 3，要么減 2。否則唯一的選擇就是減 2。我懷疑在大多數情況下，除以 3 是更好的選擇，所以這可能是第一個嘗試讓樹變小的人。
如果最小步數小于 K，則可以根據需要使用盡可能多的除以 3 操作來生成正確的 K
如果最小步數等于K，那么問題就解決了。
如果最小步數大于 K，則您需要選擇一個較低的起始數。作為初始計算的一部分，一些偶數已經被覆寫。您可以“免費”獲得這些，前提是您包括少量的記錄保存。您只需要檢查之前由于“除以 3”步驟而遺漏的大偶數。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/395981.html
上一篇：如何有效地確定完美冪？