Category Archives: 4. Потоковая обработка

A153.Потоковая обработка

А136з

А136е

А136и

А165г. Среднее геометрическое

A278

e-olymp 5082. Degrees of vertices

Условие

Код на Java:

Алгоритм:

Ссылки:

А137г

А137е

e-olimp 7365 — Молоко и пирожок

java@Cat

Category Archives: 4. Потоковая обработка

A153.Потоковая обработка

А136з

А136е

А136и

А165г. Среднее геометрическое

A278

e-olymp 5082. Degrees of vertices

Условие

Код на Java:

Алгоритм:

Ссылки:

А137г

А137е

e-olimp 7365 — Молоко и пирожок

Ссылка на Ideone

Постановка задачи

Задача A278

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

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

Тесты :

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

Ссылка на Ideone

Постановка задачи

Задача A278

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

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

Тесты :

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

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

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

Код

Тесты

Решение

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

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

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

Условие

Решение

Код

Тест

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

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

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

Код

Тесты

Решение

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

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

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

Условие

Решение

Код

Тест

В этот раздел входят задачи, читающие и обрабатывающие некоторый поток входных данных. В основном данные будут поступать или записываться в стандартные потоки ввода вывода. Основная особенность этих задач состоит в том, что поступающие данные не следует запоминать — после обработки очередного значения программа никогда к нему не возвращается. Такие задачи следует отличать от задач в которых входные данные необходимо сначала сохранить в памяти, а потом выполнить их обработку.
Например, если Вам нужно отыскать самое большое число во входном потоке, то это потоковая задача — запоминать нужно только текущее предполагаемое максимальное значение.
Если же в задаче, например, требуется вывести числа из входного потока в измененном порядке (в обратном порядке, по возрастанию или убыванию), то задача к потоковым не относится. Все числа нужно хранить в оперативной памяти во время выполнения программы. Такие задачи относятся к разделу «Массивы» или другим структурам данных.
В некоторых задачах требуется, например, поменять местами чётные и нечётные буквы вводимого текста. Естественно, хранить весь текст необходимости нет, но нужно запоминать предыдущую букву. Это тоже потоковая задача — используется всего одна или несколько переменные простых типов,
Формально задачи этого типа определяются так — последовательная обработка входного потока данных сколь угодно длинного потока входных данных при использовании постоянного объёма оперативной памяти.

28/05/2017 by Anh Tuan

Условие
Даны натуральное число [latex]n[/latex], действительный числа [latex]x[/latex], [latex]a_{n}, a_{n-1}, \ldots, a_{0}[/latex]. Вычислить используя схему Горнера, значение [latex]a_{n}{x}^{n} + a_{n-1}{x}^{n-1} + \cdots + a_{0}.[/latex] [latex]a_{n}{x}^{n} + a_{n-1}{x}^{n-1} + \cdots + a_{0} = \left( \ldots \left(a_{n}{x} + a_{n-1}\right)x + \cdots + a_{1}\right)x + a_{0}.[/latex]

package lab4;
import java.util.Scanner;
public class Lab4 
{
    public static void main(String[] args) 
    {
        Scanner scanIn=new Scanner(System.in); 
        int n, x;
        n = scanIn.nextInt();
        x = scanIn.nextInt();
        int a[] = new int[n + 1];
        for (int i = n; i >= 0; --i) 
        {
            a[i] = scanIn.nextInt();
        }
        int s = a[n];
        for (int i = 1; i <= n; ++i) 
        {
            s *= x; 
            s += a[n - i];
        }
     
        System.out.println("S = " + s);
    }
}

package lab4;

import java.util.Scanner;

public class Lab4

