Golang算法问题之整数拆分实现方法分析
发布时间:2020-12-16 19:29:48 所属栏目:大数据 来源:网络整理
导读:本篇章节讲解Golang算法问题之整数拆分实现方法。供大家参考研究具体如下: 一个整数总可以拆分为2的幂的和,例如: 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有6种不同的拆分方式。 再比如:4可以拆分成:4 =
本篇章节讲解Golang算法问题之整数拆分实现方法。分享给大家供大家参考,具体如下: 一个整数总可以拆分为2的幂的和,例如: 7=1+2+4 总共有6种不同的拆分方式。 再比如:4可以拆分成:4 = 4,4 = 1 + 1 + 1 + 1,4 = 2 + 2,4=1+1+2。 用f(n)表示n的不同拆分的种数,例如f(7)=6. 要求编写程序,读入n(不超过1000000),输出f(n) 输入:一个整数N(1<=N<=1000000)。 输出:f(n) 输入数据如果超出范围,输出-1。 样例输入: 7 样例输出: 6 代码实现: 复制代码 代码如下: package huawei
import ( "fmt" ) func Test08Base() { input := 1000000 output := numberSplit(input) fmt.Println(output) } func numberSplit(n int) int { if n < 1 || n > 1000000 { return -1 } //1=1,1种拆分方式 if n == 1 { return 1 } //2=2,2=1+1,2种拆分方式 if n == 2 { return 2 } //n>=3 //保存已经计算出来的数值 data := make([]int,n+1) data[0] = 0 //该值无意义纯占位作用 data[1] = 1 data[2] = 2 for i := 3; i <= n; i++ { if i%2 == 0 { //偶数 data[i] = data[i-2] + data[i/2] } else { //奇数 data[i] = data[i-1] } } return data[n] } 希望本文所述对大家Go语言程序设计有所帮助。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |