java项目Euler问题18帕斯卡三角形

1 周，3 日 Questions & Answers 130

编辑2 在Gavin的建议下，我将offset代码分离成一个新方法：

private static int getOffset(int offset, int row, int col, ArrayList<ArrayList<Integer>> triangle, ArrayList<ArrayList<Integer>> p_triangle, ArrayList<Integer> sums) {
    int row_num = (row+1); //= 1-indexed row #
    int p_value = p_triangle.get(row).get(col); // number from pascal's triangle

    if (col > 1)  {
        // element is in the left half of Pascal's Triangle
        if (col <= (row_num/2))       offset++;
        // penultimate element
        else if (col == row_num - 2)  offset = sums.size() - p_value;
        // elements halfway until penultimate;
        // [-2, -3] all work up until row 10 and fail thereafter
        else                          offset = sums.size() - p_value - (row_num - col - 2);
    }

    return offset;
  }

并且发现，奇怪的是，在计算给定行后半部分（在中间和倒数第二行之间）的元素偏移量时，减去2或3都会起作用。我不知道为什么会这样

更奇怪的是，我修改了奥列格的答案

public static int findMaxSum(ArrayList<ArrayList<Integer>> data) {
    for (int row = data.size() - 2; row >= 0; row--)
      for (int col = 0; col < data.get(row).size(); col++)
        data.get(row).set(col, data.get(row).get(col) + Math.max(data.get(row + 1).get(col), data.get(row + 1).get(col + 1)));

    return data.get(0).get(0);
  }

并发现算法的行为在一个大小为10的三角形内似乎是正确的。但是，之后开始细分，第11-15行出现以下差异：

size = 11 [correct:772 | mine:752]
size = 12 [correct:850 | mine:830]
size = 13 [correct:908 | mine:921]
size = 14 [correct:981 | mine:961]
size = 15 [correct:1074 | mine:1059]

不幸的是，我仍然无法从中辨别出一种模式

编辑我想强调的是，我不是在寻找更好的方法来解决这个特殊的项目问题；相反，我只想知道是否有可能使用Pascal三角形以我所描述的方式（或以一些稍微修改的方式）来完成，是否有人可以看到我代码中的逻辑，我可能对此一无所知

原始问题 我正在试图解决Project Euler problem 18

目标是找到三角形中所有2^14条路径的最大和

我被帕斯卡三角形的相似性所震惊，想知道它是否可以用来解决这个问题

我的逻辑如下：

1.）按行计算总和。 2.）使用帕斯卡三角形确定必须有多少行（每行加起来等于二的幂），并确定与前几行总和的开始的偏移量

前

Pascal's Triangle
   1
  1 1
 1 2 1
1 3 3 1

Triangle To Process
   3
  7 4
 2 4 6
8 5 9 3

Sums
              [3]
            [10, 7]
        [12, 14, 11, 13]
[20, 17, 19, 16, 23, 20, 22, 16]

对于第3行，我们看到Pascal三角形告诉我们将有1+2+1或4个值。此外，它还描述了如何构建和，因为它是直接添加到它们前面的和的第一个和最后一个元素，中间值添加到这两个和，因为它与前面的两个链都有联系

通过扩展，第四行显示要处理的三角形中的第二个数字应添加到第三行的前三个和中，第三个数字应添加到最后三个

我得到偏移量的方式有点难看（可能是麻烦的根源）：

if (i > 1)  {
  if (i < (p_triangle.get(row).size()/2))   offset++;
  else if (i == triangle.get(row).size()-2) offset = sums.size() - p_triangle.get(row).get(i);
  else  offset = sums.size() - p_triangle.get(row).get(i) - (p_triangle.get(row).size() - i - 2);
}

其中p_triangle.get(row)是正在使用的当前Pascal三角形行，sums是累积和的数组（长度为2^（行-1）），偏移量是从何处开始求和，Pascal三角形数是从偏移量开始的和列表中有多少个元素与三角形中索引i处的数字求和以进行处理，即triangle.get(row).get(i)

我知道这可能不是解决这个问题的最有效的算法，但它似乎是一个不错的算法。问题是，我不能让它工作

关于问题答案的扰流板警报 正确答案显然是1074

谁能告诉我，在使用帕斯卡三角形的代码或逻辑中，我可能把事情弄糟了

完整代码：

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.lang.Math;

public class MaxPathSum {


  private static ArrayList<ArrayList<Integer>> pascalsTriangle(int n_rows) {
    ArrayList<ArrayList<Integer>> triangle = new ArrayList<>();
    triangle.add(new ArrayList<Integer>(){{add(1);}});
    triangle.add(new ArrayList<Integer>(){{add(1); add(1);}});

    for (int row = 2; row < n_rows; row++) {
      ArrayList<Integer> next_row = new ArrayList<>();
      next_row.add(1);
      for (int i = 1; i < triangle.get(row-1).size(); i++) {
        next_row.add(triangle.get(row-1).get(i-1) + triangle.get(row-1).get(i));
      }
      next_row.add(1);
      triangle.add(next_row);
    }
    return triangle;
  }

  private static ArrayList<ArrayList<Integer>> buildTriangle(int n_rows) {
    Scanner sc = new Scanner(System.in);
    ArrayList<ArrayList<Integer>> triangle = new ArrayList<>();

    for (int row = 1; row <= n_rows; row++) {
      ArrayList<Integer> row_arr = new ArrayList<>();
      for (int elem = 1; elem <= row; elem++) {
        row_arr.add(sc.nextInt());
      }
      triangle.add(row_arr);
    }
    return triangle;
  }


  private static int findLargestSum(ArrayList<ArrayList<Integer>> triangle, ArrayList<ArrayList<Integer>> p_triangle) {
    ArrayList<Integer> sums = new ArrayList<>();
    sums.add(triangle.get(0).get(0));

    // traverse the rows
    for (int row = 1, offset = 0; row < triangle.size(); row++, offset = 0) {
      ArrayList<Integer> new_sums = new ArrayList<>();
      
      // traverse each element in each row
      new_sums.add(sums.get(0) + triangle.get(row).get(0));
      for (int i = 1; i < triangle.get(row).size()-1; i++) {
        int n_times = p_triangle.get(row).get(i);
        for (int j = 0; j < n_times; j++) {
          new_sums.add(triangle.get(row).get(i) + sums.get(j+offset));
        }
        if (i > 1)  {
          if (i < (p_triangle.get(row).size()/2))   offset++;
          else if (i == triangle.get(row).size()-2) offset = sums.size() - p_triangle.get(row).get(i);
          else  offset = sums.size() - p_triangle.get(row).get(i) - (p_triangle.get(row).size() - i - 2);

          System.out.println("Row: " + row + " | Offset: " + offset);
        }
      }
      new_sums.add(sums.get(sums.size()-1) + triangle.get(row).get(triangle.get(row).size()-1));
      sums = new_sums;
    }

    Collections.sort(sums);
    return sums.get(sums.size() - 1);
  }


  public static void main(String[] args) {
    int n_rows = Integer.parseInt(args[0]);

    // build pascalsTriangle
    ArrayList<ArrayList<Integer>> p_triangle = pascalsTriangle(n_rows);

    // build triangle from input
    ArrayList<ArrayList<Integer>> triangle = buildTriangle(n_rows);

    // traverse triangle finding largest sum
    int largest_sum = findLargestSum(triangle, p_triangle);

    // display results
    System.out.println(largest_sum);
  }
}

Python中文网

有 Java 编程相关的问题?

java项目Euler问题18帕斯卡三角形

共 (1) 个答案

# 1 楼答案