Класс комплексных чисел

26/08/2016 by Дарья Пиндус

Задача.

Напишите класс для хранения комплексных чисел и реализуйте основные операции работы с ними.

Тесты.

Исходные числа	Операция	Результат
z1 = 2 + 3i z2 = -1 + 2i	+	1.0 + 5.0i
	—	3.0 + i
	*	-8.0 + i
	/	0.8 — 1.4i
3 + 4i	√	2.0 + i, -2.0 -i
-1 + 2i	pow	-3.0 — 4.0i

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

/**
 * <h1>Complex Numbers</h1>
 * The ComplexNumber program implements an application that
 * allows to calculate complex numbers
 **/

public class ComplexNumber {

    /**
     * Represents the real part of a complex number
     */
    private double re;

    /**
     * Represents imaginary part of a complex number
     */
    private double im;

    public ComplexNumber(double re, double im) {
        this.re = re;
        this.im = im;
    }

    public double getRe() {
        return re;
    }

    public double getIm() {
        return im;
    }

    /**
     * @return modulus (or absolute value) of the number
     */
    private double getModule() {
        return Math.sqrt(this.re * this.re + this.im * this.im);
    }

    /**
     * Allows to get the sum of two complex numbers given in the parameters.
     *
     * @return the new complex number
     */
    public static ComplexNumber sum(ComplexNumber cn1, ComplexNumber cn2) {
        return new ComplexNumber(cn1.getRe() + cn2.getRe(), cn1.getIm() + cn2.getIm());
    }

    /**
     * Allows to get the product of two complex numbers given in the parameters.
     *
     * @return the new complex number
     */
    public static ComplexNumber multiply(ComplexNumber cn1, ComplexNumber cn2) {
        return new ComplexNumber(cn1.getRe() * cn2.getRe() - cn1.getIm() * cn2.getIm(), cn1.getRe() * cn2.getIm() + cn1.getIm() * cn2.getRe());
    }

    /**
     * Allows to get the difference of two complex numbers given in the parameters.
     *
     * @return the new complex number
     */
    public static ComplexNumber subtract(ComplexNumber cn1, ComplexNumber cn2) {
        return new ComplexNumber(cn1.getRe() - cn2.getRe(), cn1.getIm() - cn2.getIm());
    }

    /**
     * Allows to get the product of two complex numbers given in the parameters.
     *
     * @return the new complex number
     */
    public static ComplexNumber divide(ComplexNumber cn1, ComplexNumber cn2) {
        ComplexNumber temp = new ComplexNumber(cn2.getRe(), (-1) * cn2.getIm());
        temp = ComplexNumber.multiply(cn1, temp);
        double denominator = cn2.getRe() * cn2.getRe() + cn2.getIm() * cn2.getIm();
        return new ComplexNumber(temp.getRe() / denominator, temp.getIm() / denominator);
    }

    /**
     * This function allows to get the argument of complex number to represent it in trigonometric form
     *
     * @return argument of complex number
     */
    private double GetArg() {
        if (this.re > 0) {
            return Math.atan(im / re);
        } else {
            if (re < 0 && im > 0) {
                return Math.PI + Math.atan(im / re);
            } else {
                return -Math.PI + Math.atan(im / re);
            }
        }
    }

    /**
     * Allows to raise complex number to specified power with the help of de Moivre's formula.
     *
     * @param cn    needed complex number (the base)
     * @param power the exponent
     * @return the new complex number
     */
    public static ComplexNumber pow(ComplexNumber cn, int power) {
        double factor = Math.pow(cn.getModule(), power);
        return new ComplexNumber(factor * Math.cos(power * cn.GetArg()), factor * Math.sin(power * cn.GetArg()));
    }

    /**
     * The function of getting square roots of complex number cn
     *
     * @return an array of pair of square roots
     */
    public static ComplexNumber[] sqrt(ComplexNumber cn) {
        double a = cn.getModule() / 2;
        ComplexNumber pos = new ComplexNumber(Math.sqrt(a + cn.getRe() / 2), Math.signum(cn.getIm()) * Math.sqrt(a - cn.getRe() / 2));
        ComplexNumber neg = new ComplexNumber((-1) * pos.getRe(), (-1) * pos.getIm());
        ComplexNumber[] answer = {pos, neg};
        return answer;
    }

