Addition chains: Difference between revisions
→{{header|Scala}}
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: Fix link: Perl 6 --> Raku) |
|||
Line 2,418:
Brauer example : (1 2 4 8 16 32 64)
Number of minimum length non-Brauer chains : 0</pre>
=={{header|Ruby}}==
{{trans|D}}
<lang ruby>def check_seq(pos, seq, n, min_len)
if pos > min_len or seq[0] > n then
return min_len, 0
elsif seq[0] == n then
return pos, 1
elsif pos < min_len then
return try_perm(0, pos, seq, n, min_len)
else
return min_len, 0
end
end
def try_perm(i, pos, seq, n, min_len)
if i > pos then
return min_len, 0
end
res11, res12 = check_seq(pos + 1, [seq[0] + seq[i]] + seq, n, min_len)
res21, res22 = try_perm(i + 1, pos, seq, n, res11)
if res21 < res11 then
return res21, res22
elsif res21 == res11 then
return res21, res12 + res22
else
raise "try_perm exception"
end
end
def init_try_perm(x)
return try_perm(0, 0, [1], x, 12)
end
def find_brauer(num)
actualMin, brauer = init_try_perm(num)
puts
print "N = ", num, "\n"
print "Minimum length of chains: L(n)= ", actualMin, "\n"
print "Number of minimum length Brauer chains: ", brauer, "\n"
end
def main
nums = [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]
for i in nums do
find_brauer(i)
end
end
main()</lang>
{{out}}
<pre>
D:\Code\github\ncoe\rosetta\Addition_chains\Ruby>N = 7
Minimum length of chains: L(n)= 4
Number of minimum length Brauer chains: 5
N = 14
Minimum length of chains: L(n)= 5
Number of minimum length Brauer chains: 14
N = 21
Minimum length of chains: L(n)= 6
Number of minimum length Brauer chains: 26
N = 29
Minimum length of chains: L(n)= 7
Number of minimum length Brauer chains: 114
N = 32
Minimum length of chains: L(n)= 5
Number of minimum length Brauer chains: 1
N = 42
Minimum length of chains: L(n)= 7
Number of minimum length Brauer chains: 78
N = 64
Minimum length of chains: L(n)= 6
Number of minimum length Brauer chains: 1
N = 47
Minimum length of chains: L(n)= 8
Number of minimum length Brauer chains: 183
N = 79
Minimum length of chains: L(n)= 9
Number of minimum length Brauer chains: 492
N = 191
Minimum length of chains: L(n)= 11
Number of minimum length Brauer chains: 7172
N = 382
Minimum length of chains: L(n)= 11
Number of minimum length Brauer chains: 4
N = 379
Minimum length of chains: L(n)= 12
Number of minimum length Brauer chains: 6583</pre>
=={{header|Scala}}==
| |||