本文介紹了尋找最少的移動次數(shù)的處理方法，對大家解決問題具有一定的參考價值，需要的朋友們下面隨著小編來一起學習吧！
問題描述
我有以下問題陳述：
給定一個數(shù)字n(1<；n<；10^9)，最少有多少
集合中的數(shù)學運算(n除以2，n除以3，
從n中減去1)可用于將數(shù)字n轉換為1？
到目前為止，我編寫了以下代碼來嘗試解決該問題：
while(n!=1){
if(n%3==0 || n%2==0){
if(n%3==0){
n=n/3;
c=c+1;
}
if(n%2==0){
n=n/2;
c=c+1;
}
}
else{
n=n-1;
c=c+1;
}
}
System.out.println(c);
但我沒有得到所需的輸出。有誰能幫我一下嗎？
推薦答案
最簡單的解決方案可能是探索所有可能性。
public static ArrayList<Integer> solve(int n,
ArrayList<Integer> moves, int bestMove,HashMap<Integer,Integer> memory) {
if (moves.size() >= bestMove) return null;
if (n == 1) return moves;
Integer sizeOfPathN= memory.get(n);
if (sizeOfPathN!=null && sizeOfPathN<=moves.size())return null;
memory.put(n,moves.size());
int size_1=Integer.MAX_VALUE, size_2 = Integer.MAX_VALUE, size_3 = Integer.MAX_VALUE;
ArrayList<Integer> moves3 = null, moves2 = null, moves1;
if (n % 3 == 0) {
ArrayList<Integer> c = new ArrayList<Integer>(moves);
c.add(3);
moves3 = solve(n / 3, c,bestMove,memory);
if (moves3!=null)
size_3 = moves3.size();
}
bestMove = Math.min(bestMove, size_3);
if (n % 2 == 0) {
ArrayList<Integer> c = new ArrayList<Integer>(moves);
c.add(2);
moves2 = solve(n / 2, c,bestMove,memory);
if (moves2!=null)
size_2 = moves2.size();
}
bestMove = Math.min(bestMove, size_2);
ArrayList<Integer> c = new ArrayList<Integer>(moves);
c.add(1);
moves1 = solve(n - 1, c,bestMove,memory);
if (moves1!=null)
size_1 = moves1.size();
int r = Math.min(Math.min(size_1, size_2),size_3);
if (r==size_1) return moves1;
if (r==size_2) return moves2;
return moves3;
}
說明：
n：N
moves：包含移動的ArrayList。(用于打印底稿)
bestMove：包含找到的最小解決方案大小的值。
memory：包含先前探索的”狀態(tài)”和路徑長度的HashMap。
如果我們調用
PUBLIC STATIC VOID Main(字符串[]參數(shù)){
long a = System.currentTimeMillis();
Object[] sol=solve(10, new ArrayList<Integer>(),Integer.MAX_VALUE,new HashMap<Integer,Integer>()).toArray();
System.out.println(sol.length);
System.out.println(Arrays.toString(sol));
System.out.println((System.currentTimeMillis()-a));
}
輸出為：
3
[1, 3, 3]
1
相當于n-1, n/3,n/3(@特里斯坦的最佳解決方案)
如果我們使用1000 000 000as n：
調用它
30
[1, 3, 3, 3, 3, 1, 3, 3, 1, 3, 1, 1, 3, 3, 3, 3, 1, 2, 2, 1, 3, 2, 1, 3, 3, 2, 1, 3, 2, 2]
55
如果我們用11調用：
4
[1, 1, 3, 3]
1
編輯：
如果只需要移動次數(shù)：
public static int solve(int n,int moves,int bestMove,HashMap<Integer,Integer> memory) {
if (moves >= bestMove) return Integer.MAX_VALUE;
if (n == 1) return moves;
Integer sizeOfPathN= memory.get(n);
if (sizeOfPathN!=null && sizeOfPathN<=moves)return Integer.MAX_VALUE;
memory.put(n,moves);
int size_1=Integer.MAX_VALUE;
int size_2 = Integer.MAX_VALUE;
int size_3 = Integer.MAX_VALUE;
moves=moves+1;
if (n % 3 == 0) size_3 = solve(n / 3, moves,bestMove,memory);
bestMove = Math.min(bestMove, size_3);
if (n % 2 == 0) size_2=solve(n >> 1, moves,bestMove,memory);
bestMove = Math.min(bestMove, size_2);
size_1 = solve(n - 1, moves,bestMove,memory);
return Math.min(Math.min(size_1, size_2),size_3);
}
使用
調用此方法
long a = System.currentTimeMillis();
System.out.println(
solve(1000 *1000*1000, 0,Integer.MAX_VALUE,new HashMap<Integer,Integer>()));
System.out.println((System.currentTimeMillis()-a));
輸出：
30
24
足夠快
這篇關于尋找最少的移動次數(shù)的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，
