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

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]; 

下一步:

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;
     }