algorithm

Finding winning strategies

This time I want to show how to solve a game using a perfect play which means being able to predict the outcome of the game from any position. The perfect play is the strategy that leads to the best possible outcome for that player regardless of the response by the opponent. For the illustration I have selected two children’s games with stones. The rules are very simple. There is a pile of 99 stones. Two player take n stones out of the pile in turn. The one who takes the last stone is the winner. In each game n is different: it is in the closed interval between 1 and 3 power of 2 Let’s find out how to always win these kind of games.

Solving a payment without change problem

I have come across an interesting problem. A customer is standing at the checkout of a grocery store with his purchases and is asked to pay the exact amount without creating any change. There are notes of various denominations in his pockets in random order (note denomination is not tied to a real bank notes, the only boundary is that it is an integer greater than 0). The objective is to pick up the necessary sum or indicate that it is not possible. If several solutions are possible then any of them is acceptable. So, let's solve it using C# language.