Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- * Calculates the weight being carried by the person at row, col.
- *
- * @param row The row position of the person.
- * @param col The column position of the person.
- * @return A double representing the amount of weight the person at row col is carrying.
- */
- private static double weightOn(int row, int col) {
- if (row == 0 && col == 0) {
- //base case: we are at (0,0)
- return 0;
- } else if (col == 0) {
- //recursive case: left edge
- //(weight of the person above + the weight they are carrying) divide by 2
- return (weightOn(row-1, col) + weight) / 2;
- } else if (row == col) {
- //recursive case: right edge
- //(weight of the person above + the weight they are carrying) divide by 2
- return (weightOn(row-1, col-1) + weight) / 2;
- } else {
- //recursive case: somewhere in the middle
- //(weight of the people above + the weight they are carrying) divide by 2
- double leftNode = weightOn(row-1,col-1);
- double rightNode = weightOn(row-1,col);
- return (leftNode + rightNode + weight*2) / 2;
- }
- }
- /**
- * Calculate the weight being carried by ther person at row, col.
- * Uses memoization for optimization
- * RETURNS: A 2d ragged array of weights, filled out for the given row and column
- *
- * @param row The row position of the person.
- * @param col The column position of the person.
- * @return A double representing the amount of weight the person at row col is carrying.
- */
- private static double[][] weightOnMemo(int row, int col, double[][] arr) {
- //initialize ragged array and fill with 0.0 if arr is empty
- if (arr.length == 0) {
- arr = new double[row+1][];
- for (int r = 0; r < arr.length; r++ ) {
- arr[r] = new double[r+1];
- for (int c = 0; c < r+1; c++) {
- arr[r][c] = 0.0;
- }
- }
- }
- //check if value already exists
- if (arr[row][col] != 0.0) {
- //value already exists
- return arr;
- }
- // Do calculation and recursive method calls.
- //Past here, we know the value for arr[row][col] does not exist so we need to calculate and insert it
- if (col == 0) {
- //left edge
- //check if value above exists
- double val = arr[row-1][col]; //(weightOn(row-1, col) + weight) / 2;
- if (val == 0 && row-1 > 0) {
- //if val is empty and we are not checking (0,0)
- arr = weightOnMemo(row-1, col, arr); //fill target index with weight value
- val = arr[row-1][col]; //update val with new weight
- }
- //fill value for current index
- arr[row][col] = (val+weight)/2;
- return arr;
- } else if (row == col) {
- //right edge
- //check if value above exists
- double val = arr[row-1][col-1]; //(weightOn(row-1, col-1) + weight) / 2;
- if (val == 0 && row-1 > 0) {
- //if val is empty and we are not checking (0,0)
- arr = weightOnMemo(row-1, col-1, arr); //fill target index with weight value
- val = arr[row-1][col-1]; //update val with new weight
- }
- //fill value for current index
- arr[row][col] = (val+weight)/2;
- return arr;
- } else {
- //middle: need both left and right weights above
- //At this point, we know we cannot check (0,0) directly from out position
- double left = arr[row-1][col-1];
- double right = arr[row-1][col];
- if (left == 0) {
- //if val is empty
- arr = weightOnMemo(row-1, col-1, arr); //fill target index with weight value
- left = arr[row-1][col-1]; //update val with new weight
- }
- if (right == 0) {
- //if val is empty
- arr = weightOnMemo(row-1, col, arr); //fill target index with weight value
- right = arr[row-1][col]; //update val with new weight
- }
- //fill value for current index
- arr[row][col] = (left+right+weight*2)/2;
- return arr;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement