Addition chains: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: Fix link: Perl 6 --> Raku) |
|||
Line 2,418: | Line 2,418: | ||
Brauer example : (1 2 4 8 16 32 64) |
Brauer example : (1 2 4 8 16 32 64) |
||
Number of minimum length non-Brauer chains : 0</pre> |
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}}== |
=={{header|Scala}}== |