Блог

Я хочу добавить диагонали в квадратную или прямоугольную матрицу, чтобы эмулировать процесс добавления частичных результатов в алгоритм умножения.

Вот так:

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

Мне нужно выполнить это, шаг за шагом, чтобы удовлетворить требованиям онлайн-программы оценки. Я уже выяснил, как получить частичные результаты умножения (числа 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) ; 
newCarry = (partialResult[0][2]   partialResult[1][3]   carry) / 10; 
  

Ну, я застрял в написании двойного вложенного цикла, который должен добавлять эти диагонали, начиная с верхней правой. Справка. Пожалуйста.

В итоге я использовал это (не спрашивайте, почему это преобразует 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] = resu< //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] = resu<//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) amp;amp; (colIndex<=colLimit)){

           diagonal2Acum = partialResult[auxRow  ][colIndex  ];


        }

        if ((colIndex==0)amp;amp;(row==rowLimit)) {

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

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


        }

        else {
        copyDigit=(diagonal2Acum carryDigit);
        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;
     }
  

Предположим, что ваши 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 amp;amp; 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 amp;amp; d2   c < height; c  )
        carry  = partialResult[d2   c][c];
    result[--digit] = carry % 10;
    carry /= 10;
}
  

Примечание: Перенос может быть непустым в конце, что означает еще одну цифру перед первой в результате.