Страница 1 из 1

Задача 3 (Квадрат в квадрате)

СообщениеДобавлено: 04 апр 2015, 10:25
Vladislav_133
Здесь будет обсуждение

Re: Задача 3 (Квадрат в квадрате)

СообщениеДобавлено: 05 апр 2015, 01:55
hardcore_test
Нужно было пройти всю матрицу от начала до конца по столбцам и строкам и найти максимальную сумму элементов стоящих по периметру новой матрицы.
Решал задачку обычным перебором, основные моменты:
Когда считаешь сумму элементов по периметру, то нужно учитывать что крайние элементы входят как в строку, так и в столбец, но тут нужно быть осторожным, если новая матрица равна 1
Самое трудное в этой задаче, на мой взгляд, было решить до какого максимального элемента мы идем, путем экспериментов было установлено, что это n-m+1
Код: Выделить всё
import java.util.Scanner;

public class kvadrat {

   public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();   // размер данной матрицы
      int m = sc.nextInt();   // размер новой матрицы
      int max = 0;         // максимальная сумма элементов по периметру
      int mas[][] = new int[n][n];
      for (int i = 0; i < n; i++)
         for (int j = 0; j < n; j++)
            mas[i][j] = sc.nextInt();
      for (int i = 0; i < n - m + 1; i++)   // перебираем значение по столбцам и строкам   
         for (int j = 0; j < n - m + 1; j++) { // от 0 до n-m+1
            int sum = 0;
            for (int k = i; k < i + m; k++) { // сумма элементов строк
               sum += mas[k][j];
               sum += mas[k][j + m - 1];
            }
            for (int k = j; k < j + m; k++) { // сумма элементов столбцов
               sum += mas[i][k];
               sum += mas[i + m - 1][k];
            }
            sum = sum - mas[i][j] - mas[i + m - 1][j] // убираем из суммы крайние элементы, т.к их считали два раза
                  - mas[i + m - 1][j + m - 1] - mas[i][j + m - 1];
            if (m == 1)   //но если мы уберем крайние элементры при единице, то получим 0
               sum = mas[i][j];
            if (sum > max) { // проверили максимум
               max = sum;
            }
         }
      System.out.println(max);
      sc.close();
   }

}

С подцветкой синтаксиса, тык
Поясню почему при m=1 мы получаем после вычитания 0. Возьмем для примера матрицу 2 на 2:
Код: Выделить всё
10    20
30    15

Если m=2 то по моему алгоритму посчитаем сумму строк 10+30+20+15=75
Сумма столбцов 75+10+20+30+15=150
и вычитаем крайние элементы 150-10-30-15-20=75 все верно
Если m=1, то находим сумму и получаем сумма строк 10+10=20
сумма столбцов 20+10+10=40
и вычли крайние 40-10-10-10-10=0
Поэтому при m=1 задача сводится к нахождению максимума в матрице

Re: Задача 3 (Квадрат в квадрате)

СообщениеДобавлено: 05 апр 2015, 10:54
Vladislav_133
Здесь вся проблема в аккуратности работы с индексами. Это так называемая ошибка "на единицу".

Re: Задача 3 (Квадрат в квадрате)

СообщениеДобавлено: 06 апр 2015, 10:10
Vladislav_133
Приведу программу. Без комментариев.

Подсветка синтаксиса: [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка cpp
#include <stdio.h>
#include <string.h>
#include <math.h>
//--------------------------------------
int n,m,i,j,s,s1,s2,s3,s4,s0,k;
//======================================
int main(){
    int ma[101][101];
    if(scanf("%d",&n)==EOF){
        printf("Error\n"); return 0;
    }
    if(scanf("%d",&m)==EOF){
        printf("Error\n"); return 0;
    }
    if(m>n||n>100||n<=0||m<=0){
        printf("Error\n"); return 0;
    }
//=======================================
    for(i=0; i<n; i++){
        for(j=0; j<n; j++){
            if(scanf("%d",&ma[i][j])==EOF){
                printf("Error\n"); return 0;
            }
        }
    }
//=======================================
    s0=0;s=0;
    for(i=0; i<n-m+1; i++){
        for(j=0; j<n-m+1; j++){
            s1=s2=s3=s4=0;
            for(k=0;   k<m; k++)s1=s1+ma[k+j][i];
            for(k=0; k<m-1; k++)s2=s2+ma[j+m-1][k+i+1];
            for(k=0; k<m-1; k++)s3=s3+ma[k+j][i+m-1];
            for(k=0; k<m-2; k++)s4=s4+ma[j][k+i+1];
            s=s1+s2+s3+s4;
            if(s>s0)s0=s;
        }
    }
    printf("%d\n",s0);
//=======================================
    return 0;
}

 

Re: Задача 3 (Квадрат в квадрате)

СообщениеДобавлено: 08 апр 2015, 20:17
[DD]
Подсветка синтаксиса: (3.php) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка php
  1. <?php
  2. function Out($result){//вывод и завершение
  3.     file_put_contents("./output.txt", $result);
  4.     die();
  5. }
  6. $input = fopen("./input.txt", "r");
  7. $n = trim(fgets($input));
  8. $m = trim(fgets($input));
  9. $data = [];
  10. $max = 0;
  11. while(!feof($input)){
  12.     $line = preg_split("/\s+/", fgets($input), NULL, PREG_SPLIT_NO_EMPTY);
  13.     $data[] = $line;
  14.     $max = max($max, max($line));//пока читали данные до кучи посчитали еще и максимальное в массиве
  15. }
  16. if($m == 1){//если сторона квадрата обхода равна 1 - то сумма будет равна максимальному значению
  17.     Out($max);
  18. }
  19. /**
  20.     максимум равен нулу для того что бы заполнить его первой найденно суммой на тот случай если все
  21.     числа в матрице окажутся отрицательными
  22. */
  23. $max = NULL;
  24. for($i = 0; $i <= $n - $m; $i++){
  25.     for($k = 0; $k <= $n - $m; $k++){
  26.         $lastRow = $m - 1 + $i;//получаем индекс последней строки в массиве обхода
  27.         $lastCol = $m - 1 + $k;//ну и номер столбца тоже не забудем
  28.         //считаем сумму угловых элементов
  29.         $sum = $data[$i][$k] + $data[$lastRow][$lastCol] + $data[$lastRow][$k] + $data[$i][$lastCol];
  30.         for($j = 1; $j < $m - 1; $j++){
  31.             $sum += $data[$i+$j][$k];//левый столбец
  32.             $sum += $data[$i][$k + $j];//верхняя строка
  33.             $sum += $data[$lastRow][$lastCol - $j];//нижняя строка
  34.             $sum += $data[$lastRow - $j][$lastCol];//правый столбец
  35.         }
  36.         if(NULL === $max){
  37.             $max = $sum;//заполняем не нулом
  38.         }
  39.         else{
  40.             $max = max($max, $sum);//избрали максимум
  41.         }
  42.     }
  43. }
  44.  
  45. Out($max);