алгоритм добавления диагоналей на квадратную или прямоугольную матрицу, начиная с правой

Question

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

Примерно так:

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

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