weixin_42105291
2019-12-10 10:55
采纳率: 100%
浏览 273

C语言约瑟夫循环,不使用链表,依靠指针和循环实现?

求问如何在这个代码的基础上进行修改(不删除主体),实现约瑟夫环呢?

要求淘汰的序号大于总人数时也能实现
谢谢了

#include <stdio.h>
#define MAX_M 100
#define MAX_N 100

int monkey_king(int, int);
int* inner_loop(int*, int, int);
int next(const int*, int, int);

int main() {
    int m, n;
    printf("请输入M和N(空格分隔):");
    scanf("%d%d", &m, &n);
    int king = monkey_king(m, n);
    printf("大王是:%d\n", king);
    return 0;
}

int monkey_king(int m, int n) {
    int monkeys[m];

    for(int i=0; i<m; i++)
        monkeys[i]=i;

    return inner_loop(monkeys, m, n)-monkeys;
}

int* inner_loop(int* idx, int m, int n) {
    int n_candidate = m;
    int current_idx = 1;
    while(n_candidate) {
        for(int i=1; i<=n; i++) {
            if(current_idx==n) //如果报数为N
                idx[current_idx-1] = 0; //出圈

            current_idx = next(idx, m, current_idx); //找出下一个猴子
        }
    }
    for(int i=0; i<n; i++) {
        if(idx[i])
            return idx+i;
    }
    return NULL;
}

int next(const int* idx, int m, int cur) {
    while(true) {
        if(cur<=m)
            cur++;
        else
            cur=1;

        if(idx[cur-1])
            return cur;
    }
}
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • bobhuang 2019-12-10 16:21
    已采纳
    #include <stdio.h>
    #define MAX_M 100
    #define MAX_N 100
    
    int monkey_king(int m, int n);
    int inner_loop(int *idx, int m, int n);
    
    int main() {
      int m, n;
      printf("请输入M和N(空格分隔):");
      scanf("%d %d", &m, &n);
      int king = monkey_king(m, n);
      printf("大王是:%d\n", king);
      return 0;
    }
    
    int monkey_king(int m, int n)
    {
      int monkeys[MAX_M];
      int i;
    
      for (i = 0; i < m; i++)
        monkeys[i] = 1; // 标记是否出圈, 0 - 出圈, 1 - 未出圈
    
      return inner_loop(monkeys, m, n);
    }
    
    int inner_loop(int *idx, int m, int n)
    {
      int n_candidate = m;
      int current_idx; // 报数序号
      int pos = 0;         // 报数的位置
    
      while (n_candidate) {
        // 找下一个未出圈的位置
        while (idx[pos] == 0) {
          pos = (pos + 1) % m;
        }
    
        current_idx = 1; // 从1开始报数
        while (current_idx < n) {
          // 找下一个未出圈的位置
          do {
            pos = (pos + 1) % m;
          } while (idx[pos] == 0);
          current_idx += 1;
        }
        // 当前位置出圈
        printf("%d ", pos + 1);
        idx[pos] = 0;
        n_candidate--;
      }
    
      return pos + 1;
    }
    
    
    点赞 2 打赏 评论
  • dabocaiqq 2019-12-10 15:08
    点赞 打赏 评论

相关推荐 更多相似问题