将数组中的负索引转换为正索引(三项三角形) [英] Convert negative index to positive index in an array (Trinomial Triangle)

问题描述

我正在尝试找到三项式系数，并且我想避免在数组中使用负索引.在某些情况下，i或j将变为负数，并将返回数组超出范围的错误.无论如何，我可以将负索引中包含的数组镜像为正索引吗?

以下是递归公式:

注意:下面的代码从中间索引 0 向右遍历数组.

 公共类ClassNameHere {公共静态void main(String [] args){int n = Integer.parseInt(args [0]);int k = Integer.parseInt(args [1]);long [] [] DP =新的long [n + 1] [k +1];DP [0] [0] = 1；for(int i = 0; i< = n; i ++){for(int j = 0; j< = Math.min(i，k); j ++){if(i == j ||(((j == 0)& i< 2))DP [i] [j] = 1;否则(j< -i){DP [i] [j] = 0;} else DP [i] [j] = DP [i-1] [j];}}System.out.println(DP [n] [k]);}} 

现在我可以使用我的代码将条款从 T(0，0)转换为 T(1，0)，但无法继续通过通过添加 T(1,0)+ T(1，1)+ T(1，2)向前添加T(2，0).当我尝试实现 DP [i] [j] = DP [i-1] [j-1] + DP [i-1] [j] + DP [i-1] [j + 1] ，它再次返回 ArrayIndexOutOfBoundsException ..我认为上述语句 ^ 的实现存在问题.有关如何进行此操作的任何建议?

解决方案

我找到了原因.

这可以通过在2D数组中初始化正确的长度来完成.

  long [] [] tri =新的long [n + 1] [k + n + 1]; 

并使用Math.abs()处理j索引将流向负索引的实例.

  tri [i] [j] = tri [i-1] [Math.abs(j-1)] + tri [i-1] [j] + tri [i-1] [j +1]; 

I am trying to find trinomial coefficients and I want to avoid using negative index in my array. There will be instances whereby i or j will become negative and will return array out of bounds error. Is there anyway I can mirror the array contained in the negative indexes to a positive index?

Here’s the recursive formula: Recursion Formula

I recognize that T(0, -1) = T(0, 1) but how do I implement it?

example:

row 0: T(0, 0) = 1 , T(0, 1) = 0 ...

row 1: T(1, 0) = T(0, -1) + T(0, 0) + T(0, 1) , T(2, 0) ...

The trinomial coefficient T(n,k) is the coefficient of x^(n+k) in the expansion of (1+x+x^2)^n.

Trinomial triangle (middle index is 0, negative on the left of 0, positive on the right of 0):

Note: The code below iterates through the array from middle index 0 to the right.

public class ClassNameHere {
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        int k = Integer.parseInt(args[1]);
        long[][] DP = new long[n + 1][k + 1];
        DP[0][0] = 1;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= Math.min(i, k); j++) {
                if (i == j || ((j == 0) && i < 2)) DP[i][j] = 1;
                else if (j < -i) {
                    DP[i][j] = 0;
                } else DP[i][j] = DP[i - 1][j];
            }
        }
        System.out.println(DP[n][k]);
    }
}

Now I am able to get the terms from T(0, 0) to T(1, 0) with my code but unable to continue past T(2, 0) onwards by adding T(1,0) + T(1, 1) + T(1, 2). When I tried to implement DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j] + DP[i - 1][j + 1], it returns ArrayIndexOutOfBoundsException again.. I think that something is wrong with the implementation of the above statement ^. Any suggestions on how to go on with this?

解决方案

I have found the cause.

It can be done by initializing the correct length in the 2D array.

long[][] tri = new long[n + 1][k + n + 1];

and using Math.abs() to handle instances where j index will flow to negative indices.

tri[i][j] = tri[i - 1][Math.abs(j - 1)] + tri[i - 1][j] + tri[i - 1][j + 1];

这篇关于将数组中的负索引转换为正索引(三项三角形)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！