题目描述: 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 5 37 2 8 4 1 10 3 6 9 5 2 23 22 1 1 1 11注:此程序默认输入合理。即n > 0 , m > 0 ,  1  <=  s  <=  n。