{

public static void main(String[] args)

{

Scanner scanIn=new Scanner(System.in);

int n, x;

n = scanIn.nextInt();

x = scanIn.nextInt();

int a[] = new int[n + 1];

for (int i = n; i >= 0; --i)

{

a[i] = scanIn.nextInt();

}

int s = a[n];

for (int i = 1; i <= n; ++i)

{

s *= x;

s += a[n - i];

}

System.out.println("S = " + s);

}

Решение
Начинаем с коэффициента с рядом с $latex X$-ом c максимальной степенью, у нас это элемент $latex { a }_{ n }$, мы последовательно умножаем его (коэффициент) на $latex X$, а потом прибавляем следующий считанный коэффициент и сохраняем полученное значение в переменной.
Это был пример решения для$latex n$=2 , если же$latex X$ > 2 , то мы должны выполнить алгоритм для $latex n$=2, после чего $latex X$ — 2 раз умножать полученное в переменной значение на $latex X$ и прибавлять последующий элемент.

Ideone.com

23/11/2016 by Коваль Максим

Задача Вычислить: Реализовать формулу, x+=[знак который зависит от четности/нечетности определяется отдельно для каждого элемента массива]*[соответствующий элемент массива]/[факториал текущего номера элемента массива].

Тест

n	последовательность	sum(wolframalpha)
2	0 0	0
2	5 8	-1
3	5 8 12	-3
4	1 2 3 24	1
5	0 0 0 2 3	0, 058333

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception{
                Scanner in = new Scanner(System.in);
                int n = in.nextInt();
                int[] a = new int[n];
                for (int i=0; i<n; i++){
                     a[i] = in.nextInt();
                }
                double sum=0;
                int f=1;
                for (int i=1; i<=n; i++){
                     f*=i;
                     double sign = (i%2==0) ? 1 : -1;
                     sum+=(sign*a[i-1])/f;
                }
                System.out.println(sum);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int[] a = new int[n];

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

a[i] = in.nextInt();

}

double sum=0;

int f=1;

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

f*=i;

double sign = (i%2==0) ? 1 : -1;

sum+=(sign*a[i-1])/f;

}

System.out.println(sum);

}

Решение:
В этой задаче главное правильно расставить знаки, так как это повлияет на результат.Поэтому мы заводим переменную $sign$ , которая будет следить за знаком. Далее проверяем чётность, если элемент делиться на 2 без остатка, то он получает знак $+$

http://ideone.com/ZB6a2C

16/10/2016 by Эдуард Брагар

Даны натуральное число [latex]n[/latex] и действительные числа [latex]a_{1}, a_{2}, \ldots, a_{n}[/latex]

Вычислить [latex]a_{1}+a_{2}+\cdots+a_{n}[/latex] и [latex]a_{1}a_{2}\cdots a_{n}[/latex].

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		double s = 0, p = 1, a = 0;
		for( int i = 0; i < n; i++ ){
			a = in.nextInt();
			s += a;
			p *= a;
		}
		System.out.println(s);
		System.out.print(p);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

double s = 0, p = 1, a = 0;

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

a = in.nextInt();

s += a;

p *= a;

}

System.out.println(s);

System.out.print(p);

}

n	[latex]a_{1}, a_{2}, \cdots, a_{n}[/latex]	s	p
2	3 4	7	12
4	1 3 5 7	16	105
6	2 2 3 3 4 4	18	576
1	9	9	9

В программе задаем число [latex]n[/latex]— количество элементов сумм и произведения и [latex]a[/latex]— элементы сумм и произведения; [latex]n[/latex] и [latex]a[/latex] вводим с клавиатуры. В цикле находим сумму и произведение.

http://ideone.com

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

Задача: Даны натуральное число n, действительные числа [latex]k_{1}, k_{2}, \dots, k_{n}[/latex] Вычислить [latex]\frac{k_{1}}{0!} + \frac{k_{2}}{1!} + \dots + \frac{k_{n}}{(n-1!)} [/latex]

Тесты

Число-n	Действительные числа	Результат
5	4 5 6 7 8	13,5
7	5 4 7 9 2 8 3	14,1542
3	6 9 3	16,5

Код:

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

class Ideone{
	public static void main (String[] args) throws java.lang.Exception{
		double k;
		double d = 0;
		int b=1;
		Scanner x = new Scanner(System.in);
		int n=x.nextInt();
		for (int i=1;i<=n;i++){
			k = x.nextDouble();
			k/=b;
			b*=i;
			d+=k;
		}
		System.out.print(d);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone{

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

double k;

double d = 0;

int b=1;

Scanner x = new Scanner(System.in);

int n=x.nextInt();

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

k = x.nextDouble();

k/=b;

b*=i;

d+=k;

}

System.out.print(d);

}

Решение:

Вводим n, k (действительные числа);
Получаем очередное действительное число k.
Делим на факториал и суммируем;

Решение на Ideone

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

Задача:
Даны действительные числа [latex]a_{1}, a_{2},\ldots[/latex] .
Известно, что [latex]a_{1} > 0,[/latex] и что среди [latex]a_{2}, a_{3},\ldots[/latex] есть хотя бы одно отрицательное число.
Пусть [latex]a_{1},\ldots,a_{n}[/latex] — члены данной последовательности, предшествующие первому отрицательному члену([latex]n[/latex] заранее неизвестно)
Получить:
г) среднее геометрическое [latex]a_{1},\ldots,a_{n}[/latex].

Тесты:

Последовательность	Среднее геометрическое
3 6 8 -9 4 5	5.24
13 14 1 4 5 6 -8 1 12	5.29
2 -3 4	2.00
2 2 2 -3 2 3 4 5	2.00
79 3 0.05	2.28

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

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

class Ideone {
	public static void main (String[] args) {
		Scanner x = new Scanner(System.in);
		double p = 1, a ;
		int c = 0;
		while( x.hasNext() ) {
			a = x.nextDouble();
			if(a >= 0) {
				c++;
				p*=a;
			} else break;
		}
		System.out.printf("%.2f", Math.pow(p,1.0/c) );
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

Scanner x = new Scanner(System.in);

double p = 1, a ;

int c = 0;

while( x.hasNext() ) {

a = x.nextDouble();

if(a >= 0) {

c++;

p*=a;

} else break;

}

System.out.printf("%.2f", Math.pow(p,1.0/c) );

}

Алгоритм:

Считывать числа с потока ввода. Умножаем числа пока не встретится отрицательное. После чего извлекаем корень используя данные счетчика.
Формула для нахождения Среднего геометрического : [latex]a_{gm} = \sqrt[n]{a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n}}[/latex] Рабочий код на ideone.com

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

Даны натуральные числа $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

06/07/2016 by Владислав Козачков

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

Дан простой неориентированный невзвешенный граф. Требуется для каждой вершины подсчитать ее степень.

В первой строчке находится число $1 \leq N \leq 1000$ . В следующих $N$ строчках находится матрица смежности.

Выведите $N$ чисел – степени всех вершин.

Ввод	Вывод
2 0 1 1 0	1 1
3 0 1 0 1 0 1 0 1 0	1 2 1
3 0 1 0 1 1 1 0 1 0	1 4 1
5 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1	6 1 6 1 6
5 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1	1 3 4 3 3
5 0 1 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0	4 1 4 1 4
5 1 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0	3 3 2 1 1

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int N;
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		String strout = new String();
		for (int i = 0; i < N; i++) {
			int counter = 0;
			int x;
			for (int j = 0; j < N; j++) {
				x = scan.nextInt();
				if (x > 0) counter += (i == j? 2 : 1);
			}
			strout += counter + " ";
		}
		System.out.print(strout);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

int N;

Scanner scan = new Scanner(System.in);

N = scan.nextInt();

String strout = new String();

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

int counter = 0;

int x;

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

x = scan.nextInt();

if (x > 0) counter += (i == j? 2 : 1);

}

strout += counter + " ";

}

System.out.print(strout);

}

Для решении задачи даже не нужно запоминать значения элементов матрицы. Выполняем данные действия $N$ раз, для каждой строки матрицы. Храним ответ в переменной $counter$ , изначально $0$ . По очереди считываем все ее элементы и, если текущий элемент равен $1$ , то прибавляем степени $2$ , если элемент принадлежит главной диагонали (так как тогда это ребро является петлей, а при подсчете степени ребро-петля учитывается дважды), иначе прибавляем $1$ . Формируем строку-результат и выводим её.

Рабочий код для тестирования на Ideone.com: Ideone.com

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

Даны натуральное число [latex]n[/latex], действительные числа [latex]a_{1}, a_{2}, \ldots a_{n}[/latex].
Вычислить: [latex]a_{1},-a_{1}a_{2},a_{1}a_{2}a_{3}, \ldots (-1)^{n+1}a_{1}a_{2} \ldots a_{n}[/latex].

Решение. Вводим переменную [latex]n[/latex], переменную a(куда будем считывать наши числа), а так же [latex]f[/latex]-произведение введенных чисел. Каждый раз в цикле уже введенные числа умножаются на следующее число взятое с противоположным знаком, а изначально [latex]»f»[/latex] равна [latex]»-1″[/latex] так как «Очередное произведение отличается от предыдущего сомножителем [latex](-a_{i})[/latex]».

Тесты:
[latex]n=3[/latex]

