在正方形或矩形矩阵上添加对角线的算法，从右侧开始

Question

我想在正方形或矩形矩阵中添加对角线，以模拟在乘法算法中添加部分结果的过程。

像这样：

     2412
   x 3231
---------
     2412
    7236
   4824
+ 7236
---------
  7793172

我需要一步一步地运行它，以满足在线判断程序的要求。我已经弄清楚如何获得乘法的部分结果（humbers 2412、7236、4824、7236），并将它们放在方阵上。

我意识到我可以通过考虑正方形或矩形来获得该矩阵的加法结果：

2 4 1 2
7 2 3 6
4 8 2 4
7 2 3 6

并通过添加每个对角线（从右上角开始）并考虑加法的进位并使用辅助来获得加法的结果与 number_of_digits_in_operand_a + number_of_digits_in_operand_b 具有相同位数的数组（在本例中，操作数 a 为 2412，操作数 b 为 3231）。

例如，数组结果在其最右边的位置应该是：

result[(digits_a+digits_b)-1] = partialResult[0][3]; 

next:

result[digits_a+digits_b]=(partialResult[0][2] + partialResult[1][3] + carry) %10; 
newCarry = (partialResult[0][2] + partialResult[1][3] + carry) / 10; 

好吧，我一直在编写双重嵌套循环，该循环应该从右上角开始添加这些对角线。帮助。请。

Answer 1

我最终使用了这个（不要问为什么它将 BigInteger 转换为 ArrayList，反之亦然，这是一个奇怪的家庭作业要求）。

  public static BigInteger simpleMultiply(BigInteger x, BigInteger y) throws IOException {

        char [] longerNum;
        char [] shorterNum;


        ArrayList<Integer> multResult= new ArrayList<Integer>(2000);

        if(x.compareTo(y)>=0){ // x is a longer/equal num

            longerNum = x.toString().toCharArray();
            shorterNum = y.toString().toCharArray();

        }

       else { //y is a longer num

           longerNum = y.toString().toCharArray();
           shorterNum = x.toString().toCharArray();

       }


       //shorter num equals the number of rows in partial result
       // longer num + 1 equals the number of columns in partial result


        int [][] partialResult = new int [shorterNum.length][longerNum.length+1];

        int pastCarry=0;
        int result=0;
        int carry=0;

        for (int sIndex=(shorterNum.length-1); sIndex>=0; sIndex--){

            pastCarry=0;
            for (int lIndex = (longerNum.length-1); lIndex>=0; lIndex--)
            {
                int sInt = Integer.parseInt(""+shorterNum[sIndex]+"");
                int lInt = Integer.parseInt(""+longerNum[lIndex]+"");

                int product = sInt*lInt;

                if (lIndex==0){

                 result  =  (pastCarry+product)% 10;
                 carry   = (pastCarry+product) /  10;

                 pastCarry = carry;

                 partialResult [sIndex][lIndex+1] = result; //one more column element in partialResult

                 partialResult[sIndex][lIndex] = carry;


               }

                else {

                 result  = (pastCarry+product) % 10;
                 carry   = (pastCarry+product) /  10;

                 pastCarry = carry;

                 partialResult [sIndex][lIndex+1] = result;//one more column element in partialResult


                }

            }
        }
            for (int i=0; i<partialResult.length;i++)
                for (int j=0; j<partialResult[0].length;j++)
                {

                      System.out.print(partialResult[i][j] + " ");
                      if (j==partialResult[0].length-1){System.out.println();}
                }

        int auxColumn=0;
        int diagonalAcum=0;
        //add diagonals

        int copyDigit=0;
        int carryDigit=0;

        int lastCarry=0;



     rowCycle:
     for (int column=partialResult[0].length-1; column>=0; column--){

          diagonalAcum=0; //carryDigit=0;
          diagonalAcum+=carryDigit;
          auxColumn=column;

          for (int row=0; row<partialResult.length; row++){

              if (auxColumn+1 ==partialResult[0].length){

                  diagonalAcum+=partialResult[row][auxColumn++];

                   copyDigit=diagonalAcum % 10;
                   carryDigit=diagonalAcum / 10;

                   multResult.add(copyDigit);

                   continue rowCycle;

              }
              diagonalAcum+=partialResult[row][auxColumn++];
          } //end row cycle

          copyDigit= diagonalAcum % 10;
          carryDigit=diagonalAcum / 10;
          multResult.add(copyDigit);

          if(column==0){
              lastCarry = carryDigit;
          }
       }

     carryDigit=0; //reset

     int diagonal2Acum=0;
    // diagonal2Acum +=lastCarry;
    int auxRow;

    int diagCarry=0;

    int rowLimit=partialResult.length-1;
    int colLimit=partialResult[0].length-1;

    int initialRow=1;
    int colIndex=0;


    for (int row=initialRow;row<=rowLimit;row++){

        diagonal2Acum=0;
        diagonal2Acum +=lastCarry;
        lastCarry=0;

        auxRow = row;
        colIndex=0;

       // partialResult[auxRow][]
        while ((auxRow<=rowLimit) && (colIndex<=colLimit)){

           diagonal2Acum+= partialResult[auxRow++][colIndex++];


        }

        if ((colIndex==0)&&(row==rowLimit)) {

            copyDigit=(diagonal2Acum+carryDigit)%10;
            carryDigit=(diagonal2Acum+carryDigit)/10;

                multResult.add(copyDigit);
            multResult.add(carryDigit);


        }

        else {
        copyDigit=(diagonal2Acum+carryDigit)%10;
        carryDigit=(diagonal2Acum+carryDigit)/10;

        multResult.add(copyDigit);
        }


     } // end row for


     StringBuilder appended = new StringBuilder();

     for (int i=multResult.size()-1;i>=0;i--){

         appended.append(multResult.get(i));

     }

       System.out.println("result is " + appended.toString());

       BigInteger the_result1 = new BigInteger(appended.toString());
       return the_result1;
     }

Answer 2

假设您的 partialResult 尺寸为 width 和 height，您可以通过以下两个循环添加（请参阅此处 实际操作）：

int digit = width + height - 1;
int carry = 0;

for (int d1 = width - 1; d1 >= 0; d1--) {
    for (int r = 0; r < height && d1 + r < width; r++)
        carry += partialResult[r][d1 + r];
    result[--digit] = carry % 10;
    carry /= 10;
}

for (int d2 = 1; d2 < height; d2++) {
    for (int c = 0; c < width && d2 + c < height; c++)
        carry += partialResult[d2 + c][c];
    result[--digit] = carry % 10;
    carry /= 10;
}

注意：末尾进位可能不为空，这意味着结果中第一个数字之前还有一个数字。