Go笔记-分治策略:迭代和递归

分治策略是算法的一大类,典型的分治是 迭代和递归

迭代:循环执行相同的步骤

反复执行一个步骤,就像for while一样

  • 迭代的效率非常高,是递归的成千上万倍
  • 处理逻辑嵌套比较多,代码不美观
package main
//迭代实例应用
//流程处理是单向进行。

import "fmt"

type data struct {		//数据结构
	id int
	//序号
	name string
	//数据名
	parent int
	//父级序号
}

func main() {
	table := []data{
		{1, "电子产品", 0},
		{2, "垃圾", 0},
		{3, "手表", 1},
		{4, "食物", 0},
		{5, "电脑", 1},
		{6, "废纸", 2},
		{7, "面包", 4},
		{8, "鼠标", 1},
	}
	for i, v := range Sort(table){
		fmt.Println(i, v)
	}
}

//树状排序
func Sort(temp []data)(result []data){
	for i, v := range temp{
		if v.parent == 0 {
			result = append(result, temp[i])
			for i1, v1 := range temp{
				if v1.parent == v.id{
					result = append(result, temp[i1])
				}
			}
		}
	}
	return
}

输出:

0 {1 电子产品 0}
1 {3 手表 1}
2 {5 电脑 1}
3 {8 鼠标 1}
4 {2 垃圾 0}
5 {6 废纸 2}
6 {4 食物 0}
7 {7 面包 4}

Process finished with exit code 0

递归:函数调用自己执行

一般用作分而治之,把大问题化解成多个小问题,逐个解决。分 治 合
也可以用作循环,但是并不常用

  • 代码量较少,但是逻辑比较绕
  • 不是高效的解决方案相比于循环来讲
package main
//递归:函数调用自己执行
//一般用作分而治之,把大问题化解成多个小问题 解决体量小的问题,逐个解决。分 治 合
//也可以用作循环,但是并不常用
//流程处理是由外执行至内,再由内执行至外。
import "fmt"

func main() {
	fmt.Println(factorial(10))

	loop(1)

	fmt.Println(
		FibonacciSequence(5, 1, 1),
	)
}

func FibonacciSequence(i, i1, i2 int)int{
	if i == 3{
		return i1 + i2
	}
	if i == 2{
		return i1
	}
	return FibonacciSequence(i - 1, i1, i2) + FibonacciSequence(i - 2, i1, i2)
}
//斐波那契数列 递归使用场景

func factorial(n int)int{
	if n == 1 {
		return 1
	}
	return n * factorial(n - 1)
	//如果传入的数字不是1,就把他减1然后递归,直到为1
}
//阶乘递归使用场景

func loop(i int)  {
	fmt.Println(i)
	if i == 10 {
		return
	} else {
		i++
		loop(i)
	}
}
//迭代循环输出i-20

输出:

3628800
1
2
3
4
5
6
7
8
9
10
5

Process finished with exit code 0
# Go 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×