• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

C语言如何使用双向循环链表解决Josephus(约瑟夫)问题

OC/C/C++ 水墨上仙 2074次浏览

题目描述: n个人围坐一圈,标号1-n,从s开始报数,第m个报的人出列,一直循环下去直到所有人出列。设计一算法,输入n,m,s,输出出列顺序。这个问题有好多种算法,我是用双向循环链表实现的转自:http://blog.csdn.net/shiyanhui66/article/details/5991752

/*
 *use two-directioned looped linkedList
 */
#include <cstdio>
using namespace std ;
class node
{
public:
    node* last ;
    node* next ;
    int element ;
    node( )
    {
        last = next = NULL ;
        element = 0 ;
    }
    node( int element )
    {
         last = next = NULL ;
         this->element = element ;
    }
} ;
typedef node* node_pointer ;
//pick the list recommended out
void func( int n , int m , int s )
{
    //there is only one element in the list
    if( n == 1 )
    {
        printf( "1/n" ) ;
    }
    //there is only two element in the list
    else if( n == 2 )
    {
        if( m & 1 )
        {
            printf( "%d %d/n" , s , 3 - s ) ;
        }
        else
        {
            printf( "%d %d/n" , 3 - s , s ) ;
        }
    }
    else
    {
        //size:the size of the list
        //cnt:the counter to find the start pointer
        int size = n , cnt = 1 ;
        node_pointer head = new node( 1 ) ;//the first node pointer built
        node_pointer current = head , start_pointer ; //start_pointer:the start pointer
        if( s == 1 )
        {
            start_pointer = current ;
        }
        for( int i = 2 ; i <= size ; i ++ )
        {
            node_pointer tmp = new node( i ) ;
            current->next = tmp ;
            tmp->last = current ;
            current = tmp ;
            if( ++ cnt == s )
            {
                start_pointer = current ;
            }
        }
        current->next = head ;
        head->last = current ;
        
        current = start_pointer ;
        cnt = 1 ;
        //the loop to pick the list out
        while( true )
        {
            if( cnt == m )
            {
                if( size  >= 3 )
                {
                    printf( "%d " , current->element ) ;
                    node_pointer tmp1 = current->last ;
                    node_pointer tmp2 = current->next ;
                    tmp1->next = tmp2 ;
                    tmp2->last = tmp1 ;
                    
                    delete current ;
                    current = tmp2 ;
                    cnt = 1 ;
                    
                    size -- ;
                }
                else if( size == 2 )
                {
                    printf( "%d " , current->element ) ;
                    node_pointer tmp = current->next ;
                    tmp->last = tmp->next = tmp ;
                    
                    delete current ;
                    current = tmp ;
                    cnt = 1 ;
                    
                    size -- ;
                }
                else if( size == 1 )
                {
                    printf( "%d/n" , current->element ) ;
                    delete current ;
                    break ; //over
                }
            }
            else
            {
                current = current->next ;
                cnt ++ ;
            }
        }
    }
}
int main()
{
    int n , m , s ;//n:the total number , m:every m is picked , s:the start
    while( scanf( "%d%d%d" , &n , &m , &s ) == 3 )
    {
        func( n , m , s ) ;
    }
    return 0 ;
}

给出几组样例:10&nbsp5&nbsp37&nbsp2&nbsp8&nbsp4&nbsp1&nbsp10&nbsp3&nbsp6&nbsp9&nbsp5&nbsp2&nbsp23&nbsp22&nbsp1&nbsp1&nbsp1&nbsp11注:此程序默认输入合理。即n&nbsp>&nbsp0&nbsp,&nbspm&nbsp>&nbsp0&nbsp,&nbsp&nbsp1&nbsp&nbsp<=&nbsp&nbsps&nbsp&nbsp<=&nbsp&nbspn。


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明C语言如何使用双向循环链表解决Josephus(约瑟夫)问题
喜欢 (0)
加载中……