A704

07/07/2016 by Игорь Варламов

Задача: Даны квадратные матрицы [latex]A[/latex], [latex]B[/latex] и [latex]C[/latex] порядка [latex]n[/latex]. Получить матрицу [latex](A+B)C.[/latex]

Тесты:

n	A	B	C	Output
3	1 2 3 4 5 6 7 8 9	0 1 0 0 0 0 0 0 0	1 0 0 0 1 0 0 0 1	1 3 3 4 5 6 7 8 9
2	4 6 12 7	3 2 1 1	7 3 2 8	65 85 107 103
3	3 4 1 1 2 1 5 6 7	1 3 1 2 4 5 6 5 1	1 1 0 5 8 1 2 3 2	43 66 11 45 69 18 82 123 27

Код:

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone{
	public static void main (String[] args) throws java.lang.Exception{
		int n,i=0,j=0,k,p;
		Scanner x = new Scanner(System.in);
		n = x.nextInt();
		int [][] a;
		a = new int[n][n];
		int [][] b;
		b = new int[n][n];
		int [][] c;
		c = new int[n][n];
		int [][] d;
		d = new int[n][n];
		d[i][j]=0;
		for( i=0 ; i<n ; i++ ){
			for( j=0 ; j<n ; j++ ){ 
				a[i][j]=x.nextInt();
			}
		}
		for(  i=0 ; i<n ; i++ ){
			for(  j=0 ; j<n ; j++ ){
				b[i][j]=x.nextInt();
				a[i][j] += b[i][j];
			}
		}
		for(  i=0 ; i<n ; i++ ){
			for(  j=0 ; j<n ; j++ ){
				c[i][j]=x.nextInt();
			}
		}
		for(  i=0 ; i<n ; i++ ){		
			for(  j=0 ; j<n ; j++ ){			
				for(  k=0 ; k<n ; k++ ){			
					d[i][j] += a[i][k] * c[k][j];
				}
			}
		}
		for ( k = 0; k < n; k++) {
    		for ( p = 0; p < n; p++) {
        		System.out.print(d[k][p] + "\t");
    		}
			System.out.println();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone{

public static void main (String[] args) throws java.lang.Exception{

int n,i=0,j=0,k,p;

Scanner x = new Scanner(System.in);

n = x.nextInt();

int [][] a;

a = new int[n][n];

int [][] b;

b = new int[n][n];

int [][] c;

c = new int[n][n];

int [][] d;

d = new int[n][n];

d[i][j]=0;

for( i=0 ; i<n ; i++ ){

for( j=0 ; j<n ; j++ ){

a[i][j]=x.nextInt();

}

for( i=0 ; i<n ; i++ ){

for( j=0 ; j<n ; j++ ){

b[i][j]=x.nextInt();

a[i][j] += b[i][j];

}

for( i=0 ; i<n ; i++ ){

for( j=0 ; j<n ; j++ ){

c[i][j]=x.nextInt();

}

for( i=0 ; i<n ; i++ ){

for( j=0 ; j<n ; j++ ){

for( k=0 ; k<n ; k++ ){

d[i][j] += a[i][k] * c[k][j];

}

for ( k = 0; k < n; k++) {

for ( p = 0; p < n; p++) {

System.out.print(d[k][p] + "\t");

}

System.out.println();

}

Решение:
В первом цикле читаем матрицу [latex]A[/latex]. Во втором цикле читаем матрицу [latex]B[/latex] и сразу прибавляем ее к матрице [latex]A[/latex], получаем сумму матриц. В третьем цикле умножаем сумму матриц [latex]A[/latex] и [latex]B[/latex] на матрицу [latex]C[/latex] и выводим результат.

Код на Ideone

A406

06/07/2016 by Дарья Пиндус

Задача

С помощью $x_{ij}, i=1,2; j=1,\ldots,n.$ – действительной матрицы на плоскости задано n точек так, что $x_{1j}, x_{2j}$ – координаты $j$ – точки. Точки попарно соединены отрезками. Найти длину наибольшего отрезка.

Тест

n	Матрица $x_{ij}, i=1,2.$	Длина наибольшего отрезка	Комментарий
3	2 8 4 9 1 5	10	Пройдено
4	6 14 2 1 9 3 8 0	13.3417	Пройдено
5	1 8 4 3 7 2 9 5 0 11	11.7047	Пройдено

Код программы:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class A406 {
    public static void main(String[] args) {
        int[][] matrix;
        double maxDistance = 0;
        double distance;
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        matrix = new int[2][m];
 
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < m; j++)
                matrix[i][j] = scanner.nextInt();
 
        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j < m; j++) {
                distance = Math.sqrt((matrix[0][j] - matrix[0][i]) * (matrix[0][j] - matrix[0][i]) + (matrix[1][j] - matrix[1][i]) * (matrix[1][j] - matrix[1][i]));
                if (distance > maxDistance) {
                    maxDistance = distance;
                }
            }
        }
 
        System.out.println(maxDistance);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class A406 {

public static void main(String[] args) {

int[][] matrix;

double maxDistance = 0;

double distance;

Scanner scanner = new Scanner(System.in);

int m = scanner.nextInt();

matrix = new int[2][m];

for (int i = 0; i < 2; i++)

for (int j = 0; j < m; j++)

matrix[i][j] = scanner.nextInt();

for (int i = 0; i < m; i++) {

for (int j = i + 1; j < m; j++) {

distance = Math.sqrt((matrix[0][j] - matrix[0][i]) * (matrix[0][j] - matrix[0][i]) + (matrix[1][j] - matrix[1][i]) * (matrix[1][j] - matrix[1][i]));

if (distance > maxDistance) {

maxDistance = distance;

}

System.out.println(maxDistance);

}

Ход решения:

Вводим матрицу.
Находим длину наибольшего отрезка.
С помощью вложенных циклов мы находим длины всех отрезков по формуле
$AB=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}, A(x_{1},y_{1}), B(x_{2},y_{2}).$
По алгоритму нахождения максимума находим длину наибольшего отрезка.
Выводим матрицу.
Выводим длину наибольшего отрезка.
Ссылка на код

A401. Удаление строки и столбца из матрицы

05/07/2016 by Сережа Туромша

Условие задачи:

Дана действительная квадратная матрица порядка $n$ , натуральные числа $i, j \left(1\leq i\leq n, 1\leq j\leq n \right)$ . Из матрицы удалить $i$ -строку и $j$ -столбец.

Тесты:

$n$	Матрица.	$i$	$j$	Полученная Матрица
4	10 10 20 20 30 30 40 40 50 50 60 60 70 70 80 80	1	1	30 40 40 50 60 60 70 80 80
5	1.1 1.1 1.1 1.1 1.1 2.2 2.2 2.2 2.2 2.2 3.3 3.3 3.3 3.3 3.3 4.4 4.4 4.4 4.4 4.4 5.5 5.5 5.5 5.5 5.5	2	3	1.1 1.1 1.1 1.1 3.3 3.3 3.3 3.3 4.4 4.4 4.4 4.4 5.5 5.5 5.5 5.5
3	2 -2 2 3 -3 3 5 -5 5	1	3	3 -3 4 -4

Код программы:

import java.util.*;
import java.lang.*;
import java.io.*;
 

class Ideone {
	public static void main (String[] args) {
		Scanner x = new Scanner (System.in);
		int n;
		n = x.nextInt();
		double [][]m = new double[n][n];
		double [][]m1 = new double[n-1][n-1];
		for (int i=0; i<n; i++) {
			for (int j=0; j<n; j++) {
				m[i][j] = x.nextDouble();
			}
		}
		int deli, delj;
		deli = x.nextInt();
		delj = x.nextInt();
		for (int i=0, ln=0; ln<n-1;) {
			if (i!=deli-1) {
				for (int j=0, cn=0; cn<n-1; j++, cn++) {
					if (j==delj-1) j++;
					m1[ln][cn]=m[i][j];
				}
				i++;
				ln++;
			} else i++; 
		}
		m=m1;
		for (int i=0; i<n-1; i++) {
			for (int j=0; j<n-1; j++) {
				System.out.print(m[i][j]+"    ");
			}
			System.out.println();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

Scanner x = new Scanner (System.in);

int n;

n = x.nextInt();

double [][]m = new double[n][n];

double [][]m1 = new double[n-1][n-1];

for (int i=0; i<n; i++) {

for (int j=0; j<n; j++) {

m[i][j] = x.nextDouble();

}

int deli, delj;

deli = x.nextInt();

delj = x.nextInt();

for (int i=0, ln=0; ln<n-1;) {

if (i!=deli-1) {

for (int j=0, cn=0; cn<n-1; j++, cn++) {

if (j==delj-1) j++;

m1[ln][cn]=m[i][j];

}

i++;

ln++;

} else i++;

}

m=m1;

for (int i=0; i<n-1; i++) {

for (int j=0; j<n-1; j++) {

System.out.print(m[i][j]+" ");

}

System.out.println();

}

Алгоритм:

Пользователь вводит порядок матрицы $n$ и её элементы.Затем он вводит $i$ -строку и $j$ -столбец, которые он хочет удалить.
В первом цикле создаем переменную — индекс строки нового массива со значением 0. Проверяем, если указанный нам номер строки совпадает с текущим, то мы переходим на следующую по номеру строку, так как эта строка нам больше не понадобится.
Если не совпадает, во внутреннем цикле создаем переменную — номер столбца нового массива со значением 0. Проверяем или совпадает индекс текущего столбца с индексом указанным нам. Если да, то увеличиваем на 1 индекс нашего столбца ( этим мы «обращаем свое внимание» на следующий столбик, игнорируя этот ).
После этого присваиваем значения текущего индекса строки и столбца, получившимся в ходе циклов,значениям индексов нового массива. С помощью внутреннего цикла заполняем данную строку до конца.
После заполнения увеличиваем на 1 индексы данного и нового массива ( переходим на следующую строку матрицы ). Возвращаемся к условию внешнего цикла и продолжаем заполнять новый массив.
Данному массиву присваиваем новый. В конце выводим полученный массив.

Работающая версия программы на ideone.com

А404

03/07/2016 by Ирина Литвиненко

Условие задачи

Даны натуральные числа [latex]i[/latex], [latex]j[/latex], действительная матрица размера [latex]18 / 24[/latex], [latex]1\leq i\leq j\leq 24[/latex].
Поменять местами в матрице [latex]i[/latex]-й и [latex]j[/latex]-й столбцы.

Входные данные

Вводим матрицу [latex]M[/latex]– строк, [latex]N[/latex]– столбцов. В следующей строке вписываем номера столбцов которые хотим поменять.

Выходные данные

Матрица, в которой поменялись местами столбцы.

Тесты

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

3 6

0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
0 1 5 3 4 2 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

Код программы

import java.util.*;
import java.lang.*;
import java.io.*;

	
class Ideone{
	
	public static final int M = 18;
	public static final int N = 24;


	public static void main (String[] args) throws java.lang.Exception {
		
		double[][] a = new double[M][N];
		
		Scanner in = new Scanner(System.in);
		for(int i = 0; i < M; i++) {
			for(int j = 0; j < N; j++) {
				a[i][j] = in.nextDouble();
			}
		}
		int i , j;
		
		i = in.nextInt();
		j = in.nextInt();
	
		for(int k = 0; k < M; k++){
			double temp = a[k][i-1];
			a[k][i-1] = a[k][j-1];
			a[k][j-1] = temp;
		}
		
		for(int q = 0; q < M; q++){
			for(int z = 0; z < N; z++){
				System.out.print(a[q][z] + ((z == N-1)? "\n": " "));
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone{

public static final int M = 18;

public static final int N = 24;

public static void main (String[] args) throws java.lang.Exception {

double[][] a = new double[M][N];

Scanner in = new Scanner(System.in);

for(int i = 0; i < M; i++) {

for(int j = 0; j < N; j++) {

a[i][j] = in.nextDouble();

}

int i , j;

i = in.nextInt();

j = in.nextInt();

for(int k = 0; k < M; k++){

double temp = a[k][i-1];

a[k][i-1] = a[k][j-1];

a[k][j-1] = temp;

}

for(int q = 0; q < M; q++){

for(int z = 0; z < N; z++){

System.out.print(a[q][z] + ((z == N-1)? "\n": " "));

}

www.ideone.com

Решение

Для задания размера матрицы объявлены константы M и N. В вложенном цикле вводим значения матрицы. Вводим номера столбцов, которые мы хотим переставить. В цикле переставляем местами элементы указанных столбцов. Затем выводим матрицу.

Segmented Array

05/12/2015 by Максим Швандт

Задача

Необходимо реализовать некоторую коллекцию индексированных данных некоторого типа T, выглядящую как несколько необычный массив. Вместо операции присваивания значения элементу массива в нём имеется операция присваивания одинаковых значений всем элементам для некоторого диапазона индексов. Также и операции поиска минимума и максимума должны работать для некоторого диапазона значений индексов.

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

Big array	Small \|T\|	Often				Student
Big array	Small \|T\|	get()	set()	indexOf()	min()/max()	Student
1	0	0	0	1	0	Швандт

Тест

input	output
set 2 2 H	ok
set 3 3 E	ok
set 4 5 L	ok
set 6 6 O	ok
set8 8 W	ok
set 9 9 O	ok
set 10 10 R	ok
set 11 11 L	ok
set 12 12 D	ok
set 13 13 !	ok
set 14 14 !	ok
set 15 15 !	ok
show	segment#0 { null null H E } segment#1 { L L O null } segment#2 { W O R L } segment#3 { D ! ! ! }
exit	N/A

Структура программы

Код программы состоит из следующих элементов, объединенных в пакет odessa.uni.imem.maxim:

Интерфейс SegmentedArray, который описывает заданную функциональность доступа к сегментированному массиву
Класс SegmentedArrayImpl, имплементирует данный интерфейс
Класс SegmentedArrayApp, который имплементирует тестевое приложение, он содержит метод main и вспомогательные методы ввода данных и вывода результата.

Интерфейс SegmentedArray

package odessa.uni.imem.maxim;

public interface SegmentedArray<Comparable>
{
   int indexOf(Comparable value, int fromIndex);
   void set(int fromIndex, int toIndex, Comparable value);
   Comparable min(int fromIndex, int toIndex);
}

package odessa.uni.imem.maxim;

public interface SegmentedArray<Comparable>

{

int indexOf(Comparable value, int fromIndex);

void set(int fromIndex, int toIndex, Comparable value);

Comparable min(int fromIndex, int toIndex);

}

Методы интерфейса:

indexOf — возвращает абсолютный индекс элемента в массиве начиная с заданного индекса.
set — присваивает последовательности элементов массива одно и тоже значение в заданном диапазоне
min — возвращает минимальный элемент в заданном диапазоне

Класс SegmentedArrayImpl

package odessa.uni.imem.maxim;

public class SegmentedArrayImpl<Item extends Comparable<Item>> implements SegmentedArray<Item>
{
   private int size;
   private int segmentSize;
   private Object[][] segments;

   public SegmentedArrayImpl(int aSegmentSize, int aSegmentCount)
   {
      segmentSize = aSegmentSize;
      size = segmentSize * aSegmentCount;

      segments = new Object[aSegmentCount][segmentSize];
   }

   public int indexOf(Item value, int fromIndex)
   {
      if (fromIndex >= size)
      {
         return -1;
      }

      int segmentIndex = findSegmentIndex(fromIndex);
      int indexInSegment = fromIndex - segmentIndex * segmentSize;

      while (segmentIndex < segments.length)
      {
         // @SuppressWarnings("unchecked")
         if (((Item) (segments[segmentIndex][indexInSegment])).compareTo(value) == 0)
         {
            return segmentIndex * indexInSegment;
         }

         indexInSegment++;

         if (indexInSegment == segmentSize)
         {
            indexInSegment = 0;
            segmentIndex++;
         }
      }

      return -1;
   }

   public void set(int fromIndex, int toIndex, Item value)
   {
      if (fromIndex >= size || toIndex >= size || fromIndex > toIndex)
      {
         return;
      }

      int index = fromIndex;
      int segmentIndex = findSegmentIndex(fromIndex);
      int indexInSegment = fromIndex - segmentIndex * segmentSize;

      while (segmentIndex < segments.length && index <= toIndex)
      {
         // @SuppressWarnings("unchecked")
         segments[segmentIndex][indexInSegment] = value;
         index++;
         indexInSegment++;

         if (indexInSegment == segmentSize)
         {
            indexInSegment = 0;
            segmentIndex++;
         }
      }
   }

   public Item min(int fromIndex, int toIndex)
   {
      if (fromIndex >= size || toIndex >= size || fromIndex > toIndex)
      {
         return null;
      }

      int index = fromIndex;
      int segmentIndex = findSegmentIndex(fromIndex);
      int indexInSegment = fromIndex - segmentIndex * segmentSize;
      Item minimum = null;

      while (segmentIndex < segments.length && index < toIndex)
      {
         // @SuppressWarnings("unchecked")
         Item val = (Item) segments[segmentIndex][indexInSegment];
         if (minimum == null || val.compareTo(minimum) < 0)
         {
            minimum = val;
         }

         index++;
         indexInSegment++;

         if (indexInSegment == segmentSize)
         {
            indexInSegment = 0;
            segmentIndex++;
         }
      }

      return null;
   }

   // check if the absolute index falls into given segment index
   private int compareIndexToSegment(int index, int segmentIndex)
   {
      int lowerIndex = segmentIndex * segmentSize;
      int higherIndex = (segmentIndex + 1) * segmentSize - 1;

      if (index < lowerIndex) // index falls before segment
      {
         return -1;
      }
      else if (index > higherIndex) // index falls after segment
      {
         return 1;
      }

      return 0;
   }

   // find segment that contains given absolute index using binary search
   // in array
   private int findSegmentIndex(int index)
   {
      int lo = 0; // lower segment index
      int hi = segments.length - 1; // higher segment index

      while (lo <= hi)
      {
         int mid = lo + (hi - lo) / 2; // middle segment index
         int cmp = compareIndexToSegment(index, mid);

         if (cmp < 0)
         {
            hi = mid - 1;
         }
         else if (cmp > 0)
         {
            lo = mid + 1;
         }
         else if (cmp == 0)
         {
            return mid;
         }
      }

      return lo;
   }

   public void show()
   {
      for (int i = 0; i < segments.length; i++)
      {
         System.out.printf("segment#%d { ", i);

         for (int j = 0; j < segmentSize; j++)
         {
            System.out.print((Item) segments[i][j]);
            System.out.print(" ");
         }

         System.out.printf("}\n");
      }
   }

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

package odessa.uni.imem.maxim;

public class SegmentedArrayImpl<Item extends Comparable<Item>> implements SegmentedArray<Item>

{

private int size;

private int segmentSize;

private Object[][] segments;

public SegmentedArrayImpl(int aSegmentSize, int aSegmentCount)

{

segmentSize = aSegmentSize;

size = segmentSize * aSegmentCount;

segments = new Object[aSegmentCount][segmentSize];

}

public int indexOf(Item value, int fromIndex)

{

if (fromIndex >= size)

{

return -1;

}

int segmentIndex = findSegmentIndex(fromIndex);

int indexInSegment = fromIndex - segmentIndex * segmentSize;

while (segmentIndex < segments.length)

{

// @SuppressWarnings("unchecked")

if (((Item) (segments[segmentIndex][indexInSegment])).compareTo(value) == 0)

{

return segmentIndex * indexInSegment;

}

indexInSegment++;

if (indexInSegment == segmentSize)

{

indexInSegment = 0;

segmentIndex++;

}

return -1;

}

public void set(int fromIndex, int toIndex, Item value)

{

if (fromIndex >= size || toIndex >= size || fromIndex > toIndex)

{

return;

}

int index = fromIndex;

int segmentIndex = findSegmentIndex(fromIndex);

int indexInSegment = fromIndex - segmentIndex * segmentSize;

while (segmentIndex < segments.length && index <= toIndex)

{

// @SuppressWarnings("unchecked")

segments[segmentIndex][indexInSegment] = value;

index++;

indexInSegment++;

if (indexInSegment == segmentSize)

{

indexInSegment = 0;

segmentIndex++;

}

public Item min(int fromIndex, int toIndex)

{

if (fromIndex >= size || toIndex >= size || fromIndex > toIndex)

{

return null;

}

int index = fromIndex;

int segmentIndex = findSegmentIndex(fromIndex);

int indexInSegment = fromIndex - segmentIndex * segmentSize;

Item minimum = null;

while (segmentIndex < segments.length && index < toIndex)

{

// @SuppressWarnings("unchecked")

Item val = (Item) segments[segmentIndex][indexInSegment];

if (minimum == null || val.compareTo(minimum) < 0)

{

minimum = val;

}

index++;

indexInSegment++;

if (indexInSegment == segmentSize)

{

indexInSegment = 0;

segmentIndex++;

}

return null;

}

// check if the absolute index falls into given segment index

private int compareIndexToSegment(int index, int segmentIndex)

{

int lowerIndex = segmentIndex * segmentSize;

int higherIndex = (segmentIndex + 1) * segmentSize - 1;

if (index < lowerIndex) // index falls before segment

{

return -1;

}

else if (index > higherIndex) // index falls after segment

{

return 1;

}

return 0;

}

// find segment that contains given absolute index using binary search

// in array

private int findSegmentIndex(int index)

{

int lo = 0; // lower segment index

int hi = segments.length - 1; // higher segment index

while (lo <= hi)

{

int mid = lo + (hi - lo) / 2; // middle segment index

int cmp = compareIndexToSegment(index, mid);

if (cmp < 0)

{

hi = mid - 1;

}

else if (cmp > 0)

{

lo = mid + 1;

}

else if (cmp == 0)

{

return mid;

}

return lo;

}

public void show()

{

for (int i = 0; i < segments.length; i++)

{

System.out.printf("segment#%d { ", i);

for (int j = 0; j < segmentSize; j++)

{

System.out.print((Item) segments[i][j]);

System.out.print(" ");

}

System.out.printf("}\n");

}

Данный класс реализует интерфейс SegmentedArray с учетом требования задачи, а именно:

Допускаются массивы очень большого размера
Методы indexOf и max должны работать максимально быстро

Используемый алгоритм

С учетом условий задачи был выбран алгориnм, описанный в статье Segmented Tree.

Согласно условию задачи, массив может быть очень большим, а это означает очень широкий диапазон индексов элементов. Следовательно, стоит задача максимально быстро находить начальный и конечный сегменты, которые покрывают индексы диапазона, заданные в качестве параметров методов интерфейса.

Выбранный алгоритм позволяет быстрыое нахождение нужных сегментов благодаря бинарному дереву, которым описывается набор диапазонов.

Алгоритм поиска нужного сегмента реализован с помощью методов findSegmentIndex и compareIndexToSegment.

Первый метод — это обычный двоичный поиск в массиве отсортированных элементов, которыми являются номера сегментов в порядке их следования. Данный метод заимствован из Coursera. Внутри он использует второй метод compareIndexToSegment для проверки попадания заданного абсолютного индекса в сегмент с заданным номером, т. е. он реализует нобходимый для бинарного поиска метод сравнения, где фактически абсолютный индекс сравнивается с сегментом с целью его выбора.

Методы родительского интерфейса

indexOf — находит нужный сегмент посредством findSegmentIndex и далее — индекс в сегменте, затем производит поиск в этом и последующих сегментах нужного значения
set — находит первый и последний сегменты посредством findSegmentIndex, которые покрывают входные индексы диапазона, затем выполняет запись начиная с начального сегмента и индекса в нем, и заканчивая последним сегментом и индексом в нем.
min — находит диапазон сегментов для поиска таким же образом, как и метод set и находит минимальное значения в данном диапазоне сегментов

Собственные методы

конструктор — принимает 2 аргумента — размер и количество сегментов
compareIndexToSegment — проверяет, попадает ли абсолютный индекс в данный сегмент и возвращает одно из значений: -1 — если индекс перед сегментом, 0 — если попадает в сегмент, 1 — если после сегмента
findSegmentIndex — находит сегмент, который содержит данный абсолютный индекс используя бинарный поиск в массиве
show — диагностическая печать содержимого

Класс SegmentedArrayApp

package odessa.uni.imem.maxim;

import java.util.*;

public class SegmentedArrayApp
{
   public static Vector<String> parseTextToTokens(String text)
   {
      Vector<String> tokens = new Vector<String>();
      StringTokenizer st = new StringTokenizer(text);

      while (st.hasMoreTokens())
      {
         tokens.add(st.nextToken());
      }

      return tokens;
   }

   public static Integer strToInt(String s)
   {
      Integer x = null;
      try
      {
         x = Integer.parseUnsignedInt(s);
      }
      catch (NumberFormatException e)
      {
      }

      return x;
   }

   public static void main(String[] args)
   {
      SegmentedArrayImpl<String> storage = new SegmentedArrayImpl<String>(4, 4);

      Scanner in = new Scanner(System.in);

      for (;;)
      {
         String inputLine = in.nextLine();
         if (inputLine.isEmpty())
         {
            continue;
         }

         String cmd = null;
         String arg1 = null;
         String arg2 = null;
         String arg3 = null;

         {
            Vector<String> inputTokens = parseTextToTokens(inputLine);
            if (inputTokens.size() > 0)
            {
               cmd = inputTokens.get(0);
            }
            if (inputTokens.size() > 1)
            {
               arg1 = inputTokens.get(1);
            }
            if (inputTokens.size() > 2)
            {
               arg2 = inputTokens.get(2);
            }
            if (inputTokens.size() > 3)
            {
               arg3 = inputTokens.get(3);
            }
         }

         if (cmd.equals("exit"))
         {
            break;
         }
         else if (cmd.equals("show"))
         {
            storage.show();
         }
         else if (cmd.equals("index"))
         {
            String value = (arg1 != null && !arg1.isEmpty()) ? arg1 : null;
            Integer fromIndex = (arg2 != null) ? strToInt(arg2) : null;

            if (value == null || fromIndex == null)
            {
               System.out.printf("*** ERROR: wrong arguments: <%s> <%s> <%d>\n", cmd, arg1, arg2);
               continue;
            }

            System.out.println(storage.indexOf(value, fromIndex));
         }
         else if (cmd.equals("set"))
         {
            Integer fromIndex = (arg1 != null) ? strToInt(arg1) : null;
            Integer toIndex = (arg2 != null) ? strToInt(arg2) : null;
            String value = (arg3 != null && !arg3.isEmpty()) ? arg3 : null;

            if (fromIndex == null || toIndex == null || value == null)
            {
               System.out.printf("*** ERROR: wrong arguments: <%s> <%d> <%d> <%s>\n", cmd, arg1, arg2, arg3);
               continue;
            }

            storage.set(fromIndex, toIndex, value);
            System.out.println("Ok");
         }
         else if (cmd.equals("min"))
         {
            Integer fromIndex = (arg1 != null) ? strToInt(arg1) : null;
            Integer toIndex = (arg2 != null) ? strToInt(arg2) : null;

            if (fromIndex == null || toIndex == null)
            {
               System.out.printf("*** ERROR: wrong arguments: <%s> <%d> <%d>\n", cmd, arg1, arg2);
               continue;
            }

            System.out.println(storage.min(fromIndex, toIndex));
         }

      }

      in.close();

   }

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

package odessa.uni.imem.maxim;

import java.util.*;

public class SegmentedArrayApp

{

public static Vector<String> parseTextToTokens(String text)

{

Vector<String> tokens = new Vector<String>();

StringTokenizer st = new StringTokenizer(text);

while (st.hasMoreTokens())

{

tokens.add(st.nextToken());

}

return tokens;

}

public static Integer strToInt(String s)

{

Integer x = null;

try

{

x = Integer.parseUnsignedInt(s);

}

catch (NumberFormatException e)

{

}

return x;

}

public static void main(String[] args)

{

SegmentedArrayImpl<String> storage = new SegmentedArrayImpl<String>(4, 4);

Scanner in = new Scanner(System.in);

for (;;)

{

String inputLine = in.nextLine();

if (inputLine.isEmpty())

{

continue;

}

String cmd = null;

String arg1 = null;

String arg2 = null;

String arg3 = null;

{

Vector<String> inputTokens = parseTextToTokens(inputLine);

if (inputTokens.size() > 0)

{

cmd = inputTokens.get(0);

}

if (inputTokens.size() > 1)

{

arg1 = inputTokens.get(1);

}

if (inputTokens.size() > 2)

{

arg2 = inputTokens.get(2);

}

if (inputTokens.size() > 3)

{

arg3 = inputTokens.get(3);

}

if (cmd.equals("exit"))

{

break;

}

else if (cmd.equals("show"))

{

storage.show();

}

else if (cmd.equals("index"))

{

String value = (arg1 != null && !arg1.isEmpty()) ? arg1 : null;

Integer fromIndex = (arg2 != null) ? strToInt(arg2) : null;

if (value == null || fromIndex == null)

{

System.out.printf("*** ERROR: wrong arguments: <%s> <%s> <%d>\n", cmd, arg1, arg2);

continue;

}

System.out.println(storage.indexOf(value, fromIndex));

}

else if (cmd.equals("set"))

{

Integer fromIndex = (arg1 != null) ? strToInt(arg1) : null;

Integer toIndex = (arg2 != null) ? strToInt(arg2) : null;

String value = (arg3 != null && !arg3.isEmpty()) ? arg3 : null;

if (fromIndex == null || toIndex == null || value == null)

{

System.out.printf("*** ERROR: wrong arguments: <%s> <%d> <%d> <%s>\n", cmd, arg1, arg2, arg3);

continue;

}

storage.set(fromIndex, toIndex, value);

System.out.println("Ok");

}

else if (cmd.equals("min"))

{

Integer fromIndex = (arg1 != null) ? strToInt(arg1) : null;

Integer toIndex = (arg2 != null) ? strToInt(arg2) : null;

if (fromIndex == null || toIndex == null)

{

System.out.printf("*** ERROR: wrong arguments: <%s> <%d> <%d>\n", cmd, arg1, arg2);

continue;

}

System.out.println(storage.min(fromIndex, toIndex));

}

in.close();

}

Данный класс реализует тестовое приложение для интерфейса. Он содержит вспомогательные функции ввода и функцию main, содержащую код теста.

Методы класса

parseTextToTokens — разбирает входной текст на слова используя известный класс StringTokenizer и возвращает вектор слов
strToInt — превращает строку в число с подавлением исключения NumberFormatException
main — реализует простейший интерпритатор команд, в котором каждая команда представляет соостветствующий интерфейсный метод, состоит из цикла, где в каждом цикле посредством объекта Scanner читается полностью входная строка, которая затем разбирается на команду и ее аргументы посредством parseTextToTokens, это в дальнейшем превращается в соответствующие вызовы интерфейсных методов.

Ссылка на Ideone: https://ideone.com/BknxiN

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Category Archives: Многомерные массивы

A704

A406

A401. Удаление строки и столбца из матрицы

А404

Segmented Array