最快硬币运动

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

}

在多个解决方案最优的情况下，您可以修改代码以返回一组列表。