e-olimp 5074. Степени вершин по спискам ребер

02/05/2015 by Карташов Денис Геннадійович

Задача:

Неориентированный граф задан списком ребер.

Найдите степени всех вершин графа.

Технические условия:

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

Входной файл содержит числа [latex]n[/latex] [latex] (1 \leq n \leq 100) [/latex] — число вершин в графе и

[latex]m[/latex] [latex](1 \leq m \leq \frac{n(n-1)}{2})[/latex] — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа.

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

Выведите в выходной файл [latex]n[/latex] чисел — степени вершин графа.

Код на C++:

#include <iostream>
using namespace std;

int main() {
   int n = 0 , m = 0, i, buf;
   cin >> n >> m;
   int *a = new int [n];
   for(i = 0; i < n; a[i] = 0, ++i);
   for(i = 0 , buf; i < 2*m ; cin >> buf, ++a[buf - 1], ++i);
   for(i = 0; i < n; ++i){
   		 cout << a[i] << endl;
   }
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n = 0 , m = 0, i, buf;

cin >> n >> m;

int *a = new int [n];

for(i = 0; i < n; a[i] = 0, ++i);

for(i = 0 , buf; i < 2*m ; cin >> buf, ++a[buf - 1], ++i);

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

cout << a[i] << endl;

}

return 0;

}

Код на Java:

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

public class Main
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n, m, i, buf;
		n = in.nextInt();
		m = in.nextInt();
		int[] a = new int [n];
		for(i = 0; i < n; a[i] = 0, ++i);
		for(i = 0; i < 2*m ;buf = in.nextInt(), ++a[buf - 1], ++i);
		for(i = 0; i < n; ++i){
			out.println(a[i]);
		}
		out.flush();
	}
}

import java.io.*;

import java.util.*;

public class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

int n, m, i, buf;

n = in.nextInt();

m = in.nextInt();

int[] a = new int [n];

for(i = 0; i < n; a[i] = 0, ++i);

for(i = 0; i < 2*m ;buf = in.nextInt(), ++a[buf - 1], ++i);

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

out.println(a[i]);

}

out.flush();

}

Описание:

Мне дан неориентированный граф, значит каждое упоминание вершины в списке ребер увеличивает её степень на единицу. Заводим массив (размер массива равен числу вершин) и при каждом упоминании вершины увеличиваем её ячейку в массиве на единицу. Выводим результат.

Related Images:

AA1

01/04/2015 by Карташов Денис Геннадійович

Задача:

В заданной строке заменить подряд идущие пробелы на один пробел.

Примечание:

Будем называть строку правильной, если она не содержит подряд идущих пробелов.

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

Исходная строка	Оптимистичное ожидание	Комментарий
Gagarin became an international celebrity, and was awarded many medals and titles, including Hero of the Soviet Union.	Gagarin became an international celebrity, and was awarded many medals and titles, including Hero of the Soviet Union.	Пройден.
Leonardo was, and is, renowned primarily as a painter.	Leonardo was, and is, renowned primarily as a painter.	Пройден.

Код на С++

#include <iostream>
using namespace std;

#define withRL     //Печать красной строки (если она была)

