A295

12/03/2016 by Женя Максимова

Задача. Даны целые числа [latex]a_{1},\ldots, a_{n}[/latex]. Наименьший член последовательности [latex]a_{1}, \ldots, a_{n}[/latex] заменить целой частью среднего арифметического всех членов, остальные члены оставить без изменения. Если в последовательности несколько членов со значением min [latex](a_{1}, \ldots, a_{n})[/latex], то заменить последний по порядку.

Тесты

Test	Input	Output
1	2 4 8 16 2 4	2 4 8 16 6 4
2	1 1 1 1	1 1 1 1
3	-5 5 -10 10 -10 5 5	-5 5 -10 10 0 5 5
4	2 6 9 -4 -5 7 13	2 6 9 -4 4 7 13
5	0 0 0 0 0 1	0 0 0 0 0 1
6	0 1 0 0 2 0 25	0 1 0 0 2 4 25

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

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

int main()
{
  vector<int>a;
  int el; //supporting variable for saving input values
  while(cin >> el)
    {
      a.push_back(el); //adding value to the vector
    }
  int min = a[0]; // minimal value
  int num = 0; // number of the minimal value
  double sum = 0; 
  for(int i=0; i<a.size(); i++)
    {
      if(a[i]<=min) //finding the number of the minimal value
        {
          min = a[i]; 
          num = i;
        }
      sum += a[i];
    }
  int average = floor(sum/a.size()); //calculing the average of vector elements
  a[num] = average; //replacing minimal value by the average
  for(int i = 0; i < a.size(); i++)
    {
      cout << a[i] << " ";
    }
  return 0;
}

#include<iostream>

#include<cmath>

#include<vector>

using namespace std;

int main()

{

vector<int>a;

int el; //supporting variable for saving input values

while(cin >> el)

{

a.push_back(el); //adding value to the vector

}

int min = a[0]; // minimal value

int num = 0; // number of the minimal value

double sum = 0;

for(int i=0; i<a.size(); i++)

{

if(a[i]<=min) //finding the number of the minimal value

{

min = a[i];

num = i;

}

sum += a[i];

}

int average = floor(sum/a.size()); //calculing the average of vector elements

a[num] = average; //replacing minimal value by the average

for(int i = 0; i < a.size(); i++)

{

cout << a[i] << " ";

}

return 0;

}

Алгоритм

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

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

Related Images:

Mif 8

07/10/2015 by Настя Ивасенко

Задача

Условие взято отсюда

Четырёхугольник [latex]ABCD[/latex] задан на плоскости целочисленными координатами вершин. Определите тип четырёхугольника: квадрат, ромб, прямоугольник, параллелограмм, трапеция, произвольный четырёхугольник. Из характеристик указать наиболее частную.

Тесты

[latex]a_1[/latex] [latex]a_2[/latex]	[latex]b_1[/latex] [latex]b_2[/latex]	[latex]c_1[/latex][latex]c_2[/latex]	[latex]d_1[/latex] [latex]d_2[/latex]	Ответ
0 0	1 0	1 1	0 1	квадрат
0 -3	2 0	0 3	-2 0	ромб
0 0	4 0	4 1	1 4	прямоугольник
0 0	10 0	12 4	2 4	пaраллелограмм
0 0	2 0	1 1	0 1	трапеция
0 0	0 2	1 1	1 0	трапеция
-4 -5	-15 7	5 8	6 -7	произвольный
0 0	1 0	10 20	-5 7	произвольный

Код

#include <iostream>
using namespace std;
 
int main() {
	int a1, a2, b1, b2, c1, c2, d1, d2;
	double  AB, BC, CD, DA, AC, BD, A, B, C, D;
	cin >> a1 >> a2 >> b1 >> b2 >> c1 >> c2 >> d1 >> d2;
	AB= ((a1-b1)*(a1-b1)+(a2-b2)*(a2-b2)); //длина стороны во второй степени
	BC= ((b1-c1)*(b1-c1)+(b2-c2)*(b2-c2));
	CD= ((c1-d1)*(c1-d1)+(c2-d2)*(c2-d2));
	DA= ((d1-a1)*(d1-a1)+(d2-a2)*(d2-a2));
	AC= ((a1-c1)*(a1-c1)+(a2-c2)*(a2-c2)); //длина диагонали во второй степени
	BD= ((b1-d1)*(b1-d1)+(b2-d2)*(b2-d2));
	if(AB==CD && BC==DA) {
		if (AB==BC){
			if(AC==BD){
				cout << "квадрат";
			}
			else {
				cout << "ромб";
			}
		}
		else 
		if (AC==BD){
			cout<< "прямоугольник";
		}
		else{
			cout << "параллелограмм";
		}
	}
	else 
	if ( ((a1-b1)*(c2-d2)==(a2-b2)*(c1-d1)) || ((a1-d1)*(b2-c2)==(a2-d2)*(b1-c1)) ){
		cout << "трапеция";
	}
	else {
		cout << "произвольный";
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int a1, a2, b1, b2, c1, c2, d1, d2;

double AB, BC, CD, DA, AC, BD, A, B, C, D;

cin >> a1 >> a2 >> b1 >> b2 >> c1 >> c2 >> d1 >> d2;

AB= ((a1-b1)*(a1-b1)+(a2-b2)*(a2-b2)); //длина стороны во второй степени

BC= ((b1-c1)*(b1-c1)+(b2-c2)*(b2-c2));

CD= ((c1-d1)*(c1-d1)+(c2-d2)*(c2-d2));

DA= ((d1-a1)*(d1-a1)+(d2-a2)*(d2-a2));

AC= ((a1-c1)*(a1-c1)+(a2-c2)*(a2-c2)); //длина диагонали во второй степени

BD= ((b1-d1)*(b1-d1)+(b2-d2)*(b2-d2));

if(AB==CD && BC==DA) {

if (AB==BC){

if(AC==BD){

cout << "квадрат";

}

else {

cout << "ромб";

}

else

if (AC==BD){

cout<< "прямоугольник";

}

else{

cout << "параллелограмм";

}

else

if ( ((a1-b1)*(c2-d2)==(a2-b2)*(c1-d1)) || ((a1-d1)*(b2-c2)==(a2-d2)*(b1-c1)) ){

cout << "трапеция";

}

else {

cout << "произвольный";

}

return 0;

}

Решение

Для начала стоит найти длины всех сторон:

[latex]AB^{2}=((a1-b1)^{2}+(a2-b2)^{2})[/latex]. (аналогично для остальных сторон)

Затем можно найти длины диагоналей четырёхугольника

[latex]AC^{2}=((a1-c1)^{2}+(a2-c2)^{2})[/latex]. (аналогично для [latex]BD[/latex]).

Через условие задаем равность противоположных сторон [latex]AB=CD[/latex] и [latex]BC=DA[/latex]:

У ромба смежные стороны равны, но если у ромба диагонали равны, то это квадрат;
Если четырёхугольник не является квадратом, но диагонали равны, то это прямоугольник;
В противном случае — параллелограмм.

Если одна из пар противополижных сторон параллельны, то данный четырёхугольник — трапеция. Впротивном случае — произвольный четырёхугольник.

Код на ideone

Related Images:

A841

18/06/2015 by Григорян Артак

Задача. «Исправление ошибок». Пусть по некоторому каналу связи передается сообщение, имеющее вид последовательностей нулей и единиц (или, аналагично, точек и тире). Из-за помех, возможен ошибочный прием некоторых сигналов: нуль может быть воспринят как единица и наоборот. Можно передавать каждый сигнал трижды, заменяя, например, последовательность 1, 0, 1 последовательностью 1, 1, 1, 0, 0, 0, 1, 1, 1. Три последовательные цифры при расшифровке заменяются той цифрой, которая встречается среди них по крайне мере дважды. Такое утраивание сигналов существенно повышает вероятность правильного приема сообщения. Написать программу расшифровки.

1 0 1 0 0 1 1 1 0	1 0 1
0 0 0 1 1 1 0 0 0	0 1 0
0 1 0 1 0 1 0 1 0 1 0 1	0 1 0 1

#include<iostream>
#include<vector>
using namespace std;
 int main()
 {
 	int n;
 	vector<int> m; 
	int k=0;
 	while(cin>>n)
 	{
 		m.push_back(n);
 		k++;
 	}	
 	int p=k/3;
 	for(int j=0;j<p;j++)
 		{	
 			int a=0;
 			for(int i=0;i<3;i++)
 				{
 					if(m[i]==1)a++;
 				}
 			m.erase(m.begin(),m.begin()+3);
 			if(a==0||a==1) cout<<"0";
 			if(a==2||a==3) cout<<"1";
 		}
 	return 0;
 }

#include<iostream>

#include<vector>

using namespace std;

int main()

{

int n;

vector<int> m;

int k=0;

while(cin>>n)

{

m.push_back(n);

k++;

}

int p=k/3;

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

{

int a=0;

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

{

if(m[i]==1)a++;

}

m.erase(m.begin(),m.begin()+3);

if(a==0||a==1) cout<<"0";

if(a==2||a==3) cout<<"1";

}

return 0;

}

Записываем входные данные в вектор. Делим вектор на части по три символа. Пробегаем по этим трем символам, увеличивая счетчик, если символ «1». Если единиц больше, чем нулей, то записываем «1». Если нулей больше, чем единиц, то записываем «0». Удаляем фрагмент вектора, для удобства, и пробегаем по следующим трем символам.

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

Related Images:

А701б

13/06/2015 by Царев Николай Александрович

Условие

Даны квадратная матрица [latex]A[/latex] порядка [latex]n[/latex] и вектор [latex]b[/latex] c [latex]n[/latex] элементами. Получить вектор [latex]{ A }^{ 2 }b[/latex]

Тесты

n	A	b	Результат
3	1 1 11 1 1 1 1 1	5 5 5	45 45 45
5	1 0 0 0 00 2 0 0 0 0 0 3 0 0 0 0 0 4 0 0 0 0 0 5	8 1 8 1 8	8 4 72 16 200
2	1 00 1	2 2	2 2

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >>n;
    double matr1[n][n];  //Матрица А
    double matr2[n][n]; // Матрица А^2
    double vet1[n];  //Вектор данный по условию (вектор b)
    double vet2[n];  //Конечный вектор
    for(int i=0;i<n;i++){
        for(int j=0; j<n; j++) // Инициализация матрицы А
            cin>>matr1[i][j];
    }

    for(int i=0; i<n;i++){
        for(int j=0;j<n;j++){  //Возведение матрицы А в квадрат
            matr2[i][j]=0;
            for(int p=0;p<n;p++)
                matr2[i][j]+=(matr1[i][p]*matr1[p][j]);
        }
    }

    for(int i=0; i<n; i++) //Инициализация вектора
        cin >> vet1[i];

    for(int i=0;i<n;i++){
        vet2[i]=0;
        for(int j=0; j<n; j++){
            vet2[i]+=matr2[i][j]*vet1[j]; //Умножение матрицы на вектор
        }
    }

    for(int i=0; i<n; i++)
        cout << vet2[i] << "\t"; //Вывод вектора
    cout << endl;

    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >>n;

double matr1[n][n]; //Матрица А

double matr2[n][n]; // Матрица А^2

double vet1[n]; //Вектор данный по условию (вектор b)

double vet2[n]; //Конечный вектор

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

for(int j=0; j<n; j++) // Инициализация матрицы А

cin>>matr1[i][j];

}

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

for(int j=0;j<n;j++){ //Возведение матрицы А в квадрат

matr2[i][j]=0;

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

matr2[i][j]+=(matr1[i][p]*matr1[p][j]);

}

for(int i=0; i<n; i++) //Инициализация вектора

cin >> vet1[i];

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

vet2[i]=0;

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

vet2[i]+=matr2[i][j]*vet1[j]; //Умножение матрицы на вектор

}

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

cout << vet2[i] << "\t"; //Вывод вектора

cout << endl;

return 0;

}

Алгоритм

Считываем матрицу. Возводим ее в квадрат ( перемножение матрицы осуществляется при помощи циклов). Считываем вектор. Умножаем матрицу на вектор. Выводим ответ.

Фактически, умножение матриц пишется по определению. Сумма произведений элементов строки на элементы столбцов.

Ссылка на ideone.com

Related Images:

Ю4.6

04/11/2014 by Царев Николай Александрович

Задача: Угол между векторами

Найти угол между векторами [latex]A(n)[/latex] и [latex]B(n)[/latex] используя формулу:

[latex]cos\varphi =\cfrac { \left( A,B \right) }{ \left| A \right| \cdot \left| B \right| } =\cfrac { \sum _{ i=1 }^{ n }{ { a }_{ i }{ b }_{ i } } }{ \sqrt { \sum _{ i=1 }^{ n }{ { a }_{ i }^{ 2 } } } \sqrt { \sum _{ i=1 }^{ n }{ { b }_{ i }^{ 2 } } } }[/latex]

N	A(n)	B(n)	Rad & Deg
2	3 4	4 3	0.283794 16.2596
2	7 1	5 5	0.643501 36.8686
3	3 4 0	4 4 2	0.367208 21.0388
10	7 7 7 7 7 7 7 7 7 7	7 7 7 7 7 7 7 7 7 7	0 0
2	0 2	3 0	1.5708 89.9969
2	-3 5	4 -1	2.35619 134.995

Код программы на С++

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int n, m;
    cin >> n; //Кол-во элементов из которых состоит вектор
    double A[n], B[n];
    double coq, s1, s2, s3, deg;
    for(int j=0; j<n; j++) //Инициализация А
		cin >> A[j];
	for(int j=0; j<n; j++) //Инициализация В
		cin >> B[j];
	for(int i=0; i<n; i++){ // Вычисление каждой суммы указанной в формуле
		s1+=A[i]*B[i];
		s2+=A[i]*A[i];
		s3+=B[i]*B[i];
	}
	coq=s1/sqrt(s2*s3);
	deg=acos(coq);
	cout << "Rad:" << deg << "\nDeg:" << (deg*180)/3.1417;
	
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n, m;

cin >> n; //Кол-во элементов из которых состоит вектор

double A[n], B[n];

double coq, s1, s2, s3, deg;

for(int j=0; j<n; j++) //Инициализация А

cin >> A[j];

for(int j=0; j<n; j++) //Инициализация В

cin >> B[j];

for(int i=0; i<n; i++){ // Вычисление каждой суммы указанной в формуле

s1+=A[i]*B[i];

s2+=A[i]*A[i];

s3+=B[i]*B[i];

}

coq=s1/sqrt(s2*s3);

deg=acos(coq);

cout << "Rad:" << deg << "\nDeg:" << (deg*180)/3.1417;

return 0;

}

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

import java.util.*;
import java.lang.*;
import java.io.*;
import java.lang.Math;
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in=new Scanner(System.in);
    	int n, m;
    	n=in.nextInt();
    	double A[]=new double[n]; 
    	double B[]=new double[n]; 
    	double coq, s1, s2, s3, deg;
    	s1=0;
    	s2=0;
    	s3=0;
    	for(int j=0; j<n; j++) //Инициализация А
			A[j]=in.nextDouble();
		for(int j=0; j<n; j++) //Инициализация В
			B[j]=in.nextDouble();
		for(int i=0; i<n; i++){ // Вычисление каждой суммы указанной в формуле
			s1+=A[i]*B[i];
			s2+=A[i]*A[i];
			s3+=B[i]*B[i];
		}
		coq=s1/Math.sqrt(s2*s3);
		deg=Math.acos(coq);
		System.out.printf("Rad: %8.6f \n", deg);
		System.out.printf("Deg: %8.4f", (deg*180)/3.1417);
}
	}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.lang.Math;

class Main

{

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

{

Scanner in=new Scanner(System.in);

int n, m;

n=in.nextInt();

double A[]=new double[n];

double B[]=new double[n];

double coq, s1, s2, s3, deg;

s1=0;

s2=0;

s3=0;

for(int j=0; j<n; j++) //Инициализация А

A[j]=in.nextDouble();

for(int j=0; j<n; j++) //Инициализация В

B[j]=in.nextDouble();

for(int i=0; i<n; i++){ // Вычисление каждой суммы указанной в формуле

s1+=A[i]*B[i];

s2+=A[i]*A[i];

s3+=B[i]*B[i];

}

coq=s1/Math.sqrt(s2*s3);

deg=Math.acos(coq);

System.out.printf("Rad: %8.6f \n", deg);

System.out.printf("Deg: %8.4f", (deg*180)/3.1417);

}

Чтобы выполнить задачу, требуется всего лишь следовать вычислениям формулы. Для того, что бы узнать значение не косинуса а самого угла, применяем математическую функцию [latex]acos[/latex].

Ссылка C++

Ссылка на Java

Related Images:

Ю11.12

21/10/2014 by Бронфен-Бова Роман

Задача:
Интерполяционный многочлен Лагранжа. Значения функции [latex]y=f\left(x\right)[/latex] заданы таблично в массиве [latex]Y\left(x\right)[/latex] при соответствующих значениях аргумента в упорядоченном массиве [latex]X\left(x\right)[/latex]. Найти значение функции в произвольной точке [latex]x[/latex] по формуле Лагранжа:
[latex]y={L}_{n}\left(x\right)=\sum _{i=1}^{n}{{y}_{i}\prod _{\underset{j\neq i}{j=1}}^{n}{\frac{x-{x}_{j}}{{x}_{i}-{x}_{j}}}}[/latex]

Вводимые значения:

X:	-1	0	1	2
Y:	1	2	3	-1

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

#include <iostream>
#include <vector>
using namespace std;

double LP(double x, vector<double> xv, vector<double> yv) { //Lagrange polynomial
	int size = xv.size(); //Количество точек (для удобства)
	double sum = 0; //Значение функции
	for(int i = 0; i < size; i++){
		double mul = 1; //Произведение
		for(int j = 0; j < size; j++){
			if(i!=j) mul *= (x - xv[j])/(xv[i]-xv[j]);
		}
		sum += yv[i]*mul;
	}
	return sum;
}

int main() {
	int counter = 0;
	double a = -3; //Левая грань
	double b = 3; //Правая грань
	int fragments = 101; //Разбиение
	vector<double> xv {};
	vector<double> yv {};
	double inp;
	while(cin >> inp) counter++%2 ? yv.push_back(inp) : xv.push_back(inp); //Заполнение
	for(int i = 0; i < fragments; i++){
		double x = a + (b-a)/(fragments-1)*i;
		printf("%6.3lf\t%6.3lf\n", x, LP(x, xv, yv));
	}
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

double LP(double x, vector<double> xv, vector<double> yv) { //Lagrange polynomial

int size = xv.size(); //Количество точек (для удобства)

double sum = 0; //Значение функции

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

double mul = 1; //Произведение

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

if(i!=j) mul *= (x - xv[j])/(xv[i]-xv[j]);

}

sum += yv[i]*mul;

}

return sum;

}

