问tic tac toe的阶乘数组
EN

Stack Overflow用户

提问于 2012-03-09 04:05:41

回答 3查看 607关注 0票数 2

我目前正在尝试自学C++和一般编程。因此，作为一个初学者项目，我正在制作一个遗传算法，它为Tic-Tac-Toe游戏创建了一个最优的人工智能。我没有参加任何编程课程，所以这不是家庭作业。我只是对人工智能很感兴趣。

所以我尝试创建一个阶乘的多维数组，在我的例子中是9！例如，如果你做了3个中的一个！它将是array3 ={ {1，2，3}，{1，3，2}，{2，3，1}，{2，1，3}，{3，2，1}，{3，1，2}}。基本上是3！或者3*2*1是您可以按顺序排列3个数字的数量。

我认为解决方案应该是简单的，但我却卡住了，试图找出一个简单的解决方案。我试着交换它们，试着将它们向右移动，递增等等。有效的方法是显而易见的，我不知道如何对它们进行编码。

所以，如果你知道如何解决这个问题，那就太好了。如果你能给出一个编码格式，那就更好了。任何帮助都是非常感谢的。

另外，我用c++编写了这个代码。

c++

logic

校园云服务器 2H2G30元起

云+校园是针对学生用户推出的扶持计划，2核2G云服务器30元起，1核1G云数据库4元起，并享受免费体验6个月云开发

回答 3

Stack Overflow用户

回答已采纳

发布于 2012-03-09 04:10:50

你可以使用STL的next_permutation函数

http://www.cplusplus.com/reference/algorithm/next_permutation/

票数 3

Stack Overflow用户

发布于 2012-03-09 05:06:04

实际上，我曾经手工写过一个算法。这就是它：

bool incr(int z[NUM_INDICES]){
    int a=NUM_INDICES-1;
    for(int i=NUM_INDICES-2;i>=0;i--)
      if(z[i]>z[i+1]) a--;
      else break;
    if(a==0) return false;
    int b=2147483647,c;
    for(int i=a;i<=NUM_INDICES-1;i++)
      if(z[i]>z[a-1]&&z[i]-z[a-1]<b){
        b=z[i]-z[a-1];
        c=i;
      }
    int temp=z[a-1]; z[a-1]=z[c]; z[c]=temp;
    qsort(z+a,NUM_INDICES-a,sizeof(int),comp);
    return true;
}

这是增量函数(例如，你有一个像3,2,4,1这样的数组，你把它传递给它，它把它修改为3,4,1,2)。如果数组的最后d个元素是降序的，那么下一个数组(按字母顺序)应该满足以下条件: 1)最后的d+1元素是它们之间的排列；2)倒数d+1的最后一个元素是最后的d+1元素中的下一个最高元素；3)最后的d个元素应该是升序的。当你有2,5,3，8,7,6,4,1: d=5这样的元素时，你可以直观地看到这一点；3变成最后一个d+1 =6元素中的下一个最高的元素；最后的d=5按升序排列，所以它变成了2,5,4，1,3,6,7,8。

第一个循环基本上确定d。它向后循环数组，比较连续的元素，以确定末尾按降序排列的元素的数量。在循环结束时，a成为降序序列中的第一个元素。如果为a==0，则整个数组按降序排列，不能再执行其他操作。

下一个循环确定倒数第d+1个元素应该是什么。我们指定它应该是最后一个d+1元素中的下一个最高元素，所以这个循环决定了它是什么。(请注意，za-1是d+1倒数第二个元素。)在该循环结束时，b包含的最低z[i]-z[a-1]为正；也就是说，z[i]应大于z[a-1]，但应尽可能小(以便z[a-1]成为下一个最高的元素)。c包含相应元素的索引。我们丢弃了b，因为我们只需要索引。

接下来的三行交换了z[a-1]和z[c]，这样d+1倒数第二个元素就得到了下一个元素，而另一个元素(z[c])则保持z[a-1]。最后，我们使用qsort对最后d个元素进行排序(comp必须在其他地方声明；请参阅qsort上的C++文档)。

票数 2

Stack Overflow用户

发布于 2012-03-09 10:45:10

如果您需要一个手工创建的函数来生成所有排列，您可以使用

#include <cstdio>
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define GI ({int t;scanf("%d",&t);t;})

int a[22], n;

void swap(int & a, int & b) {
    int t = a; a = b; b = t;
}

void perm(int pos) {
    if(pos==n) {
        REP(i,n) printf("%d ",a[i]); printf("\n");
        return;
    }
    FOR(i,pos,n) {
        swap(a[i],a[pos]);
        perm(pos+1);
        swap(a[pos],a[i]);
    }
    return;
}

int main (int argc, char const* argv[]) {

    n = GI;
    REP(i,n) a[i] = GI;
    perm(0);

    return 0;
}