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.