e-olymp 6128. Простой дек

01/06/2017 by Сабиров Ильдар

Задача. Простой дек

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

push_front

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

push_back

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

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

pop_back

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

front

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

back

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

size

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

clear

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

exit

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

Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Все операции:

pop_front
pop_back
front
back

всегда корректны.

Объяснение: Количество элементов во всех структурах данных не превышает 10000, если это не указано особо.

Тесты

№

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

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

push_back 3

push_back 14

size

clear

push_front 1

back

push_back 2

front

pop_back

size

pop_front

size

exit

bye

size

push_back 8

push_front 4

size

front

back

push_back 3

pop_front

front

pop_back

back

exit

bye

Решение

#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct Deque
{
    vector<int> box1;
    vector<int> box2;
    int n, box_size=0;
    void push_front(int n)
    {
        box1.push_back(n);
        box_size++;
    }
    void push_back(int n)
    {
        box2.push_back(n);
        box_size++;
    }
    int pop_front()
    {
        if(box1.size()>0)
        {
            int a=box1[box1.size()-1];
            box1.erase(box1.end()-1);
            box_size--;
            return a;
        }
        else if(box2.size()>0)
        {
            int a=box2[0];
            box2.erase(box2.begin());
            box_size--;
            return a;
        }
        return 1;
    }
    int pop_back()
    {
        if(box2.size()>0)
        {
            int a=box2[box2.size()-1];
            box2.erase(box2.end()-1);
            box_size--;
            return a;
        }
        else if(box1.size()>0)
        {
            int a=box1[0];
            box1.erase(box1.begin());
            box_size--;
            return a;
        }
        return 1;
    }
    int front()
    {
        if(box1.size()>0)
        {
            int a=box1[box1.size()-1];
            return a;
        }
        else if(box2.size()>0)
        {
            int a=box2[0];
            return a;
        }
        return 1;
    }
    int back()
    {
        if(box2.size()>0)
        {
            int a=box2[box2.size()-1];
            return a;
        }
        else if(box1.size()>0)
        {
            int a=box1[0];
            return a;
        }
        return 1;
    }
    int size()
    {
        return box_size;
    }
    string clear()
    {
        box1.erase(box1.begin(), box1.end());
        box2.erase(box2.begin(), box2.end());
        box_size=0;
        return "ok";
    }
    string exit()
    {
        return "bye";
    }
};
int main() 
{
    Deque a;
    string s;
    while(cin>>s)
    {
        if(s=="push_front")
        {
            int n;
            cin>>n;
            a.push_front(n);
            cout<<"ok"<<endl;
        }
        if(s=="push_back")
        {
            int n;
            cin>>n;
            a.push_back(n);
            cout<<"ok"<<endl;
        }
        if(s=="pop_front")
        {
            cout<<a.pop_front()<<endl;
        }
        if(s=="pop_back")
        {
            cout<<a.pop_back()<<endl;
        }
        if(s=="front")
        {
            cout<<a.front()<<endl;
        }
        if(s=="back")
        {
            cout<<a.back()<<endl;
        }
        if(s=="size")
        {
            cout<<a.size()<<endl;
        }
        if(s=="clear"){
            a.clear();
            cout<<a.clear()<<endl;
        }
        if(s=="exit")
        {
            cout<<a.exit()<<endl;
            break;
        }
    }
    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

146

147

148

149

150

151

#include <iostream>

#include <vector>

#include <string>

using namespace std;

struct Deque

{

vector<int> box1;

vector<int> box2;

int n, box_size=0;

void push_front(int n)

{

box1.push_back(n);

box_size++;

}

void push_back(int n)

{

box2.push_back(n);

box_size++;

}

int pop_front()

{

if(box1.size()>0)

{

int a=box1[box1.size()-1];

box1.erase(box1.end()-1);

box_size--;

return a;

}

else if(box2.size()>0)

{

int a=box2[0];

box2.erase(box2.begin());

box_size--;

return a;

}

return 1;

}

int pop_back()

{

if(box2.size()>0)

{

int a=box2[box2.size()-1];

box2.erase(box2.end()-1);

box_size--;

return a;

}

else if(box1.size()>0)

{

int a=box1[0];

box1.erase(box1.begin());

box_size--;

return a;

}

return 1;

}

int front()

{

if(box1.size()>0)

{

int a=box1[box1.size()-1];

return a;

}

else if(box2.size()>0)

{

int a=box2[0];

return a;

}

return 1;

}

int back()

{

if(box2.size()>0)

{

int a=box2[box2.size()-1];

return a;

}

else if(box1.size()>0)

{

int a=box1[0];

return a;

}

return 1;

}

int size()

{

return box_size;

}

string clear()

{

box1.erase(box1.begin(), box1.end());

box2.erase(box2.begin(), box2.end());

box_size=0;

return "ok";

}

string exit()

{

return "bye";

}

};

int main()

{

Deque a;

string s;

while(cin>>s)

{

if(s=="push_front")

{

int n;

cin>>n;

a.push_front(n);

cout<<"ok"<<endl;

}

if(s=="push_back")

{

int n;

cin>>n;

a.push_back(n);

cout<<"ok"<<endl;

}

if(s=="pop_front")

{

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

}

if(s=="pop_back")

{

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

}

if(s=="front")

{

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

}

if(s=="back")

{

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

}

if(s=="size")

{

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

}

if(s=="clear"){

a.clear();

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

}

if(s=="exit")

{

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

break;

}

return 0;

}

Алгоритм решения

Реализация двусторонней очереди идет посредством векторов [latex]box1[/latex] и [latex]box2[/latex], поэтому нет необходимости делать проверку на переполнение. Команды [latex]push_front[/latex] и [latex]push_back[/latex] соответственно добавляют в концы векторов [latex]box1[/latex] и [latex]box2[/latex] элементы и увеличивают размер дека box_size (на единицу за каждый добавленный элемент). Рассмотрим команду [latex]front[/latex]. Проверяя присутствие элементов в [latex]box1[/latex] мы выводим последний элемент вектора, так как добавляли элемент с помощью [latex]push_front[/latex] в конец вектора [latex]box1[/latex]. Если же вектор [latex]box1[/latex] пуст, то выводим первый элемент вектора [latex]box2[/latex], который в случае пустого вектора [latex]box1[/latex] является первым элементом дека. Команда [latex]back[/latex] относительно [latex]front[/latex] с векторами работает инверсивно. Т.е. Проверяя присутствие элементов в [latex]box2[/latex] выводим последний элемент данного вектора. Если же вектор [latex]box2[/latex] пуст, то выводим первый элемент вектора [latex]box1[/latex] , который в случае пустого вектора [latex]box2[/latex] является последним элементом дека. С командами [latex]pop_front[/latex] и [latex]pop_back[/latex] работают идентично [latex]front[/latex] и [latex]back[/latex]. Отличие лишь в том, что команды [latex]pop[/latex] в дополнении к выводу элемента удаляют его, уменьшая размер дека [latex]box_size[/latex] (на единицу за каждый удаленный элемент). Команда [latex]size[/latex] выводит размер дека [latex]box_size[/latex]. Команда clear удаляет все элементы векторов [latex]box1[/latex], [latex]box2[/latex] и обнуляет размер дека. Команда [latex]exit[/latex] выводит «bye» и завершает работу программы. Команды принимаются из потока ввода посредством строки s.

Ссылка на код.

e-olymp.

Related Images:

А290

08/11/2016 by Сабиров Ильдар

Задача. Даны действительные числа [latex]x_{1},\ldots,x_{n}[/latex], [latex]y_{1},\ldots,y_{n}[/latex]. Получить [latex]x’_{1},\ldots,x’_{n}[/latex],[latex]y’_{1},\ldots,y’_{n}[/latex], преобразовав для получения [latex]x’_{i},y’_{i}[/latex] члены [latex]x_{i},y_{i}[/latex] по правилу: если они оба отрицательны, то каждый из них увеличить на 0.5; если отрицательно только одно число, то отрицательное число заменить его квадратом; если оба числа неотрицательны, то каждое из них заменить на среднее арифметическое исходных значений.

Тесты

n	[latex]x_{1},\ldots,x_{n}[/latex] [latex]y_{1},\ldots,y_{n}[/latex]	[latex]x’_{1},\ldots,x’_{n}[/latex][latex]y’_{1},\ldots,y’_{n}[/latex]	Комментарий
4	1 4 -3 8 3 -2 -4 2	2 4 -2.5 5 2 4 -3.5 5	Пройдено
5	0 -0.5 4 -9 0.35 0 -0.5 11 0.247 1.650	0 0 7.5 81 1 0 0 7.5 0.247 1	Пройдено
3	0 3 -0.14942 -3 0 793	0 1.5 0.0223263 9 1.5 793	Пройдено

Реализация (массив структур)

#include <iostream>
using namespace std;
struct okay {
    double a,b;
};
int main() {
    int numb;
    cin>>numb;
    okay x[numb];
    for(int i=0;i<numb;i++){
        cin>>x[i].a;
    }
    for(int i=0;i<numb;i++){
        cin>>x[i].b;
    }
    for(int i=0;i<numb;i++){
        if(x[i].a<0 && x[i].b<0){
            x[i].a=x[i].a+0.5;
            x[i].b=x[i].b+0.5;
        }
        else if(x[i].a<0 && x[i].b>=0){
            x[i].a=x[i].a*x[i].a;
        }
        else if(x[i].a>=0 && x[i].b<0){
            x[i].b=x[i].b*x[i].b;
        }
        else {
            x[i].a=(x[i].a+x[i].b)/2;
            x[i].b=x[i].a;
        }
    }
    for(int i=0;i<numb;i++){
        cout<<x[i].a<<" ";
    }
    cout<<endl;
    for(int i=0;i<numb;i++){
        cout<<x[i].b<<" ";
    }
    return 0;
}

#include <iostream>

using namespace std;

struct okay {

double a,b;

};

int main() {

int numb;

cin>>numb;

okay x[numb];

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

cin>>x[i].a;

}

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

cin>>x[i].b;

}

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

if(x[i].a<0 && x[i].b<0){

x[i].a=x[i].a+0.5;

x[i].b=x[i].b+0.5;

}

else if(x[i].a<0 && x[i].b>=0){

x[i].a=x[i].a*x[i].a;

}

else if(x[i].a>=0 && x[i].b<0){

x[i].b=x[i].b*x[i].b;

}

else {

x[i].a=(x[i].a+x[i].b)/2;

x[i].b=x[i].a;

}

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

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

}

cout<<endl;

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

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

}

return 0;

}

Алгоритм решения (массив структур)
Для выполнения данной задачи, воспользуемся массивом структур. Каждый [latex]i[/latex]-ый элемент такого массива заполняем двумя действительными числами [latex]x_{i}[/latex] и [latex]y_{i}[/latex]. После этого мы выполняем проверку и преобразование этих чисел по заданным в условии правилам. Затем их выводим.

Реализация (класс vector)

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

int main() {
    double a,b;
    vector<double> c;
    vector<double> d;
    while(cin>>a && cin>>b){
        c.push_back(a);
        d.push_back(b);
    }
    for(int i=0;i<c.size();i++){
        if(c[i]<0 && d[i]<0){
            c[i]=c[i]+0.5;
            d[i]=d[i]+0.5;
        }
        else if(c[i]<0 && d[i]>=0){
            c[i]=c[i]*c[i];
        }
        else if(c[i]>=0 && d[i]<0){
            d[i]=d[i]*d[i];
        }
        else {
            c[i]=(c[i]+d[i])/2;
            d[i]=c[i];
        }
    }
    for(int i=0;i<c.size();i++){
        cout<<c[i]<<" ";    
    }
    cout<<endl;
    for(int i=0;i<d.size();i++){
        cout<<d[i]<<" ";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

double a,b;

vector<double> c;

vector<double> d;

while(cin>>a && cin>>b){

c.push_back(a);

d.push_back(b);

}

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

if(c[i]<0 && d[i]<0){

c[i]=c[i]+0.5;

d[i]=d[i]+0.5;

}

else if(c[i]<0 && d[i]>=0){

c[i]=c[i]*c[i];

}

else if(c[i]>=0 && d[i]<0){

d[i]=d[i]*d[i];

}

else {

c[i]=(c[i]+d[i])/2;

d[i]=c[i];

}

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

cout<<c[i]<<" ";

}

cout<<endl;

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

cout<<d[i]<<" ";

}

return 0;

}

Алгоритм решения (класс vector)
Данный способ реализации помогает решить задачу преобразования чисел [latex]x_{1},\ldots,x_{n}[/latex], [latex]y_{1},\ldots, y_{n}[/latex] для неизвестного значения [latex]n[/latex] — количества элементов [latex]x_{i}[/latex] и [latex]y_{i}[/latex]. Их количество будет зависить от количества введенных элементов. Программа считывает элементы [latex]x_{i}[/latex] и [latex]y_{i}[/latex] поочередно, т.е. [latex]x_{1}\rightarrow y_{1}\rightarrow x_{2} \rightarrow y_{2} \rightarrow\ldots\rightarrow x_{n}\rightarrow y_{n}[/latex]. В остальном алгоритм такой же как с массивом структур.

Ссылка на код (массив структур)
Ссылка на код (класс vector)

Related Images:

A271

24/06/2016 by Сабиров Ильдар

Задача.
Даны действительные числа [latex]a_{1},\ldots,a_{k}[/latex]. Получить [latex]\sqrt{\frac{\sum\limits_{i=1}^{k}(a_{i}-\tilde{a})^{2}}{k-1}},[/latex] где [latex]\tilde{a}=\frac{1}{k}\sum\limits_{i=1}^{k}a_{i}.[/latex]

Тесты

input	[latex]\tilde{a}[/latex]	[latex]\sqrt{\frac{\sum\limits_{i=1}^{k}(a_{i}-\tilde{a})^{2}}{k-1}}[/latex]	Комментарий
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	8	4.4712	Пройдено
2 8 3 4 5 6 7 9 11 15 17 12 19 7 5 1 7 9 19 14	9	6.35834659	Пройдено
3 3 3 3 3 0 0 0 5 5 5 15 15 15 15	6	5.8554	Пройдено

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

int main() {
    double a=0,s=0,z;
    int y;
    vector<int> x;
    while(cin>>z){
        x.push_back(z);
    }
    for (int i=0;i<x.size();i++){
        a+=x[i];
    }
    a=a/x.size();
    for (int i=0;i<x.size();i++){
        s=s+(a-x[i])*(a-x[i]);
    }
    s=s/(x.size()-1);
    s=sqrt(s);
    cout<<a<<" ";
    cout<<s<<" ";
    return 0;
}

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

int main() {

double a=0,s=0,z;

int y;

vector<int> x;

while(cin>>z){

x.push_back(z);

}

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

a+=x[i];

}

a=a/x.size();

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

s=s+(a-x[i])*(a-x[i]);

}

s=s/(x.size()-1);

s=sqrt(s);

cout<<a<<" ";

cout<<s<<" ";

return 0;

}

Решение

