首页 > 代码库 > 约瑟夫环问题及python与c++实现效率对比
约瑟夫环问题及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 else: prev = node node = node.next index += 1run( 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 =http://www.mamicode.com/ index; prev = head; while(--total > 0) { curr = (LinkNodePtr)malloc(sizeof(LinkNode)); curr->value = http://www.mamicode.com/++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;}
约瑟夫环问题及python与c++实现效率对比
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。