Golang Algorithm Problem: Analysis of Integer Partition Implementation Method

This article illustrates the implementation method of integer partitioning in Golang algorithm problems. Shared for everyone's reference, as follows:

一个整数总可以拆分为2An integer can always be split into

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

of the sum of powers, for example:6There are

For example:4can be split into:4 = 4,4 = 1 + 1 + 1 + 1,4 = 2 + 2,4=1+1+2.

Use f(n) to represent the number of different ways to split n, for example, f(7)=6.

Write a program to read n (not exceeding1000000), output f(n)

Input: An integer N(1≤N≤1000000).

Output: f(n)

If the input data is out of range, output-1.

Sample Input:

7

Sample Output:

6

Code Implementation:

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,1types of splitting
　　　 if n == 1 {
　　　　　　　 return 1
　　　 }
　　　 //2=2,2=1+1,2types of splitting
　　　 if n == 2 {
　　　　　　　 return 2
　　　 }
　　　 //n>=3
　　　 //Save the calculated values
　　　 data := make([]int, n+1)
　　　 data[0] = 0 //This value has no meaning and serves as a placeholder
　　　 data[1] = 1
　　　 data[2] = 2
　　　 for i := 3; i <= n; i++ {
　　　　　　　 if i%2 == 0 {
　　　　　　　　　　　 //Even
　　　　　　　　　　　 data[i] = data[i-2] + data[i/2]
　　　　　　　 } else {
　　　　　　　　　　　 //Odd
　　　　　　　　　　　 data[i] = data[i-1]
　　　　　　　 }
　　　 }
　　　 return data[n]
}

I hope the content of this article will be helpful to everyone in Go language program design.

Statement: The content of this article is from the Internet, and the copyright belongs to the original author. The content is contributed and uploaded by Internet users spontaneously. This website does not own the copyright, has not been manually edited, and does not assume any relevant legal liability. If you find any content suspected of copyright infringement, please send an email to: notice#w3Please report via email to codebox.com (replace # with @ when sending email) and provide relevant evidence. Once verified, this site will immediately delete the infringing content.