C++中如何解决"三七二十一"问题 |21xrx.com

C++中如何解决"三七二十一"问题

2023-07-02 20:12:36 深夜i -- --

C++ 三七二十一问题解决方案

"三七二十一"问题是一个经典的面试题，在C++中可以采用数学的方法和普通的递推方法分别解决。

方法一：数学公式

首先，我们可以通过数学公式来求解"三七二十一"问题。根据题意，我们可以列出如下式子：f(n) = (f(n-1)+k) % n，其中n为每一轮剩余人数，k为报数的数量，f(n)为结果。最终留下的人即为f(n) = 0的时候，此时的n为所求。

代码如下：


#include <iostream>
using namespace std;
int main()
{
  int n, k, last;
  cin >> n >> k;
  int ans = 0;
  for (int i = 2; i <= n; i++) {
    ans = (ans + k) % i;
  }
  cout << ans + 1 << endl;
  return 0;
}

方法二：递推式

除了数学公式外，我们还可以通过递推式来求解"三七二十一"问题。我们可以用一个数组存储每一轮的剩余人数，并不断更新这个数组，直到留下的人数为1时，此时的下标即为所求。

代码如下：


#include <iostream>
using namespace std;
int main()
{
  int n, k;
  cin >> n >> k;
  bool vis[1001]; // vis数组表示当前编号的人是否还在游戏中
  for (int i = 1; i <= n; i++) {
    vis[i] = true;
  }
  int left = n; // 初始化剩余人数
  int cur = 0; // 当前编号的人
  while (left > 1) {
    for (int i = 1; i <= k; i++) {
      do { // 找到下一个在游戏中的人
        cur = (cur + 1) % n;
        if (cur == 0)
          cur = n; // 最后一个人
        
      }while (!vis[cur]);
    }
    vis[cur] = false; // 标记当前编号的人已经退出游戏
    left--; // 剩余人数减1
  }
  for (int i = 1; i <= n; i++) {
    if (vis[i])
      cout << i << endl; // 输出剩余的人的编号
      break;
    
  }
  return 0;
}

以上两种方法均可用来解决"三七二十一"问题，在面试时可以灵活运用。

上一篇: idea打包java可执行jar包

下一篇: C++中的while(cin)用法

评论区

()

相似文章