Universität Ulm, Fakultät für Mathematik und Wirtschaftswissenschaften, SAI

# Lösung zu Blatt 3 der Systemnahe Software I (WS 97/98)

## 5. Kleinholz

```#include <stdio.h>

#define Max_Stack 10

typedef struct {                      /* take num from stack */
unsigned int stack, num;
} move;

int gameover(int num, int stack[]) {  /* Test if game is over */
int i;
for (i = 0; i < num; i++) if (stack[i]) return 0;
return 1;
}

int xor(int num, int stack[]) {       /* xor stacks */
/* You will get a one in each column with a odd number of ones */
int res = stack[0], i;
for (i = 1; i < num; i++) res ^= stack[i];
return res;
}

move calc(int num, int stack[]) {     /* Calculate next move */
move res;
int i, maxcol, hi_bit, xr = xor(num, stack);
for (i = 0; i < 31; i++)  /* Determin the highest bit to be changed */
if (xr & 1 << i) maxcol = i;
for (i = 0; i < num; i++) /* Find a stack which has this bit set */
if (stack[i] & 1 << maxcol) hi_bit = i;
res.stack = hi_bit;
res.num = stack[hi_bit] - (stack[hi_bit] ^ xr);
return res;
}

void main() {
move nextturn;
int stack[Max_Stack], i;
int turn = 0;                      /* Turn = 1 = it is my turn */
int num = 4;                       /* Number of stacks */
printf("How many stacks: "); scanf("%d", &num);
for (i = 0; i < num; i++) {
printf("How many match are on stack %d: ", i + 1);
scanf("%d", &stack[i]);
}
if (xor(num, stack)) {
turn = 1;
printf("I will start the game.\n");
} else printf("You can go first.\n");
while (!gameover(num, stack)) {
for (i = 0; i < num; i++) printf("Stack %d: %4d\t", i + 1, stack[i]);
printf("\n");                   /* Print the actual situation */
if (turn)
nextturn = calc(num, stack); /* Calculate computer's move */
else {
printf("Which Stack: ");     /* Ask user for his move */
scanf("%d", &nextturn.stack);
nextturn.stack--;            /* Stacks are labeled from 0 to num-1 */
printf("How many: ");
scanf("%d", &nextturn.num);
}
printf("Haufen: %d, Anzahl: %d\n", 1 + nextturn.stack, nextturn.num);
stack[nextturn.stack] -= nextturn.num;
turn ^= 1;
}
if (turn) printf("Segmentation Fault (core dumped)\n");
else printf("You lost.\n");        /* I hope this will happen */
exit(0);
}
```

Ingo Melzer, 11. November 1997