阅读 40

约瑟夫环问题的解法

两种解法:

一、使用双向链表

二、使用数组

两种实现的算法如下:

package go_package

import (
    "fmt"
    "testing"
)

type Node struct {
    v int
    pre *Node
    next *Node
}


/**
 * 使用node链表进行计算
 */
func TestMonkey(t *testing.T) {
    first := &Node{1, nil, nil}
    pre := &Node{2, nil, nil}
    first.next = pre
    pre.pre = first
    for i := 3; i<10; i++ {
        element := &Node{i, nil, nil}
        pre.next = element
        element.pre = pre
        pre = element
    }
    pre.next = first
    first.pre = pre

    result := handleNode(first, 5)
    fmt.Println("结果是: ", result)

    arr := []int{1,2,3,4,5,6,7,8,9}
    another := handleArray(arr, 5)
    fmt.Println("另一个结果是: ", another)



}


func handleNode(node *Node, m int) int{
    num := 0
    for node != node.next {
        num++
        if num == m {
            // 将当前node丢掉
            fmt.Println("current node is : ", node.v)
            pre := node.pre
            next := node.next
            pre.next = next
            next.pre = pre
            num = 0
            node = next
            continue
        }
        node = node.next
    }
    return node.v
}



func handleArray(arr []int, m int) int{
    num := 0
    mark := 0
    i := 0
    for mark < len(arr) - 1 {
        if i >= len(arr) {
            i = 0
        }
        if arr[i] == -1 {
            i++
            continue
        }
        num++
        if num == m {
            arr[i] = -1
            i++
            num = 0
            mark++
            continue
        }
        i++
    }
    result := 0
    for i,v := range arr {
        if v != -1 {
            result = i + 1
            break
        }
    }
    return result
}

 

原文:https://www.cnblogs.com/deer-hang/p/15344150.html

文章分类
百科问答
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