约瑟夫环问题及python与c++实现效率对比
约瑟夫环是一个数学的应用问题：已知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, tag ):
assert total >= 0, 'total lq 0'
assert tag >= 0, 'tag lt 0'
node = create_cycle( total )
prev = None
start = 1
index = start
while node and node.next:
if index == tag:
print( node.value )
if tag == start:
prev = node.next
node.next = None
node = prev
else:
prev.next = node.next
node.next = None
node = prev.next
index = start
else:
prev = node
node = node.next
index += 1
run( 5, 999 )
c++实现如下：
// josephCycle.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <stdlib.h>
typedef struct _LinkNode
{
int value;
struct _LinkNode* next;
}LinkNode, *LinkNodePtr;
LinkNodePtr createCycle( int total )
{
int index = 1;
LinkNodePtr head = NULL, curr = NULL, prev = NULL;
head = (LinkNodePtr)malloc(sizeof(LinkNode));
head->value = index;
prev = head;
while(--total > 0)
{
curr = (LinkNodePtr)malloc(sizeof(LinkNode));
curr->value = ++index;
prev->next = curr;
prev = curr;
}
curr->next = head;
return head;
}
void run( int total, int tag )
{
LinkNodePtr node = createCycle( total );
LinkNodePtr prev = NULL;
int start = 1;
int index = start;
while(node && node->next)
{
if(index == tag)
{
printf("\n%d", node->value);
if(tag == start)
{
prev = node->next;
node->next = NULL;
node = prev;
}
else
{
prev->next = node->next;
node->next = NULL;
node = prev->next;
}
index = start;
}
else
{
prev = node;
node = node->next;
index++;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
run( 5, 999999 );
return 0;
}
页:
[1]