Commits

Markus Tzoe committed 25ac0ef

fibonacci basically done

Comments (0)

Files changed (1)

fibonacci/fibonacci.go

+package main
+
+import (
+	"fmt"
+)
+
+var lm []int64
+
+func init() {
+	lm = make([]int64, 100)
+	lm[0] = 1
+	lm[1] = 1
+	for i := 2; i < 100; i++ {
+		lm[i] = lm[i-1] + lm[i-2]
+	}
+}
+
+func f(n int) string {
+	switch n {
+	case 0:
+		return "0"
+	case 1:
+		return "1"
+	}
+	return f(n-1) + f(n-2)
+}
+
+func getfib(n int) int {
+	m := 0
+	for ; m < 100; m++ {
+		if lm[m] >= int64(n) {
+			break
+		}
+	}
+	return m
+}
+
+func calcmid(pattern string) (int64, int64) {
+	l0 := len(pattern)
+	m := getfib(l0)
+	b := []byte(f(m))
+	b2 := []byte(f(m + 1))
+	b = append(b[len(b)-l0+1:], b[:l0-1]...)
+	b2 = append(b2[len(b2)-l0+1:], b2[:l0-1]...)
+	l1 := len(b) - l0
+	l2 := len(b2) - l0
+	count, count2 := int64(0), int64(0)
+	for i := 0; i <= l1; i++ {
+		if string(b[i:i+l0]) == pattern {
+			count++
+			// fmt.Println("[1]: ", i, string(b[i:i+l0]))
+		}
+	}
+	for i := 0; i <= l2; i++ {
+		if string(b2[i:i+l0]) == pattern {
+			count2++
+			// fmt.Println("[2]: ", i, string(b2[i:i+l0]))
+		}
+	}
+	// fmt.Println(string(b), string(b2))
+	return count, count2
+}
+
+func calcend(pattern string) (int64, int64, int) {
+	l0 := len(pattern)
+	lim := getfib(l0)
+	fib1 := f(lim)
+	fib2 := f(lim + 1)
+	b := []byte(fib1)
+	b2 := []byte(fib2)
+	l1 := len(b) - l0
+	l2 := len(b2) - l0
+	count, count2 := int64(0), int64(0)
+	for i := 0; i <= l1; i++ {
+		if string(b[i:i+l0]) == pattern {
+			count++
+		}
+	}
+	for i := 0; i <= l2; i++ {
+		if string(b2[i:i+l0]) == pattern {
+			count2++
+		}
+	}
+	return count2, count, lim
+}
+
+func brute(num int, pattern string) int64 {
+	if num > 20 { // suitable when n is small enough
+		return -1
+	}
+	b := []byte(f(num))
+	count := int64(0)
+	l0 := len(pattern)
+	l := len(b) - len(pattern)
+	for i := 0; i <= l; i++ {
+		if string(b[i:i+l0]) == pattern {
+			count++
+		}
+	}
+	return count
+}
+
+func Calc(num int, pattern string) int64 {
+	if num > 100 || num < 0 {
+		return -1
+	}
+	a1, a2, d := calcend(pattern)
+	j := num - d
+	switch {
+	case j < 0:
+		return 0
+	case j == 0:
+		return a2
+	case j == 1:
+		return a1
+	}
+	c1, c2 := calcmid(pattern)
+	k1, k2 := int64(0), int64(0)
+	for i := 1; i < j; i++ {
+		if d%2 == i%2 {
+			k1 += lm[i-1]
+		} else {
+			k2 += lm[i-1]
+		}
+	}
+	// fmt.Printf("c1=%d,c2=%d,k1=%d,k2=%d,lm1=%d,lm2=%d\n", c1, c2, k1, k2, lm[j-1], lm[j-2])
+	return (lm[j-1]*a1 + lm[j-2]*a2 + k1*c1 + k2*c2)
+}
+
+func main() {
+	for i := 10; i < 97; i++ {
+		fmt.Printf("%d: %v\n", i, Calc(i, "10110101101101"))
+	}
+}
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.