Addition chains: Difference between revisions
Content added Content deleted
(Added Go) |
(Added C) |
||
Line 21: | Line 21: | ||
* brauer-chains(19) : count = 31 Ex: ( 1 2 3 4 8 11 19) |
* 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) |
* non-brauer-chains(19) : count = 2 Ex: ( 1 2 3 6 7 12 19) |
||
=={{header|C}}== |
|||
{{trans|Kotlin}} |
|||
<lang c>#include <stdio.h> |
|||
#include <stdlib.h> |
|||
#include <string.h> |
|||
#define TRUE 1 |
|||
#define FALSE 0 |
|||
typedef int bool; |
|||
typedef struct { |
|||
int x, y; |
|||
} pair; |
|||
int* example = NULL; |
|||
int exampleLen = 0; |
|||
void reverse(int s[], int len) { |
|||
int i, j, t; |
|||
for (i = 0, j = len - 1; i < j; ++i, --j) { |
|||
t = s[i]; |
|||
s[i] = s[j]; |
|||
s[j] = t; |
|||
} |
|||
} |
|||
pair tryPerm(int i, int pos, int seq[], int n, int len, int minLen); |
|||
pair checkSeq(int pos, int seq[], int n, int len, int minLen) { |
|||
pair p; |
|||
if (pos > minLen || seq[0] > n) { |
|||
p.x = minLen; p.y = 0; |
|||
return p; |
|||
} |
|||
else if (seq[0] == n) { |
|||
example = malloc(len * sizeof(int)); |
|||
memcpy(example, seq, len * sizeof(int)); |
|||
exampleLen = len; |
|||
p.x = pos; p.y = 1; |
|||
return p; |
|||
} |
|||
else if (pos < minLen) { |
|||
return tryPerm(0, pos, seq, n, len, minLen); |
|||
} |
|||
else { |
|||
p.x = minLen; p.y = 0; |
|||
return p; |
|||
} |
|||
} |
|||
pair tryPerm(int i, int pos, int seq[], int n, int len, int minLen) { |
|||
int *seq2; |
|||
pair p, res1, res2; |
|||
size_t size = sizeof(int); |
|||
if (i > pos) { |
|||
p.x = minLen; p.y = 0; |
|||
return p; |
|||
} |
|||
seq2 = malloc((len + 1) * size); |
|||
memcpy(seq2 + 1, seq, len * size); |
|||
seq2[0] = seq[0] + seq[i]; |
|||
res1 = checkSeq(pos + 1, seq2, n, len + 1, minLen); |
|||
res2 = tryPerm(i + 1, pos, seq, n, len, res1.x); |
|||
free(seq2); |
|||
if (res2.x < res1.x) |
|||
return res2; |
|||
else if (res2.x == res1.x) { |
|||
p.x = res2.x; p.y = res1.y + res2.y; |
|||
return p; |
|||
} |
|||
else { |
|||
printf("Error in tryPerm\n"); |
|||
p.x = 0; p.y = 0; |
|||
return p; |
|||
} |
|||
} |
|||
pair initTryPerm(int x, int minLen) { |
|||
int seq[1] = {1}; |
|||
return tryPerm(0, 0, seq, x, 1, minLen); |
|||
} |
|||
void printArray(int a[], int len) { |
|||
int i; |
|||
printf("["); |
|||
for (i = 0; i < len; ++i) printf("%d ", a[i]); |
|||
printf("\b]\n"); |
|||
} |
|||
bool isBrauer(int a[], int len) { |
|||
int i, j; |
|||
bool ok; |
|||
for (i = 2; i < len; ++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; |
|||
} |
|||
bool isAdditionChain(int a[], int len) { |
|||
int i, j, k; |
|||
bool ok, exit; |
|||
for (i = 2; i < len; ++i) { |
|||
if (a[i] > a[i - 1] * 2) return FALSE; |
|||
ok = FALSE; exit = FALSE; |
|||
for (j = i - 1; j >= 0; --j) { |
|||
for (k = j; k >= 0; --k) { |
|||
if (a[j] + a[k] == a[i]) { ok = TRUE; exit = TRUE; break; } |
|||
} |
|||
if (exit) break; |
|||
} |
|||
if (!ok) return FALSE; |
|||
} |
|||
if (example == NULL && !isBrauer(a, len)) { |
|||
example = malloc(len * sizeof(int)); |
|||
memcpy(example, a, len * sizeof(int)); |
|||
exampleLen = len; |
|||
} |
|||
return TRUE; |
|||
} |
|||
void nextChains(int index, int len, int seq[], int *pcount) { |
|||
for (;;) { |
|||
int i; |
|||
if (index < len - 1) { |
|||
nextChains(index + 1, len, seq, pcount); |
|||
} |
|||
if (seq[index] + len - 1 - index >= seq[len - 1]) return; |
|||
seq[index]++; |
|||
for (i = index + 1; i < len - 1; ++i) { |
|||
seq[i] = seq[i-1] + 1; |
|||
} |
|||
if (isAdditionChain(seq, len)) (*pcount)++; |
|||
} |
|||
} |
|||
int findNonBrauer(int num, int len, int brauer) { |
|||
int i, count = 0; |
|||
int *seq = malloc(len * sizeof(int)); |
|||
seq[0] = 1; |
|||
seq[len - 1] = num; |
|||
for (i = 1; i < len - 1; ++i) { |
|||
seq[i] = seq[i - 1] + 1; |
|||
} |
|||
if (isAdditionChain(seq, len)) count = 1; |
|||
nextChains(2, len, seq, &count); |
|||
free(seq); |
|||
return count - brauer; |
|||
} |
|||
void findBrauer(int num, int minLen, int nbLimit) { |
|||
pair p = initTryPerm(num, minLen); |
|||
int actualMin = p.x, brauer = p.y, nonBrauer; |
|||
printf("\nN = %d\n", num); |
|||
printf("Minimum length of chains : L(%d) = %d\n", num, actualMin); |
|||
printf("Number of minimum length Brauer chains : %d\n", brauer); |
|||
if (brauer > 0) { |
|||
printf("Brauer example : "); |
|||
reverse(example, exampleLen); |
|||
printArray(example, exampleLen); |
|||
} |
|||
if (example != NULL) { |
|||
free(example); |
|||
example = NULL; |
|||
exampleLen = 0; |
|||
} |
|||
if (num <= nbLimit) { |
|||
nonBrauer = findNonBrauer(num, actualMin + 1, brauer); |
|||
printf("Number of minimum length non-Brauer chains : %d\n", nonBrauer); |
|||
if (nonBrauer > 0) { |
|||
printf("Non-Brauer example : "); |
|||
printArray(example, exampleLen); |
|||
} |
|||
if (example != NULL) { |
|||
free(example); |
|||
example = NULL; |
|||
exampleLen = 0; |
|||
} |
|||
} |
|||
else { |
|||
printf("Non-Brauer analysis suppressed\n"); |
|||
} |
|||
} |
|||
int main() { |
|||
int i; |
|||
int nums[12] = {7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379}; |
|||
printf("Searching for Brauer chains up to a minimum length of 12:\n"); |
|||
for (i = 0; i < 12; ++i) findBrauer(nums[i], 12, 79); |
|||
return 0; |
|||
}</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> |
|||
=={{header|C#|C sharp}}== |
=={{header|C#|C sharp}}== |