C-爱丽丝·鲍勃硬币的最佳解决方案

考虑我在hackerrank上发现的这个问题：硬币问题

爱丽丝和鲍勃坐在阳光下。喝橙汁；看着一些迁徙的鸭子飞往非洲。爱丽丝指出，"看" 鸭子在地板上留下了一条金币。"伟大的！" 鲍勃大喊："让我们用这条硬币玩游戏。我们将轮流，我们每个人都将一枚硬币从"头"翻转到 "尾巴"状态"。"好"，同意爱丽丝并补充说："但是当我们翻转硬币时，即使那样，我们也可以选择立即翻转硬币硬币是"尾巴"，在这种情况下，它变成了"头"。"谁能不玩 - 输掉"他们俩同时哭泣。狡猾的鲍勃知道他可以依靠机智的Ieextreme参赛者来帮助他获胜。你能帮他吗？任务您的任务是编写一个程序给定一串H/T字母，计算 Flip-Coin游戏，如果有的话，或报告没有获胜移动，如果是这种情况。获胜的举动是法律举动，以至于玩家要么立即获胜（因为不再有硬币 flip），否则，在对手随后的任何一步之后，球员获胜。

例如，如果输入是tttt，那么鲍勃失去了游戏（没有 "头"，所以他不能玩，因此他输了）。对于输入tttthtttt，鲍勃通过翻转第五硬币而获胜；对于输入tthht，鲍勃获胜翻转"头"（第三和第四个硬币）；对于输入鲍勃（Bob）赢得硬币2和3的鲍勃（Bob

输入要从控制台读取的输入文件包含一行其中有一个完全由字母h和t组成的字符串，如解释的那样代表硬币的状态。

输出输出文件，要写在控制台上，包含一个线，一个数字。正数n表示翻转n 硬币是一个胜利的举动。负数，书面–n，意味着翻转n n 第1个硬币是一个胜利的举动。零，写 0，意味着没有获胜的举动。请注意，总的来说对于给定的硬币清单，可以是几个获胜的动作。您的程序可以输出任何一个。

我尝试了递归的回溯解决方案，但是" C"引起了由于stackoverflow而引起的分割故障错误。这是我的代码：（部分工作）

    #include <stdio.h>
    int main()
    {
    char a[100];
    scanf("%s",a);
    printf("%d",check(a));

}
int check(char a[])
{
    //printf("%sn",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("Lostn");
    return 0;
}

谁能帮我吗？

您无法正确删除尝试的所有动作。如果您不撤消动作，就永远不会回溯。

另外，您还从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("%sn",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");
  }
}

可能是输入字符太多，它们溢出了您的输入数组。

您可以尝试更改行：

char a[100];

将100增加到更大的数字。

当您输入字符 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 
           ...

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

相关内容

最新更新

热门标签：