go基础算法思想

1、 简单猜价格游戏

在此之前先介绍一下go语言获得随机数的方法
方法1：方法1不设置时间种子会导致每次循环的10个数字都是相同的

func test(){
  for i:=0; i<10; i   {
        fmt.Println(rand.Intn(10))
    }
}

方法2：设置了时间种子，每次随机的数都不一样了

func test2(){
  r := rand.New(rand.NewSource(time.Now().UnixNano()))
   for i:=0; i<10; i   {
       fmt.Println(r.Intn(100))
   }
}

然后开始游戏：将价格和随机数进行比较，大答错继续，答对结束游戏

package main

import "fmt"
import "math/rand"
import "time"

func main()  {
  game1()
  //test2()
  //test()
}

func getRandomNum() int {
  r := rand.New(rand.NewSource(time.Now().UnixNano()))
  return r.Intn(10)
}

func game1(){
  for {
    var randoms int = getRandomNum();
    fmt.Println("请输入您猜的价格")
    var apple_str int
    fmt.Scan(&apple_str)
    if(apple_str == randoms){
      fmt.Println("恭喜您猜对了")
      return;
    }else {
      fmt.Println("您猜错了，答案是: ",randoms)
      continue;
    }
  }
}

func test(){
  for i:=0; i<10; i   {
        fmt.Println(rand.Intn(100))
    }
}

func test2(){
  r := rand.New(rand.NewSource(time.Now().UnixNano()))
   for i:=0; i<10; i   {
       fmt.Println(r.Intn(100))
   }
}

2、递推算法

看了一片有关递推算法的文章觉得还不错
算法洗脑系列-递推算法
只不过里面用的是java，下面我用go语言来编写一下这两个案例

一、繁殖兔子的问题
如果1对兔子每月能生1对小兔子，而每对小兔在它出生后的第3个月就可以生1对小兔子，如果从1对初生的小兔子开始，1年后能繁殖多少兔子？

package main

import(
    "fmt"
)

func main()  {
  month :=12;
  fab := make([]int, 12)
  fab[0] = 1;
  fab[1] = 1;
  for i := 2; i< month; i   {
      fab[i] = fab[i-1]   fab[i-2]
  }
  for i:=0; i< month; i  {
    fmt.Printf("第%d的兔子为：%d 只\n", i, fab[i])
  }
}
/**
prinf 和 println不一样
Println 与Printf 都是fmt 包中的公共方法

Println :可以打印出字符串，和变量；

Printf : 只可以打印出格式化的字符串,可以输出字符串类型的变量，不可以输出整形变量和整形
**/

二、存钱问题

package main

import(
    "fmt"
)

func main()  {
    //go语言没有double类型
    month := make([]float32, 49)
    month[48] = 3000
    var rate float32=0.0171
    for i := 47; i > 0; i--{
      month[i] = (month[i 1]   month[48]) / (1   rate / 12)
    }
    for i := 48; i > 0; i--{
      fmt.Printf("第%d 个月末本利合计：%f元\n",i,month[i])
    }

}

附加各种占位符

3、枚举算法

枚举算法的思想是：将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。枚举算法一般使用循环实现。
实际上就是把所有的情况一一举出来，然后得出结果
算法思想-枚举算法
我要改编一下买鸡的算法，用go语言实现

百钱买百鸡问题：公鸡每只5元，母鸡每只3元，小鸡3只1元，用100块钱买100只鸡，问公鸡，母鸡，小鸡各多少只？

package main
import(
  "fmt"
)
func main()  {
  var x,y,z int
  for x=0; x<=20; x  {
    for y=0; y<=33; y  {
      z=100-x-y;
      if(z%3 == 0 && x*5 y*3 z/3 == 100){
          fmt.Printf("公鸡：%d 只 ，母鸡： %d只 ，小鸡： %d只\n",x,y,z)
      }
    }
  }
}

4、递归算法

