Вопросы по алгоритмам
pfa:
Код:
import java.util.Random;
/**
* Created by IntelliJ IDEA.
* User: pfa
* Date: 12.01.2009
* Time: 21:28:38
* To change this template use File | Settings | File Templates.
*/
public class MatrixFinder {
public static final int n = 6;
private static int matrix[][] = new int[n][n];
/**
* Заполняем случайно, коэффициент криво взвешен для того, чтобы максимальная сумма
* была не у внешнего периметра исходной матрицы
*/
private static void initMatrix() {
Random rand = new Random();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int randNum = n * 10 / ((Math.abs(n / 2 - i) + Math.abs(n / 2 - j) + 1));
matrix[i][j] = rand.nextInt(randNum);
}
}
}
(Отправлено в: Январь 13, 2009, 00:01:16)
Код:
/**
* Вывести матрицу на стандартный вывод
*/
private static void printMatrix() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.format("%02d ", matrix[i][j]);
}
System.out.println("");
}
}
/**
* Считает сумму ряда от элемента startColumn до (размер-startColumn)
* @param rowNumber номер ряда, который суммируем
* @param startColumn начальный столбец
* @return сумму
*/
private static int countRowSum(int rowNumber, int startColumn) {
int sum = 0;
for (int i = startColumn; i < n - startColumn; i++) {
sum += matrix[rowNumber][i];
}
return sum;
}
/**
* Считает сумму элементов на периметре заданной подматрицы
* @param submatrixNumber номер подматрицы от 0
* @return сумму
*/
private static int countPerimeterSum(int submatrixNumber) {
int sum = 0;
final int endElement = n - submatrixNumber-1;
sum += countRowSum(submatrixNumber, submatrixNumber);
sum += countRowSum(endElement, submatrixNumber);
for (int i = submatrixNumber+1; i < endElement; i++) {
sum += matrix[i][submatrixNumber];
sum += matrix[i][endElement];
}
return sum;
}
(Отправлено в: Январь 13, 2009, 00:02:37)
Код:
/**
* Ищет номер подматрицы с максимальной суммой элементов на периметре
* @return
*/
private static int findMaxSubmatrix() {
int maxSum = 0;
int maxNumber = -1;
for (int i = 0; i <= n / 2; i++) {
int curSum;
if (i == n / 2 && n % 2 == 1) {
curSum = matrix[i][i];
} else {
curSum = countPerimeterSum(i);
}
System.out.println("i=" + i + " sum=" + curSum);
if (curSum > maxSum) {
maxSum = curSum;
maxNumber = i;
}
}
System.out.println("Max sum: " + maxSum);
return maxNumber;
}
/**
* Считает сумму всех элементов подматрицы
* @param maxSubmatrixNum номер подматрицы
* @return
*/
private static int countSubmatrixSum(int maxSubmatrixNum) {
int sum = 0;
for (int i = maxSubmatrixNum; i < n - maxSubmatrixNum; i++) {
sum += countRowSum(i, maxSubmatrixNum);
}
return sum;
}
public static void main(String[] args) {
initMatrix();
printMatrix();
int maxSubmatrixNum = findMaxSubmatrix();
int result = countSubmatrixSum(maxSubmatrixNum);
System.out.println("Result: " + result);
}
}
(Отправлено в: Январь 13, 2009, 00:02:53)
Форум глючит и не дает за раз отправить - сорри.
(Отправлено в: Январь 13, 2009, 00:03:12)
Ах, да. Думаю, очевидно, что решение уважаемого artem90 неоптимально хотя бы потому, что в силу граничных условий выделения подматриц нам не нужно хранить все 4 угла - достаточно и одного.
Артем:
Цитата: pfa от Январь 13, 2009, 01:05:50
Думаю, очевидно, что решение уважаемого artem90 неоптимально хотя бы потому, что в силу граничных условий выделения подматриц нам не нужно хранить все 4 угла - достаточно и одного.
Да, действительно протупил :(
Alder:
Off-Topic - помечено автором как "не соответствует обсуждаемой теме"
Цитата: pfa от Январь 13, 2009, 01:05:50
Форум глючит и не дает за раз отправить - сорри.
Проверил. Да, при постинге полного листинга анализатор тегов наверное где-то зацикливается. Если постить частями - нормально.
ff000:
Объясните пожалуйста зачем в решении снау в методы простых итераций нужна матрица якоби?
EvilMax:
По-идее, при решении не нужна. Метод похож на метод решения одного уравнения, т.е. фактически идут последовательные приближения. Но есть нюанс. Сходимость решения проверяется по максимальному по модулю знаению частной производной fk по xi. Но так как для этого необходимо вычислить все частные производные, то это фактически эквивалентно расчёту Якобиана.
Навигация