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}).$
По алгоритму нахождения максимума находим длину наибольшего отрезка.
Выводим матрицу.
Выводим длину наибольшего отрезка.
Ссылка на код

Ю4.15

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

Заданы массивы $A(n)$ и $B(m)$ . Получить массив $C(m+n)$ , расположив в начале его элементы массива $A$ , а затем элементы массива $B$ .

Тесты:

n	m	A[n]	B[m]	Результат:
3	4	0 1 2	5 7 8 4	A={0 1 2} B={5 7 8 4} C={0 1 2 5 7 8 4}
2	9	9 3.6	7.4 3.6 4.6666 7.99702 1 1 1 1 1	A={9 3.6} B={7.4 3.6 4.6666 7.99702 1 1 1 1 1} C={9 3.6 7.4 3.6 4.6666 7.99702 1 1 1 1 1}

Код

import java.util.*;
import java.lang.*;
import java.io.*;
 
class U415 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n, m;
        n = scanner.nextInt();
        m = scanner.nextInt();
        double[] A = new double[n];
        double[] B = new double[m];
        double[] C = new double[n + m];
        for (int i = 0; i < n; i++) {
            A[i] = scanner.nextDouble();
        }
        for (int i = 0; i < m; i++) {
            B[i] = scanner.nextDouble();
        }
        for (int i = 0; i < n + m; i++) {
            if (i < n) {
                C [i] = A[i];
            } else {
                C [i] = B[i - n];
            }
        }
        System.out.println(Arrays.toString(C));
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class U415 {

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

int n, m;

n = scanner.nextInt();

m = scanner.nextInt();

double[] A = new double[n];

double[] B = new double[m];

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

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

A[i] = scanner.nextDouble();

}

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

B[i] = scanner.nextDouble();

}

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

if (i < n) {

C [i] = A[i];

} else {

C [i] = B[i - n];

}

System.out.println(Arrays.toString(C));

}

Решение
Задаем размерности массивов. Вводим их. Затем заполняем массив $C$ элементами сначала из массива $A$ ( $A$ элементов), а затем (с $A$ -ого элемента ) — элементами из массива $A$ . Выводим массив $C$ .

Код на ideone.com

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

e-olymp 138. Банкомат

04/07/2016 by Артур Тарасов

Задача. В банкомате имеются в достаточном количестве купюры номиналом [latex]10, 20, 50, 100, 200[/latex] и [latex]500[/latex] гривен. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в [latex]n[/latex] гривен[latex](0 \leq n \leq 100000)[/latex], или вывести [latex]-1[/latex], если указанную сумму выдать нельзя.

Тесты

Сумма	130	999	7360	3	80	123450	567	440
Число купюр	3	-1	18	-1	3	249	-1	4

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int[] Q = { 500, 200, 100, 50, 20, 10 };
		int n, q, x; //q - вспомогательная переменная в цикле
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		x=0; //количество купюр,  ему по умолчанию присваивается 0
		for(int i = 0; i < 6; ++i) //цикл перебирает все элементы массива, от большего к меньшему
		{
			q = Q[i];
			x += n / q; //считаем, сколько раз входит купюра в сумму
			n %= q;  //сумме присваивается остаток от деления на данную купюр
		}
		if(n > 0) x = -1; //проверяем наличие остатка, который банкомат не сможет выдать
		System.out.format("%d", x);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

int[] Q = { 500, 200, 100, 50, 20, 10 };

int n, q, x; //q - вспомогательная переменная в цикле

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

x=0; //количество купюр, ему по умолчанию присваивается 0

for(int i = 0; i < 6; ++i) //цикл перебирает все элементы массива, от большего к меньшему

{

q = Q[i];

x += n / q; //считаем, сколько раз входит купюра в сумму

n %= q; //сумме присваивается остаток от деления на данную купюр

}

if(n > 0) x = -1; //проверяем наличие остатка, который банкомат не сможет выдать

System.out.format("%d", x);

}

Алгоритм

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

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

Следует учесть, что сумма может быть и такой, что банкомат не сможет ее выдать. Это будет происходить тогда, когда сумма содержит некоторую часть, меньшую самой меньшей купюры. Чтобы выяснить, так ли это, мы смотрим, что осталось от суммы после применения «жадного»алгоритма. Если остаток равен [latex]0[/latex], то исходную сумму можно получить с помощью имеющихся купюр, и на экран выводится результат, полученный в цикле. Если же остаток больше [latex]0[/latex], такую операцию осуществить невозможно и программа выводит [latex]-1[/latex].

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

Засчитанное решение

Ю4.8

04/07/2016 by Иоанна Васильева

Условие

В массиве C(m) заменить каждый третий элемент полусуммой двух предыдущих, а стоящий перед ним – полусуммой соседних с ним элементов.

Решение

Задаем массив и вводим элементы массива. Задавать массив менее чем из трех элементов не имеет смысла, поэтому проверяем количество элементов. Пересчитываем каждый третий элемент, запоминая сначала значение стоящего перед ним, который также отдельно пересчитываем.

Код