Заполняем вектор действительными числами
Считаем их сумму (с помощью цикла прибавляем каждый элемент вектора).
Находим значение [latex]\tilde{a}[/latex].
Находим сумму под корнем второй формулы через цикл (аналогично п.2)
Производим необходимые арифметические операции для нахождения значения второй формулы.
Вывод значений.
Ссылка на код

Related Images:

Ю3.25

27/01/2016 by Сабиров Ильдар

Задача.

Для заданных [latex]m[/latex] и [latex]n[/latex] вычислить число сочетаний [latex]C_m^n[/latex] непосредственно: [latex]C_m^n=\frac{m!}{n!(m-n)!}[/latex] и по рекуррентным формулам:

• [latex]C_m^n=\frac{m-n+1}{n}\cdot C_m^{n-1}, C_m^1=m;[/latex]

• [latex]C_m^n=C_{m-1}^{n-1}+C_{m-1}^n;C_m^1=m,C_m^m=1.[/latex]

Сравнить время вычислений(или число операций) по каждой формуле.

Тесты:

[latex]m[/latex]	[latex]n[/latex]	[latex]C_m^n[/latex]	Комментарий
122	12	По первой формуле равно: 1.29803e+16 По второй формуле равно: 1.29803e+16 По третьей формуле равно: 12980291311103116 Первая формула сработала за(в милисек):0.056 Вторая формула сработала за(в милисек):0.009 Третья формула сработала за(в милисек):0.021	Пройдено
14	5	По первой формуле равно: 2002 По второй формуле равно: 2002 По третьей формуле равно: 2002 Первая формула сработала за(в милисек):0.064 Вторая формула сработала за(в милисек): 0.009 Третья формула сработала за(в милисек): 0.012	Пройдено
16	7	По первой формуле равно: 11440 По второй формуле равно: 11440 По третьей формуле равно: 11440 Первая формула сработала за(в милисек):0.067 Вторая формула сработала за(в милисек): 0.009 Третья формула сработала за(в милисек): 0.012	Пройдено

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

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

int main() {
	unsigned int start_time1,start_time2,start_time3,search_time1,search_time2,search_time3;
	int i,y,u,m,n,h,j,x;
	long long c3=0;
	cin>>m;
	cin>>n;
	double k=m,c2=1,c1;
	long long D[m+3][n+1];
	double b=m-n, q=n, w=m, z=b;
	if(m>n && n>=1)
	{
		start_time1 = clock();
		for(i=1;i<n;i++) {q=q*i;}
		for(y=1;y<m;y++) {w=w*y;}
		for(u=1;u<b;u++) {z=z*u;}
		c1=w/(q*z);
		cout<<"По первой формуле равно:"<<c1<<" "<<endl;
		search_time1 = clock() - start_time1;
		
		start_time2 = clock();
		for(i=n;i>=1;i--)
		{
			c2*=(k-i+1)/i;
		}
		cout<<"По второй формуле равно:"<<c2<<" "<<endl;
		search_time2 = clock() - start_time2;
		
		start_time3 =  clock();
		for(y=1;y<=m;y++) // Для каждой строки.
		{
			D[y][1]=y;
			D[y][y]=1;
			for(x=2;x<=n && x<y;x++)
			{
				D[y][x]=D[y-1][x-1]+D[y-1][x];
			}
		}
		c3=D[m][n];
		cout<<"По третьей формyле равно:"<<c3<<" "<<endl;
		search_time3 = clock() - start_time3;
	}
	else if(m<n) {
		cout<<"invalid";
	}
	
	cout<<"Первая формула сработала за:(в милисек)"<<((double)search_time1/CLOCKS_PER_SEC)*1000<<endl;
	cout<<"Вторая формула сработала за:(в милисек)"<<(double)search_time2/CLOCKS_PER_SEC*1000<<endl;
	cout<<"Третья формула сработала за:(в милисек)"<<(double)search_time3/CLOCKS_PER_SEC*1000<<endl;
	if(search_time1<search_time2 && search_time1<search_time3) { cout<<"Первая формула выполняется быстрее."<<endl; }
	else if(search_time2<search_time1 && search_time2<search_time3) { cout<<"Вторая формула выполняется быстрее."<<endl; }
	else if(search_time3<search_time2 && search_time3<search_time1) { cout<<"Третья формула выполняется быстрее."<<endl; }
	return 0;
}

#include <iostream>

#include <ctime>

using namespace std;

