An analysis of integer split algorithm for Golang algorithm

  • 2020-06-07 04:37:32
  • OfStack

An example of Golang algorithm is presented in this paper. To share for your reference, specific as follows:

An integer can always be divided into the sum of powers of 2, for example:

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

There are six different ways to break it up.

Another example: 4 can be divided into: 4= 4, 4=1+1+ 1+1, 4= 2 +2, 4=1+1+2.

f(n) is used to represent the number of different types of n split, for example, f(7)=6.

Write the program, read n(not more than 1000000), output f(n)

Input :1 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,1 Type of resolution
    if n == 1 {
        return 1
    }
    //2=2,2=1+1 . 2 Type of resolution
    if n == 2 {
        return 2
    }
    //n>=3
    // Save the calculated values
    data := make([]int, n+1)
    data[0] = 0 // This value has no pure placeholder effect
    data[1] = 1
    data[2] = 2
    for i := 3; i <= n; i++ {
        if i%2 == 0 {
            // An even number
            data[i] = data[i-2] + data[i/2]
        } else {
            // An odd number
            data[i] = data[i-1]
        }
    }
    return data[n]
}

I hope this article has been helpful in Go programming.


Related articles: