e-olymp 2820. Перемещение коня

30/06/2015 by Янішевська Альона Русланівна

Задача с сайта e-olimp №2820. Перемещение коня

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

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

Ваша задача состоит в том, чтобы написать программу, которая принимает координаты двух клеток a и b в качестве входных данных, а затем определяет количество ходов конем кратчайшим путём из a в b.

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

Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква (a—h), задающая столбец и второй – цифра (1—8), задающая строку на шахматной доске.

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

Для каждого теста вывести одну строку следующего содержания: «To get from xx to yy takes n knight moves.» (см. пример выходных данных).

Тесты:

Пример входных данных	Пример выходных данных
e2 e4	To get from e2 to e4 takes knight 2 moves.
a1 b2	To get from a1 to b2 takes knight 4 moves.
b2 c3	To get from b2 to c3 takes knight 2 moves.
a1 h8	To get from a1 to h8 takes knight 6 moves.
a1 h7	To get from a1 to h7 takes knight 5 moves.
h8 a1	To get from h8 to a1 takes knight 6 moves.
b1 c3	To get from b1 to c3 takes knight 1 moves.
f6 f6	To get from f6 to f6 takes knight 0 moves.

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

#include<cstdio>
#include<queue>
using namespace std;
 
char a, b;
int nx, ny, tx, ty;
int mx[] = { -1, -1, 1, 1, -2, -2, 2, 2 };
int my[] = { 2, -2, 2, -2, 1, -1, 1, -1 };
int A[8][8];
 
int main() {
    while(scanf("%c%d %c%d\n", &a, &ny, &b, &ty) == 4) {
        nx = a - 'a';
        ny--;
        tx = b - 'a';
        ty--;
        A[nx][ny] = 0;
        queue< pair<int, int> > q;
        q.push(make_pair(nx, ny));
        while(!q.empty()) {
            pair<int, int> c = q.front();
            int x = c.first, y = c.second;
            if(x == tx && y == ty) break;
            q.pop();
            for(int i = 0; i < 8; i++) {
                if(x + mx[i] >= 0 && x + mx[i] < 8 && y + my[i] >= 0 && y + my[i] < 8) {
                    q.push(make_pair(x + mx[i], y + my[i]));
                    A[x + mx[i]][y + my[i]] =  A[x][y] + 1;
                }
            }
        }
        printf("To get from %c%d to %c%d takes %d knight moves.\n", a, ny + 1, b, ty + 1, A[tx][ty]);
    }
}

#include<cstdio>

#include<queue>

using namespace std;

char a, b;

int nx, ny, tx, ty;

int mx[] = { -1, -1, 1, 1, -2, -2, 2, 2 };

int my[] = { 2, -2, 2, -2, 1, -1, 1, -1 };

int A[8][8];

int main() {

while(scanf("%c%d %c%d\n", &a, &ny, &b, &ty) == 4) {

nx = a - 'a';

ny--;

tx = b - 'a';

ty--;

A[nx][ny] = 0;

queue< pair<int, int> > q;

q.push(make_pair(nx, ny));

while(!q.empty()) {

pair<int, int> c = q.front();

int x = c.first, y = c.second;

if(x == tx && y == ty) break;

q.pop();

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

if(x + mx[i] >= 0 && x + mx[i] < 8 && y + my[i] >= 0 && y + my[i] < 8) {

q.push(make_pair(x + mx[i], y + my[i]));

A[x + mx[i]][y + my[i]] = A[x][y] + 1;

}

printf("To get from %c%d to %c%d takes %d knight moves.\n", a, ny + 1, b, ty + 1, A[tx][ty]);

}

Данную задачу можно решить с помощью алгоритма поиска в ширину. Из начальной клетки мы ищем все возможные ходы пока не попадем в нужную клетку. Чтобы получить длину пути, нужно хранить длины путей до данной клетки в матрице и обновлять ее, по ходу продвижения (если новое значение меньше того, что записано в клетке — записываем его, а если больше — оставляем предыдущее). Длина в начальной клетке — 0, а длина в каждой последующей — 1.

Ссылка на засчитанное решение и код решения на ideone.

Related Images:

А700в

19/06/2015 by Янішевська Альона Русланівна

Задача. Дана квадратная матрица А порядка n. Получить матрицу AB; элементы матрицы B вычисляются по формуле:

[latex]b_{ij}=\left\{\begin{matrix}\frac{1}{i+j-1}&,if\: i<j\\ 0&,if\: i=j\\-\frac{1}{i+j-1}&other\: case\end{matrix}\right.[/latex]

[latex](i,j=1,\cdots, n)[/latex]

Тесты:

Размер матрицы	Входные данные	Результат	Комментарий
n=2	[latex]\begin{pmatrix}1&7\\3&2\end{pmatrix}[/latex]	[latex]\begin{pmatrix}-3,5&0,5\\-1&1,5\end{pmatrix}[/latex]	Пройден
n=3	[latex]\begin{pmatrix}1&2&3\\7&6&5\\4&8&9\end{pmatrix}[/latex]	[latex]\begin{pmatrix}-2&-0,25&0,83333\\-4,66667&2,25&3,83333\\-7&-0,25&3,333\end{pmatrix}[/latex]	Пройден

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

#include <iostream>
 
using namespace std;
 
int main() {
	int n;
	cin >> n;
	double A[n][n];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> A[i][j];
		}
	}
 
	double B[n][n];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			B[i][j] = 0;
			if (i < j){B[i][j] = 10 * 0.1 / ((i+1) + (j+1) -1);}
			else {
				if (i == j){B[i][j] = 0;}
				else {B[i][j] = -10 * 0.1 / ((i+1) + (j+1) -1);}
			}	
		}
	}
 
	double C[n][n];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			C[i][j] = 0;
			for(int k = 0; k < n; k++){
				C[i][j] += A[i][k] * B[k][j];
			}
		}
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cout << C[i][j] << " ";
		}
		cout << endl;
	}
 
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

double A[n][n];

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

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

cin >> A[i][j];

}

double B[n][n];

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

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

B[i][j] = 0;

if (i < j){B[i][j] = 10 * 0.1 / ((i+1) + (j+1) -1);}

else {

if (i == j){B[i][j] = 0;}

else {B[i][j] = -10 * 0.1 / ((i+1) + (j+1) -1);}

}

double C[n][n];

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

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

C[i][j] = 0;

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

C[i][j] += A[i][k] * B[k][j];

}

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

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

cout << C[i][j] << " ";

}

cout << endl;

}

return 0;

}

После ввода матрицы A, мы должны найти элементы матрицы B. Из условия задачи: [latex]b_{ij}=\left\{\begin{matrix}\frac{1}{i+j-1}&,if\: i<j\\ 0&,if\: i=j\\-\frac{1}{i+j-1}&other\: case\end{matrix}\right.[/latex] , при [latex](i,j=1,\cdots, n)[/latex].

Для нахождения [latex]b_{ij}[/latex] используется условный оператор if в цикле for. Матрица C — результат умножения матрицы A на матрицу B, которое также производим в цикле for.

Код программы можно посмотреть здесь.

Решение на Java:

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 A[][];
		A = new double [n][];
		for(int i=0; i<n; i++){
			A[i] = new double [n];   
			for(int j=0; j<n; j++){
				A[i][j] = in.nextDouble();
			}
		}
		double B[][];
		B = new double [n][];
		for(int i=0; i<n; i++){
			B[i] = new double [n];  
			for(int j=0; j<n; j++){
				B[i][j]=0;
				if (i<j){
					B[i][j]=10*0.1/((i+1)+(j+1)-1);
				}
				else{
					if (i==j){
						B[i][j]=0;
					}
					else {
							B[i][j]=-10*0.1/((i+1)+(j+1)-1);
					}
				}	
			}
		}
		double C[][];
    	C = new double [n][];
		for(int i=0; i<n; i++){
		 	C[i] = new double [n];  
			for(int j=0; j<n; j++){
				C[i][j]=0;
				for(int k=0; k<n; k++){
					C[i][j]+=A[i][k]*B[k][j];
				}
			}
		}
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				System.out.print(C[i][j]+" "); 
			}
		System.out.println();
		}
	}
}

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 A[][];

A = new double [n][];

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

A[i] = new double [n];

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

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

}

double B[][];

B = new double [n][];

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

B[i] = new double [n];

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

B[i][j]=0;

if (i<j){

B[i][j]=10*0.1/((i+1)+(j+1)-1);

}

else{

if (i==j){

B[i][j]=0;

}

else {

B[i][j]=-10*0.1/((i+1)+(j+1)-1);

}

double C[][];

C = new double [n][];

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

C[i] = new double [n];

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

C[i][j]=0;

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

C[i][j]+=A[i][k]*B[k][j];

}

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

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

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

}

System.out.println();

}

Ссылка на решение.

Related Images:

Ю3.35

21/12/2014 by Янішевська Альона Русланівна

Задача. [latex]\arctan(x)=x-\frac{x^{3}}{3}+\frac{x^{5}}{5}-\cdots (-1)^{n}\frac{x^{2n+1}}{2n+1}+\cdots[/latex]

Численно убедиться в справедливости равенства, для чего для заданного значения аргумента x вычислить левую его часть и разложение, стоящее в правой части, с заданной погрешностью [latex]\varepsilon[/latex]. Испытать разложение на сходимость при разных значениях аргумента, оценить скорость сходимости, для чего вывести число итераций n (слагаемых или cомножителей), необходимых для достижения заданной точности.

