带有质数检查的三角形中的Javascript最大路径总和 [英] Javascript maximum path sum in a triangle with prime number check
问题描述
我被赋予了以下算法任务：
您将在下面输入一个三角形，并且需要根据以下给定规则找到最大的数字总和；
您将从顶部开始，然后向下移动到下面的相邻数字。
只允许您只能向下走对角线。
您只能走过非主要数字。
您必须到达
1
8 4
2 6 9
8 5 9 3
如您所见，这条路径符合NOT PRIME规则NUMBERS; 1> 8> 6> 9，1> 4> 6> 9，1> 4> 9> 9 1 + 8 + 6 + 9 =24。如您所见，1、8、6、9都不是主要数字，并且行走
根据上述规则，以下输入项的最大和是多少？这意味着请将此金字塔作为实现的输入（直接在代码内部作为文件或常量）并使用它来解决。
215
193124
117237442
218935347235
320804522417345345
229601723835835133124
248202277 433207263257
359464464504528516716871871182
461441426456656863560380380171923
381381573573533447447632387176975975449
223711445 645245543931931532937541444
330131333928377377733017778839839168197197
131131522137217217224291413528520520227229928
223626034638839839 053 627 310 713 999 629 817 410 121
924 622 911 233 325 139 721 218 253 223 107 233 230 124 233 233
请注意，每个节点都有这里只有两个孩子（最底层的孩子除外）。例如，您可以从215走到124（因为193是素数），然后从124走到237或442。从124您不能走到117，因为它不是124的直接子代。
const isNotPrime =（num）=> {
for（let i = 2; i< = Math.sqrt（num）; i ++）{
if（num％i === 0）返回true;
}
返回false；
}
函数maximumTrianglePathSum（triangle）{
函数distilLastLine（）{
让lastLine = triangle.pop（），
aboveLine = triangle.pop（）
for（让i = 0; i< aboveLine.length; i ++）
if（isNotPrime（lastLine [i]）&& isNotPrime（lastLine [i + 1 ]））{$ Line $ [i] = Math.max（$ line $ [i] + lastLine [i]，bline $ i
[i] + lasti [i + 1]
）
}否则if（isNotPrime（lastLine [i]）&&！isNotPrime（lastLine [i + 1]））{
aboveLine [i] = aboveLine [i] + lastLine [i]
}否则if（！isNotPrime（lastLine [i]）&& isNotPrime（lastLine [i + 1]））{
aboveLine [i] = aboveLine [i] + lastLine [i + 1 ]
}
triangle.push（aboveLine）
}
do {
distilLastLine（）
}而（triangle.length> 1）
return triangle [0] [0]
}
//测试
const myArray = [[1]，
[8，4]，
[2，6，9]，
[8，5，9，3]] b $ b让theTriangle = [[215]，
[193，124]，
[117 ，237、442]，
[218、935、347、235]，
[320、804、522、417、345]，
[229、601、723、835、133 ，124]，
[248、202、277、433、207、263、257]，
[359、464、504、528、516、716、871、182]，
[461，441，426，656，863，560，380，171，923]，
[381，348，573，533，447，632，387，176，975，449]，
[223、711、445、645、245、543、931、532、937、541、444]，
[330、131、333、928、377、733、17、778、839、839、168、197 ，197]，
[131，171，522，137，217，224，291，413，528，520，227，229，928]，
[223，626，34，683，839 ，53、627、310、713、999、629、817、410、121]，
[924、622、911、233、325、139、721、218、253、223、107、233、230 ，124，233]]
缺点ole.log（maximumTrianglePathSum（myArray））
console.log（maximumTrianglePathSum（theTriangle））
因此，实际上在第一个示例中，它打印的是23，而不是24，最大路径是24。
有人可以帮我看一下代码，看看是什么问题。
const isPrime =（num） => {for（let i = 2; i * i< = num; i ++）{如果（num％i === 0）返回false; } return num！== 1;}函数maximumTrianglePathSum（triangle）{if（triangle === undefined || triangle.length === 0 || triangle [0] .length === 0 || isPrime（triangle [0 ] [0]））{返回0；让sum_values = createEmptyTriangleStructure（triangle）; for（let k = triangle.length-1; k> = 0;-k）{让currentLine = triangle [k]; for（let i = 0; i< currentLine.length; i ++）{let curr_value = currentLine [i]; if（isPrime（curr_value））{sum_values [k] [i] = 0; }否则if（k === triangle.length-1）{sum_values [k] [i] = currentLine [i]; } else {if（i！== 0）{sum_values [k] [i] = Math.max（sum_values [k] [i]，curr_value + sum_values [k +1] [i-1]）; // //左对角线} sum_values [k] [i] = Math.max（sum_values [k] [i]，curr_value + Math.max（sum_values [k +1] [i]，sum_values [k +1] [i + 1]）））; //检查向下的值以及右下的对角线}}}返回sum_values [0] [0];}函数createEmptyTriangleStructure（triangle）{let sum = []; for（let i = 0; i< triangle.length; ++ i）{sum [i] = []; for（let j = 0; j< triangle [i] .length; ++ j）{sum [i] [j] = 0; }}返回总和；} const myArray = [[1]，[8，4]，[2，6，9]，[8，5，9，3]];让theTriangle = [[215]，[193， 124]，[117、237、442]，[218、935、347、235]，[320、804、522、417、345]，[229、601、723、835、133、124]，[248， 202、277、433、207、263、257]，[359、464、504、528、516、716、871、182]，[461、441、426、656、863、560、380、171、923] ，[381、348、573、533、447、632、387、176、975、449]，[223、711、445、645、245、543、931、532、937、541、444]，[330， 131、333、928、377、733、17、778、839、839、168、197、197]，[131、171、522、137、217、224、291、413、528、520、227、229、928] ，[223，6 26、34、683、839、53、627、310、713、999、629、817、410、121]，[924、622、911、233、325、139、721、218、253、223、107， 233，230，124，233]]; console.log（maximumTrianglePathSum（myArray））; console.log（maximumTrianglePathSum（theTriangle））;
div>
- 您的代码有很多问题。所以我改变了很多事情，我将尝试解释我在这里所做的事情。
-
isPrime（）检查数字是否为质数（请注意1> createEmptyTriangleStructure（）。
- 请参阅第一个
if条件，该条件可以处理许多极端情况。在这种情况下，如果第一行的第一个数字不是素数，则由于您从顶部开始，我们将返回0>，并希望使用非素数。
- 现在，我们创建一个
sum_values数组，该数组将存储每一行的总和。此数组的结构与triangle相同，所有位置都在 - 请参阅第一个
- 现在，我们将三角形从底部循环到顶部（这是您的想法）。
- 如果我们在三角形行中遇到素数，我们将该位置设置为
0c $ c> sum_values ，因为我们不能从那里移到下面。 - 如果我们要遍历三角形的最后一行，即
else if（k === triangle.length-1），然后按原样设置它们，因为在此之下没有行。 - 最后，您被允许进行3步=> 左下（对角线），下，右下（对角线） =>
i-1，i，i + 1。 -
因此，
[k + 1] [i-1]在左下方，[k +1] [i]向下[ k + 1] [i + 1]在右下方。 -
因此，最后，我们在所有这些值中采用
max的值，并将其设置为当前位置的值[k] [i]。 -
最后，我们返回
[0] [0]是最终值。这是一个经典的动态编程问题。 -
可以在空间上进一步优化。当前的空间复杂度为 O（n ^ 2），但我们可以将其降低为 O（n），我将其留给您练习。
I was given this algorithm task:
You will have a triangle input below and you need to find the maximum sum of the numbers according to given rules below;
You will start from the top and move downwards to an adjacent number as in below.
You are only allowed to walk downwards and diagonally.
You can only walk over NON PRIME NUMBERS.
You have to reach at the end of the pyramid as much as possible.
1
8 4
2 6 9
8 5 9 3
As you can see this has several paths that fits the rule of NOT PRIME NUMBERS; 1>8>6>9, 1>4>6>9, 1>4>9>9 1 + 8 + 6 + 9 = 24. As you see 1, 8, 6, 9 are all NOT PRIME NUMBERS and walking over these yields the maximum sum.
According to above rules what is the maximum sum of below input? It means please take this pyramid as an input (as file or constants directly inside the code) for your implementation and solve by using it.
215
193 124
117 237 442
218 935 347 235
320 804 522 417 345
229 601 723 835 133 124
248 202 277 433 207 263 257
359 464 504 528 516 716 871 182
461 441 426 656 863 560 380 171 923
381 348 573 533 447 632 387 176 975 449
223 711 445 645 245 543 931 532 937 541 444
330 131 333 928 377 733 017 778 839 168 197 197
131 171 522 137 217 224 291 413 528 520 227 229 928
223 626 034 683 839 053 627 310 713 999 629 817 410 121
924 622 911 233 325 139 721 218 253 223 107 233 230 124 233
Note that, each node has only two children here (except the most bottom ones). As an example, you can walk from 215 to 124 (because 193 is a prime) then from 124 to either 237 or 442. From 124 you cannot go to 117 because it’s not a direct child of 124.
const isNotPrime = (num) => {
for (let i = 2; i <= Math.sqrt(num); i++) {
if (num % i === 0) return true;
}
return false;
}
function maximumTrianglePathSum(triangle) {
function distilLastLine() {
let lastLine = triangle.pop(),
aboveLine = triangle.pop()
for (let i = 0; i < aboveLine.length; i++)
if(isNotPrime(lastLine[i]) && isNotPrime(lastLine[i + 1])){
aboveLine[i] = Math.max(
aboveLine[i] + lastLine[i],
aboveLine[i] + lastLine[i + 1]
)
}else if(isNotPrime(lastLine[i]) && !isNotPrime(lastLine[i + 1]) ) {
aboveLine[i] = aboveLine[i] + lastLine[i]
}else if(!isNotPrime(lastLine[i]) && isNotPrime(lastLine[i + 1]) ){
aboveLine[i] = aboveLine[i] + lastLine[i + 1]
}
triangle.push(aboveLine)
}
do {
distilLastLine()
} while (triangle.length > 1)
return triangle[0][0]
}
// testing
const myArray = [[1],
[8, 4],
[2, 6, 9],
[8, 5, 9, 3]]
let theTriangle = [[215],
[193, 124],
[117, 237, 442],
[218, 935, 347, 235],
[320, 804, 522, 417, 345],
[229, 601, 723, 835, 133, 124],
[248, 202, 277, 433, 207, 263, 257],
[359, 464, 504, 528, 516, 716, 871, 182],
[461, 441, 426, 656, 863, 560, 380, 171, 923],
[381, 348, 573, 533, 447, 632, 387, 176, 975, 449],
[223, 711, 445, 645, 245, 543, 931, 532, 937, 541, 444],
[330, 131, 333, 928, 377, 733, 17, 778, 839, 168, 197, 197],
[131, 171, 522, 137, 217, 224, 291, 413, 528, 520, 227, 229, 928],
[223, 626, 34, 683, 839, 53, 627, 310, 713, 999, 629, 817, 410, 121],
[924, 622, 911, 233, 325, 139, 721, 218, 253, 223, 107, 233, 230, 124, 233]]
console.log(maximumTrianglePathSum(myArray))
console.log(maximumTrianglePathSum(theTriangle))
So actually in the first example it prints 23 instead of 24 and the maximum path is 24.
Can somebody help me go through the code and see what's the problem.
const isPrime = (num) => {
for (let i = 2; i*i <= num; i++) {
if (num % i === 0) return false;
}
return num !== 1;
}
function maximumTrianglePathSum(triangle){
if(triangle === undefined || triangle.length === 0 || triangle[0].length === 0 || isPrime(triangle[0][0])){
return 0;
}
let sum_values = createEmptyTriangleStructure(triangle);
for(let k = triangle.length - 1;k >= 0;--k){
let currentLine = triangle[k];
for (let i = 0; i < currentLine.length; i++){
let curr_value = currentLine[i];
if(isPrime(curr_value)){
sum_values[k][i] = 0;
}else if(k === triangle.length - 1){
sum_values[k][i] = currentLine[i];
}else{
if(i !== 0){
sum_values[k][i] = Math.max(sum_values[k][i],curr_value + sum_values[k + 1][i-1]); // left down diagonal
}
sum_values[k][i] = Math.max(sum_values[k][i],curr_value + Math.max(sum_values[k + 1][i],sum_values[k + 1][i + 1]));// check with down value as well as right down diagonal
}
}
}
return sum_values[0][0];
}
function createEmptyTriangleStructure(triangle){
let sum = [];
for(let i=0;i < triangle.length; ++ i){
sum[i] = [];
for(let j = 0;j < triangle[i].length; ++ j){
sum[i][j] = 0;
}
}
return sum;
}
const myArray = [
[1],
[8, 4],
[2, 6, 9],
[8, 5, 9, 3]
];
let theTriangle = [
[215],
[193, 124],
[117, 237, 442],
[218, 935, 347, 235],
[320, 804, 522, 417, 345],
[229, 601, 723, 835, 133, 124],
[248, 202, 277, 433, 207, 263, 257],
[359, 464, 504, 528, 516, 716, 871, 182],
[461, 441, 426, 656, 863, 560, 380, 171, 923],
[381, 348, 573, 533, 447, 632, 387, 176, 975, 449],
[223, 711, 445, 645, 245, 543, 931, 532, 937, 541, 444],
[330, 131, 333, 928, 377, 733, 17, 778, 839, 168, 197, 197],
[131, 171, 522, 137, 217, 224, 291, 413, 528, 520, 227, 229, 928],
[223, 626, 34, 683, 839, 53, 627, 310, 713, 999, 629, 817, 410, 121],
[924, 622, 911, 233, 325, 139, 721, 218, 253, 223, 107, 233, 230, 124, 233]
];
console.log(maximumTrianglePathSum(myArray));
console.log(maximumTrianglePathSum(theTriangle));
- Your code had many issues. So I changed many things and I will try to explain what I am doing here.
isPrime()checks whether a number is prime or not(takes care of1as well).- See the first
ifcondition which handles many corner cases. In that, if the first number of the first row is not prime, we return0since you start from the top and want to walk on non-prime numbers. - Now, we create a
sum_valuesarray which will store sums of each row. The structure of this array is same astrianglewith all locations initialized to0with the help ofcreateEmptyTriangleStructure(). - Now, we loop over your triangle from bottom to top(which was your idea).
- If we come across a prime number in the triangle row, we set that location to
0insum_valuessince we can't move below from there. - If we are going through the last row in the triangle, which is
else if(k === triangle.length - 1), then we set them as is since there is no row below this. - Last, you have been allowed with 3 moves => down left(diagonally) , down , down right(diagonally) =>
i - 1,i,i + 1. So,
[k + 1][i - 1]isdown left,[k + 1][i]isdown,[k + 1][i + 1]isdown right.So, in the end, we take
maxvalues among all these and set it as the value of current location[k][i].In the end, we return
[0][0]which is the final value. This is a classic dynamic programming problem.This can be further optimized in terms of space. Current space complexity is O(n^2) but we can reduce this to O(n) and I leave that as an exercise to you.
这篇关于带有质数检查的三角形中的Javascript最大路径总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