int main() {

int counter = 0;

double a = -3; //Левая грань

double b = 3; //Правая грань

int fragments = 101; //Разбиение

vector<double> xv {};

vector<double> yv {};

double inp;

while(cin >> inp) counter++%2 ? yv.push_back(inp) : xv.push_back(inp); //Заполнение

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

double x = a + (b-a)/(fragments-1)*i;

printf("%6.3lf\t%6.3lf\n", x, LP(x, xv, yv));

}

return 0;

}

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
 
	static double LP(double x, double[] xv, double[] yv){
		int size = xv.length;
		double sum = 0;
		for(int i = 0; i < size; i++){
			double mul = 1;
			for(int j = 0; j < size; j++){
				if(i != j){
					mul *= (x-xv[j])/(xv[i]-xv[j]);
				}
			}
			sum += yv[i]*mul;
		}
		return sum;
	}
 
	static Scanner sc = new Scanner(System.in);
 
	public static void main (String[] args) throws java.lang.Exception
	{
		int counter = 0;
		double a = -3;
		double b = 3;
		int fragments = 101;
		ArrayList<Double> xvinp = new ArrayList<Double>();
		ArrayList<Double> yvinp = new ArrayList<Double>();
		double[] xv;
		double[] yv;
		while(sc.hasNext()){
			double inp = sc.nextDouble();
			if(counter%2 == 0){
				xvinp.add(inp);
			}else{
				yvinp.add(inp);
			}
			counter++;
		}
		xv = new double[xvinp.size()];
		yv = new double[yvinp.size()];
		for(int i = 0; i < xvinp.size(); i++){
			xv[i] = xvinp.get(i);
			yv[i] = yvinp.get(i);
		}
		for(int i = 0; i < fragments; i++){
			double x = a + (b-a)/(fragments-1)*i;
			System.out.println(x + "\t" + LP(x, xv, yv));
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static double LP(double x, double[] xv, double[] yv){

int size = xv.length;

double sum = 0;

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

double mul = 1;

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

if(i != j){

mul *= (x-xv[j])/(xv[i]-xv[j]);

}

sum += yv[i]*mul;

}

return sum;

}

static Scanner sc = new Scanner(System.in);

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

{

int counter = 0;

double a = -3;

double b = 3;

int fragments = 101;

ArrayList<Double> xvinp = new ArrayList<Double>();

ArrayList<Double> yvinp = new ArrayList<Double>();

double[] xv;

double[] yv;

while(sc.hasNext()){

double inp = sc.nextDouble();

if(counter%2 == 0){

xvinp.add(inp);

}else{

yvinp.add(inp);

}

counter++;

}

xv = new double[xvinp.size()];

yv = new double[yvinp.size()];

for(int i = 0; i < xvinp.size(); i++){

xv[i] = xvinp.get(i);

yv[i] = yvinp.get(i);

}

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

double x = a + (b-a)/(fragments-1)*i;

System.out.println(x + "\t" + LP(x, xv, yv));

}

Идея решения:
Использование отдельной функции, которой надо передать 3 параметра: значение аргумента, массив исходных значений аргумента и массив исходных значений функции при соответствующих аргументах. Эта функция возвращает значение многочлена Лагранжа при подстановки вместо [latex]x[/latex] конкретного значения.

В функции был использован внешний цикл for для вычисления суммы в формуле и внутренний цикл for для вычисления произведения [latex]\prod _{\underset{j\neq i}{j=1}}^{n}{\frac{x-{x}_{j}}{{x}_{i}-{x}_{j}}}[/latex].

В программе мы разбиваем отрезок [-3, 3] на 101 отдельную точку и вычисляем значение полинома Лагранжа для каждой из этих точек. Выводим на экран.

График:

Комментарии: Точки выбраны специально. Мне просто захотелось увидеть, как выглядит график функции, которую мы разбирали на паре (кстати по той же самой теме =) ). График сделан в xls. Векторы выбраны по причине ограниченности массива.