使用链表解决约瑟夫问题

1.建立一个链表

2.定义一个指针指向最后一个节点

3.对链表进行遍历

4. 找到复合条件的节点删除掉

5. 直到剩下最后一个节点

package main
import "fmt"
type Boy struct {
    No int
    Next *Boy
}
func AddBoy(num int) *Boy {
    first := &Boy{}
    if num < 1 {
        fmt.Printf("num 太小")
        return first
    }
    current := &Boy{}
    for i := 1; i <= num; i++ {
        boy := &Boy{
            No: i,
        }
        if i == 1 {
            first = boy
            current = boy
            current.Next = first
        } else {
            current.Next = boy
            current = boy
            current.Next = first
        }
    }
    return first
}
func Show(first *Boy)  {
    if first.Next == nil {
        fmt.Printf("链表为空")
        return
    }
    current := first
    for {
        fmt.Printf("body no = %d \n", current.No)
        if current.Next == first {
            fmt.Printf("完成遍历")
            break
        }
        current = current.Next
    }
}
func Play(first *Boy, startNo int, count int)  {
    if first.Next == nil {
        fmt.Printf("空链表")
        return
    }
    if startNo < 1 || startNo > 10 {
        fmt.Printf("编号范围错误")
        return
    }
    // list  最后一个节点.
    tail := first
    for  {
        if tail.Next == first {
            break
        }
        tail = tail.Next
    }
    // tail 指向到 起始节点
    for i := 1; i <= startNo -1; i++ {
        first = first.Next
        tail = tail.Next
    }
    // 开始进行 出列
    for {
        for i := 1; i <= count; i++ {
            first = first.Next
            tail = tail.Next
        }
        fmt.Printf("boy no = %v 出列 \n", first.No)
        // 删除节点
        first = first.Next
        tail.Next = first
        // 最后一个小孩退出循环
        if tail == first {
            break
        }
    }
    fmt.Printf("最后一个 boy no = %v \n", tail.No)
}
func main() {
    first := AddBoy(10)
    Show(first)
    Play(first, 1, 3)
}

递归解决约瑟夫问题

func f(n int, m int) (int) {
    if n == 1 {
        return n
    }
    return (f(n - 1, m) + m - 1) % n + 1
}