Alice Bob Coin最优解

Question

考虑一下我在hackerrank：硬币问题上发现的问题

爱丽丝和鲍勃坐在阳光下，喝着橙汁，看着一些迁徙的鸭子飞到非洲。“瞧，”爱丽丝说，“其中一只鸭子在地板上留下了一串金币。”“太棒了！”鲍勃喊道，“让我们用这一行硬币来玩个游戏吧。”我们轮流，每个人都会把一个硬币从“头”抛到“尾”状态。“好的，”爱丽丝同意并补充道，“但当我们抛硬币时，我们也可以选择在硬币之后立即抛硬币，即使硬币是”尾巴“，在这种情况下，它就变成了”头“。”“谁不能玩，谁就输。”他们俩同时喊道。狡猾的鲍勃知道，他可以依靠机智的IEEEXtreme选手来帮助他获胜。你能帮他吗？你的任务是编写一个程序，给出一系列的H/T字母，计算抛硬币游戏的胜算，如果有，或者报告没有获胜的动作，如果是这样的话。赢球是一种合法的动作，玩家可以立即获胜(因为没有更多的硬币可翻)，或者，在对手随后的任何一次移动之后，玩家都会有一个获胜的动作。例如，如果输入是TTTT，那么Bob就输掉了游戏(没有“head”，所以他不能玩，因此他输了)。对于输入的TTTTHTTTT，Bob通过翻转第五枚硬币赢；对于输入TTHHT，Bob通过翻转两个“头”(第三和第四枚硬币)赢；对于输入的THHTHTHT，如果鲍勃抛出第二和第三枚硬币，他就赢了。 输入要从控制台读取的输入文件包含一行，其中的字符串完全由字母H和T组成，表示硬币的状态，如前所述。 输出输出文件，将在控制台上写入，包含一行，只有一个数字。一个正数N意味着抛硬币是一个胜利的举动。一个负数，写在-N，意味着翻转N和N+1th硬币是一个成功的举措。零，书写为0，意味着没有获胜的移动。请注意，一般来说，对于给定的硬币列表，可以有几个获胜的动作。你的程序可以输出其中的任何一个。

我尝试了一种递归的回溯解决方案，但是“C”由于堆栈溢出抛出了一个分段错误。这是我的代码：(它部分工作)

    #include <stdio.h>

    int main()

    {

    char a[100];

    scanf("%s",a);

    printf("%d",check(a));



}

int check(char a[])

{

    //printf("%s\n",a);

    int i=0;

    for(i=0;i<strlen(a);i++){

        if(a[i]=='H'){

            a[i]='T';

            a[i+1]=a[i+1]=='H'?'T':'H';

            if(check(a)){

                a[i+1]=a[i+1]=='H'?'T':'H';

                if(check(a))a[i]='H';

                else return (i+1);

            }

            else return -(i+1);

        }

    }

    //printf("Lost\n");

    return 0;

}

有人能帮我吗？

Answer 1

您没有正确地取消您尝试的所有移动。如果你不撤销移动，你就永远无法回溯。

此外，您还将从check返回数字，该数字用作布尔函数。

这是一个有效的示例。

#include <stdio.h>
#include <string.h>

//#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define FLIP(x) ( ((x)=='H') ? 'T' : 'H' )


bool check(char* a) {
  DEBUG("%s\n",a);

  // Loop over the string.
  for (int i=0; i<strlen(a); i++) {
    // If this coin is a head, try flipping it.
    if (a[i]=='H') {
      // Try flipping just this coin.
      a[i]=FLIP(a[i]);
      // See if it is a win or a loss for the other player.
      if (!check(a)) {
        // A loss for the other player means a win for us!
        // Undo our last move.
        a[i]=FLIP(a[i]);
        return true;
      }
      // A win for the other player.  
      // See if flipping the next coin makes a difference.
      if (i+1 < strlen(a)) {
        a[i+1]=FLIP(a[i+1]);
        // See if it is a win or a loss for the other player.
        if (!check(a)) {
          // A loss for the other player means a win for us!
          // Undo our last two moves.
          a[i]=FLIP(a[i]);
          a[i+1]=FLIP(a[i+1]);
          return true;
        }
        // Still a loss.  Undo this move.
        a[i+1]=FLIP(a[i+1]);
      }
      // Still a loss.  Undo this move.
      a[i]=FLIP(a[i]);
    } // if (a[i]=='H')
  } // for (int i=0; i<strlen(a); i++)

  // Loss.
  return false;
}

int main() {
  char a[100];
  scanf("%s",a);
  if (check(a)) {
    printf("Winner!\n");
  } else {
    printf("Loser!\n");
  }
}

Answer 2

这可能是因为输入字符太多，而且它们正在溢出您的输入数组。

你可以试着换一条线：

char a[100];

将100增加到更大的数目。

Answer 3

当您输入字符H时，代码的这一部分将进入无限循环。

for(i=0;i<strlen(a);i++){
    if(a[i]=='H'){  // if passes when input char `H`  
        a[i]='T';   // its changed to `T`
        a[i+1]=a[i+1]=='H'?'T':'H'; // Here a[1] becomes `H`
        if(check(a)) {  // goes back to function call and loops infinitely 
           ...

因此，您需要检查您的算法要求对您的代码行为。