int main() {

unsigned int start_time1,start_time2,start_time3,search_time1,search_time2,search_time3;

int i,y,u,m,n,h,j,x;

long long c3=0;

cin>>m;

cin>>n;

double k=m,c2=1,c1;

long long D[m+3][n+1];

double b=m-n, q=n, w=m, z=b;

if(m>n && n>=1)

{

start_time1 = clock();

for(i=1;i<n;i++) {q=q*i;}

for(y=1;y<m;y++) {w=w*y;}

for(u=1;u<b;u++) {z=z*u;}

c1=w/(q*z);

cout<<"По первой формуле равно:"<<c1<<" "<<endl;

search_time1 = clock() - start_time1;

start_time2 = clock();

for(i=n;i>=1;i--)

{

c2*=(k-i+1)/i;

}

cout<<"По второй формуле равно:"<<c2<<" "<<endl;

search_time2 = clock() - start_time2;

start_time3 = clock();

for(y=1;y<=m;y++) // Для каждой строки.

{

D[y][1]=y;

D[y][y]=1;

for(x=2;x<=n && x<y;x++)

{

D[y][x]=D[y-1][x-1]+D[y-1][x];

}

c3=D[m][n];

cout<<"По третьей формyле равно:"<<c3<<" "<<endl;

search_time3 = clock() - start_time3;

}

else if(m<n) {

cout<<"invalid";

}

cout<<"Первая формула сработала за:(в милисек)"<<((double)search_time1/CLOCKS_PER_SEC)*1000<<endl;

cout<<"Вторая формула сработала за:(в милисек)"<<(double)search_time2/CLOCKS_PER_SEC*1000<<endl;

cout<<"Третья формула сработала за:(в милисек)"<<(double)search_time3/CLOCKS_PER_SEC*1000<<endl;

if(search_time1<search_time2 && search_time1<search_time3) { cout<<"Первая формула выполняется быстрее."<<endl; }

else if(search_time2<search_time1 && search_time2<search_time3) { cout<<"Вторая формула выполняется быстрее."<<endl; }

else if(search_time3<search_time2 && search_time3<search_time1) { cout<<"Третья формула выполняется быстрее."<<endl; }

return 0;

}

Ход решения:

1.С помощью цикла [latex]for[/latex] и функции [latex]clock[/latex] я нахожу число сочетаний и время вычислений.

Чтобы посчитать время вычислений по второй рекуррентной формуле я воспользовался Треугольником Паскаля.

Треугольник Паскаля хранится в двумерном массиве и заполняется по указанной в условии формуле начиная с верхнего левого угла.

2.Вывожу число сочетаний

3.С помощью условного оператора [latex]if[/latex] я сравниваю время вычислений.

Ссылка на код

Related Images:

А808а

27/01/2016 by Сабиров Ильдар

Задача.
Дан текст. Группы символов, разделенные пробелами(одним или несколькими) и не содержащие пробелов внутри себя, будем называть, как и прежде, словами.

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

Тесты

Input	Output	Комментарий
123 321 1441 123 456 831 1441	123 — 2 1441 -2 321 — 1 456 — 1 831 — 1	Пройдено
iW@910 b10r l4e iW@910 10o b11 a mU611211a9	10o — 1 a — 1 b10r — 1 b11 — 1 iW@910 — 2 l4e — 1 mU611211a9 — 1	Пройдено
№!4%» ^&*() +\|\/., №!4%» _-=~`;?	+\|\/., — 1 ^&*() — 1 _-=~`;? — 1 №!4%» — 2	Пройдено
Hey Jude, don’t make it bad. Take a sad song and make it better.	Hey — 1 Jude, — 1 Take — 1 a — 1 and — 1 bad. — 1 better. — 1 don’t — 1 it — 2 make — 2 sad — 1 song — 1	Пройдено

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

#include <iostream>
#include <map>
#include <cstring>
#include <cstdlib>
using namespace std;

int main() {
	map<string, int> m;
	string word;
	while( cin >> word )
		m[word]++;
	for(map<string, int>::iterator (it) = (m).begin(); (it) != (m).end() ; (it)++)
	{
		cout<<it->first<<" - "<<it->second<<endl;
	}
	return 0;
}

#include <iostream>

#include <map>

#include <cstring>

#include <cstdlib>

using namespace std;

int main() {

map<string, int> m;

string word;

while( cin >> word )

m[word]++;

for(map<string, int>::iterator (it) = (m).begin(); (it) != (m).end() ; (it)++)

{

cout<<it->first<<" - "<<it->second<<endl;

}

return 0;

}

Ход решения:

Применяя функцию [latex]map[/latex], запишем в индекс массива [latex]m[/latex] слово и увеличим элемент массива данного индекса на единицу. Используя цикл [latex]while[/latex] мы проделаем это для каждого слова введенного с клавиатуры. Если слово повторится , то элемент снова увеличится на единицу. Таким образом получаем количество слов в данном тексте.

С помощью цикла [latex]for[/latex] выводим индекс массива (т.е. слово) и значение (его количество в тексте).

Ссылка на код

Related Images:

А406

18/12/2015 by Сабиров Ильдар

Задача

С помощью [latex]x_{ij}, i=1,2; j=1,\ldots,n.[/latex] — действительной матрицы на плоскости задано n точек так, что [latex]x_{1j}, x_{2j}[/latex] — координаты [latex]j[/latex] — точки. Точки попарно соединены отрезками. Найти длину наибольшего отрезка.

Тест

n	Матрица [latex]x_{ij}, i=1,2.[/latex]	Длина наибольшего отрезка	Комментарий
3	2 8 4 9 1 5	10	Пройдено
4	6 14 2 1 9 3 8 0	13.3417	Пройдено
5	1 8 4 3 7 2 9 5 0 11	11.7047	Пройдено

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

#include <iostream>
#include <cmath>
using namespace std;
int main() 
{
	double max = 0;
	int K=2,L,x=0,y=1;
	cin >> L;
	int D[K][L];
	for (int i = 0; i < K; i++)
	{
		for (int j = 0; j < L; j++)
		{
			cin>>D[i][j];
		}
	}
	for (int i = 0; i < L-1; i++)
	{
		for (int j = 0; j < L; j++)
		{
			double q=sqrt((D[x][i]-D[x][j])*(D[x][i]-D[x][j])+(D[y][i]-D[y][j])*(D[y][i]-D[y][j]));
			if(q>max)
			{
				max=q;
			}
		}
	}
	for (int i = 0; i < K; i++)
	{
		for (int j = 0; j < L; j++)
		{
			cout<<D[i][j]<<" ";
		}
		cout<<"\n";
	}
	cout<<max;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double max = 0;

int K=2,L,x=0,y=1;

cin >> L;

int D[K][L];

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

{

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

{

cin>>D[i][j];

}

for (int i = 0; i < L-1; i++)

{

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

{

double q=sqrt((D[x][i]-D[x][j])*(D[x][i]-D[x][j])+(D[y][i]-D[y][j])*(D[y][i]-D[y][j]));

if(q>max)

{

max=q;

}

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

{

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

{

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

}

cout<<"\n";

}

cout<<max;

return 0;

}

Ход решения:

Вводим матрицу построчно (не очень удобно).
Находим длину наибольшего отрезка.
С помощью вложенных циклов мы находим длины всех отрезков по формуле
[latex] AB=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}, A(x_{1},y_{1}), B(x_{2},y_{2}). [/latex]
По алгоритму нахождения максимума находим длину наибольшего отрезка.
Выводим матрицу.
Выводим длину наибольшего отрезка.
Ссылка на код

Related Images:

А694а

14/09/2015 by Сабиров Ильдар

Задача: Получить квадратную матрицу порядка [latex]n[/latex] [latex]\begin{pmatrix}1 &0 &\cdots & 0 \\ 0 & 1 &\cdots &0 \\ \cdots &\cdots &\cdots \cdots & \cdots \\ 0 & 0 & \cdots & 1\end{pmatrix}[/latex]

Тесты:

n	Матрица
3	1 0 0 0 1 0 0 0 1
4	1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
6	1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
    int m[n][n];
    for(int i=0;i<n;i++)
    {
    	m[i][i]=1;
    }
    for(int i=0;i<n;i++)
    {
    	for(int y=0;y<n;y++)
        {
    	    if(m[i][y]!=1)
    	    {
    		    m[i][y]=0;
    	    }
        }
    }
    for(int i=0;i<n;i++)
    {
    	for(int y=0;y<n;y++)
        {
        	cout<<m[i][y]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int m[n][n];

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

{

m[i][i]=1;

}

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

{

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

{

if(m[i][y]!=1)

{

m[i][y]=0;

}

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

{

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

{

cout<<m[i][y]<<" ";

}

cout<<"\n";

}

return 0;

}

Ход работы:
1. С помощью цикла заполняем главную диагональ единицами.

2. Приравниваем элементы не равные единице к нулю.

3. Вывод массива.

Ссылка на код

Related Images:

Ю4.12

14/09/2015 by Сабиров Ильдар

Задача: Все ненулевые элементы матрицы [latex]D(k,l)[/latex] расположить в начале массива [latex]E(k \times l)[/latex] и подсчитать их количество.

K	L	Матрица D	Ненулевые элементы матрицы E	Количество ненулевых элементов
2	3	2 7 0 1 4 9	2 7 1 4 9	5
3	4	6 7 4 2 9 0 1 3 0 8 0 19	6 7 4 2 9 1 3 8 19	9
4	2	8 9 0 1 5 2 7 26	8 9 1 5 2 7 26	8

#include <iostream>
#include <stdlib.h>
#include <ctime>

using namespace std;
int main() {
    int K;
    int L;
    cin>>K;
    cin>>L;
    int M=K*L;
    int D[K][L];
    int E[M];
    int count = 0;
    for (int i = 0; i < K; ++i) {
        for (int j = 0; j < L; ++j) {
            cin>>D[i][j];
            if (D[i][j] != 0) {
                E[count++] = D[i][j];
                cout << D[i][j] << " "; 
            }
        }
    }
    cout << " количество ненулевых элементов матрицы E = " << count << endl;
    for (int u = 0; u < K; ++u) {
        for (int y = 0; y < L; ++y) {
            cout<<D[u][y]<<" ";
        }
        cout<<"\n";
    }
    return 0 ;
}

#include <iostream>

#include <stdlib.h>

#include <ctime>

using namespace std;

int main() {

int K;

int L;

cin>>K;

cin>>L;

int M=K*L;

int D[K][L];

int E[M];

int count = 0;

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

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

cin>>D[i][j];

if (D[i][j] != 0) {

E[count++] = D[i][j];

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

}

cout << " количество ненулевых элементов матрицы E = " << count << endl;

for (int u = 0; u < K; ++u) {

for (int y = 0; y < L; ++y) {

cout<<D[u][y]<<" ";

}

cout<<"\n";

}

return 0 ;

}

Заполняем матрицу с клавиатуры посредством циклов.
Выводим ненулевые элементы.
Выводим их количество.
Выводим матрицу D.

Ссылка на код

Related Images:

А71

31/03/2015 by Сабиров Ильдар

Задача.

Дано действительное число [latex]a[/latex]. Вычислить [latex]f(a)[/latex], где [latex]f[/latex] — периодическая функция с периодом 1.5, совпадающая на отрезке [latex][0;1.5][/latex] с функцией [latex]x^{3}-2.25x[/latex].

Тесты:

[latex]a[/latex]	[latex]f(a)[/latex]	Комментарий
2.12	-1.15667	Тест пройден
-8	-1.25	Тест пройден
11.6	-1.114	Тест пройден
3.7	-1.232	Тест пройден

Код:

#include <iostream>
using namespace std;
int main() 
{
	float f, a, b;
	double p=1.5;
	int c;
	cin>>a;

	if(a>=0)
	{
		c=a/p;
		b=a/p;
		a=(b-c)*p;
	}
	else if(a<0)
	{
		c=(-a)/p;
		a=(c+1)*p+a;
	}
	f=a*a*a-2.25*a;
	cout<<f<<endl;
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

float f, a, b;

double p=1.5;

int c;

cin>>a;

if(a>=0)

{

c=a/p;

b=a/p;

a=(b-c)*p;

}

else if(a<0)

{

c=(-a)/p;

a=(c+1)*p+a;

}

f=a*a*a-2.25*a;

cout<<f<<endl;

return 0;

}

Решение:

Для положительных мы просто приравниваем [latex]a[/latex] к остатку от деления числа [latex]a[/latex] на период [latex]p=1.5[/latex], таким образом мы сдвигаем [latex]a[/latex], влево на необходимое количество[latex]p[/latex] пока [latex]a[/latex] не попадет в отрезок [latex][0;1.5][/latex]. Если число [latex]a[/latex] принадлежит отрезку [latex][0;1.5][/latex], то по данному алгоритму число [latex]a[/latex] останется неизменным.

Для отрицательных чисел мы действуем проще. К левой границе(взятой по модулю) интервала в котором находится число [latex]a[/latex] мы прибавляем число [latex]a[/latex]. Таким образом мы сдвигаем число а соответствующему значению в интервале [latex][0;1.5][/latex] так, что значение функции при этом не меняется.
Например:
[latex]a=-2[/latex] , следовательно она принадлежит отрезку [latex][-3;-1.5][/latex].
берем левую границу [latex]\left|-3 \right|[/latex] и прибавляем a.
[latex]3-2=1.[/latex] [latex]f(-2)=f(1)[/latex] т.к. функция периодична.

Полученное значение [latex]a[/latex] подставляем в формулу [latex]f(a)=a^{3}-2.25a[/latex] и подсчитываем значение функции.
Ссылка на код

Related Images:

А136о

30/01/2015 by Сабиров Ильдар

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

n	[latex]a_{1}[/latex]	[latex]a_{2}[/latex]	[latex]a_{3}[/latex]	[latex]a_{4}[/latex]	[latex]a_{5}[/latex]	[latex]a_{6}[/latex]	sum	Комментарий
6	1	0.5	7	19	-9	8	51.6024	Пройден.
5	16	14.3	2	27	19	—	81.1426	Пройден.
2	61	-5	—	—	—	—	66.998	Пройден.
3	28.8	0.34	20.9	31.5	—	—	53.2915	Пройден.
1	-65.9242	—	—	—	—	—	66	Пройден.

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

int main()
{
    int i;
    int n;
    double sum=0;
    cin>>n;
    double a;
    for(i=1;i<=n;++i)
    {
        cin>>a;
        sum+=sqrt(10+a*a);
    }
    cout<<sum;
    return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main()

{

int i;

int n;

double sum=0;

cin>>n;

double a;

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

{

cin>>a;

sum+=sqrt(10+a*a);

}

cout<<sum;

return 0;

}

Вводим числа( n, [latex]a_{1},\ldots,a_{k}.[/latex])
Подсчитываем указанную сумму([latex]\sqrt{10+a_{1}^{2}}[/latex]+…+[latex]\sqrt{10+a_{n}^{2}}.[/latex])
Выводим сумму.

Ссылка на код .

Related Images:

А114а

17/11/2014 by Сабиров Ильдар

Задача. Вычислить [latex]\sum_{i=1}^{100}{1/i^2}[/latex];

[latex]\sum_{i=1}^{100}{1/i^2}[/latex]	Комментарий
1.63498	Тест пройден

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

int main()
{
   double arr[101];
   double asd = 0;
   for (int i = 1; i <= 100; i++)
   {
      arr[i] = 1 / pow(i, 2);
      asd += arr[i];
   }
   cout << asd << endl;
   return 0;
}

#include <stdio.h>

#include <math.h>

#include <iostream>

using namespace std;

int main()

{

double arr[101];

double asd = 0;

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

{

arr[i] = 1 / pow(i, 2);

asd += arr[i];

}

cout << asd << endl;

return 0;

}

Все довольно просто:

1) Программа задает функцию и её сумму;
2) Вычисляет сумму элементов функций arr(i) в цикле(прибавляет к сумме asd каждое значение фунции arr(i) , где i от 1 до 100);
3) Выводит значение суммы.

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

Related Images:

А38

30/10/2014 by Сабиров Ильдар

Задача. Даны действительные числа [latex]x[/latex], [latex]y[/latex]. Вычислить [latex]z[/latex]:

[latex]z=\begin{cases} x-y & \text{ if } x > y \\ y-x+1 & \text{ if } x \leq y \end{cases}[/latex]

x	y	z	Комментарий
18	85	68	Тест пройден
5	4	1	Тест пройден
-16	83	100	Тест пройден
16	16	1	Тест пройден

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

#include <stdio.h>

int main(void) 
{   
    double x,y,z;
    printf("Введите значение х: \n" );
    scanf("%lf", &x);
    printf("Введите значение y: \n" );
    scanf("%lf", &y);
    if (x>y)
      { 
         z=x-y;
      }
    else
      {
         z=y-x+1;
      }
    printf("z=%6.2lf \n" , z);
    return 0;
}

#include <stdio.h>

int main(void)

{

double x,y,z;

printf("Введите значение х: \n" );

scanf("%lf", &x);

printf("Введите значение y: \n" );

scanf("%lf", &y);

if (x>y)

{

z=x-y;

}

else

{

z=y-x+1;

}

printf("z=%6.2lf \n" , z);

return 0;

}

Задача выполняется в три этапа:

1.Ввод значений [latex]x[/latex] и [latex]y[/latex]

2. Сравнение значений [latex]x[/latex] и [latex]y[/latex] для выбора решения задачи согласно с условием.

3.Вывод значения [latex]z[/latex].

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

Related Images:

А18

07/10/2014 by Сабиров Ильдар

Задача. Треугольник задан величинами своих углов [latex]x[/latex], [latex]y[/latex], [latex]z[/latex] и радиусом описанной окружности [latex]R[/latex].

Найти стороны треугольника.

x	y	z	R	a	b	c	Комментарий
95	36	49	3	5.98	3.53	4.53	Тест пройден
90	45	45	7	14	9.9	9.9	Тест пройден
60	60	60	14	24.25	24.25	24.25	Тест пройден
47	34	56	9				Неверное значение углов.

#include <stdio.h>
#include<math.h>
int main(void) 
  {
    double x, y, z;
    double R, a, b, c;
    const double eps=0.01;
    
    printf("Введите величину угла x в градусах: \n" );
    scanf("%lf", &x);
    printf("Введите величину угла y в градусах: \n" );
    scanf("%lf", &y);
    printf("Введите величину угла z в градусах: \n" );
    scanf("%lf", &z);
    printf("Введите радиус описанной окружности R: \n");
    scanf("%lf", &R);
    
    if ( x+y+z>180+eps || x+y+z<180-eps) // Проверка на корректность условия
      {
        printf ("Ошибка в условии.Не правильное значение углов. \n");
      }
    else 
      {
        a=2*R*sin((x/180)*M_PI);
        b=2*R*sin((y/180)*M_PI);
        c=2*R*sin((z/180)*M_PI);
        printf("a=%5.2lf \n" , a);
        printf("b=%5.2lf \n" , b);
        printf("c=%5.2lf \n" , c);
      }
            

    return 0;
  }

#include <stdio.h>

#include<math.h>

int main(void)

{

double x, y, z;

double R, a, b, c;

const double eps=0.01;

printf("Введите величину угла x в градусах: \n" );

scanf("%lf", &x);

printf("Введите величину угла y в градусах: \n" );

scanf("%lf", &y);

printf("Введите величину угла z в градусах: \n" );

scanf("%lf", &z);

printf("Введите радиус описанной окружности R: \n");

scanf("%lf", &R);

if ( x+y+z>180+eps || x+y+z<180-eps) // Проверка на корректность условия

{

printf ("Ошибка в условии.Не правильное значение углов. \n");

}

else

{

a=2*R*sin((x/180)*M_PI);

b=2*R*sin((y/180)*M_PI);

c=2*R*sin((z/180)*M_PI);

printf("a=%5.2lf \n" , a);

printf("b=%5.2lf \n" , b);

printf("c=%5.2lf \n" , c);

}

return 0;

}

Для решения этой задачи использовалась формулы:

[latex]a=R\sin(x)[/latex] [latex]b=R\sin(y)[/latex] [latex]c=R\sin(z)[/latex]

Если при выполнении программы вы зададите некоторое значение углов и при проверке программой окажется , что значение углов больше или меньше 180+»eps» ( eps=0.01 ) , то программа не выполнит поставленную задачу, т.к. в этом случае треугольник существовать не будет.

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

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Author Archives: Сабиров Ильдар

e-olymp 6128. Простой дек

Задача. Простой дек

Тесты

Решение

Алгоритм решения

Related Images:

А290

Related Images:

A271

Related Images:

Ю3.25

Related Images:

А808а

Related Images:

А406

Related Images:

А694а

Related Images:

Ю4.12

Related Images:

А71

Related Images:

А136о

Related Images:

А114а

Related Images:

А38

Related Images:

А18

Related Images: