Addition chains: Difference between revisions
Added C#
(Added Java) |
(Added C#) |
||
Line 21:
* brauer-chains(19) : count = 31 Ex: ( 1 2 3 4 8 11 19)
* non-brauer-chains(19) : count = 2 Ex: ( 1 2 3 6 7 12 19)
=={{header|C#|C sharp}}==
{{trans|Java}}
<lang csharp>using System;
namespace AdditionChains {
class Program {
static int[] Prepend(int n, int[] seq) {
int[] result = new int[seq.Length + 1];
Array.Copy(seq, 0, result, 1, seq.Length);
result[0] = n;
return result;
}
static Tuple<int, int> CheckSeq(int pos, int[] seq, int n, int min_len) {
if (pos > min_len || seq[0] > n) return new Tuple<int, int>(min_len, 0);
if (seq[0] == n) return new Tuple<int, int>(pos, 1);
if (pos < min_len) return TryPerm(0, pos, seq, n, min_len);
return new Tuple<int, int>(min_len, 0);
}
static Tuple<int, int> TryPerm(int i, int pos, int[] seq, int n, int min_len) {
if (i > pos) return new Tuple<int, int>(min_len, 0);
Tuple<int, int> res1 = CheckSeq(pos + 1, Prepend(seq[0] + seq[i], seq), n, min_len);
Tuple<int, int> res2 = TryPerm(i + 1, pos, seq, n, res1.Item1);
if (res2.Item1 < res1.Item1) return res2;
if (res2.Item1 == res1.Item1) return new Tuple<int, int>(res2.Item1, res1.Item2 + res2.Item2);
throw new Exception("TryPerm exception");
}
static Tuple<int, int> InitTryPerm(int x) {
return TryPerm(0, 0, new int[] { 1 }, x, 12);
}
static void FindBrauer(int num) {
Tuple<int, int> res = InitTryPerm(num);
Console.WriteLine();
Console.WriteLine("N = {0}", num);
Console.WriteLine("Minimum length of chains: L(n)= {0}", res.Item1);
Console.WriteLine("Number of minimum length Brauer chains: {0}", res.Item2);
}
static void Main(string[] args) {
int[] nums = new int[] { 7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379 };
Array.ForEach(nums, n => FindBrauer(n));
}
}
}</lang>
{{out}}
<pre>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|D}}==
| |||