Тесты:

x	[latex]\varepsilon[/latex]	left	right	n	Разность	Комментарий
1	0.3	0,785398	1	0	0,214602	Пройден
0.6	0.02	0.54042	0.528	1	0.0124195	Пройден
0.7	0.0002	0.610726	0.610631	7	9.52374е-05	Пройден
0.7	0.000002	0.610726	0.610728	12	1.67214е-06	Пройден
0.7	0.00000000001	0.610726	0.610726	28	8.34648е-12	Пройден

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

#include <iostream>
#include <math.h>
using namespace std;

int main() {
	double x, eps, left, right, d, s;
	cin >> x >> eps;
	int n=0;
	left=atan(x);
	right=x;
	d=fabs(left-right);
	s=x;
	while(d>eps)
	{
		n++;
		s*=(-1)*x*x;
		right+=s/(2*n+1);
		d=fabs(left-right);
	}
	cout << "left=" << left << " right=" << right << " n=" << n << " d=" << d;
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

double x, eps, left, right, d, s;

cin >> x >> eps;

int n=0;

left=atan(x);

right=x;

d=fabs(left-right);

s=x;

while(d>eps)

{

n++;

s*=(-1)*x*x;

right+=s/(2*n+1);

d=fabs(left-right);

}

cout << "left=" << left << " right=" << right << " n=" << n << " d=" << d;

return 0;

}

В начале мы подставляем аргумент x в левую часть равенства и подсчитываем ее. Затем проверяем разность между правой частью и левой, если ее модуль меньше заданного [latex]\varepsilon[/latex], то выводим результат, а если нет, то в цикле while мы считаем последовательность до тех пор пока их разность не будет меньше [latex]\varepsilon[/latex]. Последовательность задается в цикле рекурентно, поэтому т.к. первый член последовательности будет равен x, то заведем переменную s, равную x, которая будет определять чему равен числитель дроби, домножая предыдущий на [latex](-1)x^{2}[/latex] . После этого программа выводит значение левой и правой части, их разницу и количество итераций для заданной погрешности.

Код можно проверить здесь.

Решение на Java:

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);
    	double x, eps, left, right, d, s;
    	int n=0;
    	x = in.nextDouble();
    	eps = in.nextDouble();
	    left=Math.atan(x);
	    right=x;
	    d=Math.abs(left-right);
	    s=x;
		while(d>eps)
		{
			n++;
			s*=(-1)*x*x;
			right+=s/(2*n+1);
			d=Math.abs(left-right);
		}
		System.out.print("left="+left+" right="+right+" n="+n+" d="+d); 
	}
}

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);

double x, eps, left, right, d, s;

int n=0;

x = in.nextDouble();

eps = in.nextDouble();

left=Math.atan(x);

right=x;

d=Math.abs(left-right);

s=x;

while(d>eps)

{

n++;

s*=(-1)*x*x;

right+=s/(2*n+1);

d=Math.abs(left-right);

}

System.out.print("left="+left+" right="+right+" n="+n+" d="+d);

}

Ссылка на решение.

Related Images:

А396

21/12/2014 by Янішевська Альона Русланівна

Задача. Дана действительная квадратная матрица порядка n. Построить последовательность действительных чисел [latex]a_{1}\cdots a_{n}[/latex] по правилу: если в i-й строке матрицы элемент, принадлежащий главной диагонали, отрицателен, то [latex]a_{i}[/latex] равно сумме элементов i-й строки, предшествующих первому отрицательному элементу, в противном случае [latex]a_{i}[/latex] равно сумме последних элементов i-й строки, начиная с первого по порядку неотрицательного элемента.

Тесты:

Данная матрица	Последовательность	Комментарий
[latex]\begin{Vmatrix}1 & 2 & -3 & 4\\ 3 & 5 & 6 & 7\\ 1 & 3 & 0 & 6\\ -5 & 7 & 2 & -9\end{Vmatrix}[/latex]	4 21 10 0	Пройден
[latex]\begin{Vmatrix}1 & -2 & 3\\ -7 & -3 & 0\\ 5 & 5 & 2 \end{Vmatrix}[/latex]	2 0 12	Пройден
[latex]\begin{Vmatrix}7 & 7 & 9 & 3\\ 0 & 5 & 0 & 7\\ 4 & 7 & -7 & 2\\ 1 & -4 & 8 & -3\end{Vmatrix}[/latex]	26 12 11 1	Пройден

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

#include<iostream>
using namespace std;
int main()
{
		int n;
		cin>>n;
		int **a = new int*[n]; 
        for (int i=0;i<n;i++)
           a[i] = new int [n];
        
		int *b = new int [n];
		
		for(int i = 0; i < n; i++){
			a[i] = new int [n];
			b[i] = 0;
			for(int j = 0; j < n; j++){
				cin>>a[i][j];
			}
		}
		for(int i = 0; i < n; i++){
			if(a[i][i] < 0){
				for(int j = 0; j < i; j++){
					if(a[i][j] < 0) break;
					b[i]+=a[i][j];
				}
			} 
			else{
				int k;
				for(k = 0; k < n; k++){
					if(a[i][k] >= 0) break;
				}	
				for(int j = k; j < n; j++){
					b[i]+=a[i][j];
				}
			}	
		}
 		for(int i = 0; i < n; i++){
 			cout<<b[i]<<" "; 
		}
	}

#include<iostream>

using namespace std;

int main()

{

int n;

cin>>n;

int **a = new int*[n];

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

a[i] = new int [n];

int *b = new int [n];

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

a[i] = new int [n];

b[i] = 0;

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

cin>>a[i][j];

}

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

if(a[i][i] < 0){

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

if(a[i][j] < 0) break;

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

}

else{

int k;

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

if(a[i][k] >= 0) break;

}

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

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

}

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

cout<<b[i]<<" ";

}

Для начала мы должны обнулить матрицу [latex]b_{1}\cdots b_{n}[/latex], элементы которой являются суммами элементов i-х строк входной матрицы, которую мы также задаем. А далее, с помощью циклов for , можно оценить диагональные элементы заданной матрицы. И следуя условию, если они отрицательные, то в [latex]b_{i}[/latex] мы просуммируем все элементы данной строки, если они положительные, до первого отрицательного в строчке, а если они положительные, то [latex]b_{i}[/latex] будет равно сумме последних элементов строки (т.е. после диагонального) начиная с первого по порядку неотрицательного элемента. И в конце выводим конечную последовательность [latex]b_{1}\cdots b_{n}[/latex].

Код можно проверить здесь.

Решение на Java:

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;
		n = in.nextInt();
		int a[][];
		int b[] = new int [n];
		a  = new int[n][];
		for(int i = 0; i < n; i++){
			a[i] = new int [n];
			b[i] = 0;
			for(int j = 0; j < n; j++){
				a[i][j] = in.nextInt();
			}
		}
		for(int i = 0; i < n; i++){
			if(a[i][i] < 0){
				for(int j = 0; j < i; j++){
					if(a[i][j] < 0) break;
					b[i]+=a[i][j];
				}
			} 
			else{
				int k;
				for(k = 0; k < n; k++){
					if(a[i][k] >= 0) break;
				}	
				for(int j = k; j < n; j++){
					b[i]+=a[i][j];
				}
			}	
		}
 		for(int i = 0; i < n; i++){
 			System.out.print(b[i] + " "); 
		}
	}
}

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;

n = in.nextInt();

int a[][];

int b[] = new int [n];

a = new int[n][];

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

a[i] = new int [n];

b[i] = 0;

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

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

}

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

if(a[i][i] < 0){

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

if(a[i][j] < 0) break;

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

}

else{

int k;

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

if(a[i][k] >= 0) break;

}

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

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

}

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

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

}

Код на Java.

Related Images:

Ю11.3

20/12/2014 by Янішевська Альона Русланівна

Задача. Метод Эйткена-Стеффенсона (развитие метода простой итерации). Найти решение уравнения [latex]x=\varphi(x)[/latex] методом Эйткена-Стеффенсона, в котором от заданного начального [latex]x_{0}[/latex] три очередных приближения находятся по формулам: [latex]x_{n+1}=\varphi (x_{n})[/latex]; [latex]x_{n+2}=\varphi (x_{n+1})[/latex]; [latex]x_{n+3}=\frac{x_{n}x_{n+2}-x_{n+1}^{2}}{x_{n}-2x_{n+1}+x_{n+2}}[/latex]. Процесс продолжается до достижения одного из условий: [latex]\left | x_{n+3}-x_{n+2} \right |<\varepsilon[/latex] или [latex]x_{n}-2x_{n+1}+x_{n+2}=0[/latex].

Решение. В начале мы задаем начальное приближение [latex]x=x_{0}[/latex] и [latex]\varepsilon[/latex]. Нам понадобится цикл с постусловием. Далее вычисляем первое приближение [latex]x_{1}=\varphi (x_{0})[/latex] и второе приближение [latex]x_{2}=\varphi (x_{1})[/latex]. Находим по формуле [latex]x=\frac{x_{0}x_{2}-x_{1}^{2}}{x_{0}-2x_{1}+x_{2}}[/latex]. Далее мы проверяем выполнение условия выхода из цикла: если [latex]\left | x-x_{0} \right |>\varepsilon[/latex] (нужно проверять разность [latex]\left | x-x_{0} \right |>\varepsilon[/latex], а не [latex]\left | x-x_{2} \right |>\varepsilon[/latex]) и [latex]x_{0}-2x_{1}+x_{2}\neq 0[/latex] тогда цикл продолжается, но если хотя бы одно из условий выполнено, то мы получаем, что [latex]x[/latex] — решение уравнения [latex]x=\varphi(x)[/latex].

Данная программа написана для функции [latex]9.2x^{3}+3.3x^{2}+4x-1[/latex].

Тесты:

x	[latex]\varepsilon[/latex]	Корень уравнения	Комментарий
2	0.005	1.99889	Пройден
1	0.00002	0.233905	Пройден
-4	0.0005	-3.99981	Пройден

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

#include <iostream>
#include <math.h>
using namespace std;

double f(double x)
{
	return 9.2*x*x*x+3.3*x*x+4*x-1; //задаем уравнение
}

double es(double x, double eps) //с помощью метода Эйтнена-Стеффенсона считаем приближения
{
	double x0, x1, x2, d;
	do
	{
		x0=x;
		x1=f(x0);
		x2=f(x1);
		d=x0-2*x1+x2;
		if (d!=0)
		{
			x=(x0*x2-x1*x1)/d;
		}
		else return x;
	}
	while(fabs(x-x0)>eps); //условие окончания подсчета 
	return x;
}

int main() {
	double x, eps;
	cin >> x >> eps;
	cout << es(x, eps);
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

double f(double x)

{

return 9.2*x*x*x+3.3*x*x+4*x-1; //задаем уравнение

}

double es(double x, double eps) //с помощью метода Эйтнена-Стеффенсона считаем приближения

{

double x0, x1, x2, d;

{

x0=x;

x1=f(x0);

x2=f(x1);

d=x0-2*x1+x2;

if (d!=0)

{

x=(x0*x2-x1*x1)/d;

}

else return x;

}

while(fabs(x-x0)>eps); //условие окончания подсчета

return x;

}

int main() {

double x, eps;

cin >> x >> eps;

cout << es(x, eps);

return 0;

}

Код программы можно проверить здесь.

Решение на Java:

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

class Ideone
{
	static double f(double x)
	{
	   return 9.2*x*x*x+3.3*x*x+4*x-1; 
	}
	
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner  in = new Scanner(System.in);
		double x, eps, x0, x1, x2, d;
		x = in.nextDouble();
		eps = in.nextDouble();
		do{
			x0=x;
			x1=f(x0);
			x2=f(x1);
			d=x0-2*x1+x2;
			if (d!=0)
			{
				x=(x0*x2-x1*x1)/d;
			}
			else break;
    	} 	
    	while(Math.abs(x-x0)>eps);
    	System.out.print(x+" "); 
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

static double f(double x)

{

return 9.2*x*x*x+3.3*x*x+4*x-1;

}

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

{

Scanner in = new Scanner(System.in);

double x, eps, x0, x1, x2, d;

x = in.nextDouble();

eps = in.nextDouble();

do{

x0=x;

x1=f(x0);

x2=f(x1);

d=x0-2*x1+x2;

if (d!=0)

{

x=(x0*x2-x1*x1)/d;

}

else break;

}

while(Math.abs(x-x0)>eps);

System.out.print(x+" ");

}

Ссылка на решение.

Related Images:

А98

03/11/2014 by Янішевська Альона Русланівна

Задача. Пусть [latex]a_{1}=b_{1}=1; a_{k}=3b_{k-1}+2a_{k-1}; b_{k}=2a_{k-1}+b_{k-1}[/latex], [latex]k=\overline{2, \infty }[/latex]. Дано натуральное [latex]n[/latex]. Найти [latex]\sum_{i=1}^{n}\frac{2^{k}}{(1+a_{k}^{2}+b_{k}^{2})k!}[/latex].

Тесты:

n	[latex]\sum_{i=1}^{n}\frac{2^{k}}{(1+a_{k}^{2}+b_{k}^{2})k!}[/latex]	Комментарий
2	0.0596538	Пройден
4	0.0597339	Пройден
20	0.059734	Пройден

Код:

#include <iostream>
#include <math.h>
using namespace std;

int main() {
      int n, a=1, as=a, b=1;
      double S=0.0, u=2.0;
      cin >> n;
      for(int i=1, k=2; i<=n; i++, k++)
      {
          a=3*b+2*a;
          b=2*as+b;
          u*=(2.0/k);
          S+=u*(1.0/(1+a*a+b*b));
          as=a; //запоминание переменной а
      }
       printf("%7lf", S);
       return 0;
 }

#include <iostream>

#include <math.h>

using namespace std;

int main() {

int n, a=1, as=a, b=1;

double S=0.0, u=2.0;

cin >> n;

for(int i=1, k=2; i<=n; i++, k++)

{

a=3*b+2*a;

b=2*as+b;

u*=(2.0/k);

S+=u*(1.0/(1+a*a+b*b));

as=a; //запоминание переменной а

}

printf("%7lf", S);

return 0;

}

Для решения данной задачи понадобилось ввести переменную [latex]n[/latex], которая показывает какое количество раз нужно повторить операцию сложения. В цикле for вычисляется сумма, по заданной формуле. Далее последовательность можно задать рекурентно: чтобы каждый раз не считать [latex]\frac{2^{k}}{k!}[/latex], мы заводим переменную u, равную изначально двум, потому что k начинается с 2, и u каждый раз мы будем домножать на [latex]\frac{2}{k}[/latex]. Далее остается лишь посчитать a и b (переменная [latex]as[/latex] запоминает переменную [latex]a[/latex] для последующего вычисления переменной [latex]b[/latex]) и поставить в формулу. Для проверки выполнения программы можно воспользоваться ссылкой.

Решение на Java:

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, a=1, as=a, b=1;
		double sum=0.0, u=2.0;
		n = in.nextInt();
		for(int i=1, k=2; i<=n; i++, k++)
      	{
      		a=3*b+2*a;
      		b=2*as+b;
      		u*=(2.0/k);
      		sum+=u*(1.0/(1+a*a+b*b));
      		as=a;
      	}
       System.out.printf(Locale.US, "%.8f", 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, a=1, as=a, b=1;

double sum=0.0, u=2.0;

n = in.nextInt();

for(int i=1, k=2; i<=n; i++, k++)

{

a=3*b+2*a;

b=2*as+b;

u*=(2.0/k);

sum+=u*(1.0/(1+a*a+b*b));

as=a;

}

System.out.printf(Locale.US, "%.8f", sum);

}

Ссылка на решение.

Related Images:

Ю4.1

03/11/2014 by Янішевська Альона Русланівна

Задача. Разделение по знаку. В массиве С(n) подсчитать количество отрицательных и сумму положительных элементов.

Тесты:

n	Входной массив	Кол-во отрицательных элементов	Сумма положительных элементов	Комментарий
5	1.01 3 7.11 -1 -0.99	2	11.12	Пройден
14	1 2 -4.2 3.5 6.2 8 11 -144 288 9.2 -22 12 -13.5 14	4	354.9	Пройден

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

#include <iostream>
using namespace std;

int main() {
	int n, k=0; 
	double S=0;
	cin >> n;
	double C[n];
	for(int i=0; i<n; i++)
	{
		cin >> C[i];
		if (C[i]<0)
			k++;
		else S+=C[i];
	}
	cout << "Negative numbers: " << k << "  The sum of positive numbers: " << S;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, k=0;

double S=0;

cin >> n;

double C[n];

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

{

cin >> C[i];

if (C[i]<0)

k++;

else S+=C[i];

}

cout << "Negative numbers: " << k << " The sum of positive numbers: " << S;

return 0;

}

В ходе решении данной задачи я использую цикл for, в котором сначала считываются, а затем обрабатываются данные. Переменная-счётчик [latex]k[/latex] нужна для того, чтобы узнать кол-во отрицательных элементов. А если встречаются неотрицательные элементы, то подсчитывается их сумма в переменной [latex]S[/latex]. Для проверки выполнения программы можно воспользоваться ссылкой.

Решение на Java:

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, negative=0; 
		double sum=0;
		n = in.nextInt();
		double numberArray[] = new double [n];
		for(int i=0; i<n; i++)
		{
			numberArray[i] = in.nextDouble();
			if (numberArray[i]<0) negative++;
			else sum+=numberArray[i];
		}
		System.out.print("Negative numbers: " + negative + "  The sum of positive numbers: " + 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, negative=0;

double sum=0;

n = in.nextInt();

double numberArray[] = new double [n];

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

{

numberArray[i] = in.nextDouble();

if (numberArray[i]<0) negative++;

else sum+=numberArray[i];

}

System.out.print("Negative numbers: " + negative + " The sum of positive numbers: " + sum);

}

Ссылка на решение.

Related Images:

А136в

03/11/2014 by Янішевська Альона Русланівна

Задача. Даны натуральное число [latex]n[/latex], действительные числа [latex]a_{1},…,a_{n}[/latex]. Вычислить: [latex]\left | a_{1} \right |+…+\left | a_{n} \right |[/latex].

Тесты:

[latex]n[/latex]	[latex]a_{1},…,a_{n}[/latex]	Результат	Комментарий
7	2 -1.1 4 -3.4 -6 1 2	19.5	Пройден
3	-6.73 2.01 5.99	14.73	Пройден

#include <iostream>
#include <math.h>
using namespace std;

int main() {
	int n; 
	double a, S=0;
	cin >> n;
  	for(int i=1; i<=n; i++)
  	{
		cin >> a;
		S+=fabs(a);
  	}
	cout << S;
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

int n;

double a, S=0;

cin >> n;

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

{

cin >> a;

S+=fabs(a);

}

cout << S;

return 0;

}

Вводим количество элементов ([latex]n[/latex]). После этого в цикле for считываем сами элементы [latex]a_{1},…,a_{n}[/latex] и вычисляем сумму их модулей. Для проверки выполнения программы можно воспользоваться ссылкой.

Related Images:

А58а

04/10/2014 by Янішевська Альона Русланівна

Задача. Дано действительное число [latex]a[/latex]. Для функции [latex]f\left(x \right)[/latex], график которой изображен, вычислить [latex]f\left(a \right)[/latex].

a	[latex]f\left(a \right)[/latex]	Комментарий
7	-49	Пройден
0	0	Пройден
-2	2	Пройден

#include <stdio.h>
#include <math.h>

int main() {
	double a, y;
	scanf("%lf", &a);
	if (a > 0) y = -a * a;
	else y = -a;
	printf("%lg",y);
	return 0;
}

#include <stdio.h>

#include <math.h>

int main() {

double a, y;

scanf("%lf", &a);

if (a > 0) y = -a * a;

else y = -a;

printf("%lg",y);

return 0;

}

Для решения данной задачи требуется лишь проверка знака числа [latex]a[/latex]. Если [latex]a> 0[/latex], то [latex]f\left(a \right)[/latex] вычисляется как [latex]-a^{2}[/latex], а если [latex]a< 0[/latex], то [latex]f\left(a \right)[/latex] равна [latex]-a[/latex]. При [latex]a=0[/latex], [latex]f\left(a \right)=0[/latex]. Для проверки выполнения программы можно воспользоваться ссылкой.

Решение на Java:

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);
		double a, y;
		a = in.nextDouble();
		if (a > 0) y=-a*a;
		else y=-a;
		System.out.print(y); 
	}
}

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);

