当你的才华
还撑不起你的野心时,那你就应该静下心来学习

约瑟夫问题

约瑟夫问题


题目描述

n个人(n<=100)围成一圈,从第一个人开始报数,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出圈,……依次类推,直到所有的人都出圈,请输出依次出圈人的编号.

测试样例_输入

10  3

测试样例_输出

3   6   9   2   7   1   8   5   10  4

数据范围 m , n <= 100 ;


  • 代码样例一

    通过数组标记模拟实现

    //模拟做法 (数据规模较小)
    
    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int m , n , s = 0 ;
        bool v[100] = { 0 } ;       //用来标记, 默认都为假 
        cin >> n >> m ;
        for( int i = 0 ; i < n ; i ++ ) //n个数所以要循环n次, 依次输出每个数 
        {
            for( int j = 0 ; j < m ; j ++ )
            {
                if( ++s > n )       //只要s大于最大长度就从1开始 
                    s = 1 ;
                if( v[s] )          //用来判断s是否已经输出 
                    j -- ;          //j减一用来跳过s 
            }
            cout << s << " " ;
            v[s] = true ;           //标记s已将输出 
        }
        return 0;
     } 
  • 代码样例二

    通过链表实现

    #include<bits/stdc++.h>
    using namespace std;
    
    struct Node
    {
        int ID ;
        Node *next , *front ;
     } n[100];
    
    void cut( Node *num )       //删除当前节点 
    {
        num = num->front ;
        num->next = num->next->next ;
        num = num->next ;
        num->front = num->front->front ;
    }
    
    int main()
    {
        int tot , outNum , nowNum = 1 ;
        Node *now = &n[0] ; 
        cin >> tot >> outNum ;
        
        for( int i = 1 ; i < tot - 1 ; i ++ )
        {
            n[i].front = &n[i-1] ;
            n[i].next = &n[i+1] ;
            n[i].ID = i + 1 ;
        }
            
        n[0].front = &n[tot-1] ;
        n[0].next = &n[1] ;
            
        n[tot-1].front = &n[tot-2] ;
        n[tot-1].next = &n[0] ;
             
        n[0].ID = 1 ;
        n[tot-1].ID = tot ;
        
        while( tot > 0 )
        {
            if( nowNum == outNum )
            {
                cout << now->ID << " " ;
                cut(now) ; 
                nowNum = 1 ;
                tot -- ;
                now = now->next ;
            }
            else
            {
                nowNum ++ ;
                now = now->next ;
            }
        }
        return 0;
    } 
  • 高端解法(递归)

    参考这个博客吧😂 , https://blog.csdn.net/tingyun_say/article/details/52343897

赞(2) 打赏
未经允许不得转载:啾啾鸟 » 约瑟夫问题

欢迎来到Birdjiujiu

欢迎刷题

阿巴阿巴阿巴

微信扫一扫打赏