    /**
     * Defines and returns the sign required for correct record of a number
     *
     * @return string with appropriate sign
     */
    private String sign() {
        if (im > 0) return " + ";
        else return " - ";
    }

    @Override
    public String toString() {
        String string;
        if (im == 1 || im == -1) {
            if (re == 0) {
                string = sign() + "i";
            } else {
                string = Double.toString(re) + sign() + "i";
            }
        } else {
            string = Double.toString(re) + sign() + Double.toString(Math.abs(im)) + "i";
        }
        return string;
    }

    @Override
    public boolean equals(Object obj) {
        if (this.getClass() != obj.getClass() || obj == null)
            return false;
        return true;
    }

    /**
     * In this function main test on the correctness of this program are done.
     * All operations on complex numbers are shown.
     */
    public static void main(String[] args) {
        ComplexNumber x = new ComplexNumber(2, 3);
        ComplexNumber y = new ComplexNumber(-1, 2);
        System.out.println("z1 = " + x + ",     z2 = " + y);

        ComplexNumber z;
        z = ComplexNumber.sum(x, y);
        System.out.println("+ : " + z);

        z = ComplexNumber.subtract(x, y);
        System.out.println("- : " + z);

        z = ComplexNumber.divide(x, y);
        System.out.println("/ : " + z);

        z = ComplexNumber.multiply(x, y);
        System.out.println(" * :" + z);

        z = ComplexNumber.pow(y, 2);
        System.out.println("Pow 2 of z2 : " + z);

        ComplexNumber b = new ComplexNumber(3, 4);
        ComplexNumber[] ans = ComplexNumber.sqrt(b);
        System.out.println("Sqrt of " + b + " = " + ans[0] + ",  " + ans[1]);

    }
}

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

171

172

173

174

175

176

177

178

179

180

181

182

/**

* <h1>Complex Numbers</h1>

* The ComplexNumber program implements an application that

* allows to calculate complex numbers

**/