double a, y;

a = in.nextDouble();

if (a > 0) y=-a*a;

else y=-a;

System.out.print(y);

}

Ссылка на решение.

Related Images:

Ю2.1

04/10/2014 by Янішевська Альона Русланівна

Задача. Заданы три числа: [latex]a[/latex], [latex]b[/latex], [latex]c[/latex]. Определить, могут ли они быть сторонами треугольника, и если да, то определить его тип: равносторонний, равнобедренный, разносторонний. Замечание. Условие существования треугольника: [latex]a\leq b+c[/latex]; [latex]b\leq a+c[/latex]; [latex]c\leq a+b[/latex]. Нельзя исключать экстремальных случаев, когда одна (или несколько) сторон равны нулю либо когда одно из неравенств переходит в равенство (треугольник нулевой площади).

a	b	c	Тип треугольника	Комментарий
0	3	7	—	Не треугольник
-2	5	4	—	Не треугольник
1	3	4	Треугольник нулевой площади	Пройден
7	7	7	Равносторонний	Пройден
15	9	15	Равнобедренный	Пройден
3	4	5	Разносторонний	Пройден

#include <stdio.h>
#include <math.h>
 
int main() {
double a, b, c;
scanf("%lf %lf %lf", &a, &b, &c);
	if (a<=b+c && b<=a+c && c<=b+a)
	{
		if (a==b+c || b==c+a || c==a+b || a==0 || b==0 || c==0)
			printf("Треугольник нулевой площади");
	  	else if (a==b && b==c && c==a)
			printf("Равносторонний"); 
	  	else if (a==b ^ b==c ^ c==a)
			printf("Равнобедренный");
	  	else printf("Разносторонний");
	}
	else printf("Не треугольник");
 return 0;
}

