Addition chains: Difference between revisions
Added C
(Added Go) |
(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}}==
{{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}}==
| |||