最快的硬币运动

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

此解决方案将以相反的顺序打印出最佳（但不是全部）着法：它的工作原理是使用广度优先搜索算法，尝试所有可能的组合并在每个阶段选择最佳组合。

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

}

您可以将代码修改为return一组列表，以防有多个最优解。

Answer 2

这类似于一个改变问题。如果您想找到移动次数最少的方法，可以使用动态编程方法。您设置一个数组 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。 =24=]

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)

要回答这个问题，您需要存储序列而不是打印它们，然后在递归完成后，在您的存储中搜索最短的移动序列。将它们全部打印出来，将最矮的标记为获胜者。

最快的硬币运动

Fastest coin movement

java

puzzle