107 lines
2.4 KiB
Go
107 lines
2.4 KiB
Go
package main
|
|
|
|
import (
|
|
"fmt"
|
|
"math"
|
|
"math/big"
|
|
"strings"
|
|
)
|
|
|
|
func padovanRecur(n int) []int {
|
|
p := make([]int, n)
|
|
p[0], p[1], p[2] = 1, 1, 1
|
|
for i := 3; i < n; i++ {
|
|
p[i] = p[i-2] + p[i-3]
|
|
}
|
|
return p
|
|
}
|
|
|
|
func padovanFloor(n int) []int {
|
|
var p, s, t, u = new(big.Rat), new(big.Rat), new(big.Rat), new(big.Rat)
|
|
p, _ = p.SetString("1.324717957244746025960908854")
|
|
s, _ = s.SetString("1.0453567932525329623")
|
|
f := make([]int, n)
|
|
pow := new(big.Rat).SetInt64(1)
|
|
u = u.SetFrac64(1, 2)
|
|
t.Quo(pow, p)
|
|
t.Quo(t, s)
|
|
t.Add(t, u)
|
|
v, _ := t.Float64()
|
|
f[0] = int(math.Floor(v))
|
|
for i := 1; i < n; i++ {
|
|
t.Quo(pow, s)
|
|
t.Add(t, u)
|
|
v, _ = t.Float64()
|
|
f[i] = int(math.Floor(v))
|
|
pow.Mul(pow, p)
|
|
}
|
|
return f
|
|
}
|
|
|
|
type LSystem struct {
|
|
rules map[string]string
|
|
init, current string
|
|
}
|
|
|
|
func step(lsys *LSystem) string {
|
|
var sb strings.Builder
|
|
if lsys.current == "" {
|
|
lsys.current = lsys.init
|
|
} else {
|
|
for _, c := range lsys.current {
|
|
sb.WriteString(lsys.rules[string(c)])
|
|
}
|
|
lsys.current = sb.String()
|
|
}
|
|
return lsys.current
|
|
}
|
|
|
|
func padovanLSys(n int) []string {
|
|
rules := map[string]string{"A": "B", "B": "C", "C": "AB"}
|
|
lsys := &LSystem{rules, "A", ""}
|
|
p := make([]string, n)
|
|
for i := 0; i < n; i++ {
|
|
p[i] = step(lsys)
|
|
}
|
|
return p
|
|
}
|
|
|
|
// assumes lists are same length
|
|
func areSame(l1, l2 []int) bool {
|
|
for i := 0; i < len(l1); i++ {
|
|
if l1[i] != l2[i] {
|
|
return false
|
|
}
|
|
}
|
|
return true
|
|
}
|
|
|
|
func main() {
|
|
fmt.Println("First 20 members of the Padovan sequence:")
|
|
fmt.Println(padovanRecur(20))
|
|
recur := padovanRecur(64)
|
|
floor := padovanFloor(64)
|
|
same := areSame(recur, floor)
|
|
s := "give"
|
|
if !same {
|
|
s = "do not give"
|
|
}
|
|
fmt.Println("\nThe recurrence and floor based functions", s, "the same results for 64 terms.")
|
|
|
|
p := padovanLSys(32)
|
|
lsyst := make([]int, 32)
|
|
for i := 0; i < 32; i++ {
|
|
lsyst[i] = len(p[i])
|
|
}
|
|
fmt.Println("\nFirst 10 members of the Padovan L-System:")
|
|
fmt.Println(p[:10])
|
|
fmt.Println("\nand their lengths:")
|
|
fmt.Println(lsyst[:10])
|
|
|
|
same = areSame(recur[:32], lsyst)
|
|
s = "give"
|
|
if !same {
|
|
s = "do not give"
|
|
}
|
|
fmt.Println("\nThe recurrence and L-system based functions", s, "the same results for 32 terms.")
|