Let f(n,x) be the number of ways of tracing out a number of length x starting at n.
By symmetry, f(1,x)=f(3,x)=f(7,x)=f(9,x) Simarly f(4,x)=f(2,x)=f(8,x)=f(6,x) We then just need a reacurrence relation. f(1,x)=f(5,x-1)+f(9,x-1) f(2,x)=f(4,x-1)+f(6,x-1)=2*f(2,x-1) f(5,x)=f(1,x-1)+f(3,x-1)+f(7,x-1)+f(9,x-1)=4*f(1,x-1) f(n,0)=1 You could even probably combine these to get a formula for the solution. On 12/24/06, BoBo_C <[EMAIL PROTECTED]> wrote:
Hi- I recently ran across a programming problem that I didn't even know how to begin to solve. I'm just now learning algorithms, and I imagine some type of algorithm is required. The problem is as follows: You are given a phone dial pad that looks like this: 1 2 3 4 5 6 7 8 9 Supposing that you're using a bishop (from chess) to dial numbers, and the bishop can only move like a bishop (that is, diagonally in any direction for any number of spaces), how many unique seven-digit numbers can be traced? N.B. - The number '1' is to be disregarded for the purposes of the problem - it isn't to be included in any numbers. For example, the bishop starting on '2' could travel thusly: 2-4-2-4-8-6-8. That would account for one possible number. It could also go 2-4-2-4-2-4-2, etc. If it were on 3, it could go 3-7-5-3-5-9-5. Another twist is that the design of the solution should enable you to easily substitute any other type of chess piece for the bishop, adding an object-oriented aspect to the problem. One number a rook, should you choose to use it, would be able to dial would be 7-2-7-2-7-2-7. It would be limited to moving as a rook does in chess. How would one approach solving this problem? Thanks for any advice/help/comments... >
--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---