Addition chains: Difference between revisions
Content deleted Content added
Added C# |
Added Go |
||
Line 277: | Line 277: | ||
(task 79) |
(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) |
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> |
</pre> |
||