Addition chains: Difference between revisions
Added Go
(Added C#) |
(Added Go) |
||
Line 277:
(task 79)
L(79) = 9 - brauer-chains: 492 non-brauer: 129 chains: (1 2 3 4 7 9 18 36 43 79) (1 2 3 5 7 12 24 31 48 79)
</pre>
=={{header|Go}}==
{{trans|Kotlin}}
<lang go>package main
import "fmt"
var example []int
func reverse(s []int) {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
}
func checkSeq(pos, n, minLen int, seq []int) (int, int) {
switch {
case pos > minLen || seq[0] > n:
return minLen, 0
case seq[0] == n:
example = seq
return pos, 1
case pos < minLen:
return tryPerm(0, pos, n, minLen, seq)
default:
return minLen, 0
}
}
func tryPerm(i, pos, n, minLen int, seq []int) (int, int) {
if i > pos {
return minLen, 0
}
seq2 := make([]int, len(seq)+1)
copy(seq2[1:], seq)
seq2[0] = seq[0] + seq[i]
res11, res12 := checkSeq(pos+1, n, minLen, seq2)
res21, res22 := tryPerm(i+1, pos, n, res11, seq)
switch {
case res21 < res11:
return res21, res22
case res21 == res11:
return res21, res12 + res22
default:
fmt.Println("Error in tryPerm")
return 0, 0
}
}
func initTryPerm(x, minLen int) (int, int) {
return tryPerm(0, 0, x, minLen, []int{1})
}
func findBrauer(num, minLen, nbLimit int) {
actualMin, brauer := initTryPerm(num, minLen)
fmt.Println("\nN =", num)
fmt.Printf("Minimum length of chains : L(%d) = %d\n", num, actualMin)
fmt.Println("Number of minimum length Brauer chains :", brauer)
if brauer > 0 {
reverse(example)
fmt.Println("Brauer example :", example)
}
example = nil
if num <= nbLimit {
nonBrauer := findNonBrauer(num, actualMin+1, brauer)
fmt.Println("Number of minimum length non-Brauer chains :", nonBrauer)
if nonBrauer > 0 {
fmt.Println("Non-Brauer example :", example)
}
example = nil
} else {
println("Non-Brauer analysis suppressed")
}
}
func isAdditionChain(a []int) bool {
for i := 2; i < len(a); i++ {
if a[i] > a[i-1]*2 {
return false
}
ok := false
jloop:
for j := i - 1; j >= 0; j-- {
for k := j; k >= 0; k-- {
if a[j]+a[k] == a[i] {
ok = true
break jloop
}
}
}
if !ok {
return false
}
}
if example == nil && !isBrauer(a) {
example = make([]int, len(a))
copy(example, a)
}
return true
}
func isBrauer(a []int) bool {
for i := 2; i < len(a); i++ {
ok := false
for j := i - 1; j >= 0; j-- {
if a[i-1]+a[j] == a[i] {
ok = true
break
}
}
if !ok {
return false
}
}
return true
}
func nextChains(index, le int, seq []int, pcount *int) {
for {
if index < le-1 {
nextChains(index+1, le, seq, pcount)
}
if seq[index]+le-1-index >= seq[le-1] {
return
}
seq[index]++
for i := index + 1; i < le-1; i++ {
seq[i] = seq[i-1] + 1
}
if isAdditionChain(seq) {
(*pcount)++
}
}
}
func findNonBrauer(num, le, brauer int) int {
seq := make([]int, le)
seq[0] = 1
seq[le-1] = num
for i := 1; i < le-1; i++ {
seq[i] = seq[i-1] + 1
}
count := 0
if isAdditionChain(seq) {
count = 1
}
nextChains(2, le, seq, &count)
return count - brauer
}
func main() {
nums := []int{7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379}
fmt.Println("Searching for Brauer chains up to a minimum length of 12:")
for _, num := range nums {
findBrauer(num, 12, 79)
}
}</lang>
{{out}}
<pre>
Searching for Brauer chains up to a minimum length of 12:
N = 7
Minimum length of chains : L(7) = 4
Number of minimum length Brauer chains : 5
Brauer example : [1 2 3 4 7]
Number of minimum length non-Brauer chains : 0
N = 14
Minimum length of chains : L(14) = 5
Number of minimum length Brauer chains : 14
Brauer example : [1 2 3 4 7 14]
Number of minimum length non-Brauer chains : 0
N = 21
Minimum length of chains : L(21) = 6
Number of minimum length Brauer chains : 26
Brauer example : [1 2 3 4 7 14 21]
Number of minimum length non-Brauer chains : 3
Non-Brauer example : [1 2 4 5 8 13 21]
N = 29
Minimum length of chains : L(29) = 7
Number of minimum length Brauer chains : 114
Brauer example : [1 2 3 4 7 11 18 29]
Number of minimum length non-Brauer chains : 18
Non-Brauer example : [1 2 3 6 9 11 18 29]
N = 32
Minimum length of chains : L(32) = 5
Number of minimum length Brauer chains : 1
Brauer example : [1 2 4 8 16 32]
Number of minimum length non-Brauer chains : 0
N = 42
Minimum length of chains : L(42) = 7
Number of minimum length Brauer chains : 78
Brauer example : [1 2 3 4 7 14 21 42]
Number of minimum length non-Brauer chains : 6
Non-Brauer example : [1 2 4 5 8 13 21 42]
N = 64
Minimum length of chains : L(64) = 6
Number of minimum length Brauer chains : 1
Brauer example : [1 2 4 8 16 32 64]
Number of minimum length non-Brauer chains : 0
N = 47
Minimum length of chains : L(47) = 8
Number of minimum length Brauer chains : 183
Brauer example : [1 2 3 4 7 10 20 27 47]
Number of minimum length non-Brauer chains : 37
Non-Brauer example : [1 2 3 5 7 14 19 28 47]
N = 79
Minimum length of chains : L(79) = 9
Number of minimum length Brauer chains : 492
Brauer example : [1 2 3 4 7 9 18 36 43 79]
Number of minimum length non-Brauer chains : 129
Non-Brauer example : [1 2 3 5 7 12 24 31 48 79]
N = 191
Minimum length of chains : L(191) = 11
Number of minimum length Brauer chains : 7172
Brauer example : [1 2 3 4 7 8 15 22 44 88 103 191]
Non-Brauer analysis suppressed
N = 382
Minimum length of chains : L(382) = 11
Number of minimum length Brauer chains : 4
Brauer example : [1 2 4 5 9 14 23 46 92 184 198 382]
Non-Brauer analysis suppressed
N = 379
Minimum length of chains : L(379) = 12
Number of minimum length Brauer chains : 6583
Brauer example : [1 2 3 4 7 10 17 27 44 88 176 203 379]
Non-Brauer analysis suppressed
</pre>
| |||