約瑟夫環問題及python與c++實現效率對比 - tudas－IT工程師數位筆記本

文章出處

約瑟夫環是一個數學的應用問題：已知n個人(以編號1，2，3...n分別表示)圍坐在一張圓桌周圍。從編號為k的人開始報數，數到m的那個人出列;他的下一個人又從1開始報數，數到m的那個人又出列;依此規律重復下去，直到圓桌周圍的人全部出列。

python實現：

# 單鏈表節點
class LinkNode:
    def __init__( self, value ):
        self.value = value
        self.next = None

# 創建循環單鏈表，值從1開始
def create_cycle( total ):
    head = LinkNode( 1 )
    prev = head
    index = 2
    while total - 1 > 0:
        curr = LinkNode( index )
        prev.next = curr
        prev = curr
        index += 1
        total -= 1
    curr.next = head
    return head

# 模擬約瑟夫環過程，從1開始計數
def run( total, m ):
    assert total >= 0, 'total should lq 0'
    assert m >= 0, 'm should lt 0'
    node = create_cycle( total )
    prev = None
    start = 1
    index = start
    while node and node.next:
        if index == m:
            print( 'pop:' + node.value )
            prev.next = node.next
            node.next = None
            node = prev.next
　　　　　　　index = start
        else:
            prev = node
            node = node.next
            index += 1

run( 5, 2 )

c++實現如下：

#include <stdio.h>
#include <stdlib.h>

#define COUNT_INIT 1   // 計數起點

typedef struct LINKNODE
{
    int value;
    struct LINKNODE* next;
}LinkNode, *LinkNodePtr;

// 創建結點
LinkNodePtr createNode( int value )
{
    LinkNodePtr node = ( LinkNodePtr )malloc( sizeof( LinkNode ) );
    node->value = value;
    return node;
}

// 創建循環單鏈表
LinkNodePtr createCycle( int total )
{
    int index = 1;
    LinkNodePtr head = NULL, curr = NULL, prev = NULL;
    head = createNode( index );
    prev = head;

    while( --total > 0 )
    {
        curr = createNode( ++index );
        prev->next = curr;
        prev = curr;
    }
    curr->next = head;  // 鏈表尾結點指向頭結點, 構成循環鏈表
    return head;
}

// 數到m, 節點出列, 下一個節點繼續從1開始數. m不可與COUNT_INIT同值
void run( int total, int m )
{
    LinkNodePtr node = createCycle( total );
    LinkNodePtr prev = NULL;
    int index = COUNT_INIT;

    while( node && node->next )
    {
        if( index == m )    
        {
            printf( "pop:%d\n", node->value );
            prev->next = node->next;
            node->next = NULL;
            free( node );
            node = prev->next;
            index = COUNT_INIT;
        }
        else
        {
            prev = node;
            node = node->next;
            index++;
        }
    }
}

文章列表