Go-根据单向循环链表解决约瑟夫问题

分手后的思念是犯贱 2022-09-09 02:21 119阅读 0赞

单向循环链表实现：[https://blog.csdn.net/luyaran/article/details/119970185][https_blog.csdn.net_luyaran_article_details_119970185]

约瑟夫问题代码片段如下：

/*
     *                    .::::.
     *                  .::::::::.
     *                 :::::::::::
     *             ..:::::::::::'
     *           '::::::::::::'
     *             .::::::::::
     *        '::::::::::::::..
     *             ..::::::::::::.		Utils:环形单链表的约瑟夫问题
     *           ``::::::::::::::::		Author:崔金朋
     *            ::::``:::::::::'        .:::.
     *           ::::'   ':::::'       .::::::::.
     *         .::::'      ::::     .:::::::'::::.
     *        .:::'       :::::  .:::::::::' ':::::.
     *       .::'        :::::.:::::::::'      ':::::.
     *      .::'         ::::::::::::::'         ``::::.
     *  ...:::           ::::::::::::'              ``::.
     * ```` ':.          ':::::::::'                  ::::..
     *  		           '.:::::'          			':'````..
     */
    
    package main
    
    func JosephGame(currNode *CircleLinkedList, m int) *CircleLinkedList {
    	if currNode == nil || currNode.Next == currNode || m < 1 {
    		return currNode
    	}
    
    	lastNode := currNode
    	for lastNode.Next != currNode {
    		lastNode = lastNode.Next
    	}
    
    	var key int
    	for lastNode != currNode {
    		key++
    		if key == m {
    			lastNode.Next = currNode.Next
    			key = 0
    		} else {
    			lastNode = lastNode.Next
    		}
    
    		currNode = lastNode.Next
    	}
    
    	return currNode
    }
    
    func Getlive(i, m int) int {
    	if i == 1 {
    		return 1
    	}
    
    	return (Getlive(i-1, m)+m-1)%i + 1
    }
    
    func JosephGameBetter(currNode *CircleLinkedList, m int) *CircleLinkedList {
    	if currNode == nil || currNode.Next == currNode || m < 1 {
    		return currNode
    	}
    
    	temp := Getlive(currNode.GetCircleLinkedListLength(), m)
    	currNode = currNode.SearchCircleLinkedListNode(temp)
    	currNode.Next = currNode
    	return currNode
    }

[https_blog.csdn.net_luyaran_article_details_119970185]: https://blog.csdn.net/luyaran/article/details/119970185