Created
December 18, 2013 17:39
-
-
Save tzachz/8026568 to your computer and use it in GitHub Desktop.
Spiderman exersize
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class Spiderman { | |
public int spiderman(int n) { | |
// we're going to calculate these for each floor, starting from first floor: | |
int waysToGetToThisFloorByJumpingTwoFloors = 0; // there's no -1 floor, so there's no way to jump two floors and get to first floor | |
int waysToGetToThisFloorDirectlyFromPreviousFloor = 1; // there's one way to get from 0 to 1 | |
int totalWaysToGetToThisFloor = 0; | |
for (int floor=1; floor <= n; floor++) { | |
// total ways = sum of ways ending with a big jump (2 floors) and ways ending with a small jump (1 floor): | |
totalWaysToGetToThisFloor = waysToGetToThisFloorDirectlyFromPreviousFloor + waysToGetToThisFloorByJumpingTwoFloors; | |
// now, preparing for next floor (floor+1): | |
// since there were X ways to get to 'floor' from floor-1, | |
// and we can jump straight from floor-1 to floor+1, | |
// there are exactly X ways to get to floor+1 which end with jumping two floors: | |
waysToGetToThisFloorByJumpingTwoFloors = waysToGetToThisFloorDirectlyFromPreviousFloor; | |
// since there were, in total, Y ways to get to 'floor', | |
// and we can jump one floor from floor to floor+1, | |
// there are Y ways to get to floor+1 which end with jumping one floor: | |
waysToGetToThisFloorDirectlyFromPreviousFloor = totalWaysToGetToThisFloor; | |
} | |
// we get here after the last calculation was made for floor n, | |
// so totalWaysToGetToThisFloor = total ways to get to floor n, which is what we needed | |
return totalWaysToGetToThisFloor; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment