0

我正在研究 Euler 问题项目，但我对问题 11 的解决方案并不满意。有没有一种方法可以用更少的步骤或更快速地遍历矩阵？或者一般来说，有没有更好的方法来解决它？

numbers.txt 是问题 11 中给出的数字矩阵。

http://projecteuler.net/problem=11

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;


public class Project {

    public static void main(String[] args){
        int [][] matrix = new int [20][20];
        populateMatrix(matrix, "numbers.txt");
        System.out.println( greatestProduct(matrix) );
    }
    public static long greatestProduct(int [][] matrix){
        final int NUMBER = 4; 
        final int LIMIT = matrix.length - NUMBER;
        long max = 0;

        for(int i= 0; i < matrix.length; i++){
            for(int j= 0; j <= LIMIT; j++){
                long diagTrack = 1, diagTrack2 = 1, horTrack = 1, horTrack2 = 1;
                int y = j;
                int x = i;
                int r = matrix.length-i-1;
                for(int index =0; index<NUMBER; index++){
                    if(i <= LIMIT){
                        diagTrack *= matrix[x][y];
                        diagTrack2*= matrix[r][y];
                        x++;
                        r--;
                    }
                    horTrack *= matrix[i][y];
                    horTrack2*= matrix[y][i];
                    y++;
                }
                if(max < diagTrack) max = diagTrack;
                if(max < diagTrack2) max = diagTrack2;
                if(max < horTrack) max= horTrack;
                if(max < horTrack2) max = horTrack2;
            }
        }
        return max;     
    }

    public static void populateMatrix(int [][] matrix, String fileName){
        File file = new File(fileName);

        try {

            Scanner scanner = new Scanner(file);

            for(int i= 0; scanner.hasNextLine(); i++) {
                String line[] = ( (String) scanner.nextLine() ).split(" ");
                for(int j= 0; j < line.length; j++)
                    matrix[i][j]= Integer.parseInt(line[j].trim() );
            }
            scanner.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }
}
4

1 回答 1

0

我能想到的一个技巧是使用事实，如果你有 a,b,c,d,e,f 你可以通过

val1 = a*b*c*d
val2 = val1*e/a
val3 = val2*f/b

但由于除法非常昂贵，我认为这甚至比 2 次乘法还要糟糕。可能还有其他一些超级技巧会使代码变得更加复杂。例如。

If a>e than a*b*c*d > b*c*d*e

但这只是复杂性过大。让我们假设由于某种原因乘法非常慢。这将不是通过记忆和表达来实现的。

a*b*c*d =  multiply(a,b)*multiply(c,d)

最后，我认为实际上乘法与存储一样快，然后再从中读取（如果不是更快），这意味着您的方法与其他任何方法一样好，但最重要的是它可以轻松实现这种幼稚的解决方案.

于 2012-12-23T18:48:00.430 回答