1

我正在做一个 Java 作业，我完全被难住了。

问题是：

使用递归编写一个函数来执行以下操作：您有 X 张不同的卡片。你只有 Y 个信封。Y 小于或等于 X。对于 X 和 Y 的任何给定值，

  1. 当订单不重要且不允许重复时，显示您可以填写 Y 信封的所有可能方式。hint: X! / (( X-Y)! * Y!)

  2. 当订单很重要且允许重复时，显示您可以填写 Y 信封的所有可能方式hint: X^Y

  3. 当订单很重要且不允许重复时，显示您可以填写 Y 信封的所有可能方式提示：X! / (X – Y)!

  4. 当顺序不重要且允许重复时，显示所有可能的方式来填充 Y 信封提示：(X + Y – 1)! / (Y! * (X – 1)!)

例如，在情况 (1) 下，if X = {J, Q, K, A) and Y = 3输出应为：{J,Q,K} {J,Q,A} {J,K,A} {Q,K,A}.

我不希望任何人发布任何代码，我也不想找人帮我解决这个问题！我希望一旦我完成了第一部分（问题a），它将打开闸门。有人可以在制定伪代码算法方面提供一些指导吗，据我所知：

用增加的卡片依次填充 Y 信封 用最高的卡片(ex: X=5, Y=3) {1, 2, 3}. 替换最高的信封{1, 2, 5}，递减直到我们找到它的原始值{1, 2, 4}。对从最高到最低的每个信封执行此操作（其中数字尚未使用）{1, 5, 4} {1, 3, 4} {5, 3, 4} {2, 3, 4}.

这是我在它崩溃之前得到的，因为它缺少 3 个组合{1, 5, 3} {3, 4, 5} {5, 3, 2}.

我将不胜感激任何帮助，因为这是我将重复的任务，我不想要解决方案，我需要帮助自己解决问题。谢谢！

编辑：我已经尝试了概述的所有 3 种解决方案，但我仍然没有得到它。这就是我到目前为止所得到的：

public static void comboNoRep(String[] a, int y, boolean[] used)
{

    if(y == 0) {
        // found a valid solution.
        System.out.println(result);
    }

    for(int i=0; i<a.length; i++) {
        if(!used[i]) {
            used[i] = true;
            result = result + a[i];
            comboNoRep(a, y - 1, used);
            result = result + " ";
            used[i] = false;
        }
        else {
        }
    }

}

谁能帮忙指出我的缺点？

4

4 回答 4

1

你的老师希望你使用递归。

对于给定的 X，如果 Y 为零，答案是什么？使用您的代码解决此问题。

答案是什么，对于给定的 X，如果我免费为您提供 Y = 某个随机整数 n 的解决方案，那么 n + 1 的解决方案是什么？换句话说，如果我告诉你 X = 5, Y = 3 的解是 { { ... }, { ... }, ... }，你能很容易地找出 X = 5 的解吗？ Y = 3 + 1 = 4？

这是一个完全不同的问题的示例：

假设您知道前两个斐波那契数是 1 和 1。那么找到下一个很容易，对吧？它是 2。现在假设你知道前两个是 1 和 2，下一个是 3！如果前两个是2和3，下一个是5！

一些伪代码：

public int fib(int stop) {
     if (stop < 2) return 1;
     return fibHelp(stop - 2, 1, 1);
}

public int fibHelp(int stop, int oneBelow, int twoBelow) {
   if (stop == 0) return oneBelow;

   return fibHelp(stop - 1, oneBelow + twoBelow, oneBelow);
}

看看 fibHelp 是如何调用自己的？那是递归！只要确保你有一个停止条件（我的 if 语句）。

对于您的具体问题，不要 return void，而是要comboNoRepreturn a Set<Set<Integer>>。当 时y=0，返回Set带有一个元素的 a（一个空的Set）。y=1，返回 a通过向更大集合中的每个集合添加一个元素来Set构建一堆s（在它为空的情况下，依此类推）。Sety=1Set

使用Set而不是List因为您想确保没有重复项。

于 2012-11-04T03:06:16.623 回答
0

第一部分可以使用埃克塞特算法。请参阅以下链接以获取更多信息：

访问这里：http://www.bearcave.com/random_hacks/permute.html

我不知道如何在 JAVA 中执行此操作，但我的旧 C 代码片段可能会达到目的。

#include <stdio.h>

//Print Function
void print(const int *arr, const int size)
{
    int i;

    if (arr != 0) 
    {
        for (i = 0; i < size; i++)
            printf("%d ", arr[i]);
        printf("\n");
    }
}

//Permute Function
void permute(int *arr, const int start, const int sets, const int len)
{  
    int i,tmp;

    if (start == sets-1)
        print(arr, sets);
    else
    {
        for (i = start; i < len; i++)
        {
            tmp = arr[i];

            arr[i] = arr[start];
            arr[start] = tmp;

            permute(arr, start+1, sets, len);   //<-- Recursion

            arr[start] = arr[i];
            arr[i] = tmp;
        }
    }
}

int main()
{
  int sets,arr[] = {1, 2, 3, 4, 5};

  //Accept Number Of Sets To Form
  printf("Enter Number Of Sets: ");
  scanf("%d",&sets);

  //Call Permute Function
  permute(arr, 0, sets, sizeof(arr)/sizeof(int));

  return 0;
}
于 2013-09-29T07:05:00.400 回答
0

您必须探索所有可能的路线：

创建一个空的“解决方案”列表

对于每张卡片 a，您的第一组解决方案首先将卡片放在每个信封中 - x*y 解决方案

对于您选择的每张卡片：重复，从同一组卡片中删除您使用的卡片，直到您完成解决方案并将其放入数组中时用完卡片

打印数组

于 2012-11-04T02:57:42.373 回答
0

对于问题一，假设您的卡被命名card_1为card_x。请注意，填充 Y 信封的所有可能方式都包含card_1或不包含。如果是这样，您已将问题减少到用卡片 2 到 X 填充 Y-1 信封；如果不是，您已将问题减少到用卡片 2 到 X 填充 Y 信封。

希望这足以为您提供帮助而不会太多。祝你好运！

于 2012-11-04T03:02:15.510 回答