c - C/C++中的仿真算法实现

Question

让一排8000盏灯。最初，只有位于左侧的那个被点亮。 然后，每一秒钟，都会执行以下操作:如果其左侧的灯在一秒钟前点亮，则每个灯都会更改状态(打开或关闭)。最左边的灯一直亮着。此操作是瞬时的。 当右端的灯第一次亮起时，该过程停止。 有多少盏灯亮着？

我下面的问题实现是错误的，你能帮帮我吗？

#include <cstdio>

int t[8001][2];

int main()
{
    t[1][0] = 1;
    t[1][1] = 1;
    int cpt1 = 0, ip = 0;
    while (t[8000][0] != 1 && t[8000][1] != 1)
    {
        ip++; 
        for (int j=2;j<8001;j++)
        {
            if(t[j-1][!(ip&1)])
                t[j][(ip & 1)] = !t[j][!(ip & 1)];      
        }
    }   

    for(int j = 1;j < 8001; j++)
        cpt1 += t[j][1];

    printf("cpt=%d\n", cpt1);
}

Answer 1

当左边没有变化时，代码缺少更新。

代码简化(基于零的偏移量，使用 bool)并在下面更正

#include<stdbool.h>
#include<stdio.h>
#define N 8000

bool t[N][2];

int main(void) {
  t[0][0] = true;
  t[0][1] = true;
  int ip = 0;

  while (t[N - 1][0] == 0 && t[N - 1][1] == 0) {
    ip = !ip;
    for (int j = 1; j < N; j++) {
      if (t[j - 1][!ip]) {
        t[j][ip] = !t[j][!ip];
      } else {
        t[j][ip] = t[j][!ip];  // add
      }
    }
  }

  int cpt1 = 0;
  for (int j = 0; j < N; j++) {
    cpt1 += t[j][1];
  }
  printf("N=%d cpt=%d\n", N, cpt1);
  return 0;
}

输出

N=8000 cpt=2048