Golang算法問題之整數拆分實現方法分析

2020-04-01 19:06:38

字體：大中小

來源：轉載

供稿：網友

本文實例講述了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。

樣例輸入:

樣例輸出:

代碼實現：

復制代碼代碼如下:

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