約瑟夫問題

type Boy struct {
	No   int
	Next *Boy //指向下一個小孩的指針
}

func addBoy(num int) *Boy {
	//num表示小孩的個數，*Boy返回第一個小孩的指針
	first := &Boy{}
	temp := &Boy{}
	if num < 1 {
		fmt.Println("num值錯誤")
		return first
	}

	for i := 1; i <= num; i++ {
		boy := &Boy{
			No: i,
		}
		if i == 1 {
			first = boy //不變
			temp = boy
			temp.Next = first
		} else {
			temp.Next = boy
			temp = boy
			temp.Next = first //構成環形
		}
	}
	return first
}

func show(first *Boy) {
	if first.Next == nil {
		fmt.Println("列表為空")
		return
	}
	temp := first
	for {
		fmt.Printf("編號%d~>", temp.No)
		if temp.Next == first {
			break
		}
		temp = temp.Next
	}
}

func play(first *Boy, k int, m int) {
	//從第k人開始報數m出列
	if first.Next == nil {
		fmt.Println("列表為空")
		return
	}
	tail := first
	for {
		if tail.Next == first {
			break
		}
		tail = tail.Next
	}
	//讓first移動到k
	for i := 0; i < k-1; i++ {
		first = first.Next
		tail = tail.Next
	}

	//開始數m
	for {
		for i := 1; i <= m-1; i++ {
			first = first.Next
			tail = tail.Next
		}
		fmt.Println(first.No, "出列")
		first = first.Next
		tail.Next = first

		//退出
		if tail == first {
			break
		}
	}
	fmt.Println(first.No, "為最後一個")
}
func main() {
	first := addBoy(41)
	show(first)
	fmt.Println()
	play(first, 1, 3)
}

上次修改於 2021-09-01