#include <stdio.h>

#include <math.h>

int main() {

double a, b, c;

scanf("%lf %lf %lf", &a, &b, &c);

if (a<=b+c && b<=a+c && c<=b+a)

{

if (a==b+c || b==c+a || c==a+b || a==0 || b==0 || c==0)

printf("Треугольник нулевой площади");

else if (a==b && b==c && c==a)

printf("Равносторонний");

else if (a==b ^ b==c ^ c==a)

printf("Равнобедренный");

else printf("Разносторонний");

}

else printf("Не треугольник");

return 0;

}

После ввода чисел [latex]a [/latex], [latex]b [/latex], [latex]c [/latex] проверяем, есть ли равные нулю или есть ли сторона, равная сумме двух других сторон, если такие числа или такая сторона есть, то такой треугольник с нулевой площадью. Далее проверяем условие существования треугольника. Если в треугольнике все стороны равны, то он является равносторонним, если равны только две стороны-равнобедренным, а если нет равных между собой сторон, то треугольник разносторонний. Также мы проверяем, есть ли числа меньше нуля (если такие числа есть, то треугольника со сторонами [latex]a [/latex], [latex]b [/latex], [latex]c [/latex] не существует).

Для проверки выполнения программы можно воспользоваться ссылкой.

Решение на Java:

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);
		double a, b, c;
		a = in.nextDouble();
		b = in.nextDouble();
		c = in.nextDouble();
		if (a<=b+c && b<=a+c && c<=b+a)
		{
			if (a==b+c || b==c+a || c==a+b || a==0 || b==0 || c==0)
				System.out.print("Треугольник нулевой площади");
		  	else if (a==b && b==c && c==a)
				System.out.print("Равносторонний"); 
		  	else if (a==b ^ b==c ^ c==a)
				System.out.print("Равнобедренный");
		  	else System.out.print("Разносторонний");
		}
		else System.out.print("Не треугольник");
	}
}

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);

