210927 约瑟夫环

数组实现

//约瑟夫环问题，数组实现，从1开始编号
#include <iostream>
using namespace std;
int a[110] = {0};
int main() {
    int n,m;
    int cnt = 0, i=0,k=0; //cnt表示目前出局的人数
    cin >> n >> m;
    while(cnt != n) //当前出局的人数小于n
    {
        i++;
        if(i>n) i = 1;
        if(a[i] == 0)
        {
            k++;
            if(k == m)
            {
                a[i] = 1;
                k = 0; //方便下一个人重新从1开始报数
                cnt ++ ;
                cout << i << " ";
            }
        }
    }
    return 0;
}

循环链表实现

//约瑟夫环链表解法
#include <iostream>
using namespace std;
typedef struct node{
    int data;
    struct node *next;
}Node;
void ysflb(int n, int k) // 总共有n个人，报到数字为k的人出局。
{
    //创建循环链表
    Node *head = NULL, *p = NULL, *r = NULL;
    head = (Node *)malloc(sizeof(Node));    //申请空间
    if(head == NULL)    //如果空间申请失败
    {
        cout << "Memory Failed!";
        return;
    }
    head -> data = 0;
    head -> next = NULL;
    p = head;
    //循环链表创建，使用尾插法
    for(int i=1;i<n;i++)
    {
        r = (Node *)malloc(sizeof(Node));
        r -> data = i;
        r -> next = NULL;
        p -> next = r;
        p = r;
    }
    p -> next = head;
    p = head;
    //约瑟夫环模拟
    while(p -> next != p)
    {
        for(int i=1;i<k;i++)
        {
            r = p;  //保存前一个节点
            p = p -> next;  //p为出局的节点
        }
        cout << p->data << ' ';
        r -> next = p -> next;  //删除p节点
        p = p->next;
    }
    cout << endl << p->data;
}
int main() {
    //int n,k;
    //cin >> n >> k;
    ysflb(10,3);
    return 0;
}

递归求解

#include <iostream>
using namespace std;
int ysf(int n,int k, int i)
//设f(n,k,i)为n个人的环，报数为k，第i个人出环的编号，
//则f(10,3,10)是我们想要的结果
{
    if(i == 1)
        return (n+k-1)%n;
    else
        return (ysf(n-1,k,i-1)+k)%n;
}
int main() {
    int n,m;
    cin >> n >> m;
    for(int i = 1; i<=n;i++)
        printf("第%d次出环：%d\n",i,ysf(n,m,i));
    return 0;
}