Exam & Solution - A Concise and Practical Introduction to Programming Algorithms in Java - page 241

Transition (4 , null ))));
System . out . println ( "\ns1" );
testAll(s1);
System . out . println ( "\ns2" );
testAll(s2);
System . out . println ( "\ns3" );
testAll(s3);

System . out . println ( "s2^s3" );
print(xorSignals(s2 , s3)) ;

System . out . println ( "\nsigna1" );
testAll (signal1) ;

}

}

Solution 11.4 (Nim game)

The game of Nim is a two-player game. We consider m bins (indexed
from 0 to m

1), with bin i containing x i fruits. A game configuration
is therefore represented by an array of integers.

−

The two players are playing in turn. A player move consists of taking as
many as wished (but at least one) fruit(s) in a same bin. The winner
is the player who takes that last remaining fruit (hence all bins become
empty).

The outcome of this game is fully predictable: One of the two players
(depending on the initial bin configuration and the first player) has a
winning strategy whatever the second player does. We shall study here
this strategy.

We begin by writing two conversion functions as follows: The first
function converts a number written in base 2 to a number written in
base 10. The second function is the reciprocal function: conversion from
base 10 to 2.

- An integer n represented in base 2 shall be modeled using an
integer array binaryRepresentation of length k storing the k bits.
We assume that all values in this array are equal to 0 or 1, and
binaryRepresentation[i] is the i -th bit of the decomposition of n in base
2:

i<k

2 i

n =

∗

binaryRepresentation[i]

i=0