最快的硬币移动

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); 
     } 
    } 

} 

如果多个解决方案是最优的，您可以修改代码以返回一组列表。