数据布局代码集训day16（得当考研、自学、期末和专升本）

本题来自B站up：白话拆解数据布局

---

本日标题就一个：约瑟夫环题目。
        一个圈共有N个人（N为不确定的数字），第一个人的编号为0大概1（两个都可以，看你的步伐怎样编写），假设这边我将第一个人的编号设置为1号，那么第二个人的编号就为2号，第三个人的编号就为3号，第N个人的编号就为N号，如今提供一个数字M，第一个人开始从1报数，第二个人报的数就是2，依次类推，报到M这个数字的人出局，紧接着从出局的这个人的下一个人重新开始从1报数，和上面过程类似，报到M的人出局，直到N个人全部出局，叨教，这个出局的次序是什么？

        这张图内圈代表元素，外圈代表出局的次序。这里的元素有10个，报到三出局。出局就相称于从这个圈出去了，圈内元素减1。

---

        这题有三种方法，第一个方法是用次序表，用i记载出列下标，用count记载出列的个数，由于走完一圈后须要回到开头继续数，以是要i=i%L.length重置一下，删除的操纵就是元素前移，前面已经说过了。
    void fa1(SqList &L,int N,int M){    
        int count=0,i=0;  
        while(count!=N){
            for(int k=0;k<M-1;k++,i++);
            if(i>=L.length)      i=i%L.length;
            printf("%d ",L.data);
            for(int j = i; j < L.length - 1; j++) {
            L.data[j] = L.data[j + 1];
        }
            count++;
            L.length--;     
        }
    }
实践：打印依次出队的元素

        法二：用循环单链表，刚好类似于图上的布局，和上面一样，找M，然后删除，就是重置的时间注意一下就行了。
    void fa2(Linklist &L,int N,int M){
        if (L == NULL || L->next == L)
            return; // 空链表或链表只有一个节点时，无需删除
        Lnode *pre ,*p;        // 删除的两个指针
        pre=L;
        p=L->next;
        while(L!=L->next){
            for(int i=0;i<M-1;i++){
                pre=p;
                p=p->next;
                if(p==L){        // 重置
                p=p->next;
                pre=pre->next;
                }
            }
            printf("%d ",p->data);
           
            pre->next=p->next;
            free(p);
            p=pre->next;
            }
    }
实践：

 
        法三：递归的做法，当 i == 1 时，表现只剩下一个人。这时，这个人的位置通过公式 (M - 1 + N) % N 来盘算；函数通过调用自身，递归地淘汰人数（N-1）和索引（i-1），渐渐缩小题目的规模；递归调用的结果会通过加上步长 M 并取模 N 来调解，确保盘算的位置在当前圆圈中有用。
  int fa3(int N,int M,int i){
        if(i==1)    return (M-1+N)%N;
        else return (fa3(N-1,M,i-1)+M)%N;
    }
 实践：这里输出的是位序，换算出来和上面一样。

2. #include <iostream>
3. #include <cstdio>
4. #include <stack>
5. #include <ctime>
6. using namespace std;
8. typedef int ElemType;
10. struct SqList {
11.     ElemType data[100];
12.     int length;
13. };
15. typedef struct Lnode{
16.     int data;
17.     Lnode *next;
18. }Lnode,*Linklist;
20. Linklist list_insertbytail(Linklist &L) {
21.     Lnode *s;
22.     int x;
23.    
24.     // 初始化头节点（哨兵节点），不存储实际数据
25.     L = (Lnode*)malloc(sizeof(Lnode));
26.     L->next = L;  // 初始化为循环结构
27.     Lnode *r = L; // r始终指向链表的尾节点
28.    
29.     cin >> x;
30.     while (x != 9999) {
31.         s = (Lnode*)malloc(sizeof(Lnode));  // 为新节点分配空间
32.         s->data = x;                        // 将数据存入新节点
33.         s->next = L;                        // 新节点的next指向头节点，形成环
35.         r->next = s;                        // 将新节点链接到尾部
36.         r = s;                              // 更新尾节点指针为r
37.         
38.         cin >> x;                           // 继续输入下一个数据
39.     }
41.     return L;  // 返回循环链表
42. }
44. // 约瑟夫环问题,N个人报数，报到M的出列，从M的下一个开始报，报到M的再次出列，问剩下的那个是谁
45. class Solution{
46. public:
47.     void fa1(SqList &L,int N,int M){    // 找M，删M，从下一个开始
48.         int count=0,i=0;  // count统计出列个数，到N-1就行了
49.         while(count!=N){
50.             for(int k=0;k<M-1;k++,i++);
51.             if(i>=L.length)      i=i%L.length;
52.             printf("%d ",L.data[i]);
53.             for(int j = i; j < L.length - 1; j++) {
54.             L.data[j] = L.data[j + 1];
55.         }
56.             count++;
57.             L.length--;
58.             
59.         }
61.     }
63.     void fa2(Linklist &L,int N,int M){
64.         if (L == NULL || L->next == L)
65.             return; // 空链表或链表只有一个节点时，无需删除
66.         Lnode *pre ,*p;
67.         pre=L;
68.         p=L->next;
69.         while(L!=L->next){
70.             for(int i=0;i<M-1;i++){
71.                 pre=p;
72.                 p=p->next;
73.                 if(p==L){
74.                 p=p->next;
75.                 pre=pre->next;
76.                 }
77.             }
78.             printf("%d ",p->data);
79.             
80.             pre->next=p->next;
81.             free(p);
82.             p=pre->next;
83.             }
85.     }
87.     int fa3(int N,int M,int i){
88.         if(i==1)    return (M-1+N)%N;
89.         else return (fa3(N-1,M,i-1)+M)%N;
90.     }
92. };
94. int main(){
95.     // SqList L;
96.     // L.length =10;
97.     // // srand(static_cast<unsigned int>(time(nullptr)));
98.     // // // 随机赋值
99.     // for(int i =0;i<L.length;i++){
100.     //     L.data[i] = i+1;   
101.     // }
102.     // Linklist L;
103.     // list_insertbytail(L);
104.     // Lnode *p = L->next;
105.     int N,M;
106.     cin>>N>>M;
107.     printf("start:");
108.     Solution a;
109.     // a.fa1(L,10,3);
110.     for(int i=1;i<=N;i++)
111.         printf("%d ",a.fa3(N,M,i));
112.     return 0;
113. }

复制代码