三角拼图：从顶部到底部查找最大总数，从顶部开始移动到相邻数字 [英] Triangle Puzzle: Find maximum total from top to bottom, starting at top moving moving to adjacent numbers
问题描述
正如标题所示，我需要解决这个难题。
As the title suggests, I need to solve this puzzle.
5
9 6
4 6 8
0 7 1 5
我需要找到的路径是最大和从上到下，只能移动到相邻的孩子。因此，该路径为5-9-6-7，总和为27。
The path I need to find is the max sum from top to bottom, only moving to adjacent children. So this path would be 5-9-6-7, with a sum of 27.
我的代码适用于我自己输入的每组数据，但是当我尝试带有提供的textFile数据的难题，我的总和/答案不正确。
My code works for every set of data I input myself, but when I attempt the puzzles with the provided textFile's data, my sum/answer is not accepted as correct.
我无法终生弄清楚我的代码有什么问题。我没有看到某些例外情况吗？
I cannot for the life of me figure out what is wrong with my code. Is there some exception I am not seeing?
public class Triangle
{
public static void main(String[] args) throws IOException
{
File file = new File("Tri.txt");
byte[] bytes = new byte[(int) file.length()];
try{
//Read the file and add all integers into an array with the correct size. Array size is found with number of bytes file.length()
//Parse string to integer
FileInputStream fis = new FileInputStream(file);
fis.read(bytes);
fis.close();
String[] valueStr = new String(bytes).trim().split("\\s+");
int[] list = new int[valueStr.length];
for (int i = 0; i < valueStr.length; i++)
list[i] = Integer.parseInt(valueStr[i]);
System.out.println(computeMaxPath(list));
}
catch(Exception e)
{
e.printStackTrace();
}
}
static int computeMaxPath(int[] list){
//Disregard row number one since it is the root. Start row number count at 2
int rowNumber = 2;
//set the sum to the value of the root.
int sum = list[0];
//selected index begins at the root, index 0
int selectedIndex = 0;
for (int j = 1; j < list.length; j=j+rowNumber)
{
// for every iteration the right child is found by adding the current selected index by z. What is z?
// the left child is of course found in the index -1 of the right child.
// z is the amount of of elements in the triangle's row. Row 3 has 3 elements, 4 has 4, etc.
// For exmaple, if the selectedIndex is index 4, its right child can be found by adding the index to the next row element count.
// 4 + 4 = 8 the right child is in index 8 and left is in index 7
int rightChildIndex = selectedIndex + rowNumber;
int leftChildIndex = selectedIndex + rowNumber - 1;
//set the appropriate index for the greater child's index
selectedIndex = list[rightChildIndex] >= list[leftChildIndex] ? rightChildIndex : leftChildIndex;
//increment the sum of the path
sum = sum + list[selectedIndex];
System.out.println(selectedIndex);
//increment the row number
rowNumber++;
}
return sum;
}
}
本质上，我的算法通过添加整数字符串来工作从文本文件到数组。当然，第一个选择的索引是根节点。要找到合适的孩子，我将所选索引加到下一行的长度，然后减去1以找到左边的孩子索引。
Essentially, my algorithm works by adding the string of ints from the text file into an array. The first selected index is of course the root node. To find the right child I add the selected index by the next row's length and subtract by 1 to find the left child index.
有什么想法吗？
推荐答案
此算法使用了错误的逻辑。在这种情况下，您的算法有效是因为它具有使您的算法有效所需的属性，对于其他输入，显然不是这种情况。例如，考虑以下（极端）示例：
This algorithm uses the wrong logic. In this case your algorithm works because it has the required properties to make your algorithm work, for other inputs this obviously not the case. For example consider the following (extreme) example:
1
1 0
0 0 9
您的算法的工作原理是始终选择总和较大的子代，因此在这种情况下，您的算法会导致路径 {1，1，0} ，而正确的算法将导致 {1，0，9}
Your algorithm works by simply always selecting the child with the larger sum, so in this case your algorithm would result in the path {1 , 1 , 0}, while the correct algorithm would result in {1 , 0 , 9}.
正确的算法将需要遍历树并搜索所有路径，以找到正确的解决方案：
The correct algorithm would require to traverse the tree and search all paths in order to find the correct solution:
int findSum(int[] tree , int at_node){
if(at_node >= length(tree))
return 0 //end of the tree, quit recursive search
//maximum-path including node is the path with the greatest sum that includes either the left or right child of the node.
return max(findSum(tree , leftChild(at_node)) ,
findSum(tree , rightChild(at_node)) + tree[at_node]
}
正如@JohnBollinger提到的那样：
这种自上而下的方法非常简单，但是却要提高效率，这是一种效率更高，效率也更高的解决方案，它仅精确遍历每个节点一次。在上述算法中，代表每个节点被访问时间的树看起来像帕斯卡三角形，因此进行 2 ^ height 数组查找。自上而下的方法只需要 height + height-1 + ... + 1 查找。
As @JohnBollinger mentioned:
This top-to-bottom-approach is pretty simple. But on cost of efficiency. A more efficient, but also more efficient solution that only traverses each node exactly once. In the above stated algorithm a tree that represents the time each node was visited would look like a pascal's triangle, thus making 2 ^ height array-lookups. The bottom-top approach would only require height + height - 1 + ... + 1 lookups.
int findSumBottomTop(int[] tree , int height){
//initialize counter for previous level
int[] sums = new int[height + 1]
fill(sums , 0)
//counter for the level counts down to 1 (note that this variable is not 0-based!!!)
int lvl = height
//counter for nodes remaining on the current level (0-based)
int remaining_in_lvl = lvl - 1
//maximum-paths for each node on the current level
int[] next_level = new int[lvl]
//iterate over all nodes of the tree
for(int node = length(tree) - 1; node > -1 ; node--){
int left_max_path = sums[remaining_in_lvl]
int right_max_path = sums[remaining_in_lvl + 1]
next_level[remaining_in_lvl] = max(right_max_path , left_max_path) + tree[node]
//decrement counter for remaining nodes
remaining_in_lvl -= 1
if(remaining_in_lvl == -1){
//end of a level was encountered --> continue with lvl = lvl - 1
lvl--
//update to match length of next
remaining_in_lvl = lvl - 1
//setup maximum-path counters for next level
sums = next_level
next_level = new int[sums.length - 1]
}
//there is exactly one sum remaining, which is the sum of the maximum-path
return sums[0];
}
其基本概念如下：
Consider this example tree:
0 ^ 6
0 1 | 3 6
0 1 2 | 1 3 5
0 1 2 3 | 0 1 2 3
0 0 0 0 0
tree traversal sums
总和将是每个级别产生的总和的值。我们仅从底部开始搜索，然后搜索一个级别中每个节点到底部的最大路径。这将是左子节点的最大路径和右子节点的最大路径的最大值加上节点的值。
sums would be the values of sums that would be produced for each level. We simply start searching at the bottom and searching the maximum-path from each node in a level to the bottom. This would be the maximum of the maximum-path of the left child and the maximum-path of the right child + the value of the node.
这篇关于三角拼图：从顶部到底部查找最大总数，从顶部开始移动到相邻数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