递归是以自相似的方式重复项的过程。这同样适用于其它编程语言，在编程语言中允许在函数内调用同一个函数称为递归调用，如下所示。
这个很简单，就是自己调用自己喽

func recursion() {
   recursion() /* function calls itself */
}

func main() {
   recursion()
}

5、分治算法思想

一、基本概念

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。例如，对于n个元素的排序问题，当n=1时，不需任何计算。n=2时，只要作一次比较即可排好序。n=3时只要作3次比较即可，…。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。

二、基本思想及策略

分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

如果原问题可分割成k个子问题，1

三、分治法分治法所能解决的问题一般具有以下几个特征：

1) 该问题的规模缩小到一定的程度就可以容易地解决

2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3) 利用该问题分解出的子问题的解可以合并为该问题的解；

4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。适用的情况

四、分治法的基本步骤

分治法在每一层递归上都有三个步骤：
step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

step3 合并：将各个子问题的解合并为原问题的解。

它的一般的算法设计模式如下：

Divide-and-Conquer(P)

1. if |P|≤n0

2. then return(ADHOC(P))

3. 将P分解为较小的子问题 P1 ,P2 ,…,Pk

4. for i←1 to k

5. do yi ← Divide-and-Conquer(Pi) △ 递归解决Pi

6. T ← MERGE(y1,y2,…,yk) △ 合并子问题

7. return(T)

其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时直接用算法ADHOC(P)求解。算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解。

五、可使用分治法求解的一些经典问题

（1）二分搜索
（2）大整数乘法
（3）Strassen矩阵乘法
（4）棋盘覆盖
（5）合并排序
（6）快速排序
（7）线性时间选择
（8）最接近点对问题
（9）循环赛日程表
（10）汉诺塔

七、依据分治法设计程序时的思维过程

实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。
1、一定是先找到最小问题规模时的求解方法
2、然后考虑随着问题规模增大时的求解方法
3、找到求解的递归函数式后（各种规模或因子），设计递归程序即可。

分治算法原文：红脸书生

6、贪婪算法

来自红脸书生的贪婪算法概念总结

输入要找的零钱数，怎样才能用最少的纸币找开零钱，思路肯定是先给最大的面值，再依次往下筛选

package main
import(
  "fmt"
)

func main()  {
  var input float32
  var n float32
  fmt.Println("请输入要找的零钱")
  fmt.Scanln(&input)
  for input*10 !=0{
      n = getMoney(input*10)
      input = input - n
      fmt.Println(n)
      continue
  }

}

func getMoney(input float32) float32 {
  moneyCount := []float32{1000，500, 200, 100, 50, 20, 10, 5, 2, 1}
  var rtn float32
  for i:=0;i<len(moneyCount);i  {
    for moneyCount[i] <= input {
      input -= moneyCount[i]
      rtn = moneyCount[i]
      continue
    }
  }
  return rtn/10
}

当我输入261的时候

这就是最贪婪的一种获取方式

7、试探算法

试探算法，顾名思义，就是摸着石头过河，针对所给的问题来给出易于搜索的程序，在得到正确解之前，不断得进行，一旦走不通，重新返回继续试探，直到得出结论
这种算法思想感觉还蛮大众的，一般都是if和for结合循环不断通过限定的条件来搜寻结果，并无特殊的地方，就不在举例子了

到此这篇关于“go基础算法思想”的文章就介绍到这了,更多文章或继续浏览下面的相关文章，希望大家以后多多支持JQ教程网！

您可能感兴趣的文章：
想系统学习GO语言(Golang
Go语言发展历史、核心、特性及学习路线
[go基础] go基础之字符串中查找汉字数量
Go语言基础、实战
go基础算法思想
Go 语言十年而立，Go2 蓄势待发
应用编程基础课第三讲：Go编程基础
从零开始学习GO语言-搭建Go语言开发环境-快速开发入门第一个小程序
Go 语言到底适合干什么？
Go 开发关键技术指南 | 为什么你要选择 Go？(内含超全知识大图）