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 언어 프로그래밍에 도움이 되길 바랍니다.

성명: 이 문서의 내용은 인터넷에서 가져왔으며, 저작권자는 모두입니다. 내용은 인터넷 사용자가 자발적으로 기여하고 자체로 업로드한 것이며, 이 사이트는 소유권을 가지지 않으며, 인공 편집 처리를 하지 않았으며, 관련 법적 책임도 부담하지 않습니다. 저작권 침해가 의심되는 내용이 있으면, notice#w로 이메일을 보내 주세요.3codebox.com（보고할 때는 #을 @으로 변경하십시오. 관련 증거를 제공하고, 사실이 확인되면, 이 사이트는 즉시 저작권 침해 내용을 삭제합니다。）