Ссылка на Ideone.

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone {
	public static void main ( String[] arg s ) {
		Scanner in = new Scanner( System.in );
		int n = in.nextInt();
		int[] array = new int[n];
		if(n >= 3) {
			for( int i = 0; i < n; i++ ) array[i] = in.nextInt();
			for( int i=2; i<n; i=i+3 ) {
				int elem = array[i-1];
				array[i-1] = ( array[i-2] + array[i] ) / 2;
				array[i] = ( array[i-2] + elem ) / 2;
			}
			String ArrayString = Arrays.toString(array);
			System.out.print( ArrayString );
		} else System.out.print( "Try again" );
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main ( String[] arg s ) {

Scanner in = new Scanner( System.in );

int n = in.nextInt();

int[] array = new int[n];

if(n >= 3) {

for( int i = 0; i < n; i++ ) array[i] = in.nextInt();

for( int i=2; i<n; i=i+3 ) {

int elem = array[i-1];

array[i-1] = ( array[i-2] + array[i] ) / 2;

array[i] = ( array[i-2] + elem ) / 2;

}

String ArrayString = Arrays.toString(array);

System.out.print( ArrayString );

} else System.out.print( "Try again" );

}

Тест

Входные данные		Выходные данные
Размер массива	Элементы	Выходные данные
4	2 7 4 1	2.0, 3.0, 4.5, 1.0
2	5 8	Try again

А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. В вложенном цикле вводим значения матрицы. Вводим номера столбцов, которые мы хотим переставить. В цикле переставляем местами элементы указанных столбцов. Затем выводим матрицу.

Стек v.Java

20/12/2015 by Осецимский Анатолий

Stack test = new Stack(4);

System.out.println(test.isEmpty());

test.push(12);

System.out.println(test.isEmpty());

System.out.println(test.peek());

test.push(13);

test.push(14);

test.push(15);

test.push(16);

test.push(17);

test.push(‘(‘);

System.out.println(test.size());

System.out.println(test.peek().equals(‘(‘));

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.peek());

System.out.println(test.isEmpty());

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.isEmpty());

true

false

true

false

true

Что такое стек прекрасно расскажет Википедия.

Реализация динамического стека. Есть приватная функция resize, которая меняет размер массива, выделяемого под стек. Массив копируется в новый с помощью Java’вского копирования массивов.

Есть тестовый вывод, для проверки корректности всех методов.

/**
 * Created by green on 19.12.15.
 */
class Stack {
    private int size;
    private Object[] date;
    private int capacity;
    public Stack(){
        date = new Object[2];
        capacity = 2;
    }
    public Stack(int x){
        date = new Object[x];;
        capacity = x;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    private void resize(int x){
        Object[] newDate = new Object[x];
        System.arraycopy(date, 0, newDate, 0, size);
        date = null;
        date = newDate;
    }

    public void push(Object x){
        if(size == capacity){
            resize(2*capacity);
        }
        date[size++] = x;
    }

    public Object pop(){
        if(isEmpty()){
            return null;
        }
        if(size < capacity/2){
            resize(capacity/2);
        }
        Object temp = date[size -1];
        size = size -1;
        return temp;
    }

    public Object peek(){
        if(isEmpty()) return null;
        return date[size-1];
    }

    public void clear(){
        size = 0;
    }

    public int size(){
        return size;
    }
    public int getCapacity(){
        return size;
    }
}

public class task {
    public static void main(String[] args) {
        Stack test = new Stack(4);
        System.out.println(test.isEmpty());
        test.push(12);
        System.out.println(test.isEmpty());
        System.out.println(test.peek());
        test.push(13);
        test.push(14);
        test.push(15);
        test.push(16);
        test.push(17);
        test.push('(');
        System.out.println(test.size());
        System.out.println(test.peek().equals('('));
        test.pop();
        System.out.println(test.peek());
        test.pop();
        System.out.println(test.peek());
        test.pop();
        System.out.println(test.peek());
        test.pop();
        System.out.println(test.peek());
        test.pop();
        System.out.println(test.peek());
        System.out.println(test.isEmpty());
        test.pop();
        System.out.println(test.peek());
        test.pop();
        System.out.println(test.isEmpty());
    }
}

/**

* Created by green on 19.12.15.

class Stack {

private int size;

private Object[] date;

private int capacity;

public Stack(){

date = new Object[2];

capacity = 2;

}

public Stack(int x){

date = new Object[x];;

capacity = x;

}

public boolean isEmpty(){

return size == 0;

}

private void resize(int x){

Object[] newDate = new Object[x];

System.arraycopy(date, 0, newDate, 0, size);

date = null;

date = newDate;

}

public void push(Object x){

if(size == capacity){

resize(2*capacity);

}

date[size++] = x;

}

public Object pop(){

if(isEmpty()){

return null;

}

if(size < capacity/2){

resize(capacity/2);

}

Object temp = date[size -1];

size = size -1;

return temp;

}

public Object peek(){

if(isEmpty()) return null;

return date[size-1];

}

public void clear(){

size = 0;

}

public int size(){

return size;

}

public int getCapacity(){

return size;

}

public class task {

public static void main(String[] args) {

Stack test = new Stack(4);

System.out.println(test.isEmpty());

test.push(12);

System.out.println(test.isEmpty());

System.out.println(test.peek());

test.push(13);

test.push(14);

test.push(15);

test.push(16);

test.push(17);

test.push('(');

System.out.println(test.size());

System.out.println(test.peek().equals('('));

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.peek());

System.out.println(test.isEmpty());

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.isEmpty());

}

Ссылка на ideone.

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

Immutable fractions

29/07/2015 by Valeriya Rud

Задание

Создайте класс для выполнения основных операций с дробями. В данном варианте дроби не должны изменяться после создания, а методы, реализующие арифметические операции должны быть статическими. Реализуйте метод для автоматического получения строкового представления дроби при печати. Протестируйте своё решение в методе main().
Желательно реализовать метод сокращения дробей через алгоритм Евклида для поиска наибольшего общего делителя (НОД, GCD). Вполне уместной было бы реализовать в этом классе интерфейс Comparable и продемонстрировать работу метода java.util.Arrays.sort().

Решение

class Fraction {
	final int numerator, denominator;
	static String delimiter = "/";
	
	private int gcd(int a, int b){
		while(b != 0){
			int c = a % b;
			a = b;
			b = c;
		}
		return a;
	}

	public static Fraction addition(Fraction x, Fraction y) {
		Fraction z = new Fraction(x.numerator * y.denominator + y.numerator * x.denominator, x.denominator * y.denominator);
		return z;
	}
	
	public static Fraction substraction(Fraction x, Fraction y){
		Fraction z = new Fraction(x.numerator * y.denominator - y.numerator * x.denominator, x.denominator * y.denominator);
		return z;
	}
	
	public static Fraction multiplication(Fraction x, Fraction y){
		Fraction z = new Fraction(x.numerator * y.numerator, x.denominator * y.denominator);
		return z;
	}
	
	public static Fraction division (Fraction x, Fraction y){
		Fraction z = new Fraction(x.numerator * y.denominator, x.denominator * y.numerator);
		return z;
	}
	public String toString(){
		return numerator  + delimiter + denominator; 
	}
	
	public Fraction(){// name ofthe constructor starts from upper case
		numerator = 1;
		denominator = 2;
	}		
		
	public Fraction(int d){
		numerator = 1;
		denominator = d;
	}

	public Fraction(int n, int d){
		int devider = gcd(n, d);
		numerator  = n / devider;
		denominator = d / devider;
	}
	
	public Fraction(Fraction x){
		numerator = x.numerator;
		denominator = x.denominator;
	}

	public static void main (String[] args) {	
		System.out.println(new Fraction(2147483647, 2147483645));
		Fraction x = new Fraction(5);
		System.out.println(x);
		Fraction y = x;
		System.out.println(y);
		Fraction z = new Fraction(x); //copy of x
		System.out.println(z);
		System.out.println(Fraction.addition(x, z));
		System.out.println(Fraction.substraction(z, x));
		System.out.println(Fraction.multiplication(x, z));
		System.out.println(Fraction.division(x, z));
	}
}
}

class Fraction {

final int numerator, denominator;

static String delimiter = "/";

private int gcd(int a, int b){

while(b != 0){

int c = a % b;

a = b;

b = c;

}

return a;

}

public static Fraction addition(Fraction x, Fraction y) {

Fraction z = new Fraction(x.numerator * y.denominator + y.numerator * x.denominator, x.denominator * y.denominator);

return z;

}

public static Fraction substraction(Fraction x, Fraction y){

Fraction z = new Fraction(x.numerator * y.denominator - y.numerator * x.denominator, x.denominator * y.denominator);

return z;

}

public static Fraction multiplication(Fraction x, Fraction y){

Fraction z = new Fraction(x.numerator * y.numerator, x.denominator * y.denominator);

return z;

}

public static Fraction division (Fraction x, Fraction y){

Fraction z = new Fraction(x.numerator * y.denominator, x.denominator * y.numerator);

return z;

}

public String toString(){

return numerator + delimiter + denominator;

}

public Fraction(){// name ofthe constructor starts from upper case

numerator = 1;

denominator = 2;

}

public Fraction(int d){

numerator = 1;

denominator = d;

}

public Fraction(int n, int d){

int devider = gcd(n, d);

numerator = n / devider;

denominator = d / devider;

}

public Fraction(Fraction x){

numerator = x.numerator;

denominator = x.denominator;

}

public static void main (String[] args) {

System.out.println(new Fraction(2147483647, 2147483645));

Fraction x = new Fraction(5);

System.out.println(x);

Fraction y = x;

System.out.println(y);

Fraction z = new Fraction(x); //copy of x

System.out.println(z);

System.out.println(Fraction.addition(x, z));

System.out.println(Fraction.substraction(z, x));

System.out.println(Fraction.multiplication(x, z));

System.out.println(Fraction.division(x, z));

}

java@Cat

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

Category Archives: 5. Массивы

A406

Ю4.15

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

e-olymp 138. Банкомат

Ю4.8

Условие

Решение

Код

Тест

А404

Стек v.Java

Segmented Array

Immutable fractions

Задание

Решение