Анализ метода разбиения целого числа на части в 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 {
　　　　　　　 возврат -1
　　　 }
　　　 // 1=1, 1 способ разделения
　　　 if n == 1 {
　　　　　　　 возврат 1
　　　 }
　　　 // 2=2, 2=1+1, 2 способа разделения
　　　 if n == 2 {
　　　　　　　 возврат 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]
　　　　　　　 }
　　　 }
　　　 возврат data[n]
}

Надеюсь, что описание в этой статье поможет вам в программировании на языке Go.

Заявление: содержимое этой статьи взято из Интернета, авторские права принадлежат соответствующему автору. Контент предоставлен пользователями Интернета, загружен самостоятельно, сайт не имеет права собственности, не редактировался вручную и не несет ответственности за связанные с этим юридические обязательства. Если вы обнаружите материалы,涉嫌侵犯版权， пожалуйста, отправьте письмо по адресу: notice#oldtoolbag.com (при отправке письма замените # на @) для сообщения о нарушении и предоставьте соответствующие доказательства. Если подтвердится, что материал нарушил права на интеллектуальную собственность, сайт немедленно удалят.