Числа[latex](a_{n})[/latex]	Результат
1	1
2	-2
3	6

[latex]n=7[/latex]

Числа[latex](a_{n})[/latex]	Результат
1.8	1.8
3.9	-7.02
0.0001	0.000702
-79	0.055458
456.98	-25.3432
0.9001	22.8114
4	-91.2456

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

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

class Ideone {
	public static void main (String[] args) {
		int n; //Количество вводимых чисел.
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		double a,f; //а-переменна для считывания чисел, f-произведения введенных чисел, m-результат из f умноженый на -1 в степени n+1.
		f = -1;
		for (int k=1; k<=n; ++k) {
			a = sc.nextDouble();
			f *= -a;
			System.out.print(f);
			if (k < n) System.out.print(", ");
			else System.out.print(".");
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

int n; //Количество вводимых чисел.

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

double a,f; //а-переменна для считывания чисел, f-произведения введенных чисел, m-результат из f умноженый на -1 в степени n+1.

f = -1;

for (int k=1; k<=n; ++k) {

a = sc.nextDouble();

f *= -a;

System.out.print(f);

if (k < n) System.out.print(", ");

else System.out.print(".");

}

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

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

Даны натуральные [latex]n[/latex], действительные [latex]a_1,\ldots, a_n[/latex].

Вывести: [latex]a_1+1!, a_2 +2!,\ldots, a_n+n![/latex].

Тесты:

n	a1	a2	a3	a4
4	1	2	3	4	Output	2	4	9	28
4	0.1	0.2	0.3	0.4	Output	1.1	2.2	6.3	24.4

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

class Main {
	
	public static void main (String[] args) throws java.lang.Exception {
		
		int n;
		double a, fact = 1.0;
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt(); //читаем n
		
		for(int k = 1; k <= n; k++) {
			
			a = scanner.nextDouble(); //читаем из потока k-ый элемент 
			fact *= k; //увеличиваем фаториал
			System.out.print( (a+fact) + " "); //выводим сумму цифры из потока и факториала
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

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

int n;

double a, fact = 1.0;

Scanner scanner = new Scanner(System.in);

n = scanner.nextInt(); //читаем n

for(int k = 1; k <= n; k++) {

a = scanner.nextDouble(); //читаем из потока k-ый элемент

fact *= k; //увеличиваем фаториал

System.out.print( (a+fact) + " "); //выводим сумму цифры из потока и факториала

}

www.ideone.com

Описываем переменную факториала и переменную из потока типа [latex]double[/latex]. Запускаем цикл for, от [latex]1[/latex] до [latex]n[/latex]. Дальше в теле цикла описываем чтение элементов, увеличение факториала и вывод суммы цифр из потока и факториала.

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

Задача на e-olimp.

Ученикам первого класса дополнительно дают стакан молока и пирожок, если вес первоклассника менее 30 кг. В первых классах школы учится n учеников. Стакан молока имеет емкость 200 мл, а упаковки молока – 0,9 л. Определить количество дополнительных пакетов молока и пирожков, необходимых каждый день.

Возьмем количество пирожков за счетчик. Используя for найдем количество пирожков для детей, вес которых не превышает 30кг. По количеству пирожков мы можем найти количество упаковок молока. При этом мы можем получить не целое число. Чтобы избежать этого, используем метод ceil из класса Math для округления до целого.

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		 Scanner in = new Scanner(System.in);
		 int n = in.nextInt();
		 int pie = 0; 
  		 for (int i=0; i<n; i++)
  		 {
  		 	int w = in.nextInt();
  		 	if (w < 30)
  		 		pie++;
  		 }
  		 int pack = (int)Math.ceil((pie*0.2)/0.9);
  		 System.out.print(pack+ " " + pie);
	}
}

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int pie = 0;

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

{

int w = in.nextInt();

if (w < 30)

pie++;

}

int pack = (int)Math.ceil((pie*0.2)/0.9);

System.out.print(pack+ " " + pie);

}

Ссылка на Ideone.

Входящие данные		Выходящие данные
n	w(вес)	pack	pie
4	30 29 40 25	1	2
7	21 20 22 29 26 27 26	2	7

Проверка решения на e-olimp.

$latex { a }_{ n }$

$latex { a }_{ n-1 }$

$latex { a }_{ n-2 }$

$latex { a }_{ n-3 }$