0

任何人都可以给我一个想法，我如何在 Java 中计算以下问题。多少个可能的有效数字，其中有效数字是 0-9 之间的任何数字，长度为 10 位，不包括 # 或 *，棋子在通过电话键盘时可以追踪。假设我有一个国王，它只能像在真正的游戏中一样向任何方向移动，但一次只能移动一个单元格。

所以键盘看起来像这样：

         1  2  3
         4  5  6
         7  8  9
         *  0  #

所以棋子每次移动 10 步，它创建的每个唯一数字都是有效数字。一块从最初的起始位置开始它的旅程。

更新：一块可以移动或停留在一个地方（移动或停留都将被视为移动）以及重新访问单元格（只要其允许在各自的移动权限内）。因此，例如，如果国王从位置 1 移动，则创建有效数字的三个有效 10 步路径数字可能是 1236547890 或 1111111111 或 1212121212

这是一个小型版本的四格方形垫的代码，只有 4 个格子，仅用于测试目的：

public class King
{
private static final Integer[] ALLOWED_FROM_1 = {2, 3, 4};
private static final Integer[] ALLOWED_FROM_2 = {1, 3, 4};
private static final Integer[] ALLOWED_FROM_3 = {1, 2, 4};
private static final Integer[] ALLOWED_FROM_4 = {1, 2, 3};
List<Integer> visited;

public King()
{
    this.visited = new ArrayList<Integer>();

}

public List<Integer> get_destinations(int currentPos, int noOfMoves)
{
    if (noOfMoves == 0)
    {
        visited.add(currentPos);
        return visited;

    }
    else
    {

        List<Integer> possibleMoves = getPossibleMoves(currentPos);

        for (int i = 0; i < possibleMoves.size(); i++)
        {
            visited.add(possibleMoves.get(i));
            get_destinations(possibleMoves.get(i), noOfMoves - 1);

        }

        return visited;
    }



}


private List<Integer> getPossibleMoves(int currentPos)
{

    List<Integer> possibleMoves = new ArrayList<Integer>();

    switch (currentPos)
    {
        case 1 : possibleMoves.addAll(Arrays.asList(ALLOWED_FROM_1));
            break;

        case 2: possibleMoves.addAll(Arrays.asList(ALLOWED_FROM_2));
            break;

        case 3 : possibleMoves.addAll(Arrays.asList(ALLOWED_FROM_3));
            break;

        case 4 : possibleMoves.addAll(Arrays.asList(ALLOWED_FROM_4));
    }

    return possibleMoves;

}
}

上面的代码只产生了部分答案，缺少许多不同的排列。主要问题是我如何才能确保它产生所有排列，以及在上面的代码中什么时候准确地到达应该存储并稍后检索的 4 位数字（在 4 次移动之后）。另外，我怎样才能避免重新访问相同的序列，例如 1234 1234 ，所以基本上优化它，这样它就不会产生相同的路径序列/有效数字。

非常感谢所有帮助。

4

3 回答 3

0

对于国王来说，这种重复即将到来。2, 1, 2, 1, 3, 4, 3, 1 , 2, 3, 4, 2, 3, 4, 3, 1

您可以使 getPossibleMove() 函数以特定顺序返回单元格。这将有助于避免路径重复。只按数字顺序说，然后它应该返回

2, 1, 2, 1,
2, 1, 2, 3,
2, 1, 2, 5,
2, 1, 4, 1,
2, 1, 4, 5,
2, 1, 4, 7

此外，如果您不想让棋子移动到同一个单元格，只需在 getPossibleMove() 函数中删除这些单元格即可。

我没有得到写什么代码，所以只写了理论解释。

于 2012-04-27T06:34:38.127 回答
0

似乎是非常微不足道的学术递归问题。只要允许递归，语言应该无关紧要。

你需要：

  1. 设置一个。F(n,m) 数组（在您的情况下值为 3x4）b。和一块的初始位置。C。要允许任意片段，您可能需要定义定义允许移动的委托（函数指针，匿名类）函数

  2. 创建一个可递归调用的函数，用于识别下一个符合条件的位置，并将其作为输入：当前棋子位置（i，j），b。第一次迭代中的递归深度 1

  3. 从深度 = 10 的递归函数返回

  4. 如果您还需要所有序列，请使此递归函数可返回（非 void 类型）我会说字符串是最好的

  5. 如果您想让代码更简单，您不需要在允许的单元格集中的每个步骤上验证 *、# 的存在，只需验证最后 10 个符号长字符串即可解析为 UNSIGNED LONG。虽然它使递归太长。
于 2012-04-26T15:11:13.233 回答
0

这是一些可能有帮助的伪代码。您可以使用以下方法递归地解决问题：

// Returns a list of all the destinations given a current location
// and the number of moves allowed (10 for King)
list<int> get_destinations(int cur_location, int num_moves) {
  // Base case. If no more moves are allowed, return current location as list.
  if(num_moves == 0) {
    return as_list(cur_location);
  } else {
    // List of all destinations possible from here
    list<int> destinations;
    // Get all the possible moves that are 1 step away.
    // For example: from 1, we would return 2 and 4
    list<int> possible_moves = get_possible_moves(cur_location);

    // For each of the moves generated from the last step,
    // recursively call get_destinations() with (num_moves - 1)
    for(int n:possible_moves) {
      destinations += get_destinations(n, num_moves - 1);
    }

    return destinations;
  }
}

然后，您将使用以下内容调用此函数：

get_unique_nums(get_destinations); // Returns the set in the form you need it

祝你的家庭作业好运！

于 2012-04-26T14:54:18.477 回答