int main() {
	string s;
	getline(cin , s);
	int i, j = 0;
	bool ifspace = false;
	for(i = 0; i < s.length(); i++){
		if(s[i] == ' '){
			#ifdef withRL
			if(!ifspace){
			#else
			if(j && !ifspace){
			#endif
				ifspace = true;
				s[j] = s[i];
				j++;
			}
		}
		else{
			ifspace = false;
			s[j] = s[i];
			j++;
		}
	}
	s.erase(j);
	if(s.back() == ' ') s.pop_back();
	cout << s << endl;
}

#include <iostream>

using namespace std;

#define withRL //Печать красной строки (если она была)

int main() {

string s;

getline(cin , s);

int i, j = 0;

bool ifspace = false;

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

if(s[i] == ' '){

#ifdef withRL

if(!ifspace){

#else

if(j && !ifspace){

#endif

ifspace = true;

s[j] = s[i];

j++;

}

else{

ifspace = false;

s[j] = s[i];

j++;

}

s.erase(j);

if(s.back() == ' ') s.pop_back();

cout << s << endl;

}

Код на Java

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


public class Main
{
	private static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	
	public static void main (String[] args) throws java.lang.Exception
	{
		StringBuilder a;
		a = new StringBuilder(in.readLine());
		int j = 0;
		boolean isSpace = false;
		if(a.length() == 0) System.exit(0);
		for(int i = 0; i < a.length(); i++){
			if(a.charAt(i) == ' '){
				if(!isSpace){
					isSpace = true;
					a.setCharAt(j,a.charAt(i));
					j++;
				}
			}
			else{
				isSpace = false;
				a.setCharAt(j,a.charAt(i));
				j++;
			}
		}
		a.delete(j, a.length());
		if(a.charAt(a.length() - 1) == ' ') a.delete(a.length() - 1, a.length());
		System.out.println(a);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

private static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

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

{

StringBuilder a;

a = new StringBuilder(in.readLine());

int j = 0;

boolean isSpace = false;

if(a.length() == 0) System.exit(0);

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

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

if(!isSpace){

isSpace = true;

a.setCharAt(j,a.charAt(i));

j++;

}

else{

isSpace = false;

a.setCharAt(j,a.charAt(i));

j++;

}

a.delete(j, a.length());

if(a.charAt(a.length() - 1) == ' ') a.delete(a.length() - 1, a.length());

System.out.println(a);

}

Пояснение:

Вариант удаления пробелов с помощью [latex]erase()[/latex] является самым очевидным. Но у него больше недостатков, чем достоинств. Данный метод имеет линейную асимптотику, в худшем случае он выполнил бы [latex]n — 1[/latex] ( в дальнейшем [latex]»n»[/latex] — это длина строки ) сдвиг в индексах строки.

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

Второй способ мне нравится больше (просто потому, что он работает), но выделять новую строку очень не хочется. Оказалось, что можно обойтись и без неё. В качестве новой я использовал исходную. Для этого ввел два «указателя» на позиции элементов. Первый пробегает всю строку в цикле, второй же указывает на элемент, этой строки, в который будет положено новое значение. Таким образом, полученная последовательность символов (от нулевой, до [latex]j[/latex] — той не включительно) будет правильной строкой. Осталось удалить элементы на полуинтервале от [latex]j[/latex] до [latex]n[/latex].

Related Images:

e-olimp 6130. Дек неограниченного размера.

01/04/2015 by Карташов Денис Геннадійович

Задача:

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

push_front

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

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

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

pop_back

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

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

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

Размер дека должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций pop_front, pop_back, front, back программа должна проверять, содержится ли в деке хотя бы один элемент. Если во входных данных встречается операция pop_front, pop_back, front, back, и при этом дек пуст, то программа должна вместо числового значения вывести строку error.

Результат на C++

Результат на Java

Код на C++:

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

class Deque{
	private:
	int *a = new int [100];
	int size_;
	int front_;
	int back_;
	int capacity;
	void resize(int);
	public:
	Deque(): size_(0), front_(1), back_(0), capacity(100){}
	void push_back(int);
	void push_front(int);
	void pop_back();
	void pop_front();
	int size() const;
	int back() const;
	int front() const;
	void clear();
};

void Deque::resize(int newcapacity){  //Функция изменения размера.
	int* tmp = new int [newcapacity];   //Создаем новый динамический массив с новой размерностью
	int j = front_;                     //Присваиваем начальное значение счетчику.
	for(int i = 0; j!= back_; ++i){     //Продвигаемся по деку, пока счетчик не будет равен позиции последнего элемента.
		tmp[i] = a[j];
		j = (j+1)%capacity;
	}
	tmp[size_ - 1] = a[back_];    //Так как в цикле перенос последнего элемента из старого массива в новый не произошел, вручную переносим последний элемент старого массива.
	delete []a;                   //Удаляем лишнюю память.
	a = tmp;                      //Присваиваем указателю на старый массив указатель на новый массив.
	capacity = newcapacity;       //Меняем значение вместимости.
	front_ = 0;                   //Теперь первый элемент нового массива стоит на нулевой позиции.
	back_ = size_ - 1;            //А последний - на позиции на единицу меньшей чем кол-во элементов.
}

void Deque::push_back(int b){
	if(size_ == capacity){
		this -> resize(2*capacity);
	}
	back_ = (back_ + 1)%capacity;
	a[back_] = b;
	size_++;
}
void Deque::push_front(int b){
	if(size_ == capacity){
		this -> resize(2*capacity);
	}
	front_ = (front_ - 1 + capacity)%capacity;
	a[front_] = b;
	size_++;
}

void Deque::pop_back(){
	back_ = (back_ - 1 + capacity)%capacity;
	size_--;
}
void Deque::pop_front(){
	front_ = (front_ + 1)%capacity;
	size_--;
}
int Deque::size() const{
	return size_;
}

int Deque::front() const{
	return a[front_];
}

int Deque::back() const{
	return a[back_];
}

void Deque::clear(){
	back_ = 0;
	front_ = 1;
	size_ = 0;
}
	
int main() {
	Deque a;
	string s;
	int n;
	while(cin >> s){
		if(s == "push_back"){
			cin >> n;
			a.push_back(n);
			cout << "ok\n";
		}
		else if(s == "push_front"){
			cin >> n;
			a.push_front(n);
			cout << "ok\n";
		}
		else if(s == "pop_back"){
			if(a.size()){
				cout << a.back() << endl;
				a.pop_back();
			}
			else{
				cout << "error\n";
			}
		}
		else if(s == "pop_front"){
			if(a.size()){
				cout << a.front() << endl;
				a.pop_front();
			}
			else{
				cout << "error\n";
			}
		}
		else if(s == "front"){
			if(a.size()){
				cout << a.front() << endl;
			}
			else{
				cout << "error\n";
			}
		}
		else if(s == "back"){
			if(a.size()){
				cout << a.back() << endl;
			}
			else{
				cout << "error\n";
			}
		}
		else if(s == "size"){
			cout << a.size() << endl;
		}
		else if(s == "clear"){
			cout << "ok\n";
			a.clear();
		}
		else if(s == "exit"){
			cout << "bye\n";
			return 0;
		}
	}
	return 0;
}

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

#include <iostream>

#include <string>

using namespace std;

class Deque{

private:

int *a = new int [100];

int size_;

int front_;

int back_;

int capacity;

void resize(int);

public:

Deque(): size_(0), front_(1), back_(0), capacity(100){}

void push_back(int);

void push_front(int);

void pop_back();

void pop_front();

int size() const;

int back() const;

int front() const;

void clear();

};

void Deque::resize(int newcapacity){ //Функция изменения размера.

int* tmp = new int [newcapacity]; //Создаем новый динамический массив с новой размерностью

int j = front_; //Присваиваем начальное значение счетчику.

for(int i = 0; j!= back_; ++i){ //Продвигаемся по деку, пока счетчик не будет равен позиции последнего элемента.

tmp[i] = a[j];

j = (j+1)%capacity;

}

tmp[size_ - 1] = a[back_]; //Так как в цикле перенос последнего элемента из старого массива в новый не произошел, вручную переносим последний элемент старого массива.

delete []a; //Удаляем лишнюю память.

a = tmp; //Присваиваем указателю на старый массив указатель на новый массив.

capacity = newcapacity; //Меняем значение вместимости.

front_ = 0; //Теперь первый элемент нового массива стоит на нулевой позиции.

back_ = size_ - 1; //А последний - на позиции на единицу меньшей чем кол-во элементов.

}

void Deque::push_back(int b){

if(size_ == capacity){

this -> resize(2*capacity);

}

back_ = (back_ + 1)%capacity;

a[back_] = b;

size_++;

}

void Deque::push_front(int b){

if(size_ == capacity){

this -> resize(2*capacity);

}

front_ = (front_ - 1 + capacity)%capacity;

a[front_] = b;

size_++;

}

void Deque::pop_back(){

back_ = (back_ - 1 + capacity)%capacity;

size_--;

}

void Deque::pop_front(){

front_ = (front_ + 1)%capacity;

size_--;

}

int Deque::size() const{

return size_;

}

int Deque::front() const{

return a[front_];

}

int Deque::back() const{

return a[back_];

}

void Deque::clear(){

back_ = 0;

front_ = 1;

size_ = 0;

}

int main() {

Deque a;

string s;

int n;

while(cin >> s){

if(s == "push_back"){

cin >> n;

a.push_back(n);

cout << "ok\n";

}

else if(s == "push_front"){

cin >> n;

a.push_front(n);

cout << "ok\n";

}

else if(s == "pop_back"){

if(a.size()){

cout << a.back() << endl;

a.pop_back();

}

else{

cout << "error\n";

}

else if(s == "pop_front"){

if(a.size()){

cout << a.front() << endl;

a.pop_front();

}

else{

cout << "error\n";

}

else if(s == "front"){

if(a.size()){

cout << a.front() << endl;

}

else{

cout << "error\n";

}

else if(s == "back"){

if(a.size()){

cout << a.back() << endl;

}

else{

cout << "error\n";

}

else if(s == "size"){

cout << a.size() << endl;

}

else if(s == "clear"){

cout << "ok\n";

a.clear();

}

else if(s == "exit"){

cout << "bye\n";

return 0;

}

return 0;

}

Код на Java:

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

 
class Deque{
	private int[] a = new int [100];
	private int size_;
	private int front_;
	private int back_;
	private int capacity;
	private void resize(int newcapacity){  //Функция изменения размера.
		int[] tmp = new int [newcapacity];   //Создаем новый динамический массив с новой размерностью
		int j = front_;                     //Присваиваем начальное значение счетчику.
		for(int i = 0; j!= back_; ++i){     //Продвигаемся по деку, пока счетчик не будет равен позиции последнего элемента.
			tmp[i] = a[j];
			j = (j+1)%capacity;
		}
		tmp[size_ - 1] = a[back_];    //Так как в цикле перенос последнего элемента из старого массива в новый не произошел, вручную переносим последний элемент старого массива.
		a = tmp;                      //Присваиваем указателю на старый массив указатель на новый массив.
		capacity = newcapacity;       //Меняем значение вместимости.
		front_ = 0;                   //Теперь первый элемент нового массива стоит на нулевой позиции.
		back_ = size_ - 1;            //А последний - на позиции на единицу меньшей чем кол-во элементов.
	}
	public Deque()
	{
		size_ = 0; front_ = 1; back_ = 0; capacity = 100;
	}
	public void push_back(int b){
		if(size_ == capacity){
			this.resize(2*capacity);
		}
		back_ = (back_ + 1)%capacity;
		a[back_] = b;
		size_++;
	}
	public void push_front(int b){
		if(size_ == capacity){
			this.resize(2*capacity);
		}
		front_ = (front_ - 1 + capacity)%capacity;
		a[front_] = b;
		size_++;
	}
	public void pop_back(){
		back_ = (back_ - 1 + capacity)%capacity;
		size_--;
	}
	public void pop_front(){
		front_ = (front_ + 1)%capacity;
		size_--;
	}
	public int size(){
		return size_;
	}
	public int back(){
		return a[back_];
	}
	public int front(){
		return a[front_];	
	}
	public void clear(){
		back_ = 0;
		front_ = 1;
		size_ = 0;
	}
};

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		Deque a = new Deque();
		String s;
		String[] oper = {"push_back", "push_front", "pop_back", "pop_front", "front", "back", "size", "clear", "exit"};
		int n;
		am:while(true){
			s = in.next();
			if(s.equals(oper[0])){
				n = in.nextInt();
				a.push_back(n);
				out.println("ok");
			}
			else if(s.equals(oper[1])){
				n = in.nextInt();
				a.push_front(n);
				out.println("ok");
			}
			else if(s.equals(oper[2])){
				if(a.size() != 0){
					out.println(a.back());
					a.pop_back();
				}
				else{
					out.println("error");
				}
			}
			else if(s.equals(oper[3])){
				if(a.size() != 0){
					out.println(a.front());
					a.pop_front();
				}
				else{
					out.println("error");
				}
			}
			else if(s.equals(oper[4])){
				if(a.size() != 0){
					out.println(a.front());
				}
				else{
					out.println("error");
				}
			}
			else if(s.equals(oper[5])){
				if(a.size() != 0){
					out.println(a.back());
				}
				else{
					out.println("error");
				}
			}
			else if(s.equals(oper[6])){
				out.println(a.size());
			}
			else if(s.equals(oper[7])){
				out.println("ok");
				a.clear();
			}
			else if(s.equals(oper[8])){
				out.println("bye");
				//System.exit(0);
				break am;
			}
		}
		out.flush();
	}
}

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

import java.util.*;

import java.lang.*;

import java.io.*;

class Deque{

private int[] a = new int [100];

private int size_;

private int front_;

private int back_;

private int capacity;

private void resize(int newcapacity){ //Функция изменения размера.

int[] tmp = new int [newcapacity]; //Создаем новый динамический массив с новой размерностью

int j = front_; //Присваиваем начальное значение счетчику.

for(int i = 0; j!= back_; ++i){ //Продвигаемся по деку, пока счетчик не будет равен позиции последнего элемента.

tmp[i] = a[j];

j = (j+1)%capacity;

}

a = tmp; //Присваиваем указателю на старый массив указатель на новый массив.

capacity = newcapacity; //Меняем значение вместимости.

front_ = 0; //Теперь первый элемент нового массива стоит на нулевой позиции.

back_ = size_ - 1; //А последний - на позиции на единицу меньшей чем кол-во элементов.

}

public Deque()

{

size_ = 0; front_ = 1; back_ = 0; capacity = 100;

}

public void push_back(int b){

if(size_ == capacity){

this.resize(2*capacity);

}

back_ = (back_ + 1)%capacity;

a[back_] = b;

size_++;

}

public void push_front(int b){

if(size_ == capacity){

this.resize(2*capacity);

}

front_ = (front_ - 1 + capacity)%capacity;

a[front_] = b;

size_++;

}

public void pop_back(){

back_ = (back_ - 1 + capacity)%capacity;

size_--;

}

public void pop_front(){

front_ = (front_ + 1)%capacity;

size_--;

}

public int size(){

return size_;

}

public int back(){

return a[back_];

}

public int front(){

return a[front_];

}

public void clear(){

back_ = 0;

front_ = 1;

size_ = 0;

}

};

public class Main

{

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

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

Deque a = new Deque();

String s;

String[] oper = {"push_back", "push_front", "pop_back", "pop_front", "front", "back", "size", "clear", "exit"};

int n;

am:while(true){

s = in.next();

if(s.equals(oper[0])){

n = in.nextInt();

a.push_back(n);

out.println("ok");

}

else if(s.equals(oper[1])){

n = in.nextInt();

a.push_front(n);

out.println("ok");

}

else if(s.equals(oper[2])){

if(a.size() != 0){

out.println(a.back());

a.pop_back();

}

else{

out.println("error");

}

else if(s.equals(oper[3])){

if(a.size() != 0){

out.println(a.front());

a.pop_front();

}

else{

out.println("error");

}

else if(s.equals(oper[4])){

if(a.size() != 0){

out.println(a.front());

}

else{

out.println("error");

}

else if(s.equals(oper[5])){

if(a.size() != 0){

out.println(a.back());

}

else{

out.println("error");

}

else if(s.equals(oper[6])){

out.println(a.size());

}

else if(s.equals(oper[7])){

out.println("ok");

a.clear();

}

else if(s.equals(oper[8])){

out.println("bye");

//System.exit(0);

break am;

}

out.flush();

}

Пояснение:

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

Трудности возникли тогда, когда количество элементов в деке сравнялось с вместимостью базового массива. В таком случае необходимо величить вместимость дека. Сделать это можно следующим образом. Нужно создать новый массив, перенести в него элементы старого массива, а после присвоить указателю на старый массив указатель на новый. После увеличения вместимости дека возник вопрос: Куда указывают указатели? Мы их не меняли, а значит они имеют прежние значения, что уже не актуально. Так как первый элемент в новом массиве находится на нулевой позиции, меняем значение указателя на первый элемент (front_) на нуль. Указатель на последний элемент (back_) теперь должен иметь значение равное, уменьшенному на единицу, количеству элементов. Осталось только изменить значение вместимости (capacity), у меня вместимость увеличивается вдвое.

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

Related Images:

e-olimp 4004. Есть ли цикл?

22/03/2015 by Карташов Денис Геннадійович

Задача:

Дан ориентированный граф. Требуется определить, есть ли в нём цикл.

Технические условия:

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

В первой строке вводится натуральное число [latex]N ( N \leq 50)[/latex] — количество вершин. Далее в [latex]N[/latex] строках следуют по [latex]N[/latex] чисел, каждое из которых — «0» или «1«. [latex]j [/latex] -е число в [latex]i[/latex] -й строке равно «1» тогда и только тогда, когда существует ребро, идущее из [latex]i[/latex] -й вершины в [latex]j[/latex]-ю. Гарантируется, что на диагонали матрицы будут стоять нули.

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

Выведите «0«, если в заданном графе цикла нет, и «1«, если он есть.

Результат на С++

Результат на Java

Код на С++:

#include <iostream>
using namespace std;

int ** a; // Матрица смежности будет записана именно сюда.
int n = 51; // Число вершин. 
int * was;// Массив цвета вершины.

bool dfs(int key){
  //"Красим" вершину в серый цвет (указываем, что мы в нее вошли).
  was[key] = 1;
  //Проходим все связанные с текущей вершиной.
  for(int i = 0; i < n; i++){
  //Если значение элемента строки матрицы (по условию, нам дана матрица смежности) отлично от "0", то:
      if(a[key][i]){
          //если вершина "белая" (т. е. мы в неё еще не заходили)- 
          //запускаем рекурсивный вызов DFS от этой вершины.
          if(was[i] == 0){if(dfs(i)) return true;}
          //если вершина "серая" (мы её уже навещали, но не возвращались из ее потомков)-  
          //мы нашли цикл, следовательно поиск можно завершить.
          else if(was[i] == 1){ return true;}
      }
  }
  //Если ни один из if - ов не сработал, то "красим" вершину в черный цвет (отмечаем, как пройденную)
  was[key] = 2;
 //и возвращаем результат поиска (мы ничего не нашли).
  return false;
}
int main() {
  cin >> n;
  a = new int *[n];
  was = new int [n];
  for(int i = 0; i < n; i++){
      a[i] = new int [n];
      was[i] = 0;
      for(int j = 0; j < n; j++){
          cin >> a[i][j];
      }
  }
  for(int i = 0; i < n; i++){
      //Проверяем поиском каждую вершину. Если поиск оказался успешным - выводим "1". 
      //Проверка цвета сделана ради ускорения процесса, иначе в поиске пришлось бы проходить весь 
      //цикл, даже если вершина покрашена в черный цвет.
      if(!was[i]&&dfs(i)) {cout << "1\n"; return 0;}
  }
  //Если if ни разу не сработал - выводим "0".
  cout << "0\n";
  return 0;
}

#include <iostream>

using namespace std;

int ** a; // Матрица смежности будет записана именно сюда.

int n = 51; // Число вершин.

int * was;// Массив цвета вершины.

bool dfs(int key){

//"Красим" вершину в серый цвет (указываем, что мы в нее вошли).

was[key] = 1;

//Проходим все связанные с текущей вершиной.

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

//Если значение элемента строки матрицы (по условию, нам дана матрица смежности) отлично от "0", то:

if(a[key][i]){

//если вершина "белая" (т. е. мы в неё еще не заходили)-

//запускаем рекурсивный вызов DFS от этой вершины.

if(was[i] == 0){if(dfs(i)) return true;}

//если вершина "серая" (мы её уже навещали, но не возвращались из ее потомков)-

//мы нашли цикл, следовательно поиск можно завершить.

else if(was[i] == 1){ return true;}

}

//Если ни один из if - ов не сработал, то "красим" вершину в черный цвет (отмечаем, как пройденную)

was[key] = 2;

//и возвращаем результат поиска (мы ничего не нашли).

return false;

}

int main() {

cin >> n;

a = new int *[n];

was = new int [n];

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

a[i] = new int [n];

was[i] = 0;

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

cin >> a[i][j];

}

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

//Проверяем поиском каждую вершину. Если поиск оказался успешным - выводим "1".

//Проверка цвета сделана ради ускорения процесса, иначе в поиске пришлось бы проходить весь

//цикл, даже если вершина покрашена в черный цвет.

if(!was[i]&&dfs(i)) {cout << "1\n"; return 0;}

}

//Если if ни разу не сработал - выводим "0".

cout << "0\n";

return 0;

}

Код на Java:

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

class Graphdfs
{
	private int[][] matrix; // Матрица смежности будет записана именно сюда.
	private int n; // Число вершин. 
	private int[] was;// Массив цвета вершины.
	public Graphdfs(){}
	public Graphdfs(int n)
	{
		this.n = n;
		matrix = new int [n][n];
		was = new int [n];
	}
	public void setMatrix(Scanner in)
	{
		for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			matrix[i][j] = in.nextInt();
	}
	public void showMatrix()
	{
		for(int i = 0; i < n; i++)
		{
			for(int j = 0; j < n; j++)
			{
				System.out.print(matrix[i][j]);
				if(j < n - 1) System.out.print(" ");
				else System.out.println();
			}
		}
	}
 	public boolean dfs(int key)
 	{
		was[key] = 1;
		for(int i = 0; i < n; i++)
		{
			if(matrix[key][i] != 0)
			{
				if(was[i] == 0){
					if(dfs(i)) return true;
				}
				else if(was[i] == 1){
					return true;
				}
			}
		}
		was[key] = 2;
		return false;
	}
	public int[] getWas(){
		return was;
	}
}

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		//System.out.println("ok1");
		Scanner in = new Scanner(System.in);
		//System.out.println("ok2");
		int n = in.nextInt();
		//System.out.println("ok3");
		Graphdfs Graph = new Graphdfs(n);
		//System.out.println("ok4");
		Graph.setMatrix(in);
		//System.out.println("ok5");
		//Graph.showMatrix();
		for(int i = 0; i < n; i++){
			if(Graph.getWas()[i] == 0 &&Graph.dfs(i) == true) {System.out.println(1); System.exit(0);}
		}
		System.out.println(0);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Graphdfs

{

private int[][] matrix; // Матрица смежности будет записана именно сюда.

private int n; // Число вершин.

private int[] was;// Массив цвета вершины.

public Graphdfs(){}

public Graphdfs(int n)

{

this.n = n;

matrix = new int [n][n];

was = new int [n];

}

public void setMatrix(Scanner in)

{

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

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

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

}

public void showMatrix()

{

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

{

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

{

System.out.print(matrix[i][j]);

if(j < n - 1) System.out.print(" ");

else System.out.println();

}

public boolean dfs(int key)

{

was[key] = 1;

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

{

if(matrix[key][i] != 0)

{

if(was[i] == 0){

if(dfs(i)) return true;

}

else if(was[i] == 1){

return true;

}

was[key] = 2;

return false;

}

public int[] getWas(){

return was;

}

public class Main

{

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

{

//System.out.println("ok1");

Scanner in = new Scanner(System.in);

//System.out.println("ok2");

int n = in.nextInt();

//System.out.println("ok3");

Graphdfs Graph = new Graphdfs(n);

//System.out.println("ok4");

Graph.setMatrix(in);

//System.out.println("ok5");

//Graph.showMatrix();

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

if(Graph.getWas()[i] == 0 &&Graph.dfs(i) == true) {System.out.println(1); System.exit(0);}

}

System.out.println(0);

}

Пояснение:

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

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

Related Images:

A159

15/11/2014 by Карташов Денис Геннадійович

Задача:

Даны натуральное число n, действительные числа [latex]a_{1}, …, a_{n}[/latex] [latex]\left( n\geq 3\right)[/latex] .

Получить [latex]b_{1}, …, b_{n-2}[/latex], где [latex]b_{i} = a_{i + 1} + a_{i + 2}[/latex], [latex]i=1, 2 , … , n-2[/latex].

Таблица:

[latex]a_{1}, …, a_{n}[/latex]	[latex]b_{1}, …, b_{n-2}[/latex]	Комментарий
1 2 3 4 5 6 7	5 7 9 11 13	Пройден
1.235 2.457 2.543 4.457 4.543 6.457 6.543	5 7 9 11 13	Пройден
9 -12 17 -10 19 -8 21	5 7 9 11 13	Пройден
-21 26 -21 28 -19 30 -17 22 -15 24 -13 26	5 7 9 11 13 5 7 9 11 13	Пройден
21 -26 21 -28 19 -30 17 -22 15 -24 13 -26	-5 -7 -9 -11 -13 -5 -7 -9 -11 -13	Пройден

Исходный код:

#include <iostream>
using namespace std;

int main() {
	double a, c, d; // Объявление переменных.
	double S;     //
	cin >> c >> d;  // Ввод значений буферных переменных. Более "с" вообще использоваться не будет.
	while(cin >> a){ // Цикл ввода данных.
		S=a+d; // Создание элементов второй последовательности.
		d=a;   // Смена элементов.
		cout <<" "<< S <<" "; //Вывод элементов.
	}
	return 0;  Конец.
}

#include <iostream>

using namespace std;

int main() {

double a, c, d; // Объявление переменных.

double S; //

cin >> c >> d; // Ввод значений буферных переменных. Более "с" вообще использоваться не будет.

while(cin >> a){ // Цикл ввода данных.

S=a+d; // Создание элементов второй последовательности.

d=a; // Смена элементов.

cout <<" "<< S <<" "; //Вывод элементов.

}

return 0; Конец.

}

Работать будет и такая версия:

#include <iostream>
using namespace std;

int main() {
	double a, c, d; // Объявление переменных.
	cin >> c >> d;  // Ввод значений буферных переменных. Более "с" вообще использоваться не будет.
	while(cin >> a){ // Цикл ввода данных.
		cout <<" "<< a+d <<" "; //Вывод элементов.
		d=a;   // Смена элементов.
	}
	return 0;  Конец.
}

#include <iostream>

using namespace std;

int main() {

double a, c, d; // Объявление переменных.

cin >> c >> d; // Ввод значений буферных переменных. Более "с" вообще использоваться не будет.

while(cin >> a){ // Цикл ввода данных.

cout <<" "<< a+d <<" "; //Вывод элементов.

d=a; // Смена элементов.

}

return 0; Конец.

}

Код на Java

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


public class Main
{
	private static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	private static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	
	public static void main (String[] args) throws java.lang.Exception
	{
		Double a = 0.0;
		Double b = 0.0;
		
		while(in.nextToken() != StreamTokenizer.TT_EOF){
			a = in.nval;
			out.print(a + b);
			out.print(" ");
			b = a;
		}
		out.flush();
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

private static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

private static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

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

{

Double a = 0.0;

Double b = 0.0;

while(in.nextToken() != StreamTokenizer.TT_EOF){

a = in.nval;

out.print(a + b);

out.print(" ");

b = a;

}

out.flush();

}

Описание:

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

Алгоритм:

Объявление необходимых переменных.
Отдельно ввод первого и второго элемента первой последовательности.
Создание цикла для ввода данных.
1. Печать суммы второго и третьего элемента первой последовательности (первый элемент результирующей последовательности).
2. Обеспечение сдвига суммируемых элементов (со второго и третьего на третий и четвертый и т. д.)
Окончание работы программы после завершения цикла.

Ссылка на Ideone.

Related Images:

A412г

11/11/2014 by Карташов Денис Геннадійович

Задача:

Даны две целочисленные квадратные матрицы порядка 6. Найти последовательность из нулей и единиц [latex]b_{1} , … , b_{6}[/latex] такую, что [latex]b_{i} = 1[/latex], когда:

г) количество отрицательных и неотрицательных элементов [latex] i [/latex]- строки первой матрицы совпадает соответственно с количеством отрицательных и неотрицательных элементов [latex] i[/latex]-строки второй матрицы.

Матрица [latex]A[/latex]	Матрица [latex]B[/latex]	Ожидаемый результат	Комментарий
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	1 1 1 1 1 1	Тест пройден
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1	0 0 0 0 0 0	Тест пройден
0 2 2 3 4 4 1 3 3 4 5 5 2 4 4 5 6 6 3 5 5 6 7 7 4 6 6 7 8 8 5 7 7 8 9 9	0 2 2 3 4 4 -1 3 1 4 3 5 -2 4 0 5 2 6 -3 5 -1 6 1 7 -4 6 -2 7 0 8 -5 7 -3 8 -1 9	1 0 0 0 0 0	Тест пройден
0 2 2 3 4 4 1 3 3 -4 5 5 2 4 -4 5 6 6 3 -5 5 6 7 -7 4 6 -6 -7 8 8 5 -7 7 -8 9 -9	0 2 2 3 4 4 -1 3 1 4 3 5 -2 4 0 5 2 6 -3 5 -1 6 1 7 -4 6 -2 7 0 8 -5 7 -3 8 -1 9	1 1 1 1 1 1	Тест пройден

Исходный код:

#include <iostream>
using namespace std;

void input( int a[6][6]){                        //Решил осуществить ввод данных с помощью функции.
	for(int i=0; i<6; i++){                  // Экономит место, так как мне необходимо ввести данные в два массива.
		for(int j=0; j<6; j++){          
			cin >> a[i][j];
		}
	}
}
void EQ(int a[6][6], int b[6][6], int c[6]){                // Главная функция. Ставим два счетчика, которые будут увеличивать свое значение, как только встретят отрицательный элемент в строках массивов.
	for(int i=0; i<6; i++){
	        int t=0, g=0;
		for(int j=0; j<6; j++){          // Проверка i - той строки первого массива.
			if( a[i][j] < 0 ){
				t++;             // Увеличение первого счетчика.
			}
		}
		for(int j=0; j<6; j++){          // Проверка i - той строки второго массива.
			if( b[i][j] < 0 ){
				g++;             // Увеличение второго счетчика.
			}	
		}
		c[i]= t == g? 1 : 0;  // Условие: "Если значение первого счетчика равно значению второго, то записываем в результирующий массив единицу, иначе нуль."
	}
}

void output( int a[6]){                          // Функция для печати результирующей последовательности
	for(int i=0; i<6; i++){
		cout<< a[i] <<" ";
	}
}

int main() {
	int a[6][6], b[6][6];            // Объявление массивов.
    int c[6]; 
	input(a);                        // Применение функций.
	input(b);                        
	EQ(a, b, c); 
    output (c); 
	return 0; //Конец.
}

#include <iostream>

using namespace std;

void input( int a[6][6]){ //Решил осуществить ввод данных с помощью функции.

for(int i=0; i<6; i++){ // Экономит место, так как мне необходимо ввести данные в два массива.

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

cin >> a[i][j];

}

void EQ(int a[6][6], int b[6][6], int c[6]){ // Главная функция. Ставим два счетчика, которые будут увеличивать свое значение, как только встретят отрицательный элемент в строках массивов.

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

int t=0, g=0;

for(int j=0; j<6; j++){ // Проверка i - той строки первого массива.

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

t++; // Увеличение первого счетчика.

}

for(int j=0; j<6; j++){ // Проверка i - той строки второго массива.

if( b[i][j] < 0 ){

g++; // Увеличение второго счетчика.

}

c[i]= t == g? 1 : 0; // Условие: "Если значение первого счетчика равно значению второго, то записываем в результирующий массив единицу, иначе нуль."

}

void output( int a[6]){ // Функция для печати результирующей последовательности

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

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

}

int main() {

int a[6][6], b[6][6]; // Объявление массивов.

int c[6];

input(a); // Применение функций.

input(b);

EQ(a, b, c);

output (c);

return 0; //Конец.

}

Код на Java

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


public class Main
{
	
	private static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	private static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
	
	public static int nextInt() throws IOException{
		in.nextToken();
		return (int)in.nval;
	}
	
	
	public static void read(int[][] a)  throws IOException{
		int n = a.length;
		int m = a[0].length;
		for(int i = 0;  i < n; i++){
			for(int j = 0; j < m; j++){
				a[i][j] = nextInt();
			}
		}
	}
	
	
	public static void print(int[] a){
		int m = a.length;
		for(int j = 0; j < m; j++){
			out.print(a[j]);
		}
		out.println();
	}
	
	
	public static void EQ(int[][] a, int[][] b, int[] c){ 
		for(int i = 0; i < a.length; i++){
			
			int t=0, g=0;
			
			for(int j=0; j < a.length; j++){
				if( a[i][j] < 0 ){
					t++;
				}
			}
			
			for(int j=0; j < b.length; j++){
				if( b[i][j] < 0 ){
					g++;
				}	
			}
			
			c[i] = t == g? 1 : 0;
		}
	}
	
	
	public static void main (String[] args) throws java.lang.Exception
	{
		int [][] a = new int[6][6], b = new int[6][6];
		int [] c = new int [6];
		read(a);
		read(b);
		EQ(a,b,c);
		print(c);
		out.flush();
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

private static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

private static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

public static int nextInt() throws IOException{

in.nextToken();

return (int)in.nval;

}

public static void read(int[][] a) throws IOException{

int n = a.length;

int m = a[0].length;

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

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

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

}

public static void print(int[] a){

int m = a.length;

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

out.print(a[j]);

}

out.println();

}

public static void EQ(int[][] a, int[][] b, int[] c){

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

int t=0, g=0;

for(int j=0; j < a.length; j++){

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

t++;

}

for(int j=0; j < b.length; j++){

if( b[i][j] < 0 ){

g++;

}

c[i] = t == g? 1 : 0;

}

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

{

int [][] a = new int[6][6], b = new int[6][6];

int [] c = new int [6];

read(a);

read(b);

EQ(a,b,c);

print(c);

out.flush();

}

Описание:

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

Алгоритм:

Создаем функцию для ввода данных.
1. Создаем первый цикл для перебора строк.
2. Создаем вложенный цикл для перебора каждого элемента массива и функцию ввода данных.
Создаем главную функцию.
1. Создаем цикл, перебирающий строки массивов.
2. Создаем два счетчика.
3. Создаем первый вложенный цикл, для перебора каждого элемента второго массива.
  - В случае обнаружения отрицательных элементов, увеличиваем счетчик.
4. Создаем первый вложенный цикл, для перебора каждого элемента второго массива.
  - В случае обнаружения отрицательных элементов, увеличиваем счетчик.
5. Объявляем условие вывода данных. Так как условие находится внутри главного цикла, то будет выведено по одному значению, которое характеризует каждую строку.
Создаем функцию для печати результата.
1. Один цикл для перебора каждого элемента одномерного массива.
В функции «int main ()»:
1. Вводим значения элементов первого массива.
2. Вводим значения элементов второго массива.
3. Применяем главную функцию к данным массивам.
4. Печатаем результат.
5. Окончание работы программы.

Ссылка на Ideone.

Функция пересчета отрицательных элементов в заданной строке заданного массива.

#include <iostream>
using namespace std;
 
void check(int **arr, int m, int n, int i){
	int k = 0;
	for(int j = 0; j < n; j++){
		if(arr[i][j] < 0){
			k++;
		}
	}
	return k;
}
int main() {
	int **a = new int*[3]; 
	for(int i=0; i<3; i++){
		a[i] = new int[3];
		for( int j=0; j<3; j++){
		cin >> a[i][j];
		}
	}
	check(a, 3, 3, 1);
	return 0;
}

#include <iostream>

using namespace std;

void check(int **arr, int m, int n, int i){

int k = 0;

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

if(arr[i][j] < 0){

k++;

}

return k;

}

int main() {

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

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

a[i] = new int[3];

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

cin >> a[i][j];

}

check(a, 3, 3, 1);

return 0;

}

Рабочий образец.

Related Images:

Ю2.25

31/10/2014 by Карташов Денис Геннадійович

Задача. На шахматной доске стоят черный король и белые ладья и слон (ладья бьет по горизонтали и вертикали, слон — по диагоналям). Проверить, есть ли угроза королю и если есть, то от кого именно. Учесть возможность защиты (например, ладья не бьет через слона).

[latex]x _{1}, y_{1}[/latex]- координаты слона.

[latex]x _{2}, y_{2}[/latex]- координаты ладьи.

[latex]x _{3}, y_{3}[/latex]- координаты короля.

Таблица:

[latex]x _{1} [/latex]	[latex]y _{1} [/latex]	[latex]x _{2} [/latex]	[latex]y _{2} [/latex]	[latex]x _{3} [/latex]	[latex]y _{3} [/latex]	Предполагаемый результат	Комментарий
1	1	2	2	4	4	Ладья перекрывает шаг от слона.	Тест пройден
4	5	2	5	5	5	Слон перекрывает шаг от ладьи.	Тест пройден
1	1	4	5	5	5	Короля атакует и слон и ладья.	Тест пройден
5	1	4	5	5	5	Ладья атакует короля.	Тест пройден
5	1	5	3	5	5	Ладья атакует короля.	Тест пройден
3	1	4	2	5	3	Ладья перекрывает шаг от слона.	Тест пройден
4	2	3	1	5	3	Слон объявляет шаг королю.	Тест пройден
1	4	5	3	2	2	Короля не атакует никакая фигура.	Тест пройден

Исходный код программы:

#include <stdio.h>
#include <math.h>
int main (){
  int x1, x2, x3, y1, y2, y3;             //Объявляем переменные, обозначающие координаты фигур
  printf("Введите координаты слона\n");      //
  scanf("%d %d", &x1, &y1);                  //
  printf("Введите координаты ладьи\n");      //Вводим координаты фигур, printf'ы помогают не запутаться.
  scanf("%d %d", &x2, &y2);                  //
  printf("Введите координаты короля\n");     //
  scanf("%d %d", &x3, &y3);                  // 
  	if((x1==x2&&y1==y2)||(x2==x3&&y2==y3)||(x1==x3&&y1==y3)){    //Проверка правильности ввода
		printf("Ошибка");
		return 0;
	}    
	if(((x2!=x3)&&(y2!=y3))&&(fabs(x1-x3)!=fabs(y1-y3))){        //Проверка условия №1
		printf("Короля не атакует никакая фигура\n");
	}
	if(x2==x3||y2==y3){                                          //Проверка условия №2 
       	if( ((x1==x2&&x2==x3)||(y1==y2&&y2==y3)) &&                                           //Уточняющее условие №1
			(((y1>y2&&y3>y1)||(y1<y2&&y3<y1))||((x1>x2&&x3>x1)||(x1<x2&&x3<x1))) ) 
			printf("Слон перекрывает шаx от ладьи\n");
		else{
			printf("Ладья объявляет шаx королю\n");
		}
	}       
	if(fabs(x1-x3)==fabs(y1-y3)){                                //Проверка условия №3  
		if((fabs(x2-x1)==fabs(y2-y1)&&fabs(x3-x2)==fabs(y3-y2))&&                   //Уточняющее условие №2
			(((y2>y1)&&(y3>y2))||((y2<y1)&&(y3<y2)))) 
			printf("Ладья перекрывает шах от слона\n");
		else{
			printf("Слон объявляет шах королю\n");
		}
	}		
   return 0;   //Конец.
}

#include <stdio.h>

#include <math.h>

int main (){

int x1, x2, x3, y1, y2, y3; //Объявляем переменные, обозначающие координаты фигур

printf("Введите координаты слона\n"); //

scanf("%d %d", &x1, &y1); //

printf("Введите координаты ладьи\n"); //Вводим координаты фигур, printf'ы помогают не запутаться.

scanf("%d %d", &x2, &y2); //

printf("Введите координаты короля\n"); //

scanf("%d %d", &x3, &y3); //

if((x1==x2&&y1==y2)||(x2==x3&&y2==y3)||(x1==x3&&y1==y3)){ //Проверка правильности ввода

printf("Ошибка");

return 0;

}

if(((x2!=x3)&&(y2!=y3))&&(fabs(x1-x3)!=fabs(y1-y3))){ //Проверка условия №1

printf("Короля не атакует никакая фигура\n");

}

if(x2==x3||y2==y3){ //Проверка условия №2

if( ((x1==x2&&x2==x3)||(y1==y2&&y2==y3)) && //Уточняющее условие №1

(((y1>y2&&y3>y1)||(y1<y2&&y3<y1))||((x1>x2&&x3>x1)||(x1<x2&&x3<x1))) )

printf("Слон перекрывает шаx от ладьи\n");

else{

printf("Ладья объявляет шаx королю\n");

}

if(fabs(x1-x3)==fabs(y1-y3)){ //Проверка условия №3

if((fabs(x2-x1)==fabs(y2-y1)&&fabs(x3-x2)==fabs(y3-y2))&& //Уточняющее условие №2

(((y2>y1)&&(y3>y2))||((y2<y1)&&(y3<y2))))

printf("Ладья перекрывает шах от слона\n");

else{

printf("Слон объявляет шах королю\n");

}

return 0; //Конец.

}

Описание:

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

Алгоритм:

Объявляем переменные и вводим их значения.
Проверка условий.
1. Проверка правильности ввода (не совпадают координаты фигур).
2. Проверка условия №1. Проверяем, может ли короля хоть кто-то атаковать. Т. е. стоят ли ладья и король на одной горизонтальной или вертикальной линии или стоит ли король на одной диагонали со слоном.
3. Проверка условия №2. Проверяем отдельно ладью. Если какая-то координата у ладьи и короля совпадает, то проверяем, находится ли слон между ними. Вывод результата.
4. Проверка условия №1. Проверка слона, если король и слон расположены на одной диагонали, то проверяем, находится ли ладья между ними. Вывод результата.
Окончание работы.

Ссылка на Ideone.

Related Images:

Ю 4.24

20/10/2014 by Карташов Денис Геннадійович

«Нарастающий итог»

Задача:

В массиве А[n] каждый элемент, кроме первого, заменить суммой всех предыдущих элементов.


Вводимые данные	Предполагаемый вывод	Комментарий
1 1 1 1 1 1	1 1 2 3 4 5	Тест пройден
1 2 3 4 5 6 7 8 9	1 1 3 6 10 15 21 28 36	Тест пройден
3 5 2 9 0 4 65 156 1	3 3 8 10 19 19 23 88 244	Тест пройден
2 -7 3 8 -4 5 -2 4 2	2 2 -5 -2 6 2 7 5 9	Тест пройден

Исходный код:

#include <iostream>
using namespace std;

int main() {
    int n;                                //Объявление переменной, обозначающей размерность массива
    cin >> n;                             //Ввод величины массива
    int a[n];                             //Создание массива
    for(int i=0;i<n;i++){                 //Ввод значений элементов массива с помощью цикла
        cin >> a[i];
    }
    int b[n];                             //Создание дополнительного массива, в котором и будет храниться результат.
    int S=0;                              //Создание вспомогательной переменной
    b[0]=a[0];                            //Инициализация первого элемента второго массива
    for(int i=1;i<n;i++){                 //Преобразование элементов первого массива в элементы второго массива и ввод результата во второй массив
        S+=a[i-1];                   
        b[i]=S;
    }
    for(int i=0;i<n;i++){    
        cout << b[i] << " ";          //Вывод результата
    }
    return 0;                //Конец 
}

#include <iostream>

using namespace std;

int main() {

int n; //Объявление переменной, обозначающей размерность массива

cin >> n; //Ввод величины массива

int a[n]; //Создание массива

for(int i=0;i<n;i++){ //Ввод значений элементов массива с помощью цикла

cin >> a[i];

}

int b[n]; //Создание дополнительного массива, в котором и будет храниться результат.

int S=0; //Создание вспомогательной переменной

b[0]=a[0]; //Инициализация первого элемента второго массива

for(int i=1;i<n;i++){ //Преобразование элементов первого массива в элементы второго массива и ввод результата во второй массив

S+=a[i-1];

b[i]=S;

}

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

cout << b[i] << " "; //Вывод результата

}

return 0; //Конец

}

Описание:

Постейшие операции с массивом. С помощью цикла записываем данные в массив, после чего, снова с помощью цикла, записываем новые данные во второй массив. Далее выводим результат.

Алгоритм:

Объявление переменной и ввод размерности массива.
Создание массива.
Создание цикла, для записи вводимых данных в массив.
Создание нового массива.
Создание цикла, для ввода обработанных данных в новый массив.
Создание цикла, для вывода результата.
Окончания работы программы.

Ссылка на Ideone.

Другой вариант:

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n];
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    
    int S=0;
    int i;
    for(i=0;i<n;i++){
        for(int j=0;j<n-i-1;j++){
            S+=a[j];
        }
    a[n-i-1]=S;
    S=0;
    }
    a[0]=a[1];
    for(int i=0;i<n;i++){    
        printf(" %d ", a[i]);
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int a[n];

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

cin >> a[i];

}

int S=0;

int i;

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

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

S+=a[j];

}

a[n-i-1]=S;

S=0;

}

a[0]=a[1];

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

printf(" %d ", a[i]);

}

return 0;

}

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

Related Images:

A119(a)

20/10/2014 by Карташов Денис Геннадійович

Задача:

Вычислить бесконечную сумму с заданной точностью [latex]\varepsilon \left(\varepsilon > 0\right)[/latex]. Считать что требуемая точность достигнута, если несколько первых слагаемых и очередное слагаемое оказалось по модулю меньше, чем ε, это и все последующие слагаемые можно уже не учитывать.

[latex]\sum{\frac{1}{i^2}} [/latex]


[latex]\varepsilon[/latex]	Result	Комментарий
0.0000000000000045	1.644912487	Тест пройден
0.45	1.25	Тест пройден
0	Попробуйте…	Тест пройден
>1	1	Тест пройден

#include <iostream>
#include <iomanip>
using namespace std;
 
int main(){
	double Sum =0, e=100;      //Объявление переменных, которые обозначают член последовательности и сумму членов последовательности
	double E;           //Объявление переменной, которая обозначает точность, с которой мы будем находить сумму.
	cin >> E;           //Ввод значения точности
	if(E<=0){           //Проверка условия(точность не может быть равна нулю или быть отрицательным числом, иначе нас ждет бесконечный цикл)
		cout <<"Попробуйте ввести положительное число отличное от нуля!"<<endl;
		return 1;
	}
	else{
		for(int i = 1;e > E;i++){ //Главный цикл.
			e = 1.0/(i*i); //Вычисление члена последовательности
			Sum += e;           //Суммирование элементов
		}
	}
	cout << fixed <<setprecision(10) << Sum << endl;        //Вывод результата. P.S. Я все-таки нашел этот способ.
	return 0;        //Конец
}

#include <iostream>

#include <iomanip>

using namespace std;

int main(){

double Sum =0, e=100; //Объявление переменных, которые обозначают член последовательности и сумму членов последовательности

double E; //Объявление переменной, которая обозначает точность, с которой мы будем находить сумму.

cin >> E; //Ввод значения точности

if(E<=0){ //Проверка условия(точность не может быть равна нулю или быть отрицательным числом, иначе нас ждет бесконечный цикл)

cout <<"Попробуйте ввести положительное число отличное от нуля!"<<endl;

return 1;

}

else{

for(int i = 1;e > E;i++){ //Главный цикл.

e = 1.0/(i*i); //Вычисление члена последовательности

Sum += e; //Суммирование элементов

}

cout << fixed <<setprecision(10) << Sum << endl; //Вывод результата. P.S. Я все-таки нашел этот способ.

return 0; //Конец

}

Описание:

В задаче сказано посчитать сумму членов определенной последовательности с заданной точностью.

Алгоритм:

Объявление переменных, необходимых для обозначения члена последовательности, суммы членов последовательности и точности с которой будут проходить вычисления.
Ввод значения точности.
Проверка правильности ввода:
- Отрицательное или равное нулю [latex]\varepsilon[/latex] вызовет бесконечный цикл и как следствие — превышение лимита по времени.
Создание заведомо бесконечного цикла, который прерывается, как только член последовательности станет меньше, чем заданная точность.
Вывод результата и окончание работы.

Ссылка на Ideone.

Related Images:

Ю3.8

17/10/2014 by Карташов Денис Геннадійович

«Отскоки»

Задача: Материальная точка бросается на горизонтальную плоскость со скоростью [latex]V[/latex] и под углом [latex]\alpha[/latex] к ней ( плоскости ). При каждом ударе о плоскость, кинетическая энергия точи уменьшается в [latex]\beta[/latex] раз. Найти абсциссы первых [latex]n[/latex] точек касания. Сопротивлением воздуха пренебречь.

По умолчанию примем количество интересующих нас отскоков равным 3.

[latex]V[/latex](speed)[latex]m/c[/latex]	[latex]\alpha[/latex](corner)	[latex]\beta[/latex]	Первая координата	Вторая координата	Третья координата	Комментарий
10	15	2	5.09858	7.64787	8.92252	Тест пройден
8	30	4	5.65184	7.06480	7.41804	Тест пройден
27	45	3	74.3373	99.1164	107.376	Тест пройден
17	35	3	27.6926	36.9234	40.0004	Тест пройден
13	0	5	0.00000	0.00000	0.00000	Тест пройден

Замечание:

По неизвестной мне причине (думаю на погрешность округления) [latex]sin( \pi)[/latex] при вычислениях равен 1.24879e-15.

Исходный код:

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
   double speed, corner, twice_corner, B, Sum=0, sqrspeed;  // Ввод переменных типа double.
   const double g=9.80665;                                  // Ввод неизвестной компьютеру константы.
   int num;                                                 //Ввод числа отскоков, которые будут нас интересовать.
   cout <<" Первое число - это скорость,"
        <<endl
        <<" второе - угол,"
        <<endl
	    <<" третье - коэффициент уменьшения кинетической энергии,"
	    <<endl
	    <<" четвертое - это число точек касания с плоскостью."
	    <<endl;
	
    cin >> speed;             //Ввод значений переменных.    
    cin >> corner;
    cin >> B;
    cin >> num;
    if(speed<0||corner>90||corner<0||B<=0||num<=0){ // Проверка на недопустимые ситуации
		cout<<" Похоже произошла ошибка."<<endl<<" Пожалуйста, введите данные повторно."<<endl;
		return 1;
	} 
    twice_corner=2*M_PI*corner/180;            // Перевод величины угла из градусов в радианы и нахождение двойного угла
    sqrspeed=speed*speed;                      // Вычисление квадрата скорости точки
    for(int i=1;i<=num;i++){                   // Цикл: вычисление координат по формуле и вывод результатов.
   	    double x;
   	    x=sqrspeed*sin(twice_corner)/g;
   	    Sum+=x;
   	    cout<<"Координата точки номер " << i <<" = " << Sum <<endl;
   	    sqrspeed/=B;
   }
	return 0;                               //Конец
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double speed, corner, twice_corner, B, Sum=0, sqrspeed; // Ввод переменных типа double.

const double g=9.80665; // Ввод неизвестной компьютеру константы.

int num; //Ввод числа отскоков, которые будут нас интересовать.

cout <<" Первое число - это скорость,"

<<endl

<<" второе - угол,"

<<endl

<<" третье - коэффициент уменьшения кинетической энергии,"

<<endl

<<" четвертое - это число точек касания с плоскостью."

<<endl;

cin >> speed; //Ввод значений переменных.

cin >> corner;

cin >> B;

cin >> num;

if(speed<0||corner>90||corner<0||B<=0||num<=0){ // Проверка на недопустимые ситуации

cout<<" Похоже произошла ошибка."<<endl<<" Пожалуйста, введите данные повторно."<<endl;

return 1;

}

twice_corner=2*M_PI*corner/180; // Перевод величины угла из градусов в радианы и нахождение двойного угла

sqrspeed=speed*speed; // Вычисление квадрата скорости точки

for(int i=1;i<=num;i++){ // Цикл: вычисление координат по формуле и вывод результатов.

double x;

x=sqrspeed*sin(twice_corner)/g;

Sum+=x;

cout<<"Координата точки номер " << i <<" = " << Sum <<endl;

sqrspeed/=B;

}

return 0; //Конец

}

Для решения задачи необходимо вспомнить уроки физики в начале десятого класса, а именно главу о движении под углом к горизонту. Воспользуемся формулой расстояния полета материальной точки [latex]S=\frac{V^2sin(2\alpha) }{g}[/latex] . По условию задачи сказано, что кинетическая энергия уменьшается при каждом отскоке в [latex]\beta[/latex] раз. Если рассмотреть формулу кинетической энергии: [latex]E_{k}=\frac{ mV^2 }{2}[/latex]- можно заметить, что [latex] m[/latex] (масса) является константой, значит изменяться может только [latex]V^2[/latex] (скорость тела в квадрате). Если условится, что материальная точка начинает движение в начале координат, то координата первого отскока будет равна [latex]S[/latex], второй — [latex]S+S_{1}[/latex], третьей — [latex]S+S_{1}+S_{2}[/latex], n-ой — [latex]S+…+S_{n-1}[/latex].

Алгоритм:

Объявление переменных и константы(ускорение свободного падения).
Вывод поясняющей информации.
Ввод значений переменных.
Проверка недопустимых ситуаций:
- Проверка угла: значения угла выше 90 градусов или отрицательное значение противоречат условию задачи.
- Проверка скорости: отрицательное значение будет означать движение в противоположную интересующей нас сторону.
- Проверка коэффициента уменьшения кинетической энергии: это число должно быть хотя бы положительным.
- Проверка числа интересующих нас отскоков: это должно быть натуральное число.
Вычисление вспомогательных величин (двойной угол, скорость в квадрате).
Создание вычислительного цикла.
- Вывод значений.
Окончание работы.

Ссылка на Ideone.

Related Images:

А54

11/10/2014 by Карташов Денис Геннадійович

Задача:

Даны действительные числа [latex]x_{1}[/latex], [latex]x_{2}[/latex], [latex]x_{3}[/latex], [latex]y_{1}[/latex],[latex]y_{2}[/latex], [latex]y_{3}[/latex].

Принадлежит ли начало координат треугольнику с вершинами [latex]\left( x_{1} ; y_{1} \right) [/latex], [latex]\left( x_{2} ; y_{2} \right) [/latex], [latex]\left( x_{3} ; y_{3} \right) [/latex]?


[latex] x_{1} [/latex]	[latex] y_{1} [/latex]	[latex] x_{2} [/latex]	[latex] y_{2} [/latex]	[latex] x_{3} [/latex]	[latex] y_{3} [/latex]	Предполагаемый результат	Вывод
-400	0	240	1	210	1	Не принадлежит	Тест пройден
-400	0	240	1	210	-1	Принадлежит	Тест пройден
0	0	240	-1	2100	-1	Принадлежит	Тест пройден
-2	-2	5	-2	1	10	Принадлежит	Тест пройден
3	0	40	0	15	10	Не принадлежит	Тест пройден
-24	-2	29	-2	29	10	Принадлежит	Тест пройден
-12	-5	14	-5	7	-5	Жаль вас расстраивать…	Тест пройден

#include <iostream>
using namespace std;
 
int main() {
	double x1, x2, x3, y1, y2, y3; //
	double x=0, y=0;               // Обьявление переменных, обозначающих координаты вершин треугольника и начала координат
	cin>> x1 >> y1; //
	cin>> x2 >> y2; // Ввод координат вершин треугольника
	cin>> x3 >> y3; //
	if((y2-y1)*(x3-x1)-(y3-y1)*(x2-x1)==0){    //Небольшая перестраховка 
		cout<<"Жаль вас расстраивать, но это не треугольник."<<endl;
	}
	else{
		double A, B, C, O1, O2, O3;       //Обьявление вспомогательных переменных (нобязательные, но делают код понятнее)
		A=(y3-y2)*(x1-x2)-(y1-y2)*(x3-x2); 
		B=(y1-y3)*(x2-x3)-(y2-y3)*(x1-x3); 
		C=(y2-y1)*(x3-x1)-(y3-y1)*(x2-x1);  
		O1=(y3-y2)*(x-x2)-(y-y2)*(x3-x2);
        O2=(y3-y1)*(x-x1)-(y-y1)*(x3-x1);
        O3=(y2-y1)*(x-x1)-(y-y1)*(x2-x1);    
		if((O1*A>=0)&&(O2*B>=0)&&(O3*C>=0)){     // Главное услоие          
			cout<<"Точка принадлежит треугольнику"<<endl;
		}
		else{
			cout<<"Точка не принадлежит треугольнику"<<endl;
		}
	}
	return 0; //Конец
}

#include <iostream>

using namespace std;

int main() {

double x1, x2, x3, y1, y2, y3; //

double x=0, y=0; // Обьявление переменных, обозначающих координаты вершин треугольника и начала координат

cin>> x1 >> y1; //

cin>> x2 >> y2; // Ввод координат вершин треугольника

cin>> x3 >> y3; //

if((y2-y1)*(x3-x1)-(y3-y1)*(x2-x1)==0){ //Небольшая перестраховка

cout<<"Жаль вас расстраивать, но это не треугольник."<<endl;

}

else{

double A, B, C, O1, O2, O3; //Обьявление вспомогательных переменных (нобязательные, но делают код понятнее)

A=(y3-y2)*(x1-x2)-(y1-y2)*(x3-x2);

B=(y1-y3)*(x2-x3)-(y2-y3)*(x1-x3);

C=(y2-y1)*(x3-x1)-(y3-y1)*(x2-x1);

O1=(y3-y2)*(x-x2)-(y-y2)*(x3-x2);

O2=(y3-y1)*(x-x1)-(y-y1)*(x3-x1);

O3=(y2-y1)*(x-x1)-(y-y1)*(x2-x1);

if((O1*A>=0)&&(O2*B>=0)&&(O3*C>=0)){ // Главное услоие

cout<<"Точка принадлежит треугольнику"<<endl;

}

else{

cout<<"Точка не принадлежит треугольнику"<<endl;

}

return 0; //Конец

}

Описание:

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

Краткий алгоритм:

Объявление переменных, обозначающих координаты вершин треугольника.
Ввод координат вершин треугольника.
Небольшая проверка правильности ввода.
С помощью общего уравнения прямой [latex]\frac{y-y_{1}}{y_{2}-y_{1}}=\frac{x-x_{1}}{x_{2}-x_{1}}[/latex], приведенного в вид :[latex]\left(y_{2}-y_{1} \right) \left(x-x_{1}\right)-\left(y-y_{1} \right) \left(x_{2}-x_{1}\right)=0[/latex],- определяем расположение вершин треугольника относительно противоположных им сторон (название переменной показывает, какую вершину проверяют), а также начала координат относительно тех же сторон, после чего следует умножение соответствующих величин. В случае, если произведение больше, либо равно нулю во всех трех случаях, можно сделать вывод о том, что точка находится внутри треугольника.
Вывод вердикта и окончание работы.

Ссылка на Ideone.

Related Images:

Ю1.23

19/09/2014 by Карташов Денис Геннадійович

Задача

Треугольник задается координатами своих вершин на плоскости: [latex]A\left(x_{1};y_{1} \right)[/latex], [latex] B\left(x_{2};y_{2} \right)[/latex], [latex] C\left(x_{3};y_{3} \right)[/latex].
Найти сумму длин медиан данного треугольника.

Тесты:

[latex]x_{1}[/latex]	[latex]y_{1}[/latex]	[latex]x_{2}[/latex]	[latex]y_{2}[/latex]	[latex]x_{3}[/latex]	[latex]y_{3}[/latex]	Результат	Прохождение теста
0	4	0	7	0	2	Не является треугольником…	Пройден
51	0	97	0	68	0	Не является треугольником…	Пройден
1	7	3	13	6	22	Не является треугольником…	Пройден
0	3	0	0	4	0	10.3775	Пройден
0	0	1	1.7320	2	0	5.1960	Пройден

Исходный код программы:

#include <stdio.h>
#include <math.h>
 
int main() {      
    double x1,y1,x2,y2,x3,y3; //координаты вершин//
    double AF,BM,CN,P; //обозначения медиан и их суммы//
    printf("Введите координаты точки А\n");              
    scanf("%lf %lf",&x1,&y1);
    printf("Введите координаты точки B\n");
    scanf("%lf %lf",&x2,&y2);
    printf("Введите координаты точки C\n");
    scanf("%lf %lf",&x3,&y3);
    if((x1==x2&&x2==x3)||(y1==y2&&y2==y3)||((y2-y1)*(x3-x1)-(x2-x1)*(y3-y1)==0)) //Рассмотрение частных случаев//
    	printf("Не является треугольником, так как данные точки лежат на одной прямой \n");
    else {
       //Вычисления длин медиан;xF,yF,xM,yM,xN,yN;-координаты середин сторон треугольника//
       AF=sqrt(pow(x1-(x3+x2)/2,2)+pow(y1-(y3+y2)/2,2));   //xF=(x3+x2)/2,yF=(y3+y2)/2;//
       BM=sqrt(pow((x1+x3)/2-x2,2)+pow((y1+y3)/2-y2,2));   //xM=(x1+x3)/2, yM=(y1+y3)/2;//
       CN=sqrt(pow((x1+x2)/2-x3,2)+pow((y1+y2)/2-y3,2));   //xN=(x1+x2)/2, yN=(y1+y2)/2;//
       P=AF+BM+CN;//Вычисление суммы//
       printf("Сумма медиан треугольника ABC равна: %.4lf" ,P);
    }
    return 0;
    
}

#include <stdio.h>

#include <math.h>

int main() {

double x1,y1,x2,y2,x3,y3; //координаты вершин//

double AF,BM,CN,P; //обозначения медиан и их суммы//

printf("Введите координаты точки А\n");

scanf("%lf %lf",&x1,&y1);

printf("Введите координаты точки B\n");

scanf("%lf %lf",&x2,&y2);

printf("Введите координаты точки C\n");

scanf("%lf %lf",&x3,&y3);

if((x1==x2&&x2==x3)||(y1==y2&&y2==y3)||((y2-y1)*(x3-x1)-(x2-x1)*(y3-y1)==0)) //Рассмотрение частных случаев//

printf("Не является треугольником, так как данные точки лежат на одной прямой \n");

else {

//Вычисления длин медиан;xF,yF,xM,yM,xN,yN;-координаты середин сторон треугольника//

AF=sqrt(pow(x1-(x3+x2)/2,2)+pow(y1-(y3+y2)/2,2)); //xF=(x3+x2)/2,yF=(y3+y2)/2;//

BM=sqrt(pow((x1+x3)/2-x2,2)+pow((y1+y3)/2-y2,2)); //xM=(x1+x3)/2, yM=(y1+y3)/2;//

CN=sqrt(pow((x1+x2)/2-x3,2)+pow((y1+y2)/2-y3,2)); //xN=(x1+x2)/2, yN=(y1+y2)/2;//

P=AF+BM+CN;//Вычисление суммы//

printf("Сумма медиан треугольника ABC равна: %.4lf" ,P);

}

return 0;

}

Алгоритм:

Вводим переменные;
Вводим координаты точек [latex]A[/latex], [latex]B[/latex], [latex]C[/latex];
Используем условный оператор для выделения частного случая.
- Если точки будут лежать на одной прямой, то медиан, как и самого треугольника не может быть в принципе. Для проверки используем уравнение прямой, проходящей через две несовпадающие точки: [latex]\frac{y-y_{1}}{y_{2}-y_{1}}=\frac{x-x_{1}}{x_{2}-x_{1}}[/latex]. С помощью эквивалентных преобразований получаем формулу:[latex]\left(y_{2}-y_{1} \right) \left(x-x_{1}\right)-\left(y-y_{1} \right) \left(x_{2}-x_{1}\right)=0[/latex] c помощью которой (подставив вместо [latex]x[/latex] и [latex]y[/latex] [latex]x_{3}[/latex] и [latex]y_{3}[/latex] соответственно) сможем определить, находятся ли данные точки на одной прямой).
- В случае, если точки не находятся на одной прямой, находим длины отрезков соединяющих середины сторон с противоположными им вершинами(эти отрезки и являются медианами); (Координаты середин отрезков находим по формулам: [latex]\frac{\left(x_{1}+x_{2} \right)}{2}[/latex], [latex]\frac{\left(y_{1}+y_{2} \right)}{2}[/latex], где [latex]\left(x_{1};y_{1} \right)[/latex] и [latex]\left(x_{2};y_{2} \right)[/latex] — координаты концов отрезка, середину которого мы находим. Длину медианы находим по формуле: [latex]AB=\sqrt{\left(x_{1}-x_{2} \right)^{2}+\left(y_{1}-y_{2} \right)^{2}}[/latex] , где [latex]\left(x_{1};y_{1} \right)[/latex] и [latex]\left(x_{2};y_{2} \right)[/latex] — координаты точек [latex]A[/latex] и [latex]B[/latex] соответственно).
Находим сумму длин этих отрезков. (Простое сложение).