Golang算法问题之整数拆分如何实现
这篇文章主要介绍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 = 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] }
以上是“Golang算法问题之整数拆分如何实现”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注创新互联行业资讯频道!
分享标题:Golang算法问题之整数拆分如何实现
当前网址:http://myzitong.com/article/igdihi.html