Addition chains: Difference between revisions
Content deleted Content added
m use maxlen |
|||
Line 302: | Line 302: | ||
Non-Brauer analysis suppressed |
Non-Brauer analysis suppressed |
||
</pre> |
</pre> |
||
=={{header|C++}}== |
|||
While this worked, something made it run extremely slow. |
|||
{{trans|D}} |
|||
<lang cpp>#include <iostream> |
|||
#include <tuple> |
|||
#include <vector> |
|||
std::pair<int, int> tryPerm(int, int, const std::vector<int>&, int, int); |
|||
std::pair<int, int> checkSeq(int pos, const std::vector<int>& seq, int n, int minLen) { |
|||
if (pos > minLen || seq[0] > n) return { minLen, 0 }; |
|||
else if (seq[0] == n) return { pos, 1 }; |
|||
else if (pos < minLen) return tryPerm(0, pos, seq, n, minLen); |
|||
else return { minLen, 0 }; |
|||
} |
|||
std::pair<int, int> tryPerm(int i, int pos, const std::vector<int>& seq, int n, int minLen) { |
|||
if (i > pos) return { minLen, 0 }; |
|||
std::vector<int> seq2{ seq[0] + seq[i] }; |
|||
seq2.insert(seq2.end(), seq.cbegin(), seq.cend()); |
|||
auto res1 = checkSeq(pos + 1, seq2, n, minLen); |
|||
auto res2 = tryPerm(i + 1, pos, seq, n, res1.first); |
|||
if (res2.first < res1.first) return res2; |
|||
else if (res2.first == res1.first) return { res2.first, res1.second + res2.second }; |
|||
else throw std::runtime_error("tryPerm exception"); |
|||
} |
|||
std::pair<int, int> initTryPerm(int x) { |
|||
return tryPerm(0, 0, { 1 }, x, 12); |
|||
} |
|||
void findBrauer(int num) { |
|||
auto res = initTryPerm(num); |
|||
std::cout << '\n'; |
|||
std::cout << "N = " << num << '\n'; |
|||
std::cout << "Minimum length of chains: L(n)= " << res.first << '\n'; |
|||
std::cout << "Number of minimum length Brauer chains: " << res.second << '\n'; |
|||
} |
|||
int main() { |
|||
std::vector<int> nums{ 7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379 }; |
|||
for (int i : nums) { |
|||
findBrauer(i); |
|||
} |
|||
return 0; |
|||
}</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|C#|C sharp}}== |
=={{header|C#|C sharp}}== |