|
|
back to boardhow about use recursion think about : F(N,M) = F(N-? , M- ? ) and give the initial values. Re: how about use recursion Posted by Egor 30 Oct 2016 17:24 The number of steps is too big. By doing a single recursive step you reduce the size of the original problem to (N - 2, M - 2). If we were to reduce the size to (N / 2, M / 2) (notice that we changed minus sign to division), then we could solve it recursively. Instead you should think of this problem as a whole. There are N rows and M columns. So some part of the robots path is by row and some part is by column: path = row|column|row|column|row|column... And we are counting the number of signs | in the path. As we see, each column is surrounded by sign | from both of its sides: "|column|". The first rough estimate that comes to mind after this observation is that probably the robot does 2 * (number of columns) turns. And by thinking of different specific cases of (N, M) we can turn this estimate into a true measure of the number of turns of the robot in the general case. Edited by author 30.10.2016 17:25 |
|
|