Mif 11

15/09/2016 by Станислав Коциевский

Задача

Вычислить расстояние между двумя отрезками [latex]AB[/latex] и [latex]CD[/latex], заданных координатами вершин на плоскости.

Тесты

Входные данные	Результат работы программы
1 1 1 7 5 3 1 6	0
5 6 8 8 2 2 5 4	2
1 -1 1 -3 2 -2 4 -1	1
-5 -1 -5 -3 -2 -1 -3 -2	2
-1 1 -1 3 -4 2 -3 5	2.52982
1 4 3 6 3 4 5 4	1.41421

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

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

struct point //точка
{
    double x;
    double y;
};
struct straight //прямая в виде общего уравнения Ax + By + C = 0
{
    double A;
    double B;
    double C;
};
straight create_straight (point A, point B)
{
    straight s;
    s.A = A.y - B.y;
    s.B = B.x - A.x;
    s.C = A.x * B.y - B.x * A.y;
    return s;
}
double r (point A, point B) //расстояние между двумя точками
{
    return sqrt((A.x - B.x)*(A.x - B.x)+(A.y - B.y)*(A.y - B.y));
}
point projection (point A, point B, point C) // проекция точки С на прямую AB
{
    double x = B.y - A.y; //x и y - координаты вектора, перпендикулярного к AB
    double y = A.x - B.x;
    double L = (A.x*B.y - B.x*A.y + A.y*C.x - B.y*C.x + B.x*C.y - A.x*C.y)/(x*(B.y - A.y) + y*(A.x - B.x));
    point H;
    H.x = C.x + x * L;
    H.y = C.y + y * L;
    return H;
}
point intersection (straight a, straight b) //точка пересечения прямых a и b
{
    point ans;
    ans.x = (b.C*a.B - a.C*b.B)/(a.A*b.B - b.A*a.B);
    ans.y = (a.C*b.A - b.C*a.A)/(b.B*a.A - a.B*b.A);
    return ans;
}
void check_projection (point A, point B, point C, double & min_dis)
{
    point H = projection(A,B,C);
    if ((H.x >= min(A.x,B.x) && H.x <= max(A.x,B.x)) && (H.y >= min(A.y,B.y) && H.y <= max(A.y,B.y))) //проекция принадлежит отрезку
    {
        if (r(H,C) < min_dis)
        {
            min_dis = r(H,C);
        }
    }
}
double distance_if_not_intersect (point A, point B, point C, point D) //расстояние между отрезками, если они не пересекаются
{
    double min_dis = min(min(r(A,C),r(A,D)),min(r(B,C),r(B,D)));
    check_projection (A,B,C,min_dis);
    check_projection (A,B,D,min_dis);
    check_projection (C,D,A,min_dis);
    check_projection (C,D,B,min_dis);
    return min_dis;
}
int main()
{
    point A,B,C,D;
    cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>D.x>>D.y;
    straight AB = create_straight(A,B);
    straight CD = create_straight(C,D);
    if (AB.A/CD.A == AB.B/CD.B) //условие параллельности прямых
    {
        cout<<distance_if_not_intersect(A,B,C,D);
    }
    else
    {
        point H = intersection(AB,CD);
        if ( (H.x >= min(A.x, B.x) && H.x <= max(A.x,B.x) && H.x >= min(C.x, D.x) && H.x <= max(C.x,D.x)) && //точка пересечения принадлежит обоим отрезкам
        (H.y >= min(A.y, B.y) && H.y <= max(A.y,B.y) && H.y >= min(C.y, D.y) && H.y <= max(C.y,D.y)) )
        {
            cout<<0;
        }
        else
        {
            cout<<distance_if_not_intersect(A,B,C,D);
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

struct point //точка

{

double x;

double y;

};

struct straight //прямая в виде общего уравнения Ax + By + C = 0

{

double A;

double B;

double C;

};

straight create_straight (point A, point B)

{

straight s;

s.A = A.y - B.y;

s.B = B.x - A.x;

s.C = A.x * B.y - B.x * A.y;

return s;

}

double r (point A, point B) //расстояние между двумя точками

{

return sqrt((A.x - B.x)*(A.x - B.x)+(A.y - B.y)*(A.y - B.y));

}

point projection (point A, point B, point C) // проекция точки С на прямую AB

{

double x = B.y - A.y; //x и y - координаты вектора, перпендикулярного к AB

double y = A.x - B.x;

double L = (A.x*B.y - B.x*A.y + A.y*C.x - B.y*C.x + B.x*C.y - A.x*C.y)/(x*(B.y - A.y) + y*(A.x - B.x));

point H;

H.x = C.x + x * L;

H.y = C.y + y * L;

return H;

}

point intersection (straight a, straight b) //точка пересечения прямых a и b

{

point ans;

ans.x = (b.C*a.B - a.C*b.B)/(a.A*b.B - b.A*a.B);

ans.y = (a.C*b.A - b.C*a.A)/(b.B*a.A - a.B*b.A);

return ans;

}

void check_projection (point A, point B, point C, double & min_dis)

{

point H = projection(A,B,C);

if ((H.x >= min(A.x,B.x) && H.x <= max(A.x,B.x)) && (H.y >= min(A.y,B.y) && H.y <= max(A.y,B.y))) //проекция принадлежит отрезку

{

if (r(H,C) < min_dis)

{

min_dis = r(H,C);

}

double distance_if_not_intersect (point A, point B, point C, point D) //расстояние между отрезками, если они не пересекаются

{

double min_dis = min(min(r(A,C),r(A,D)),min(r(B,C),r(B,D)));

check_projection (A,B,C,min_dis);

check_projection (A,B,D,min_dis);

check_projection (C,D,A,min_dis);

check_projection (C,D,B,min_dis);

return min_dis;

}

int main()

{

point A,B,C,D;

cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>D.x>>D.y;

straight AB = create_straight(A,B);

straight CD = create_straight(C,D);

if (AB.A/CD.A == AB.B/CD.B) //условие параллельности прямых

{

cout<<distance_if_not_intersect(A,B,C,D);

}

else

{

point H = intersection(AB,CD);

if ( (H.x >= min(A.x, B.x) && H.x <= max(A.x,B.x) && H.x >= min(C.x, D.x) && H.x <= max(C.x,D.x)) && //точка пересечения принадлежит обоим отрезкам

(H.y >= min(A.y, B.y) && H.y <= max(A.y,B.y) && H.y >= min(C.y, D.y) && H.y <= max(C.y,D.y)) )

{

cout<<0;

}

else

{

cout<<distance_if_not_intersect(A,B,C,D);

}

return 0;

}

Решение

Основная идея состоит в том, что расстояние между непересекающимися отрезками [latex]AB[/latex] и [latex]CD[/latex] — это минимальная из длин, соединяющих вершины разных отрезков, и длин перпендикуляров, проведенных из вершины на противоположный отрезок. Подробнее о математической части поиска перпендикуляра тут. Кроме этого, отрезки могут пересекаться, что проверяется отдельно. В таком случае, расстояние между ними равно нулю.

Чтобы проверить, пересекаются ли отрезки, нужно сначала проверить, не параллельны ли они.Если они не параллельны, нужно найти точку пересечения прямых, на которых лежат отрезки, а затем проверить принадлежит ли она обоим отрезкам. Отрезки пересекаются тогда и только тогда, когда они лежат на пересекающихся прямых, точка пересечения которых принадлежит обоим отрезкам. Координаты точки пересечения находятся из системы уравнений прямых, на которых лежат отрезки.
[latex] \begin{cases} A_{1}x + B_{1}y + C_{1} = 0 \\ A_{2}x + B_{2}y + C_{2} = 0 \end{cases} [/latex]

Из первого уравнения: [latex]x = \frac{-B_{1}y-C_{1}}{A_{1}}[/latex]

Подставим [latex]x[/latex] во второе уравнение:

[latex] \frac{A_{2}}{A_{1}}(-B_{1}y-C_{1}) + B_{2}y + C_{2} = 0[/latex] [latex](*)[/latex]

Решив уравнение [latex](*)[/latex] получим:

[latex]y = \frac{C_{1}A_{2}-C_{2}A_{1}}{A_{1}B_{2}-A_{2}B_{1}}[/latex].

Тогда

[latex]x = \frac{C_{2}B_{1}-C_{1}B_{2}}{A_{1}B_{2}-A_{2}B_{1}}[/latex]

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

Related Images:

AL1

13/09/2016 by Станислав Коциевский

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

Вводится последовательность, состоящая из [latex]N[/latex] пар символов [latex](a_i, b_i)[/latex]. Каждая пара определяет порядок предшествования символов, например, пара [latex](b, c)[/latex] означает, что символ [latex]b[/latex] предшествует символу [latex]c[/latex]. Из порядка [latex](b, c)[/latex] и [latex](c, a)[/latex] следует порядок [latex](b, a)[/latex]. Необходимо определить, является ли введенная последовательность:

а) полной, т.е. все использованные для формирования пар символы (выбросив повторяющиеся) можно выстроить в цепочку [latex]A_{1},A_{2}, \cdots ,A_{s}[/latex] в порядке предшествования;

б) противоречивой, т.е. для некоторых символов [latex]x,y[/latex] можно получить одновременно порядок как [latex](x, y)[/latex] так и [latex](y, x)[/latex];

Тесты

Входные данные	Результат
4 a b b c c d b d	полный порядок
3 2 a 8 c c b	порядок неполный
3 2 a 8 c a 8	полный порядок
4 2 a 8 c c 2 a c	Порядок противоречив
10 a 5 5 4 b 3 3 4 5 3 b 5 a b 4 * * 0 4 0	полный порядок

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

#include <iostream>
#include <algorithm> //для использования функции sort
using namespace std;

int main()
{
    const int lch = 256;
    int n;
    cin>>n;
    
    char **p = new char* [n]; //Создаем массив p, где будем хранить пары символов.
    for (int i = 0; i < n; i++)
    {
        p[i] = new char [2];
    }
        
    for (int i = 0; i < n; i++)
    {
        cin >> p[i][1]>>p[i][2];
    }
    
    int chars[lch];
    for (int i = 0; i<lch; i++)
    {
        chars[i] = -1;
    }
    int K = 0;
    for (int i = 0; i<n; i++)
    {
        if (chars [ p[i][1]] == -1)
            K++;
        if (chars [ p[i][2]] == -1)
            K++;
        chars [ p[i][1]] = 0;
        chars [ p[i][2]] = 0;
    }
    
    bool change;
    char x, y;
    int M;
    for (int i = 0; i < n; i++)
    {
        change = false;
        for (int j = 0; j < n; j++)
        {
            x = p[j][1];
            y = p[j][2];
            M = max(chars[x] + 1, chars [y]);
            if (M > (K-1))
            {
                cout<<"Порядок противоречив";
                return 0;
            }
            if (chars[y] != M)
            {
                change = true;
            }
            chars[y] = M;
        }
        if (!change)
        {
            sort(chars, chars+lch);
            int previous = K;
            int i = lch-1;
            while (chars [i] > -1)
            {
                if (chars[i] == previous - 1)
                {
                    previous--;
                }
                else
                {
                    cout<<"порядок неполный";
                    return 0;
                }
                i--;
            }
            cout<<"полный порядок";
            return 0;
        }
    }
    return 0;
}

#include <iostream>

#include <algorithm> //для использования функции sort

using namespace std;

int main()

{

const int lch = 256;

int n;

cin>>n;

char **p = new char* [n]; //Создаем массив p, где будем хранить пары символов.

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

{

p[i] = new char [2];

}

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

{

cin >> p[i][1]>>p[i][2];

}

int chars[lch];

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

{

chars[i] = -1;

}

int K = 0;

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

{

if (chars [ p[i][1]] == -1)

K++;

if (chars [ p[i][2]] == -1)

K++;

chars [ p[i][1]] = 0;

chars [ p[i][2]] = 0;

}

bool change;

char x, y;

int M;

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

{

change = false;

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

{

x = p[j][1];

y = p[j][2];

M = max(chars[x] + 1, chars [y]);

if (M > (K-1))

{

cout<<"Порядок противоречив";

return 0;

}

if (chars[y] != M)

{

change = true;

}

chars[y] = M;

}

if (!change)

{

sort(chars, chars+lch);

int previous = K;

int i = lch-1;

while (chars [i] > -1)

{

if (chars[i] == previous - 1)

{

previous--;

}

else

{

cout<<"порядок неполный";

return 0;

}

i--;

}

cout<<"полный порядок";

return 0;

}

return 0;

}

Решение

Общая идея решения

Эта часть решения взята отсюда.

Пусть при записи этих [latex]N[/latex] пар встретилось всего [latex]K[/latex] различных символов, которые образуют множество [latex]X[/latex].

Идея решения задачи состоит в последовательном присвоении каждому символу [latex]s[/latex] из [latex]X[/latex] номера, который определяет количество [latex]P(s)[/latex] элементов, предшествующих ему, с учетом свойства транзитивности (из [latex](c, b)[/latex] и [latex](b, a)[/latex] следует [latex](c, a)[/latex]). Это осуществляется следующим образом:

Первоначально предполагается, что каждому символу не предшествует ни один символ, т.е. [latex]P(s)=0[/latex] для любого [latex]s[/latex].

При просмотре очередной пары [latex](x, y)[/latex] символу y присваивается большее из значений [latex]P(x)+1, P(y)[/latex].

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

Не произошло изменения ни одного из номеров символов. Если при этом номера символов различны и лежат в пределах от 0 до [latex]K-1[/latex], то эта нумерация определяет полный порядок. Иначе порядок неполный.
Номер некоторого символа превысил [latex]K-1[/latex]. Это произошло потому, что рост номеров неограничен, т.е. осуществляется циклически. Следовательно порядок противоречив.

Легко понять, что число просмотров не превысит [latex]N[/latex].

Некоторые аспекты реализации

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

Воспользуемся тем фактом, что символы воспринимаются компьютером, как числа. Заведем для номеров символов в последовательности массив chars на 256 элементов, поскольку тип данных char может принимать значения от 0 до 255. Это позволит обращаться к элементу массива, соответствующий какому-то символу напрямую, а не используя ассоциативный массив. Это дает выигрыш в скорости, хотя и с некоторым увеличением расхода памяти.

Изначально каждый элемент массива chars пусть будет равен -1. Затем, пройдя все пары, присвоим каждому символу номер 0 в этом массиве. Таким образом, мы в дальнейшем сможем определить, что символ входит в нашу последовательность, поскольку его номер неотрицательный.

Если при очередном просмотре входной строки не произошло изменений, отсортируем массив номеров и проверим каждый ли предыдущий неотрицательный меньше следующего на 1.

ссылка на код на ideone

ссылка на условие задачи

Related Images:

А282в

27/06/2016 by Станислав Коциевский

Задача

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

Тесты

Входные данные	Выходные данные
2 4 6 2 2 9 7 5	7 11 15 4
1 2 2 1	1 4
139 64 15 20 10 5 6 1	140 70 20 30
111111 22222 33333 11 25 4	111115 22247 33344
15 7 6 9	24 13
2 2	4
138 56 78 3	141 134

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

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

int main()
{
    vector <int> a;
    int b;
    while (cin>>b)
    {
        a.push_back(b);
    }
    for (int i = 0; i<a.size()/2; i++)
    {
        cout<<a[i] + a[a.size()-i-1]<<" ";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

vector <int> a;

int b;

while (cin>>b)

{

a.push_back(b);

}

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

{

cout<<a[i] + a[a.size()-i-1]<<" ";

}

return 0;

}

Решение задачи

Считаем все числа [latex]a_{1}, \cdots, a_{2n}[/latex] в ранее объявленный вектор, пока есть, что считывать. Поскольку мы используем класс vector и цикл while (cin >> b) и метод push_back(), в числе [latex]n[/latex] нет необходимости, а во входых данных присутствуют только сами числа [latex]a_{1}, \cdots, a_{2n}[/latex]. Далее, чтобы узнать количество элементов в векторе, будем использовать метод size(). Остается только выводить в цикле сумму двух текущих чисел, начиная с краев вектора и сдвигаясь в каждом витке на элемент ближе к центру вектора, пока не дойдем до центра.

Ссылки

Задача взята из задачника С. Абрамова;
Ссылка на код на ideone.com.

Related Images:

e-olymp 6124. Стек неограниченного размера

27/05/2016 by Станислав Коциевский

Задача

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

push n

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

pop

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

back

Программа должна вывести значение последнего элемента, не удаляя его из стека.

size

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

clear

Программа должна очистить стек и вывести ok.

exit

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

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

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

Описаны в условии.

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

Описаны в условии.

Тесты:

ввод	вывод	ввод	вывод
push 7 clear push 4 back push 1151 back pop back size exit	ok ok ok 4 ok 1151 1151 4 1 bye	push 2 push 7 back pop pop back push 1 back pop exit	ok ok 7 7 2 error ok 1 1 bye
pop push 42 back size pop size push 17 push 19 push 24 back size clear size exit	error ok 42 1 42 0 ok ok ok 24 3 ok 0 bye	back size clear size back pop push 2 pop push 1 size back exit	error 0 ok 0 error error ok 2 ok 1 1 bye

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

#include <iostream>
using namespace std;

const short int link_array_size = 30; //количество элементов в одном звене

struct link //звено списка
{
    int array [link_array_size]; //массив, элементы которого и являются элементами стека
    short int capacity; //свободное место в массиве
    link* next; //адресс следующего звена
    link () //создание звена
    {
        capacity = link_array_size;
    }
    void link_push (int n)
    {
        capacity--;
        array [capacity] = n; 
    }
    int link_pop ()
    {
        capacity++;
        return array[capacity-1]; 
    }
};

struct stack //сам стек
{
    link* head; //указатель на первое звено 
    int s; //количество элементов в стеке
    stack (link* h = NULL) // создание стека
    {
        head = h;
        s = 0;
    }
    void add_link() //добавление звена
    {
        link* a = new link;
        a->next = head;
        head = a;
    }
    void destroy_link() //удаление звена 
    {
        link * a = head;
        head = a->next;
        delete a;
    }
    void push (int n)
    {
        if ((head == NULL)||(head->capacity == 0))
        {
            add_link();
        }
        head->link_push(n);
        s++;
    }
    int pop ()
    {
        if (s>0)
        {
            int n = (head->link_pop());
            if (head->capacity == link_array_size)
            {
            destroy_link();
            }
            s--;
            return n;
        }
        else
        {
            throw 0;
        }
    }
    int back()
    {
        if (s>0)
        {
            return head->array[head->capacity];
        }
        else
        {
            throw 0;
        }
    }
    int size()
    {
        return s;
    }
    void clear()
    {
        while (head!=NULL)
        {
            destroy_link();
        }
        s = 0;
    }
};

int main()
{
    string s;
    stack Q;
    while (cin>>s)
    {
        if (s == "push")
        {
            int n;
            cin>>n;
            Q.push(n);
            cout<<"ok"<<endl;
        }
        if (s == "pop")
        {
            try
            {
                cout<<Q.pop()<<endl;
            }
            catch (int e)
            {
                cout<<"error"<<endl;
            }
        }
        if (s == "back")
        {
            try
            {
                cout<<Q.back()<<endl;
            }
            catch (int e)
            {
                cout<<"error"<<endl;
            }
        }
        if (s == "size")
        {
            cout<<Q.size()<<endl;
        }
        if (s == "clear")
        {
            Q.clear();
            cout<<"ok"<<endl;
        }
        if (s == "exit")
        {
            cout<<"bye"<<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

#include <iostream>

using namespace std;

const short int link_array_size = 30; //количество элементов в одном звене

struct link //звено списка

{

int array [link_array_size]; //массив, элементы которого и являются элементами стека

short int capacity; //свободное место в массиве

link* next; //адресс следующего звена

link () //создание звена

{

capacity = link_array_size;

}

void link_push (int n)

{

capacity--;

array [capacity] = n;

}

int link_pop ()

{

capacity++;

return array[capacity-1];

}

};

struct stack //сам стек

{

link* head; //указатель на первое звено

int s; //количество элементов в стеке

stack (link* h = NULL) // создание стека

{

head = h;

s = 0;

}

void add_link() //добавление звена

{

link* a = new link;

a->next = head;

head = a;

}

void destroy_link() //удаление звена

{

link * a = head;

head = a->next;

delete a;

}

void push (int n)

{

if ((head == NULL)||(head->capacity == 0))

{

add_link();

}

head->link_push(n);

s++;

}

int pop ()

{

if (s>0)

{

int n = (head->link_pop());

if (head->capacity == link_array_size)

{

destroy_link();

}

s--;

return n;

}

else

{

throw 0;

}

int back()

{

if (s>0)

{

return head->array[head->capacity];

}

else

{

throw 0;

}

int size()

{

return s;

}

void clear()

{

while (head!=NULL)

{

destroy_link();

}

s = 0;

}

};

int main()

{

string s;

stack Q;

while (cin>>s)

{

if (s == "push")

{

int n;

cin>>n;

Q.push(n);

cout<<"ok"<<endl;

}

if (s == "pop")

{

try

{

cout<<Q.pop()<<endl;

}

catch (int e)

{

cout<<"error"<<endl;

}

if (s == "back")

{

try

{

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

}

catch (int e)

{

cout<<"error"<<endl;

}

if (s == "size")

{

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

}

if (s == "clear")

{

Q.clear();

cout<<"ok"<<endl;

}

if (s == "exit")

{

cout<<"bye"<<endl;

break;

}

return 0;

}

Решение

В данном решении стек состоит из объектов, далее именуемых звеньями, каждый из которых состоит из массива, переменной, отвечающей свободному месту в массиве, ссылки на следующее звено. Кроме того, у звена есть метод для его создания, методы push и pop. В этих методах, кроме их прямой функции, отслеживается количество свободного места в звене. С этим всем работает сам стек. В самом стеке есть указатель на первое звено (звено, в которое был добавлен последний элемент, который все еще есть в стеке) и переменная S, отвечающая количеству элементов в стеке. Еще есть такие методы, как создание и удаление звена, а также все методы указанные в условии. Создается звено, если нужно что-то добавить в стек и в текущих звеньях уже нет свободного места, а удаляется, если после извлечения чего-то из стека первое звено пустое (или при методе clear). Для этого и нужна переменная отвечающая свободному месту в звене.

Теперь немного о методах, указанных в условии. Во-первых, все методы, меняющие число элементов в стеке, соответственно влияют на переменную, этому числу отвечающую, а size ее просто возвращает. Методы push и pop непосредственно для выполнения своей функции обращаются к своим аналогам в первом звене. Методы pop и back проверяют в начале, не пуст ли стек, через переменную S. Back получает значение последнего элемента, работая непосредственно с массивом первого звена. exit вообще не создан, как метод, а обрабатывается непосредственно в функции Main(). Собственно, сама эта функция только принимает и обрабатывает через условные операторы запросы, а потому описывать ее нет смысла (см. код программы).

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

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

Ссылка на засчитанное решение

ссылка на код на ideone

Related Images:

MLoop14

21/12/2015 by Станислав Коциевский

Задача

Вычислите с точностью $\varepsilon$ значение функции $f\left( x \right) = \text{cotan}x$ . При вычислениях допустимо использовать только арифметические операции.

Тесты

Аргумент функции	Точность	Результат программы	Результат сайта wolframalpha
1,6	0,000001	-0,029212	-0.0292120
0,5	0,001	1,83	1,83049
2	0,00001	-0,45766	-0,45765155….
-0,4	0,0001	-2,3652	-2,36522
-1	0,0001	-0,6421	-0,64209261…

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

#include <iostream>
using namespace std;

long double f(long double s) //модуль числа
{
	if (s<0) s=-s;
	return s;
}

long double cotan (long double x, long double e)
{
	long double sin=x, cos=1, cotan=0, a=1;
	int n=2;
	while (f(cos/sin-cotan)>e)
	{ 
		cotan = cos/sin;
		a*=-x*x/((n-1)*n);
		cos+= a;
		sin+= a*x/(n+1);
		n+=2;
	}
	cotan = cos/sin;
	return cotan;
}

int main()
{
	long double x,e,c;
	cin>>x>>e;
	c = cotan(x,e);
	int n = 0;
	x = c;
	while (f(x)>e)
	{
		x = x/10;
		n++;
	}
	cout.precision(n);
	cout<<c;
	return 0;
}

#include <iostream>

using namespace std;

long double f(long double s) //модуль числа

{

if (s<0) s=-s;

return s;

}

long double cotan (long double x, long double e)

{

long double sin=x, cos=1, cotan=0, a=1;

int n=2;

while (f(cos/sin-cotan)>e)

{

cotan = cos/sin;

a*=-x*x/((n-1)*n);

cos+= a;

sin+= a*x/(n+1);

n+=2;

}

cotan = cos/sin;

return cotan;

}

int main()

{

long double x,e,c;

cin>>x>>e;

c = cotan(x,e);

int n = 0;

x = c;

while (f(x)>e)

{

x = x/10;

n++;

}

cout.precision(n);

cout<<c;

return 0;

}

Решение

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

Ряд Маклорена для синуса: [latex]\sin{x}= [/latex] [latex] x — \frac{x^{3}}{3!} + \frac{x^{5}}{5!} — [/latex] …

Ряд Маклорена для косинуса: [latex]\cos{x}= [/latex] [latex]1 — \frac{x^{2}}{2!} + \frac{x^{4}}{4!} — [/latex] …

Отсюда видно, что [latex]n[/latex]-е слагаемое ряда для синуса равно [latex] n[/latex]-ому слагаемому ряда для косинуса, умноженному на [latex] \frac{x}{2 \cdot n+1} [/latex]. Запускаем цикл, работающий, пока модуль разности между предыдущим и следующим значением котангенса больше заданной точности, в котором каждый раз прибавляем к рядам их следующие слагаемые.

В функции int main() считаем количество знаков числа, которое нам нужно вывести, через цикл, а затем пользуемся функцией precision и выводим результат.

Примечание: Поскольку в условии разрешается пользоваться только арифметическими операциями, а модуль не совсем является таковой, я не стал пользоваться стандартной функцией Abs(), а вписал в программу ее замену.

ссылка на код на ideone

Related Images:

MLoops12

20/12/2015 by Станислав Коциевский

Задача

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел $n > 0$ (количество столбцов) и $m > 0$ (количество строк).
Замечание 1. В некоторых задачах появляется дополнительный параметр $k < n$ .
Замечание 2. Многоточие означает продолжение последовательности
Совет. Если закономерность разгадать не получается, попробуйте воспользоваться Онлайн-энциклопедией целочисленных последовательностей.

12
+-------+-------+-------+
|123...k|k...321|123...k|
|23...k1|1k...32|23...k1|
|3...k12|21k...3|3...k12|
|.......|.......|.......|
|k123...|...321k|k123...|
+-------+-------+-------+
|123...k|k...321|123...k|
|23...k1|1k...32|23...k1|

+-------+-------+-------+

|123...k|k...321|123...k|

|23...k1|1k...32|23...k1|

|3...k12|21k...3|3...k12|

|.......|.......|.......|

|k123...|...321k|k123...|

+-------+-------+-------+

|123...k|k...321|123...k|

|23...k1|1k...32|23...k1|

Тесты

Результат

+----+----+----
|1234|4321|1234
|2341|1432|2341
|3412|2143|3412
|4123|3214|4123
+----+----+----
|1234|4321|1234

+----+----+----

|1234|4321|1234

|2341|1432|2341

|3412|2143|3412

|4123|3214|4123

+----+----+----

|1234|4321|1234

+---+---+-
|123|321|1
|231|132|2
|312|213|3
+---+---+-
|123|321|1
|231|132|2

+---+---+-

|123|321|1

|231|132|2

|312|213|3

+---+---+-

|123|321|1

|231|132|2

+--+--+--+--
|12|21|12|21
|21|12|21|12
+--+--+--+--
|12|21|12|21

+--+--+--+--

|12|21|12|21

|21|12|21|12

+--+--+--+--

|12|21|12|21

+-------+-------+-------+
|1234567|7654321|1234567|
|2345671|1765432|2345671|
|3456712|2176543|3456712|
|4567123|3217654|4567123|
|5671234|4321765|5671234|
|6712345|5432176|6712345|
|7123456|6543217|7123456|
+-------+-------+-------+
|1234567|7654321|1234567|
|2345671|1765432|2345671|
|3456712|2176543|3456712|
|4567123|3217654|4567123|
|5671234|4321765|5671234|
|6712345|5432176|6712345|

+-------+-------+-------+

|1234567|7654321|1234567|

|2345671|1765432|2345671|

|3456712|2176543|3456712|

|4567123|3217654|4567123|

|5671234|4321765|5671234|

|6712345|5432176|6712345|

|7123456|6543217|7123456|

+-------+-------+-------+

|1234567|7654321|1234567|

|2345671|1765432|2345671|

|3456712|2176543|3456712|

|4567123|3217654|4567123|

|5671234|4321765|5671234|

|6712345|5432176|6712345|

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

#include <iostream>
using namespace std;

int main()
{
	int n, m, k, j, p, z=0;
	cin>>n; //количество столбцов
	cin>>m; //количество  строк
	cin>>k;
	
	for (int i = 0;z<m; i++,z++) //перебираем строки
	{
		if  (i==k+1)
		 	i=0;
		for (j = 0; j<n;)
		{
			if (i%(k+1) == 0)
			{
				cout<<'+';
				j++;
				for (p = 1; (p<=k)&&(j<n); p++,j++)
				{
					cout<<'-';
				}
			}
			else
			{
				cout<<'|';
				j++;
				for (p = i; (p<=k)&&(j<n); p++,j++)
				{
					cout<<p;
				}
				for (p = 1;(p<i)&&(j<n); p++,j++)
				{
					cout<<p;
				}
				if (j<n)
					cout<<'|';
				j++;
				for (p = i-1;(p>0)&&(j<n); p--,j++)
				{
					cout<<p;
				}
				for (p = k; (p>=i)&&(j<n); p--,j++)
				{
					cout<<p;
				}
			}
		}
		cout<<endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n, m, k, j, p, z=0;

cin>>n; //количество столбцов

cin>>m; //количество строк

cin>>k;

for (int i = 0;z<m; i++,z++) //перебираем строки

{

if (i==k+1)

i=0;

for (j = 0; j<n;)

{

if (i%(k+1) == 0)

{

cout<<'+';

j++;

for (p = 1; (p<=k)&&(j<n); p++,j++)

{

cout<<'-';

}

else

{

cout<<'|';

j++;

for (p = i; (p<=k)&&(j<n); p++,j++)

{

cout<<p;

}

for (p = 1;(p<i)&&(j<n); p++,j++)

{

cout<<p;

}

if (j<n)

cout<<'|';

j++;

for (p = i-1;(p>0)&&(j<n); p--,j++)

{

cout<<p;

}

for (p = k; (p>=i)&&(j<n); p--,j++)

{

cout<<p;

}

cout<<endl;

}

return 0;

}

Решение

Закономерности в таблице

Через каждые [latex]k[/latex] строк, начиная с нулевой, встречается строка, в которой нулевой и каждый [latex]k[/latex]-й символы — «+», а остальные — «-«. Такие строки разделяют одинаковые [latex]k[/latex]-местные блоки строк.
Каждая строка блока строк содержит, в свою очередь, [latex]k[/latex]-местные блоки символов (эти блоки уже разные), разделенные символами «|». В каждой строке из блока два вида блоков символов (далее блок 1 и блок 2). Все нечетные блоки имеют вид блока 1, четные — блока 2.
Блок 1 содержит числа по возрастанию, начиная с номера строки в блоке строк, до [latex]k[/latex] включительно, т.е. числа из сегмента [latex][i ; k][/latex], где [latex]i[/latex] — номер строки в блоке строк. После них в блоке записаны числа от [latex]1[/latex] до номера строки в блоке, не включая сам этот номер, т.е. числа из полусегмента [latex][1 ; i)[/latex].
Блок 2 каждой строки содержит те же числа, что и блок 1, но записанные в противоположном порядке.

Реализация

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

ссылка на код на ideone

Related Images:

e-olymp 901.Количество операций

03/12/2015 by Станислав Коциевский

Задача.

Определить общее количество операций сложения (+), вычитания (—) и умножения (*) в заданном арифметическом выражении.

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

В единственной строке задано арифметическое выражение, не содержащее скобок и пробелов. Количество символов в выражении не превышает 250.

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

Единственное число — количество указанных операций.

Тесты:

входящая строка	результат первой программы	результат второй программы	результат третей программы
-5+20-a+2*c	4	4	4
20+40-a	2	2	2
-2+2+2+2-a46-2*5-	8	8	8
2+6*6	2	2	2

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

Первый способ. Потоковая обработка символов.

#include 
using namespace std;
 
bool f (char x)
{
	return ((x<='9') || (x>='a' && x<='z') || (x>='A' && x<='Z')); //Проверяем является ли символ частью числа или переменной.
}
 
int main()
{
	char a,b,c;
	int n=0;
	a=getchar();
	b=getchar();
	while (EOF!=(c=getchar()))
	{
		if (f(a)&&f(c)&&(b=='*' || b=='-' || b=='+'))
		{
			n++;
		}
		a=b;
		b=c;
	}
	cout<<n;
	return 0;
}

#include

using namespace std;

bool f (char x)

{

return ((x<='9') || (x>='a' && x<='z') || (x>='A' && x<='Z')); //Проверяем является ли символ частью числа или переменной.

}

int main()

{

char a,b,c;

int n=0;

a=getchar();

b=getchar();

while (EOF!=(c=getchar()))

{

if (f(a)&&f(c)&&(b=='*' || b=='-' || b=='+'))

{

n++;

}

a=b;

b=c;

}

cout<<n;

return 0;

}

Второй способ. c-string.

#include <iostream>
#include <cstring>
using namespace std;
 
bool f (char x)
{
	return ((x<='9') || (x>='a' && x<='z') || (x>='A' && x<='Z')); //Проверяем является ли символ частью числа или переменной.
}
 
int main()
{
	short int k = 0;
	char s[250];
	while (cin>>s[k])
	{
		k++;
	}
	
	char * c = strpbrk (s+1, "+-*");
	short int n = 0;
	while (c!=NULL)
	{
		if (f(s[c-1 - s]) && f(s[c+1-s])&&(c-s!=k-1))
		{
			n++;
		}
		s[c-s] = ' ';
		c = strpbrk (s+1, "+-*");
	}
	cout<<n;
	return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

bool f (char x)

{

return ((x<='9') || (x>='a' && x<='z') || (x>='A' && x<='Z')); //Проверяем является ли символ частью числа или переменной.

}

int main()

{

short int k = 0;

char s[250];

while (cin>>s[k])

{

k++;

}

char * c = strpbrk (s+1, "+-*");

short int n = 0;

while (c!=NULL)

{

if (f(s[c-1 - s]) && f(s[c+1-s])&&(c-s!=k-1))

{

n++;

}

s[c-s] = ' ';

c = strpbrk (s+1, "+-*");

}

cout<<n;

return 0;

}

Третий способ. Класс string.

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

bool f (char x)
{
	return ((x<='9') || (x>='a' && x<='z') || (x>='A' && x<='Z')); //Проверяем является ли символ частью числа или переменной.
}
int NOP (string s, char c) //функция, читающая, сколько раз символ c встречается в строке s
{
	int n=0;
	
	if (s.find_first_of(c) == s.find_last_of(c)) // проверяем, больше ли вхождений символа с в троку, чем 1
	{
		if (s.find_first_of(c)<s.size() && s.find_first_of(c)>0)
			return 1;
		else
			return 0;
	}
	
	size_t i=s.find_first_of(c); //находим первое вхождение символа с и проверяем, не в наале ли он строки. Это делается отдельно, чтобы не выходить за пределы строки.
	if (i!=0)
		if (f(s[i-1])&&f(s[i+1]))
			n++;
	s.at(i) = '_';
	
	size_t q=s.find_last_of(c); //Аналогично, находим последнее вхождение символа с
	if (q == s.size()-1)
		if (f(s[i-1])&&f(s[i+1]))
			n--;
	
	while (i<q)
	{
		i=s.find_first_of(c);
		s.at(i) = '_';
		if (f(s[i-1])&&f(s[i+1]))
			n++;
	}
	return n;
}

int main()
{
	string s;
	getline(cin,s);
	cout<<NOP(s,'+')+NOP(s,'-')+NOP(s,'*');
	return 0;
}

#include <iostream>

#include <string>

using namespace std;

bool f (char x)

{

return ((x<='9') || (x>='a' && x<='z') || (x>='A' && x<='Z')); //Проверяем является ли символ частью числа или переменной.

}

int NOP (string s, char c) //функция, читающая, сколько раз символ c встречается в строке s

{

int n=0;

if (s.find_first_of(c) == s.find_last_of(c)) // проверяем, больше ли вхождений символа с в троку, чем 1

{

if (s.find_first_of(c)<s.size() && s.find_first_of(c)>0)

return 1;

else

return 0;

}

size_t i=s.find_first_of(c); //находим первое вхождение символа с и проверяем, не в наале ли он строки. Это делается отдельно, чтобы не выходить за пределы строки.

if (i!=0)

if (f(s[i-1])&&f(s[i+1]))

n++;

s.at(i) = '_';

size_t q=s.find_last_of(c); //Аналогично, находим последнее вхождение символа с

if (q == s.size()-1)

if (f(s[i-1])&&f(s[i+1]))

n--;

while (i<q)

{

i=s.find_first_of(c);

s.at(i) = '_';

if (f(s[i-1])&&f(s[i+1]))

n++;

}

return n;

}

int main()

{

string s;

getline(cin,s);

cout<<NOP(s,'+')+NOP(s,'-')+NOP(s,'*');

return 0;

}

Решение.

Чтобы подсчитать количество операций, указанных в условии, необходимо подсчитать символы которые соответствуют этим операциям и находятся между переменными или числами. проверять только предыдущий и следующий символ на то, является ли он буквой (значит, он является частью переменной или переменная) или цифрой (значит, он является частью числа или числом). В первой программе это осуществляется потоковой обработкой символов с запоминанием последующего и предыдущего, во второй — созданием массива символов c-string и использованием функции strpbrk, в третей — созданием объекта класса string и использованием функций find_first_of, find_last_of.

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

Ссылка на условие задачи

Ссылки на зачитанные решения:

Первый способ

Второй способ

третий способ

Ссылки на код на ideone:

Первый способ

Второй способ

третий способ

Related Images:

e-olymp 474. Максимум

22/10/2015 by Станислав Коциевский

Задача.

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

Он предложил Васе находить суммы цифр последовательных чисел — 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 — и так далее, пока Васе не надоест. Вася оказался в восторге от идеи и принялся за работу. За вчерашний день Вася нашёл суммы цифр каждого из чисел от 1 до 115. Посмотрев на результаты младшего брата, Петя заметил, что суммы цифр последовательных чисел не являются случайными, часто они идут подряд, но полностью закономерность он так и не понял.

Чтобы найти закономерности, Петя решил исследовать крайние случаи, например, какое из чисел даёт максимальную сумму цифр. Данных для чисел до 115 оказалось недостаточно для окончательных выводов, и Пете пришла в голову идея для ускорения вычислений использовать вместо братика компьютер. Поскольку сам он в программировании не очень силён, он обратился за решением этой задачи к Вам.

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

В первой строке входных данных находится число N (1 <= N <= 2 147 483 647).

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

Выведите число от 1 до N включительно с максимальной суммой цифр. Если чисел с максимальной суммой цифр несколько, выведите наибольшее из них.

Тесты:

число N	результат
1	1
98	98
13759	9999
999756	998999
2147483647	1999999999

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

#include <iostream>
using namespace std;

int TheNumberOfDigits(int n)//Количество цифр в числе
{
	int i=1;
    while ((n/=10)>0)
    {
    	i++;
    }
    return i;
}

int sc(int a) //Сумма цифр числа
{
	int sum = 0;
	while (a/1>0)
	{
		sum+=a%10;
		a/=10;
	}	
	return sum;
}

int main()
{
	int n, v, t, x;
	cin>>n;
	unsigned long long int a=10;
	t=TheNumberOfDigits(n);
	x=n;
	for (int i=1;i<t;i++)
	{
		unsigned long long int b = a*10;
		v=(n/b)*b+(n%b/a-1)*a+a-1;
		if (sc(v)>sc(x))
			x=v;
		a*=10;
	}
	cout<<x<<endl;
	return 0;
}

#include <iostream>

using namespace std;

int TheNumberOfDigits(int n)//Количество цифр в числе

{

int i=1;

while ((n/=10)>0)

{

i++;

}

return i;

}

int sc(int a) //Сумма цифр числа

{

int sum = 0;

while (a/1>0)

{

sum+=a%10;

a/=10;

}

return sum;

}

int main()

{

int n, v, t, x;

cin>>n;

unsigned long long int a=10;

t=TheNumberOfDigits(n);

x=n;

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

{

unsigned long long int b = a*10;

v=(n/b)*b+(n%b/a-1)*a+a-1;

if (sc(v)>sc(x))

x=v;

a*=10;

}

cout<<x<<endl;

return 0;

}

Решение.

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

Сумму цифр и их количество в числе считают две простых в написании функции, степени (i-я и i+1-я)десятки считаются непосредственно в основном цикле.

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

Ссылка на условие задачи

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

Ссылка на засчитанное решение

примечание: ссылка на код может выдавать старый вариант кода, где [latex]a[/latex] и [latex]b[/latex] считаются отдельно, а не [latex]b[/latex] выражается через [latex]a[/latex], как в этом коде, в связи с техническими проблемами на ideone. Этот вариант тоже проходит все тесты, однако является несколько менее эффективным.

Related Images:

Mif 17.7

05/10/2015 by Станислав Коциевский

Задача.

Принадлежит ли точка ([latex]x[/latex];[latex]y[/latex]) фигуре на рисунке? Варианты 1-20. Пожалуйста повторите в своём отчёте рисунок, выполнив его в формате SVG.

Тесты:

[latex]x[/latex]	[latex]y[/latex]	Результат
-6	3	принадлежит
0	0	не принадлежит
2	-4	не принадлежит
— 1	2	принадлежит
-5	-2	принадлежит

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

#include <iostream>
using namespace std;
 
int main()
{
    double x, y;
    cin>>x>>y;
    cout<<(((x<=-1)&&(x>=-6)&&(y>=2)&&(y<=7))||((x<=-3)&&(x>=-6)&&(y>=-3)&&(y<=2))?"принадлежит":"не принадлежит");
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

double x, y;

cin>>x>>y;

cout<<(((x<=-1)&&(x>=-6)&&(y>=2)&&(y<=7))||((x<=-3)&&(x>=-6)&&(y>=-3)&&(y<=2))?"принадлежит":"не принадлежит");

return 0;

}

Решение.

В данной задаче необходимо проверить подходят ли координаты точки под условия, описывающие фигуру. В этом варианте фигуру можно разбить на 2 прямоугольника. Тогда вышеуказанные условия выглядит так: [latex]-6<=x<=-1[/latex] и [latex]2<=y<=7[/latex] (это первый прямоугольник) или [latex]-6<=x<=-3[/latex] и [latex]-3<=y<=2[/latex] (соответственно, второй прямоугольник).

Здесь находится условие задачи

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

Related Images:

ML11

24/09/2015 by Станислав Коциевский

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

Определить время падения камня на поверхность земли с высоты $h$ .

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

Для начала оговорим трактовку условия задачи.

Поскольку в условии ничего не говорится про начальную скорость камня, будем считать ее равной нулю.
Аналогично в условии ничего не говорится про точность результата. От этого зависит как округление до определенного количества знаков после запятой в выводе, так и то, с какой точностью следует указать ускорение свободного падения, поскольку каноны физики требуют, чтобы ответ на физическую задачу указывался с точностью наимение точно указанного в условии данного. В данном решении я взял значение [latex]g[/latex] свойственное Одессе с точностью 4 значка после запятой. Соответственно, ответ будет выводиться с такой же точностью.
Предполагается что высота и время должны указываться в СИ

Тогда наша рабочая формула выглядит следующим образом: [latex]\sqrt{\frac{2 \cdot h}{g}}[/latex], где [latex] g=9.8075 \frac{m}{s^2}[/latex]. Вводить в программе [latex] g [/latex], как отдельную переменную или константу нет смысла, т.к. она используется только раз. Поэтому в коде вместо [latex] g [/latex] стоит просто ее значение.

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

//ML11.Время падения тела с высоты h
#include <iostream>
#include <cmath>
#include <iomanip> //Эта библиотека подключена, чтобы можно было пользоваться манипулятором "setprecision"
using namespace std;
int main ()
{
	double h;
	cin>>h;
	//манипулятор setprecision используется для задания точности результата
	cout<<setprecision(5)<<sqrt(2*h/9.8075)<<endl;
	return 0;
}

//ML11.Время падения тела с высоты h

#include <iostream>

#include <cmath>

#include <iomanip> //Эта библиотека подключена, чтобы можно было пользоваться манипулятором "setprecision"

using namespace std;

int main ()

{

double h;

cin>>h;

//манипулятор setprecision используется для задания точности результата

cout<<setprecision(5)<<sqrt(2*h/9.8075)<<endl;

return 0;

}

Тесты

Для тестов я выбирал такие числа, чтобы было удобно считать для [latex]g=10\frac{m}{s^2}[/latex]. Тогда первый результат, полученный при выполнении программы, должен при округлении быть равен результату подсчета вручную при [latex]g=10\frac{m}{s^2}[/latex]

Высота (м)	время (сек)
0	0
5	1.0098
20	2.0195
80	4.0391

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

Related Images:

e-olymp 918. Какая четверть?

14/09/2015 by Станислав Коциевский

Задача. Задана точка с координатами [latex]x[/latex] и [latex]y[/latex]. Определить, в какой координатной четверти она расположена.

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

В единственной строке через пробел заданы [latex]2[/latex] вещественных числа — координаты точки, значения координат по модулю не превышают [latex]100[/latex].

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

Единственное число — номер соответствующей четверти, либо [latex]0[/latex], если однозначно определить четверть невозможно.»

#include <iostream>
using namespace std;
int main ()
{
    double x;
    cin>>x;
    double y;
    cin>>y;
    cout<<((x==0)||(y==0)?"0":(x>0?
    (y>0?"1":"4"):(y>0?"2":"3")));
    return 0;
}

#include <iostream>

using namespace std;

int main ()

{

double x;

cin>>x;

double y;

cin>>y;

cout<<((x==0)||(y==0)?"0":(x>0?

(y>0?"1":"4"):(y>0?"2":"3")));

return 0;

}

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

Тесты

[latex]x[/latex]	[latex]y[/latex]	четверть	[latex]x[/latex]	[latex]y[/latex]	четверть
2	-2	4	0	54	0
5	7	1	-3	4	2
-3	0	0	-3	-8	3
0	0	0

Поскольку в любом случае мы обращаемся к оператору вывода, имеет смысл вложить условия в этот оператор. Сначала мы проверяем, не равна ли хотя бы одна переменная нулю. Если да — выводим [latex] 0[/latex], если нет — проверяем, больше ли [latex]x[/latex] нуля. Если да — это будет первая или четвертая четверть, если нет — вторая или третья. Внутри проверки [latex]x[/latex] проверяем [latex]y[/latex]. Если y больше нуля — это первая или вторая четверть, если меньше — вторая или третья.