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]
}

希望本文所述对大家Go语言程序设计有所帮助。

赞 (0)

相关推荐

  • Golang最大递减数算法问题分析

    本文实例讲述了Golang最大递减数算法问题.分享给大家供大家参考,具体如下: 给出一个非负整数,找到这个非负整数中包含的最大递减数.一个数字的递减数是指相邻的数位从大到小排列的数字. 如: 95345323,递减数有:953,95,53,53,532,32, 那么最大的递减数为953. 如果输入的数字为负数,返回-1. 如果找不到递减数,也返回-1. 代码实现: 复制代码 代码如下: package huawei import (     "fmt"     "sort&q

  • Go语言实现AzDG可逆加密算法实例

    本文实例讲述了Go语言实现AzDG可逆加密算法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: package main import (  "fmt"  "crypto/md5"  "encoding/base64"  "time" ) var cipher = "密鑰" var h = md5.New() func cipherEncode(sourceText string) stri

  • Go语言通过Luhn算法验证信用卡卡号是否有效的方法

    本文实例讲述了Go语言通过Luhn算法验证信用卡卡号是否有效的方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: package main import (     "fmt"     "strings" ) const input = `49927398716 49927398717 1234567812345678 1234567812345670` var t = [...]int{0, 2, 4, 6, 8, 1, 3, 5, 7, 9}

  • Golang排列组合算法问题之全排列实现方法

    本文实例讲述了Golang排列组合算法问题之全排列实现方法.分享给大家供大家参考,具体如下: [排列组合问题] 一共N辆火车(0<N<10),每辆火车以数字1-9编号,要求以字典序排序输出火车出站的序列号. 输入: 包括N个正整数(0<N<10),范围为1到9,数字之间用空格分割,字符串首位不包含空格. 输出: 输出以字典序排序的火车出站序列号,每个编号以空格隔开,每个输出序列换行. 样例输入: 1 2 3 样例输出: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3

  • Go语言实现汉诺塔算法

    hano.go package main import ( "bufio" "fmt" "os" "strconv" ) func main() { fmt.Print("输入要移动的盘子数:") reader := bufio.NewReader(os.Stdin) lool: data, _, _ := reader.ReadLine() n, err := strconv.Atoi(string(da

  • Go语言展现快速排序算法全过程的思路及代码示例

    快速排序算法 快速排序是一个递归的思想,首先选择一个数作为基数,把数组中小于它的数放在它的左边,把大于它的数放在它的右边,然后对左右两边的数递归进行排序. 算法的关键部分是实现数组的划分,即怎么把数组的元素划分成两部分,使得左边的数比基数小,右边的数比基数大.划分有许多不同的实现方法,这里主要使用单向扫描的方法,后面再稍微介绍双向扫描的方法. 选择最右边的数字作为基数.使用一个变量j记录当前左边数字(比基数小的数)的最右的下标值.然后使用变量i从左到右遍历数组,如果a[i]比基数小,说明a[i]

  • Golang算法之田忌赛马问题实现方法分析

    本文实例讲述了Golang算法之田忌赛马问题实现方法.分享给大家供大家参考,具体如下: [田忌赛马问题] 输入: 输入有多组测试数据. 每组测试数据包括3行: 第一行输入N(1≤N≤1000),表示马的数量. 第二行有N个整型数字,即渊子的N匹马的速度(数字大表示速度快). 第三行有N个整型数字,即对手的N匹马的速度. 当N为0时退出. 输出: 若通过聪明的你精心安排,如果能赢得比赛(赢的次数大于比赛总次数的一半),那么输出"YES". 否则输出"NO". 样例输入

  • Golang算法问题之数组按指定规则排序的方法分析

    本文实例讲述了Golang算法问题之数组按指定规则排序的方法.分享给大家供大家参考,具体如下: 给出一个二维数组,请将这个二维数组按第i列(i从1开始)排序,如果第i列相同,则对相同的行按第i+1列的元素排序, 如果第i+1列的元素也相同,则继续比较第i+2列,以此类推,直到最后一列.如果第i列到最后一列都相同,则按原序排列. 样例输入: 1,2,3 2,3,4 2,3,1 1,3,1 按第2列排序,输出: 1,2,3 2,3,1 1,3,1 2,3,4 代码实现: 复制代码 代码如下: pac

  • Golang正整数指定规则排序算法问题分析

    本文实例讲述了Golang正整数指定规则排序算法问题.分享给大家供大家参考,具体如下: 给定字符串内有很多正整数,要求对这些正整数进行排序,然后返回排序后指定位置的正整数 排序要求:按照每个正整数的后三位数字组成的整数进行从小到大排序 1)如果不足三位,则按照实际位数组成的整数进行比较 2)如果相等,则按照输入字符串中的原始顺序排序 说明(以下内容考生无须检查,调用者保证): 1) 字符串内正整数之间以单个空格分隔,字符串首尾没有空格 2) 正整数格式为十进制,大小:1~1000000,正整数的

  • go语言睡眠排序算法实例分析

    本文实例讲述了go语言睡眠排序算法.分享给大家供大家参考.具体分析如下: 睡眠排序算法是一个天才程序员发明的,想法很简单,就是针对数组里的不同的数开多个线程,每个线程根据数的大小睡眠,自然睡的时间越长的,数越大,哈哈,搞笑吧,这种算法看起来很荒唐,但实际上很天才,它可以充分利用多核cpu进行计算. 复制代码 代码如下: package main import (     "fmt"     "time" ) func main() {     tab := []in

  • GO语言利用K近邻算法实现小说鉴黄

    Usuage:   go run kNN.go --file="data.txt" 关键是向量点的选择和阈值的判定 样本数据来自国家新闻出版总署发布通知公布的<40部淫秽色情网络小说名单> package main import ( "bufio" "flag" "fmt" "io" "log" "math" "os" "pa

  • Go语言算法之寻找数组第二大元素的方法

    本文实例讲述了Go语言算法之寻找数组第二大元素的方法.分享给大家供大家参考.具体如下: 该算法的原理是,在遍历数组的时,始终记录当前最大的元素和第二大的元素.示例代码如下: 复制代码 代码如下: package demo01    import (      "fmt"  )    func NumberTestBase() {      fmt.Println("This is NumberTestBase")        nums := []int{12, 2

  • Go语言实现的树形结构数据比较算法实例

    本文实例讲述了Go语言实现的树形结构数据比较算法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: // Two binary trees may be of different shapes, // but have the same contents. For example: // //        4               6 //      2   6          4     7 //     1 3 5 7       2   5 //          

随机推荐