算法 in Golang:D & C(分而治之)

算法inGolang:D&C(分而治之)D&C算法(策略)Divide&Conquer属于递归算法的一种其实它更像是一种思路、策略递归递归Recursion基线条件BaseCase递归条件RecursiveCaseD&C的步骤找到

算法 in Golang:D & C(分而治之)

D & C 算法(策略)

  • Divide & Conquer
  • 属于递归算法的一种
  • 其实它更像是一种思路、策略

递归

  • 递归 Recursion
    • 基线条件 Base Case
    • 递归条件 Recursive Case

D & C 的步骤

  1. 找到一个简单的基线条件(Base Case)
  2. 把问题分开处理,直到它变为基线条件

例子

  • 需求:将数组 [1, 3, 5, 7, 9] 求和
  • 思路1:使用循环(例如 for 循环)
  • 思路2:D & C (分而治之)

例子:D & C 策略

  • 基线条件:空数组 [],其和为0
  • 递归:[1, 3, 5, 7, 9]
    • 1 + SUM([3, 5, 7, 9])
    • 3 + SUM([5, 7, 9])
      • 5 + SUM([7, 9])
      • 7 + SUM([9])
        • 9 + SUM([])

创建项目并用vscode 打开

~/Code/go via 🐹 v1.20.3 via 🅒 base
➜ mcd divide_conquer

Code/go/divide_conquer via 🐹 v1.20.3 via 🅒 base
➜ go mod init divide_conquer
go: creating new go.mod: module divide_conquer

Code/go/divide_conquer via 🐹 v1.20.3 via 🅒 base
➜ c

Code/go/divide_conquer via 🐹 v1.20.3 via 🅒 base
➜

main.go 代码

package main

import "fmt"

func main() {
 total := sum([]int{1, 3, 5, 7, 9})
 fmt.Println("total: ", total)
}

func sum(arr []int) int {
 if len(arr) == 0 {
  return 0
 }
 return arr[0] + sum(arr[1:])
}

运行

Code/go/divide_conquer via 🐹 v1.20.3 via 🅒 base 
➜ go run .                  
total:  25

Code/go/divide_conquer via 🐹 v1.20.3 via 🅒 base 
➜ 
点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
寻月隐君
寻月隐君
0x750E...B6f5
不要放弃,如果你喜欢这件事,就不要放弃。如果你不喜欢,那这也不好,因为一个人不应该做自己不喜欢的事。