c – 在n * n棋盘上争夺q主教的算法

概述我正在使用C,但我的问题更多的是算法而不是实现. 问题如下： Write a program that inputs two integers n and k, where n>=k. Your program should calculate the number of different ways that k bishops could be placed on an nXn chessbo 我正在使用C,但我的问题更多的是算法而不是实现.

问题如下：

Write a program that inputs two integers n and k,where n>=k. Your program should calculate the number of different ways that k bishops Could be placed on an nXn chessboard.

我的基本想法是将每个主教表示为具有X值和Y值的结构.然后我将主教放在板上以获得配置.

我写了一个名为movetoNextPlace的方法,它允许我将主教移动到下一个可用的位置.我返回一个字符串来帮助调试.

struct bishop {int y=0;int x=0;string movetoNextPlace (int n){    if (y<n-1) {y++; return "move to next y value";}    else if (x<n-1) {x++; return "move to next x value";}    else {reset(); return "reset";};}voID setValueslike (bishop b){    y=b.y;    x=b.x;}voID reset (){    y=0;    x=0;}bool clashesWith (bishop b){    if (b.x==x && b.y==y){        return true;    }    if ( b.y-y == b.x-x ) return true; //if their slope is 1    return false;}};

然后我通过使用我想要的设置调用findSolutions将电路板设置为初始配置.

int findSolutions (int k,int n){ //k bishops on n*n boardbishop *b = new bishop [k];for (int i=0; i<k; i++){    findAspot (b,n,i);}}bool check (int num,bishop b[]){for (int i=0 ; i<num; i++){    if (b[i].clashesWith (b[num])) return false;}return true;}voID findAspot (bishop b[],int n,int num){ //n=boardsizewhile (1){    if (check(num,b)){return;}    if (b[num].movetoNextPlace(n) == "reset") break;}b[num-1].movetoNextPlace(n);findAspot (b,num-1);b[num].setValueslike ( b[num-1] );findAspot (b,num);}

然后,我想继续回溯,直到我有多个解决方案,但我不知道如何找到下一个解决方案.

我以为我可以写一个findNextSolution,它会在findSolutions函数结束时被调用,直到它到达一个循环.但我不知道用什么算法来寻找下一个解决方案.

解决方法 你想要将主教阵地存放在一个阵列中,这是一个良好的开端.这是电路板状态的紧凑表示.

你必须纠正检查一位主教是否与另一位主教发​​生冲突的方法.请记住,两个冲突的主教可以被垂直距离dy和水平距离dx分开,使得dx == -dy.因此,您需要比较绝对值：如果abs(dx)== abs(dy),主教会发生冲突.

现在讨论计算k主教在没有冲突的情况下安排的董事会状态数的一般问题.您需要定义一个返回整数值的函数.让我们说这个函数看起来像

count(currentBishops,numRemaining)

其中currentBishops是主教的可行位置,numRemaining是你还没有放置的主教的数量.

然后问题的解决方案是

count([],k)

其中[]表示尚未安置主教.

计数功能可以根据以下伪代码实现.

count(currentBishops,numRemaining):  if numRemaining == 0:    return 1  sum = 0  for each possible board position (x,y):    if (x,y) does not clash with any bishop in currentBishops:      let nextBishops be currentBishops augmented with (x,y)      sum += count(nextBishops,numRemaining-1)  return sum

为了避免递归调用的指数级爆炸,您需要缓存每个子问题的结果.这种技术称为memoization,您可以按如下方式实现.

let memo be a map from (currentBishops,numRemaining) to an integer valuecount(currentBishops,numRemaining):  if numRemaining == 0:    return 1  if memo contains (currentBishops,numRemaining):    return memo[(currentBishops,numRemaining)]  sum = 0   for each possible board position (x,numRemaining-1)  memo[(currentBishops,numRemaining)] = sum  return sum

currentBishops的映射应该是一个不关心你放置主教的顺序的映射.您可以通过在计算备忘录密钥时对主教职位进行排序或制作董事会位图来实现此目的.

总结

以上是内存溢出为你收集整理的c – 在n * n棋盘上争夺q主教的算法全部内容，希望文章能够帮你解决c – 在n * n棋盘上争夺q主教的算法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。