最快的硬幣移動

Question

我有一個難題，我需要通過刪除一些條件中的17來減少一個數字爲零。以下是您理解的難題。

從138個硬幣開始，找到最少移動次數達到0個硬幣。隨着每一步你可以（a）丟棄17個硬幣，（b）丟棄1個硬幣或（c）丟棄一半硬幣（但只有當你有偶數個硬幣時）。編寫一個程序，測試所有可能的移動組合並打印最快移動組合所需的移動次數。

我發現使用下面的代碼最快的移動。現在，我需要找出其他可能的動作，但我堅持下去。有人能幫忙嗎？

package com.infy.cis.test; 

public class CoinMovementPuzzle { 

    static int times=0; 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     numDiv(138,2,17,1); 

    } 
    public static void numDiv(int a, int b,int c,int d) { 

     if(a!=0) 
     { 
      int remainder=a%b;; 
      if(remainder==0 && a>=2) 
      { 
       evenNumber(a,b); 
      } 
      else if(remainder!=0 && a>=17) 
      { 
       oddNumber17(a,c); 
      } 
      else 
      { 
       oddNumber1(a,d); 
      } 

     } 
     System.out.println("FINAL"+times); 
     } 
    private static void oddNumber1(int a,int d) { 
     // TODO Auto-generated method stub 
     a=a-d; 
     times=times+1; 
     System.out.println("odd number::"+a+"::"+times); 
     numDiv(a, 2,17,1); 

    } 
    private static void oddNumber17(int a,int c) { 
     // TODO Auto-generated method stub 
     //int rem; 
     int rem=a%c; 
     a/=c; 
     times=times+a; 

     System.out.println("odd number::"+a+"::"+times); 
     numDiv(rem, 2,17,1); 

    } 
    private static void evenNumber(int a,int b) { 
     // TODO Auto-generated method stub 
     a/=2; 
     times=times+1; 
     //System.out.println(a/=b); 
     //remainder=a%b; 
     System.out.println("Value of a"+a); 
     System.out.println("even number::"+a+"::"+times); 
     numDiv(a, 2,17,1); 


    } 
} 

Answer 1

這與改變問題類似。如果您想要以最少的移動次數找到方法，則動態編程方法將起作用。您建立了一個數組a[i],i=0..138並從最小到最大。從a[0]=0開始。您在a[i]中存儲的號碼是min(a[i-1]+1, a[i-17]+1, a[i/2]+1 (if i even))。工作你的方式達到a[138]。然後找到實際的移動順序，找出a[138-1],a[138-17],a[138/2]中的哪一個小於a[138]並重復，直到您點擊0。

a[0] = 0 
for i = 1 to 138 
    if (i<17) 
    if (i odd) 
     a[i] = a[i-1]+1 
    else // i even 
     a[i] = min(a[i-1]+1, a[i/2]+1) 
    else // i >= 17 
    if (i odd) 
     a[i] = min(a[i-1]+1, a[i-17]+1) 
    else // i even 
     a[i] = min(a[i-1]+1, a[i-17]+1, a[i/2]+1) 
    // end if 
// a[138] now contains the minimum number of moves 
// find the actual sequence by working backwards 
i = 138 
while (i>0) 
    if a[i-1] < a[i] 
    print -1 
    i = i-1 
    else if a[i-17] < a[i] 
    print -17 
    i = i-17 
    else if a[i/2] < a[i] 
    print /2 
    i = i/2 
    else 
    // shouldn't end up here 
    print error 

這是發現的最大，在我看來，最好的辦法，但它不回答你的問題，因爲它沒有找到所有的答案，然後從中挑選最好的。

您可能會找到解決方案，使用較少的內存來解決更大的問題。

如果你想找到的最小序列可以使用遞歸這樣的事情很難，緩慢的方式：

sequenceOfMoves(string sequenceSoFar, int targetNumber) 
    if targetNumber is 0, print sequenceSoFar // done 
    if targetNumber > 0 sequenceOfMoves(sequenceSoFar + "-1", targetNumber-1) 
    if targetNumber > 16 sequenceOfMoves(sequenceSoFar + "-17", targetNumber-17) 
    if targetNumber is even sequenceOfMoves(sequenceSoFar + "/2", targetNumber/2) 

您最初的電話應該是sequenceOfMoves("", 138)

要回答這個問題，你需要存儲序列而不是打印它們，然後當遞歸完成時，在存儲器中搜索最短的移動序列。將他們全部打印出來，標記爲最短的贏家。

Answer 2

該解決方案將打印出相反的順序最好的（但不是全部）的舉動： 它的工作原理是利用廣度優先搜索算法，通過嘗試所有可能的組合，並選擇在每個階段的最優者。

import java.util.ArrayList; 
import java.util.List; 

public class Main { 


    List<String> getMinMoves(int amount){ 

     if (amount <= 0){ 
      return new ArrayList<String>(); 
     } 

     int numMovesSubtractingSeventeen = Integer.MAX_VALUE; 
     List<String> movesSubtractingSeventeen = null; 
     if (amount >= 17){ 
      movesSubtractingSeventeen = getMinMoves(amount - 17); 
      numMovesSubtractingSeventeen = 1 + movesSubtractingSeventeen.size(); 
     } 

     List<String> movesSubtractingOne = getMinMoves(amount - 1); 
     int numMovesSubtractingOne = 1 + movesSubtractingOne.size(); 

     List<String> movesDividingByTwo = null; 
     int numMovesDivideByTwo = Integer.MAX_VALUE; 
     if (amount % 2 == 0) { 
      movesDividingByTwo = getMinMoves(amount/2); 
      numMovesDivideByTwo = 1 + movesDividingByTwo.size(); 
     } 

     if (numMovesSubtractingSeventeen < numMovesSubtractingOne){ 
      if (numMovesSubtractingSeventeen < numMovesDivideByTwo){ 
       movesSubtractingSeventeen.add("Subtract 17 from " + amount); 
       return movesSubtractingSeventeen; 

      } else { 
       movesDividingByTwo.add("Divide " + amount + " by 2"); 
       return movesDividingByTwo; 
      } 
     } else { 
      if (numMovesSubtractingOne < numMovesDivideByTwo) { 
       movesSubtractingOne.add("Subtract 1 from " + amount); 
       return movesSubtractingOne; 
      } 
      else { 
       movesDividingByTwo.add("Divide " + amount + " by 2"); 
       return movesDividingByTwo; 
      } 
     } 
    } 



    public static void main(String[] args) { 
     Main main = new Main(); 
     List<String> moves = main.getMinMoves(138); 
     System.out.println("Min number of moves: " + moves.size()); 
     for (String move : moves){ 
      System.out.println(move); 
     } 
    } 

} 

如果多個解決方案是最優的，您可以修改代碼以返回一組列表。