double a, b, c;

a = in.nextDouble();

b = in.nextDouble();

c = in.nextDouble();

if (a<=b+c && b<=a+c && c<=b+a)

{

if (a==b+c || b==c+a || c==a+b || a==0 || b==0 || c==0)

System.out.print("Треугольник нулевой площади");

else if (a==b && b==c && c==a)

System.out.print("Равносторонний");

else if (a==b ^ b==c ^ c==a)

System.out.print("Равнобедренный");

else System.out.print("Разносторонний");

}

else System.out.print("Не треугольник");

}

Ссылка на решение.

Related Images:

А23б

30/09/2014 by Янішевська Альона Русланівна

Задача. Треугольник задан длинами сторон. Найти длины медиан.

Длины сторон: [latex]a[/latex], [latex]b[/latex], [latex]c[/latex]. Длины медиан: [latex]a_1[/latex], [latex]b_1[/latex], [latex]c_1[/latex].

Тесты:

a	b	c	a1	b1	c1	Комментарий
1	4	5	4,5	3	1,5	Пройден
21	12	9	1,5	15	16,5	Пройден
24	17	9	6,40312	16,0078	20,3039	Пройден

#include <stdio.h>
#include <math.h>
 
int main(void) {
	double a, b, c, a1, b1, c1;
	printf("Введите длины строн a, b, c (a, b, c не могут быть меньше либо равными нулю): \n");
	scanf("%lf %lf %lf", &a, &b, &c);
	b1=0.5*sqrt(2*a*a+2*c*c-b*b);
	a1=0.5*sqrt(2*b*b+2*c*c-a*a);
	c1=0.5*sqrt(2*a*a+2*b*b-c*c);
	printf("b1=%8lg\n", b1);
    printf("a1=%8lg\n", a1);    
    printf("c1=%8lg\n", c1); 
  return 0;
}

#include <stdio.h>

#include <math.h>

int main(void) {

double a, b, c, a1, b1, c1;

printf("Введите длины строн a, b, c (a, b, c не могут быть меньше либо равными нулю): \n");

scanf("%lf %lf %lf", &a, &b, &c);

b1=0.5*sqrt(2*a*a+2*c*c-b*b);

a1=0.5*sqrt(2*b*b+2*c*c-a*a);

c1=0.5*sqrt(2*a*a+2*b*b-c*c);

printf("b1=%8lg\n", b1);

printf("a1=%8lg\n", a1);

printf("c1=%8lg\n", c1);

return 0;

}

Решение:

Когда известны все стороны треугольника, медианы вычисляются по следующей формуле: [latex]\frac{1}{2}\sqrt{2a^2+2b^2-c^2}[/latex], где [latex]c[/latex] — сторона к которой проведена медиана, а [latex]a[/latex] , [latex]b[/latex] — стороны треугольника.

Для проверки выполнения программы можно воспользоваться ссылкой .

Решение на Java:

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);
		double a, b, c, a1, b1, c1;
		System.out.println("Введите длины строн a, b, c (a, b, c не могут быть меньше либо равными нулю): ");
		a = in.nextDouble();
		b = in.nextDouble();
		c = in.nextDouble();
		a1=0.5*Math.sqrt(2*b*b+2*c*c-a*a);
		b1=0.5*Math.sqrt(2*a*a+2*c*c-b*b);
		c1=0.5*Math.sqrt(2*a*a+2*b*b-c*c);
		System.out.printf(Locale.US, "a1=%.7f\n",a1);
		System.out.printf(Locale.US, "b1=%.7f\n",b1);
		System.out.printf(Locale.US, "c1=%.7f\n",c1);
	}
}