Analisi del metodo di spaccamento degli interi in Golang

Questo esempio descrive la soluzione di un problema di algoritmo Go in linguaggio di programmazione. Condivido con tutti per riferimento, come segue:

Un numero intero può sempre essere suddiviso in somme di potenze di 2, ad esempio:

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

Ci sono in totale 6 modi diversi di suddividere.

Ad esempio: 4 può essere suddiviso in: 4 = 4, 4 = 1 + 1 + 1 + 1, 4 = 2 + 2, 4=1+1+2.

f(n) rappresenta il numero di diverse suddivisioni di n, ad esempio f(7) = 6.

È richiesto di scrivere un programma per leggere n (non superiore a 1000000) e output f(n)

Input: un intero N (1 <= N <= 1000000).

Output: f(n)

Se i dati di input superano il range, l'output è -1.

Input di esempio:

7

Output di esempio:

6

Implementazione del codice:

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, ci sono 1 modo di suddividere
　　　 if n == 1 {
　　　　　　　 return 1
　　　 }
　　　 //2=2, 2=1+1, ci sono 2 modi di suddividere
　　　 if n == 2 {
　　　　　　　 return 2
　　　 }
　　　 //n>=3
　　　 //Salva i numeri già calcolati
　　　 data := make([]int, n+1)
　　　 data[0] = 0 //Questo valore non ha significato, ha solo lo scopo di occupare spazio
　　　 data[1] = 1
　　　 data[2] = 2
　　　 for i := 3; i <= n; i++ {
　　　　　　　 if i%2 == 0 {
　　　　　　　　　　　 //Numero pari
　　　　　　　　　　　 data[i] = data[i-2] + data[i/2]
　　　　　　　 } else {
　　　　　　　　　　　 //Numero dispari
　　　　　　　　　　　 data[i] = data[i-1]
　　　　　　　 }
　　　 }
　　　 return data[n]
}

Spero che il contenuto di questo articolo possa essere utile per la progettazione di programmi Go.

Dichiarazione: il contenuto di questo articolo è stato tratto da Internet, il copyright è di proprietà del rispettivo proprietario, il contenuto è stato contribuito e caricato autonomamente dagli utenti di Internet, questo sito non possiede il diritto di proprietà, non è stato editato manualmente e non assume alcuna responsabilità legale correlata. Se trovi contenuti sospetti di violazione del copyright, ti preghiamo di inviare una e-mail a notice#oldtoolbag.com (sostituisci # con @) per segnalare il problema e fornire prove pertinenti. Una volta verificata, questo sito eliminerà immediatamente il contenuto sospetto di violazione del copyright.