public class ComplexNumber {

/**

* Represents the real part of a complex number

private double re;

/**

* Represents imaginary part of a complex number

private double im;

public ComplexNumber(double re, double im) {

this.re = re;

this.im = im;

}

public double getRe() {

return re;

}

public double getIm() {

return im;

}

/**

* @return modulus (or absolute value) of the number

private double getModule() {

return Math.sqrt(this.re * this.re + this.im * this.im);

}

/**

* Allows to get the sum of two complex numbers given in the parameters.

* @return the new complex number

public static ComplexNumber sum(ComplexNumber cn1, ComplexNumber cn2) {

return new ComplexNumber(cn1.getRe() + cn2.getRe(), cn1.getIm() + cn2.getIm());

}

/**

* Allows to get the product of two complex numbers given in the parameters.

* @return the new complex number

public static ComplexNumber multiply(ComplexNumber cn1, ComplexNumber cn2) {

return new ComplexNumber(cn1.getRe() * cn2.getRe() - cn1.getIm() * cn2.getIm(), cn1.getRe() * cn2.getIm() + cn1.getIm() * cn2.getRe());

}

/**

* Allows to get the difference of two complex numbers given in the parameters.

* @return the new complex number

public static ComplexNumber subtract(ComplexNumber cn1, ComplexNumber cn2) {

return new ComplexNumber(cn1.getRe() - cn2.getRe(), cn1.getIm() - cn2.getIm());

}

/**

* Allows to get the product of two complex numbers given in the parameters.

* @return the new complex number

public static ComplexNumber divide(ComplexNumber cn1, ComplexNumber cn2) {

ComplexNumber temp = new ComplexNumber(cn2.getRe(), (-1) * cn2.getIm());

temp = ComplexNumber.multiply(cn1, temp);

double denominator = cn2.getRe() * cn2.getRe() + cn2.getIm() * cn2.getIm();

return new ComplexNumber(temp.getRe() / denominator, temp.getIm() / denominator);

}

/**

* This function allows to get the argument of complex number to represent it in trigonometric form

* @return argument of complex number

private double GetArg() {

if (this.re > 0) {

return Math.atan(im / re);

} else {

if (re < 0 && im > 0) {

return Math.PI + Math.atan(im / re);

} else {

return -Math.PI + Math.atan(im / re);

}

/**

* Allows to raise complex number to specified power with the help of de Moivre's formula.

* @param cn needed complex number (the base)

* @param power the exponent

* @return the new complex number

public static ComplexNumber pow(ComplexNumber cn, int power) {

double factor = Math.pow(cn.getModule(), power);

return new ComplexNumber(factor * Math.cos(power * cn.GetArg()), factor * Math.sin(power * cn.GetArg()));

}

/**

* The function of getting square roots of complex number cn

* @return an array of pair of square roots

public static ComplexNumber[] sqrt(ComplexNumber cn) {

double a = cn.getModule() / 2;

ComplexNumber pos = new ComplexNumber(Math.sqrt(a + cn.getRe() / 2), Math.signum(cn.getIm()) * Math.sqrt(a - cn.getRe() / 2));

ComplexNumber neg = new ComplexNumber((-1) * pos.getRe(), (-1) * pos.getIm());

ComplexNumber[] answer = {pos, neg};

return answer;

}

/**

* Defines and returns the sign required for correct record of a number

* @return string with appropriate sign

private String sign() {

if (im > 0) return " + ";

else return " - ";

}

@Override

public String toString() {

String string;

if (im == 1 || im == -1) {

if (re == 0) {

string = sign() + "i";

} else {

string = Double.toString(re) + sign() + "i";

}

} else {

string = Double.toString(re) + sign() + Double.toString(Math.abs(im)) + "i";

}

return string;

}

@Override

public boolean equals(Object obj) {

if (this.getClass() != obj.getClass() || obj == null)

return false;

return true;

}

/**

* In this function main test on the correctness of this program are done.

* All operations on complex numbers are shown.

public static void main(String[] args) {

ComplexNumber x = new ComplexNumber(2, 3);

ComplexNumber y = new ComplexNumber(-1, 2);

System.out.println("z1 = " + x + ", z2 = " + y);

ComplexNumber z;

z = ComplexNumber.sum(x, y);

System.out.println("+ : " + z);

z = ComplexNumber.subtract(x, y);

System.out.println("- : " + z);

z = ComplexNumber.divide(x, y);

System.out.println("/ : " + z);

z = ComplexNumber.multiply(x, y);

System.out.println(" * :" + z);

z = ComplexNumber.pow(y, 2);

System.out.println("Pow 2 of z2 : " + z);

ComplexNumber b = new ComplexNumber(3, 4);

ComplexNumber[] ans = ComplexNumber.sqrt(b);

System.out.println("Sqrt of " + b + " = " + ans[0] + ", " + ans[1]);

}

Ссылка на Ideone.

e-olymp 982. Связность

26/08/2016 by Дарья Пиндус

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

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

В первой строке заданы количество вершин $n$ и ребер $m$ в графе соответственно $(1 \leq n \leq 100, 1 \leq m \leq 10000)$ . Каждая из следующих m строк содержит по два числа $u_i$ и $v_i$ $(1 \leq u_i, v_i \leq n);$ каждая такая строка означает, что в графе существует ребро между вершинами $u_i$ и $v_i$ .

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

Выведите «YES», если граф является связным и «NO» в противном случае.

Тесты

Test	Input	Output
1	4 2 1 2 3 4	NO
2	5 4 1 2 5 3 4 5 3 4	NO
3	5 4 1 2 5 1 3 5 4 3	YES

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

import java.util.*;
 
class Graph {
    public static void main(String[] args) {
        int n, m;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
 
        ArrayList<Integer> gr[] = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            gr[i] = new ArrayList<>();
        }
 
        int s = 0;
        for (int i = 0; i < m; i++) {
            int u, v;
            u = scanner.nextInt();
            v = scanner.nextInt();
            gr[u - 1].add(v - 1);
            gr[v - 1].add(u - 1);
        }

        LinkedList<Integer> queue = new LinkedList<>();
        queue.push(s);
        boolean used[] = new boolean[n];
        used[s] = true;
 
        while (!queue.isEmpty()) {
            int v = queue.peek();
            queue.pop();
            for (int i = 0; i < gr[v].size(); ++i) {
                int to = gr[v].get(i);
                if (!used[to]) {
                    used[to] = true;
                    queue.push(to);
                }
            }
        }
        String answer = "YES";
        for (int i = 0; i < used.length; i++) {
            if (used[i] == false) {
                answer = "NO";
            }
        }
        System.out.println(answer);
    }
}

import java.util.*;

class Graph {

public static void main(String[] args) {

int n, m;

Scanner scanner = new Scanner(System.in);

n = scanner.nextInt();

m = scanner.nextInt();

ArrayList<Integer> gr[] = new ArrayList[n];

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

gr[i] = new ArrayList<>();

}

int s = 0;

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

int u, v;

u = scanner.nextInt();

v = scanner.nextInt();

gr[u - 1].add(v - 1);

gr[v - 1].add(u - 1);

}

LinkedList<Integer> queue = new LinkedList<>();

queue.push(s);

boolean used[] = new boolean[n];

used[s] = true;

while (!queue.isEmpty()) {

int v = queue.peek();

queue.pop();

for (int i = 0; i < gr[v].size(); ++i) {

int to = gr[v].get(i);

if (!used[to]) {

used[to] = true;

queue.push(to);

}

String answer = "YES";

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

if (used[i] == false) {

answer = "NO";

}

System.out.println(answer);

}

Алгоритм

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

Ссылка на Ideone

e-olymp 6123. Стек с защитой от ошибок

26/08/2016 by Дарья Пиндус

Задача

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

push n

Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из стека последний элемент. Программа должна вывести его значение.

back

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

size

Программа должна вывести количество элементов в стеке.

clear

Программа должна очистить стек и вывести ok.

exit

Программа должна вывести bye и завершить работу.

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

Команды для стека.

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

Соответствующие значения для каждой команды(см. выше).

Тесты

№	Последовательность	Результат
1	push 2 back pop size pop push 1 size exit	ok 2 2 0 error ok 1 bye
2	push 3 push 1 push 5 size pop size exit	ok ok ok 3 5 2 bye
3	back push 9 pop pop exit	error ok 9 error bye
4	size push 1 size back pop exit	0 ok 1 1 1 bye

Код

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
 
class Stack {
 
    private int pointer;
    private int[] stack;
    private int size;
 
 
    public Stack() {
        this(20);
    }
 
    public Stack(int capacity) {
            size = capacity;
            stack = new int[size];
            pointer = -1;
    }
 
    public void push(int element) {
        stack[++pointer] = element;
    }
 
    public int pop() {
        int i = stack[pointer];
        stack[pointer--] = 0;
        return i;
    }
 
    public int back() {
        return stack[pointer];
    }
 
    public void clear() {
        Arrays.fill(stack, 0);
        pointer = -1;
    }
 
    public boolean isEmpty() {
        if (pointer < 0)
            return true;
        else
            return false;
    }
 
    public int size() {
        return this.pointer + 1;
    }
 
    public static void main(String[] args) {
        Stack stack = new Stack();
 
        Scanner scanner = new Scanner(System.in);
        System.out.println("enter your command");
        String command = scanner.nextLine();
 
        while (!command.equals("exit")) {
            if (command.matches("^push [0-9]")) {
                String[] comm = command.split(" ");
                stack.push(Integer.parseInt(comm[1]));
                System.out.println("OK");
            } else if (command.equals("pop")) {
                if (stack.isEmpty()) {
                    System.out.println("Error. Stack is empty");
                } else {
                    System.out.println(stack.pop());
                }
            } else if (command.equals("size")) {
                System.out.println(stack.size());
            } else if (command.equals("back")) {
                if (stack.isEmpty()) {
                    System.out.println("Error. Stack is empty");
                } else {
                    System.out.println(stack.back());
                }
            } else if (command.equals("clear")) {
                stack.clear();
                System.out.println("OK");
            } else {
                System.out.println("Command doesn't exist");
            }
            command = scanner.nextLine();
        }
        System.out.println("bye");
 
    }
}

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Scanner;

class Stack {

private int pointer;

private int[] stack;

private int size;

public Stack() {

this(20);

}

public Stack(int capacity) {

size = capacity;

stack = new int[size];

pointer = -1;

}

public void push(int element) {

stack[++pointer] = element;

}

public int pop() {

int i = stack[pointer];

stack[pointer--] = 0;

return i;

}

public int back() {

return stack[pointer];

}

public void clear() {

Arrays.fill(stack, 0);

pointer = -1;

}

public boolean isEmpty() {

if (pointer < 0)

return true;

else

return false;

}

public int size() {

return this.pointer + 1;

}

public static void main(String[] args) {

Stack stack = new Stack();

Scanner scanner = new Scanner(System.in);

System.out.println("enter your command");

String command = scanner.nextLine();

while (!command.equals("exit")) {

if (command.matches("^push [0-9]")) {

String[] comm = command.split(" ");

stack.push(Integer.parseInt(comm[1]));

System.out.println("OK");

} else if (command.equals("pop")) {

if (stack.isEmpty()) {

System.out.println("Error. Stack is empty");

} else {

System.out.println(stack.pop());

}

} else if (command.equals("size")) {

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

} else if (command.equals("back")) {

if (stack.isEmpty()) {

System.out.println("Error. Stack is empty");

} else {

System.out.println(stack.back());

}

} else if (command.equals("clear")) {

stack.clear();

System.out.println("OK");

} else {

System.out.println("Command doesn't exist");

}

command = scanner.nextLine();

}

System.out.println("bye");

}

Решение

Создаем структуру в которой реализуем все команды для стека с помощью функций и указателя $cursor$ . $cursor$ указывает на последний элемент в строке. Изначально $cursor$ , т.к. элементы в массиве, на которые бы он указывал, отсутствуют.

$push n$ записывает в ячейку с номером $cursor$ элемент $n$ . $size$ возвращает $cursor$ т.е. действительный размер стека. $pop$ возвращает последний помещённый в стек элемент, то есть элемент с номером $pointer+1$ , при этом удаляя его из стека. $back$ возвращает последний помещённый в стек элемент, то есть элемент с номером $cursor-1$ .В обоих случаях для проверки того, пуст ли стек, используется логическая функция $error$ . $clear$ обнуляет массив $cursor$ и присваивает $cursor$ начальное значение = -1.Команды считываются и выполняются пока не будет введено $exit$ , после чего выведется соответствующее сообщение и программа завершится.

Ссылка на Ideone

e-olymp 378. Таинственная записка

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

Задача e-olymp 378.

Условие

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

Закодированное сообщение: HPC PJVYMIY

Декодированное сообщение: ACM CONTEST

В этом примере выполнены следующие замены: H=A, P=C, C=M, J=O, V=N, Y=T, M=E иI=S.

Чтобы не заниматься кодированием и декодированием вручную, подруги просят Вас написать программу. Помогите девочкам!

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

В первой строке входного файла записано закодированное сообщение. Вторая строка –26 латинских букв верхнего регистра, представляющих собой код для соответствующего символа алфавита: первый символ дает код для A, второй для B и так далее. Используются только буквы верхнего регистра. В закодированном сообщении могут появиться пробелы, которые должны быть сохранены в выходной строке.

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

В выходной файл вывести одну строку, в которой содержится расшифрованное сообщение.

Тесты

Входные данные	Выходные данные
HPC PJVYMIYBLMRGJIASOPZEFDCKWYHUNXQTV	ACM CONTEST
FDY GAI BG UKMY KIMHOTSQYRLCUZPAGWJNBVDXEF	THE SKY IS BLUE
LJBSLJL IJWWDEJ KCFAGWRZMEXDNUYHVBOIJLSTPQ	DECODED MESSAGE

Код

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

class Ideone {
	public static void main (String[] args) throws java.lang.Exception {
		Scanner scanner = new Scanner(System.in);
		String message, cipher;
		message = scanner.nextLine();
		cipher = scanner.nextLine();
		char[] decoded = new char [message.length()];
 
		for (int i = 0; i < message.length(); i++) {
			if (message.charAt(i) == ' ') {
				decoded[i] = ' ';
			} else {
				decoded[i] = cipher.charAt(findIndex(message.charAt(i)));
			}			
		}
		System.out.println(decoded);
	}
	
	static int findIndex(char c) {
        String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        for (int i = 0; i < alphabet.length(); i++) {
            if (c == alphabet.charAt(i)) {
                return i;
            }
        }
        return -1;
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

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

Scanner scanner = new Scanner(System.in);

String message, cipher;

message = scanner.nextLine();

cipher = scanner.nextLine();

char[] decoded = new char [message.length()];

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

if (message.charAt(i) == ' ') {

decoded[i] = ' ';

} else {

decoded[i] = cipher.charAt(findIndex(message.charAt(i)));

}

System.out.println(decoded);

}

static int findIndex(char c) {

String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

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

if (c == alphabet.charAt(i)) {

return i;

}

return -1;

}

Решение

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

Ссылка на Ideone

A278

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

Задача A278

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

Даны натуральные числа $n_{1},\dots,n_{m}$ , действительные числа $x_{1},\dots,x_{m}$ . Вычислить $\frac{n_{1}\cdot x_{1}+\dots+n_{m}\cdot x_{m}}{n_{1}+\dots+n_{m}}$ .

Тестирование

№	Входные данные	Выходные данные
1.	1 2 4 -1	-0.4
2.	1 2 3 4 5 0.6	1.88889
3.	5 -2 1 0.2 3 -3 2 0	-1.70909
4.	10 3.3 4 0.4 6 0.01 8 1 1 8	1.7469
5.	3 -0.5 2 -0.4 1 -0.3 5 32 11 5 20 -1	4.58095

Код

import java.util.*;
import java.lang.*;
import java.io.*;
 
class A278 {
	public static void main (String[] args) throws java.lang.Exception {
		Scanner scanner = new Scanner(System.in);
		double numerator = 0;
		int denominator = 0;
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			double x = scanner.nextDouble();
			numerator += n * x;
			denominator += n;
		}
		double result = numerator / denominator;
		System.out.println(result);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class A278 {

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

Scanner scanner = new Scanner(System.in);

double numerator = 0;

int denominator = 0;

while (scanner.hasNext()) {

int n = scanner.nextInt();

double x = scanner.nextDouble();

numerator += n * x;

denominator += n;

}

double result = numerator / denominator;

System.out.println(result);

}

Алгоритм решения (потоковая обработка)

Считываем числа до конца входного потока и поочередно записываем их в переменные $n$ и $n$ соответственно.
Пока вводятся данные:

Вычисляем значение выражения $n_1\cdot x_1+\dots+n_m\cdot x_m$ , накапливая сумму в числитель $n$ .
Вычисляем значение выражения $n_1+\dots+n_m$ , накапливая сумму в делителе $n$ .
Находим результат $n$ от деления $n$ на $n$

Код на ideone.com

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

ML14

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

Задача. Вычислить период колебания маятника длины $l$ .

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

Длина нити маятника $l$ .

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

Период колебаний маятника.

Тесты

№	Входные данные	Выходные данные
1	0,3	1.09891
2	1	2.00632
3	40	12.6891

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main(String[] args) {
        double T, l, g = 9.8075;
        Scanner scanner = new Scanner(System.in);
        l = scanner.nextDouble();
        T = 2 * Math.PI * Math.sqrt(l / g);
        System.out.println(T);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main(String[] args) {

double T, l, g = 9.8075;

Scanner scanner = new Scanner(System.in);

l = scanner.nextDouble();

T = 2 * Math.PI * Math.sqrt(l / g);

System.out.println(T);

}

Решение

Условием задачи было вычислить период колебаний маятника $T$ , имея длину маятника $l$ . Период колебаний маятника можно рассчитать с помощью формулы: $T = 2\pi\sqrt{\frac{l}{g}}$ . Мы объявляем три переменные типа $double$ $T, l, g,$ где $T$ -период колебаний маятника, $l$ – длина маятника, $g$ = $9.8075$ – ускорение свободного падения на поверхности Земли в Одессе. $l$ – входной параметр. Затем, используя формулу $T = 2\pi\sqrt{\frac{l}{g}}$ , вычисляем и выводим значение периода.

Решение на ideone.com

e-olymp 127. Баксы в банке

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

Условие

Папа Карло подарил Буратино $1$ доллар в его первый день рождения, а экономный Буратино сложил подарок в банку. Каждый последующий год папа Карло удваивал свой предыдущий подарок и прибавлял к нему столько долларов, сколько лет исполнилось Буратино, а тот в свою очередь продолжал складывать баксы в банку. На какой $N$ -й день рождения в банке будет не менее чем $S$ долларов?

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

Единственное число – значение $S$ . $1\le S \le 240$ .

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

Искомое значение $N$ .

Задача взята с сайта e-olymp.

Тесты

Входные данные	Выходные данные
15	3
25	4
9	3
99	5
199	6
333	7
56	5
478	8
809	8

Код

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone {
	public static void main(String[] args) {
        int startSum = 1;
        int years = 1;
        int k = 1;
        int currentSum = startSum;
 
        Scanner scanner = new Scanner(System.in);
        int sum = scanner.nextInt();
        while (currentSum < sum) {
            years++;
            k = k*2 + years;
            currentSum += k;
        }
        System.out.println(years);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main(String[] args) {

int startSum = 1;

int years = 1;

int k = 1;

int currentSum = startSum;

Scanner scanner = new Scanner(System.in);

int sum = scanner.nextInt();

while (currentSum < sum) {

years++;

k = k*2 + years;

currentSum += k;

}

System.out.println(years);

}

Решение

В данной задаче $sum$ – сколько долларов в банке, $p$ – сколько долларов Папа Карло подарил Буратино. Пока $sum<s$ мы увеличиваем $N$ на $1$ и считаем сколько Папа Карло подарит Буратино $p=p\cdot 2+n$ и суммируем его с тем что лежит в банке $sum += p$ .

Задача на Ideone.com

ML 24

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

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

Треугольник задан длинами сторон. Найти радиус вписанной $r$ и описанной $R$ окружностей.

Тесты :

$a$	$b$	$c$	$r$	$R$
3	4	5	1	2.5
7.5	10	13	2.450117	6.5236096
1	3	4	0	inf
1	1	3	Не существует!	Не существует!

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

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

class Ideone
{
	public static void main (String[] args)
	{
		float a, b, c;
		Scanner scanner = new Scanner(System.in);
		System.out.println("Enter values: ");
		a = scanner.nextFloat();
		b = scanner.nextFloat();
		c = scanner.nextFloat();
		if (a + b >= c || b + c >= a || a + c >= b) {
			float p = (a + b + c) / 2;
			float S = (float) Math.sqrt(p * (p - a) * (p - b) * (p - c));
			float R = (a * b * c) / (4 * S);
			float r = S/p;
			System.out.println("Radius of incircle of triangle = " + r + "\nRadius of excircle of triangle = " + R);     
		} else {
			System.out.println("Wrong input data. Triangle doesn't exist");
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

float a, b, c;

Scanner scanner = new Scanner(System.in);

System.out.println("Enter values: ");

a = scanner.nextFloat();

b = scanner.nextFloat();

c = scanner.nextFloat();

if (a + b >= c || b + c >= a || a + c >= b) {

float p = (a + b + c) / 2;

float S = (float) Math.sqrt(p * (p - a) * (p - b) * (p - c));

float R = (a * b * c) / (4 * S);

float r = S/p;

System.out.println("Radius of incircle of triangle = " + r + "\nRadius of excircle of triangle = " + R);

} else {

System.out.println("Wrong input data. Triangle doesn't exist");

}

Алгоритм :

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

if (a + b < c || b + c < a || a + c < b) {
            System.out.println("Wrong input data. Triangle doesn't exist");
        }

if (a + b < c || b + c < a || a + c < b) {

System.out.println("Wrong input data. Triangle doesn't exist");

}

Если треугольник существует, проводим следующие вычисления (порядок сохранен) :

Вычисляем полупериметр $p$ треугольника: $p$ = $\frac{a + b + c}{2}$
Находим площадь $S$ по формуле Герона: $S$ = $\sqrt{p(p-a)(p-b)(p-c)}$
Вычисляем радиус $r$ вписанной окружности по формуле: $r$ = $\frac{S}{p}$
Вычисляем радиус $R$ описанной окружности по формуле: $R$ = $\frac{abc}{4S}$

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

java@Cat

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

Author Archives: Дарья Пиндус

Класс комплексных чисел

e-olymp 982. Связность

e-olymp 6123. Стек с защитой от ошибок

Задача

Стек с защитой от ошибок

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

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

Тесты

Решение

e-olymp 378. Таинственная записка

A278

Задача A278

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

Тестирование

Алгоритм решения (потоковая обработка)

A406

Ю4.15

ML14

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

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

Тесты

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

Решение

e-olymp 127. Баксы в банке

Условие

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

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

Тесты

Код

Решение

ML 24