AA26.

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

Задача

В строке заменить последний и предпоследний символ, соответственно, на первый и второй. Если длина строки меньше четырех, то вывести, что это сделать невозможно.

Тесты

Input	Output
aabbcc	ccbbaa
input data	atput dani
Kalamabanga	aglamabanaK

#include <iostream>
#include <string>

using namespace std;

int main(){
    string str;
    getline(cin,str);
    int l=str.length();
    if(l<4)
        cout << "False!" << endl;
    else{
        string s1;
        s1=str[l-1];
        s1+=str[l-2];
        for(int i=2; i<l-2; i++)
            s1+=str[i];
        s1+=str[1];
        s1+=str[0];
        cout<< s1 << endl;
    }
    return 0;
    }

#include <iostream>

#include <string>

using namespace std;

int main(){

string str;

getline(cin,str);

int l=str.length();

if(l<4)

cout << "False!" << endl;

else{

string s1;

s1=str[l-1];

s1+=str[l-2];

for(int i=2; i<l-2; i++)

s1+=str[i];

s1+=str[1];

s1+=str[0];

cout<< s1 << endl;

}

return 0;

}

Алгоритм

Поскольку в условии задачи, количество слов не оговорено — для ввода строки используем функцию getline. Затем проверяем ее длину. Если количество символов ( пробел также учитывается как символ!) не меньше 4, то делаем следующее:

1) Кладем в дополнительную строку два последних символа.

2) Заменяем последние символы в исходной строке на первые

3) В первые символы кладем то, что сохранили в дополнительной строке.

Если число символов меньше 4 — выдаем сообщение об ошибке.

Ссылка на ideone.com

Related Images:

А701б

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

Условие

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

Тесты

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

#include <iostream>

using namespace std;

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

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

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

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

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

    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >>n;

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

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

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

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

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

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

cin>>matr1[i][j];

}

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

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

matr2[i][j]=0;

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

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

}

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

cin >> vet1[i];

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

vet2[i]=0;

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

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

}

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

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

cout << endl;

return 0;

}

Алгоритм

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

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

Ссылка на ideone.com

Related Images:

e-olymp 2479. Баланс скобок

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

Условие

(Ссылка на задачу в e-olymp)

Имеется строка, содержащая скобки () и []. Скобочное выражение считается правильным, если:

оно является пустым
если A и B правильны, то AB правильно
если A правильно, то (A) и [A] правильны

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

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

Первая строка содержит количество тестов n. Каждая из следующих n строк содержит выражение, состоящее из скобок () и [].

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

Для каждого теста вывести в отдельной строке «Yes«, если выражение является правильным и «No» иначе.

Тесты

3
([])
(([()])))
([()[]()])()

Yes
No
Yes

(тесты взяты с e-olymp.com)

Результаты задачи № 2479

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main()
{
    int n;
    cin >> n;
    char l;
    cin.get(l); //считывание конца строки после числа
    for(int z=0;z<n;z++){
        bool q=1; //переменная "фиксирующая" ошибку
        char hab;
        string str;
        getline(cin,str); //используем, чтобы читать до конца строки
        int j=str.size(); //размер строки ( кол-во обрабатываемых символов)
        stack<char> res; //стэк скобок
        for(int i=0;i<j;i++){
            if((str[i]=='(')||(str[i]=='[')) //если открывающая скобка - то кладем в стэк
                res.push(str[i]);
            else{ //если закрывающая скобка
                    if(!res.empty()){ //если стэк не пуст
                        hab=res.top(); //вытаскиваем последний элемент
                        if(str[i]==')'){ //сверяем на типы скобок
                            if(hab=='('){
                                res.pop(); //удаляем пару
                               }
                            else{
                                q=0;
                                cout << "No" << endl;
                                break;

                            }
                        }
                        else{
                            if(hab=='['){ //второй тип скобок (те же действия)
                                res.pop();
                               }
                            else{
                                q=0;
                                cout << "No" << endl;
                                break;
                            }
                        }
                    }
                    else{ //если стэк пуст  - то ошибочка вышла!
                        cout << "No" << endl;
                        q=0;
                        break;
                    }
            }
        }
        if(q){
        if(res.empty()) //собственно ответ
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
        }

    }
    return 0;
}

#include <iostream>

#include <stack>

#include <string>

using namespace std;

int main()

{

int n;

cin >> n;

char l;

cin.get(l); //считывание конца строки после числа

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

bool q=1; //переменная "фиксирующая" ошибку

char hab;

string str;

getline(cin,str); //используем, чтобы читать до конца строки

int j=str.size(); //размер строки ( кол-во обрабатываемых символов)

stack<char> res; //стэк скобок

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

if((str[i]=='(')||(str[i]=='[')) //если открывающая скобка - то кладем в стэк

res.push(str[i]);

else{ //если закрывающая скобка

if(!res.empty()){ //если стэк не пуст

hab=res.top(); //вытаскиваем последний элемент

if(str[i]==')'){ //сверяем на типы скобок

if(hab=='('){

res.pop(); //удаляем пару

}

else{

q=0;

cout << "No" << endl;

break;

}

else{

if(hab=='['){ //второй тип скобок (те же действия)

res.pop();

}

else{

q=0;

cout << "No" << endl;

break;

}

else{ //если стэк пуст - то ошибочка вышла!

cout << "No" << endl;

q=0;

break;

}

if(q){

if(res.empty()) //собственно ответ

cout << "Yes" << endl;

else

cout << "No" << endl;

}

return 0;

}

Алгоритм

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

Маленький костыль для этой задачи — это лишнее считывание символа в самом начале. Делается это для того, чтобы дальше, мы спокойно могли использовать функцию getline, которая читает строку до символа конца строки. Эти дополнительным вводом, мы как бы забираем на себя символ конца строки стоящий после числа, определяющее кол-во строк.

Ссылка на ideone.com

Related Images:

e-olymp 5072. Подсчет количества ребер (ОГ)

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

Задача

Ориентированный граф задан матрицей смежности.
Найдите количество ребер в графе.

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

Входной файл содержит число n (1 ≤ n ≤ 100) — число вершин в графе, и затем n строк по n чисел, каждое из которых равно 0 или 1 — его матрицу смежности.

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

Выведите в выходной файл количество ребер заданного графа.

Решение

Задача на E-Olimp.

30 1 11 0 1

0 1 1

50 1 1 1 11 0 0 0 0

1 0 0 0 0

0 0 1 0 1

1 0 0 0 0

21 11 1

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int k, l=0;
    for(int i=0;i<n;i++){
        for(int j=0; j<n; j++){
            cin >> k;
            if(k)
            l++;
        }
    }
    cout << l << endl;

    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int k, l=0;

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

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

cin >> k;

if(k)

l++;

}

cout << l << endl;

return 0;

}

Алгоритм решения прост. Количество ребер ориентированного графа равно количеству единиц в его матрице смежности. Поэтому просто считываем, суммируем если 1, и выводим ответ.

Задача на ideone

Related Images:

e-olymp 432. Подземелье

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

Подземелье

Вы попали в 3D подземный лабиринт и необходимо найти быстрый выход! Карта подземелья составлена из единичных кубических комнат, по которым можно или нельзя передвигаться. Нужно всего одну минуту, чтобы переместиться она одну единицу на север, юг, восток, запад, вверх или вниз. Вы не можете двигаться по диагонали, и лабиринт окружен твердой скальной породой со всех сторон.

Можно ли выбраться из лабиринта? Если да, то какое времени это займет?

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

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

Состоит из ряда подземелий. Каждое описание подземелья начинается со строки, содержащей три целых числа: количество уровней в подземелье l, а также r и c — количество строк и столбцов, описывающих план каждого уровня (все числа не больше 30).

Далее следует l блоков по r строк, каждая по c символов. Каждое число описывает одну ячейку подземелья. Запрещенные для перемещения кубы подземелья обозначены символом ‘#‘, а пустые клетки обозначены ‘.‘. Ваша стартовая позиция обозначается буквой ‘S‘, а выход буквой ‘Е‘. Все описания подземелий отделены пустой строкой. Описание входных данных заканчивается тремя нулями.

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

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

Escaped in X minute(s).

где X — наименьшее время, необходимое для достижения выхода.

Если достичь выход невозможно, вывести строку

Trapped!

ТЕСТЫ:

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

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

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

3 4 5

S....

.###.

.##..

###.#

#####

##.##

##...

#####

#.###

####E

1 3 3

S##

#E#

###

0 0 0

Escaped in 11 minute(s).
Trapped!

1 2	Escaped in 11 minute(s). Trapped!

Тесты взяты с сайта e-olimp. Подтверждение прохождения задачи на e-olimp.

Задача на E-Olimp!

#include <iostream>

using namespace std;

struct node{
   int x,y,z;
   node *prev;
   node (int x0, int y0, int z0,  node* las) { x = x0; y=y0; z=z0;  prev = las;}
   node();
};  //Структура "Узел" используемая в структуре "Очередь"

struct quene{ //Структура "Очередь"
   int k=0;
   node *last=NULL;
   node *first=NULL;
   node *tmp=NULL;

   void push( int n, int m, int g){
       node* x = new node(n,m,g, NULL);
       k++;
       if(k!=1)
           last->prev = x;
       last = x;
       if(k==1)
           first=x;
   }
   
   void pop(){
       tmp=first;
       first=first->prev;
       delete tmp;
       k--;
       }

};



int main()
{
   int l,r,c;
   cin >> l >> r >> c;
   while((l!=0)&&(r!=0)&&(c!=0)){ //Внешний цикл
   int mas[l+2][r+2][c+2];
   bool masb[l+2][r+2][c+2];
   char u;
   int st1,st2,st3;
   int fs1,fs2,fs3;
   for(int i1=0; i1<l+2; i1++){ //Начало считывания и обработки данных
       for(int i2=0; i2<r+2; i2++){
           for(int i3=0; i3<c+2; i3++){
               masb[i1][i2][i3]=0;
               if((i1==0)||(i2==0)||(i3==0)||(i1==l+1)||(i2==r+1)||(i3==c+1))
                   mas[i1][i2][i3]=-1;
               else{
               cin>>u;
               if(u=='#'){
               mas[i1][i2][i3]=-1;}
               if(u=='.'){
                   mas[i1][i2][i3]=0;
               }
               if(u=='S'){
                   mas[i1][i2][i3]=0;
                   st1=i1;st2=i2;st3=i3;
               }
               if(u=='E'){
                   mas[i1][i2][i3]=0;
                   fs1=i1;fs2=i2;fs3=i3;
               }
               }
           }
           }
       } // Конец обработки

   quene ts; //Создание очереди
   ts.push(st1,st2,st3);// Кладем в нее "стартовую" вершину
   while(ts.k!=0){  //Запускаем поиск
       int x1=ts.first->x;
       int y1=ts.first->y;
       int z1=ts.first->z;  //Для удобства сохраняем координаты 
       //обрабатываемой вершины в специальных переменных

       if(mas[x1+1][y1][z1]>=0){ // Вершина справа
           if(mas[x1+1][y1][z1]!=0)
               mas[x1+1][y1][z1]=min(mas[x1+1][y1][z1],mas[x1][y1][z1]+1);
           else
               mas[x1+1][y1][z1]=mas[x1][y1][z1]+1;
           if(masb[x1+1][y1][z1]==0){
               masb[x1+1][y1][z1]=1;
               ts.push(x1+1,y1,z1);
           }
       }

       if(mas[x1-1][y1][z1]>=0){ //Вершина слева
           if(mas[x1-1][y1][z1]!=0)
               mas[x1-1][y1][z1]=min(mas[x1-1][y1][z1],mas[x1][y1][z1]+1);
           else
               mas[x1-1][y1][z1]=mas[x1][y1][z1]+1;
           if(masb[x1-1][y1][z1]==0){
               masb[x1-1][y1][z1]=1;
               ts.push(x1-1,y1,z1);
           }
       }

       if(mas[x1][y1+1][z1]>=0){ //Вершина вверху
           if(mas[x1][y1+1][z1]!=0)
               mas[x1][y1+1][z1]=min(mas[x1][y1+1][z1],mas[x1][y1][z1]+1);
           else
               mas[x1][y1+1][z1]=mas[x1][y1][z1]+1;
           if(masb[x1][y1+1][z1]==0){
               masb[x1][y1+1][z1]=1;
               ts.push(x1,y1+1,z1);
           }
       }

       if(mas[x1][y1-1][z1]>=0){ //Вершина внизу
           if(mas[x1][y1-1][z1]!=0)
               mas[x1][y1-1][z1]=min(mas[x1][y1-1][z1],mas[x1][y1][z1]+1);
           else
               mas[x1][y1-1][z1]=mas[x1][y1][z1]+1;
           if(masb[x1][y1-1][z1]==0){
               masb[x1][y1-1][z1]=1;
               ts.push(x1,y1-1,z1);
           }
       }

       if(mas[x1][y1][z1+1]>=0){ //Вершина на уровень выше
           if(mas[x1][y1][z1+1]!=0)
               mas[x1][y1][z1+1]=min(mas[x1][y1][z1+1],mas[x1][y1][z1]+1);
           else
               mas[x1][y1][z1+1]=mas[x1][y1][z1]+1;
           if(masb[x1][y1][z1+1]==0){
               masb[x1][y1][z1+1]=1;
               ts.push(x1,y1,z1+1);
           }
       }

       if(mas[x1][y1][z1-1]>=0){ //Вершина на уровень ниже
           if(mas[x1][y1][z1-1]!=0)
               mas[x1][y1][z1-1]=min(mas[x1][y1][z1-1],mas[x1][y1][z1]+1);
           else
               mas[x1][y1][z1-1]=mas[x1][y1][z1]+1;
           if(masb[x1][y1][z1-1]==0){
               masb[x1][y1][z1-1]=1;
               ts.push(x1,y1,z1-1);
           }
       }
       ts.pop(); //Удаление обработанной вершины из очереди

       }
       if(mas[fs1][fs2][fs3]!=0) // Последняя проверка результата
       cout <<"Escaped in " << mas[fs1][fs2][fs3] << " minute(s)."<< endl;
       else
       cout << "Trapped!" << endl;
       cin >> l >> r >> c; // Считывание чисел для внешнего цикла
       }
   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

152

153

154

155

156

157

158

159

#include <iostream>

using namespace std;

struct node{

int x,y,z;

node *prev;

node (int x0, int y0, int z0, node* las) { x = x0; y=y0; z=z0; prev = las;}

node();

}; //Структура "Узел" используемая в структуре "Очередь"

struct quene{ //Структура "Очередь"

int k=0;

node *last=NULL;

node *first=NULL;

node *tmp=NULL;

void push( int n, int m, int g){

node* x = new node(n,m,g, NULL);

k++;

if(k!=1)

last->prev = x;

last = x;

if(k==1)

first=x;

}

void pop(){

tmp=first;

first=first->prev;

delete tmp;

k--;

}

};

int main()

{

int l,r,c;

cin >> l >> r >> c;

while((l!=0)&&(r!=0)&&(c!=0)){ //Внешний цикл

int mas[l+2][r+2][c+2];

bool masb[l+2][r+2][c+2];

char u;

int st1,st2,st3;

int fs1,fs2,fs3;

for(int i1=0; i1<l+2; i1++){ //Начало считывания и обработки данных

for(int i2=0; i2<r+2; i2++){

for(int i3=0; i3<c+2; i3++){

masb[i1][i2][i3]=0;

if((i1==0)||(i2==0)||(i3==0)||(i1==l+1)||(i2==r+1)||(i3==c+1))

mas[i1][i2][i3]=-1;

else{

cin>>u;

if(u=='#'){

mas[i1][i2][i3]=-1;}

if(u=='.'){

mas[i1][i2][i3]=0;

}

if(u=='S'){

mas[i1][i2][i3]=0;

st1=i1;st2=i2;st3=i3;

}

if(u=='E'){

mas[i1][i2][i3]=0;

fs1=i1;fs2=i2;fs3=i3;

}

} // Конец обработки

quene ts; //Создание очереди

ts.push(st1,st2,st3);// Кладем в нее "стартовую" вершину

while(ts.k!=0){ //Запускаем поиск

int x1=ts.first->x;

int y1=ts.first->y;

int z1=ts.first->z; //Для удобства сохраняем координаты

//обрабатываемой вершины в специальных переменных

if(mas[x1+1][y1][z1]>=0){ // Вершина справа

if(mas[x1+1][y1][z1]!=0)

mas[x1+1][y1][z1]=min(mas[x1+1][y1][z1],mas[x1][y1][z1]+1);

else

mas[x1+1][y1][z1]=mas[x1][y1][z1]+1;

if(masb[x1+1][y1][z1]==0){

masb[x1+1][y1][z1]=1;

ts.push(x1+1,y1,z1);

}

if(mas[x1-1][y1][z1]>=0){ //Вершина слева

if(mas[x1-1][y1][z1]!=0)

mas[x1-1][y1][z1]=min(mas[x1-1][y1][z1],mas[x1][y1][z1]+1);

else

mas[x1-1][y1][z1]=mas[x1][y1][z1]+1;

if(masb[x1-1][y1][z1]==0){

masb[x1-1][y1][z1]=1;

ts.push(x1-1,y1,z1);

}

if(mas[x1][y1+1][z1]>=0){ //Вершина вверху

if(mas[x1][y1+1][z1]!=0)

mas[x1][y1+1][z1]=min(mas[x1][y1+1][z1],mas[x1][y1][z1]+1);

else

mas[x1][y1+1][z1]=mas[x1][y1][z1]+1;

if(masb[x1][y1+1][z1]==0){

masb[x1][y1+1][z1]=1;

ts.push(x1,y1+1,z1);

}

if(mas[x1][y1-1][z1]>=0){ //Вершина внизу

if(mas[x1][y1-1][z1]!=0)

mas[x1][y1-1][z1]=min(mas[x1][y1-1][z1],mas[x1][y1][z1]+1);

else

mas[x1][y1-1][z1]=mas[x1][y1][z1]+1;

if(masb[x1][y1-1][z1]==0){

masb[x1][y1-1][z1]=1;

ts.push(x1,y1-1,z1);

}

if(mas[x1][y1][z1+1]>=0){ //Вершина на уровень выше

if(mas[x1][y1][z1+1]!=0)

mas[x1][y1][z1+1]=min(mas[x1][y1][z1+1],mas[x1][y1][z1]+1);

else

mas[x1][y1][z1+1]=mas[x1][y1][z1]+1;

if(masb[x1][y1][z1+1]==0){

masb[x1][y1][z1+1]=1;

ts.push(x1,y1,z1+1);

}

if(mas[x1][y1][z1-1]>=0){ //Вершина на уровень ниже

if(mas[x1][y1][z1-1]!=0)

mas[x1][y1][z1-1]=min(mas[x1][y1][z1-1],mas[x1][y1][z1]+1);

else

mas[x1][y1][z1-1]=mas[x1][y1][z1]+1;

if(masb[x1][y1][z1-1]==0){

masb[x1][y1][z1-1]=1;

ts.push(x1,y1,z1-1);

}

ts.pop(); //Удаление обработанной вершины из очереди

}

if(mas[fs1][fs2][fs3]!=0) // Последняя проверка результата

cout <<"Escaped in " << mas[fs1][fs2][fs3] << " minute(s)."<< endl;

else

cout << "Trapped!" << endl;

cin >> l >> r >> c; // Считывание чисел для внешнего цикла

}

return 0;

}

ССЫЛКА НА IDEONE.COM

(Программа также проверенна в Code::Blocks)

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

Основа всего алгоритма — поиск в ширину, реализованный на трехмерном массиве. Для реализации я использовал собственную структуру очереди. В двух словах идея такова:
1) Считываем данные, заполняя массив по принципу: Если «комната закрыта» — ставим -1. Если открыта — ставим ноль. Старт и Финиш также заполняем нулями, но запоминаем их координаты.

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

2) Реализация самого поиска. Создаем очередь и помещаем в нее стартовую вершину. Затем запускаем цикл до тех пор, пока очередь не пуста.

3) Действия в цикле повторяются шесть раз, на каждое из возможных направлений.

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

4) Извлекаем вершину из очереди.

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

Примечание!

1)Для удобной реализации поиска, оба массива создаем на два уровня больше, как бы делая ему рамку ( маску).

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

Related Images:

А816

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

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

Тесты*:

Инфиксная форма	Постфиксная форма	Инфиксная форма	Постфиксная форма
3+4	3 4 +	3+4*2/(1-5)^2	3 4 2 * 1 5 — 2 ^ / +
(5-4)+2	5 4 — 2 +	(1+2)*4+3	1 2 + 4 * 3 +
2(3+4)5	2 3 4 + * 5 *	78^6-3+9^(2-1)	78 6 ^ 3 — 9 2 1 — ^ +

*тесты взяты из примеров Абрамова, примеры из Википедии и немного собственных тестов.

Несколько оговорок по поводу программы:

1. Я расширил множество допустимых операторов добавив туда возведение в степень

2. Программа предполагает, что в выражении согласованы все скобки, иначе она будет работать не правильно.

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

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

Вообще постфиксная запись еще называется Обратной Польской Нотацией ( ОПН). За алгоритмом преобразования выражений из инфиксной ( привычной нам формы записи) в ОНП можно обратится к Википедии.

Алгоритм

Пока есть ещё символы для чтения:

Читаем очередной символ.
Если символ является числом, добавляем его к выходной строке..
Если символ является открывающей скобкой, помещаем его в стек.
Если символ является закрывающей скобкой:

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

Если символ является оператором о1, тогда:

1) пока приоритет o1 меньше либо равен приоритету оператора, находящегося на вершине стека выталкиваем верхние элементы стека в выходную строку;

2) помещаем оператор o1 в стек.

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

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

Реализация через <string>

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

int main() {
	string str,stack;       
	char word, word_last;
	while(cin>>word){   
		if((word>=48)&&(word<=57)){ //если символ это число
			if((word_last>=48)&&(word_last<=57)){ // Проверка, является ли предыдущий символ - числом
				str+=word; //Если да , то просто добавляем его, тем самым не разрушая число
			}
			else{
				str+=' '; // В противном  случае добавляем пробел и добавляем символ в главную строку
				str+=word;
				}
			}
			
		if(((word>=42)&&(word<=47))||(word==94)){ //если символ это операнд
			if(word=='*'){  //Замена умножения
				word='.';
				}
			if(word=='-'){ //Замена минуса
				word=',';
				}
			if(stack.empty()){ //  Если стэк пустой - то просто кладем символ в стэк
				stack+=word;
				}
			else{	 // Если стэк не пуст
				if((stack.back()>=word)||(stack.back()==word-1)||(stack.back()==word+1)){ // Если  верхний элемент стэка имеет больший приоритет 
					while((stack.back()>=word)||(stack.back()==word-1)||(stack.back()==word+1)){ //выталкиваем все элементы из стэка
						str+=' ';														//До тех пор, пока приоритет верхнего элемента не будет
						str+=stack.back();													//ниже входящего символа
						stack.pop_back();
					}
					stack+=word;
				}
				else{ // если же верхний элемент ниже приоритетом - то просто кладем символ в стэк
					stack+=word;
				}
			}
		}
		if(word=='('){ //Если символ - открывающая скобка
			stack+=word;  //добавляем ее в стэк
		}
		if(word==')'){    //Если встречающийся символ - закрывающая скобка
			while(stack.back()!='('){ // пока в стеке не встретится открывающая скобка 
				str+=' ';        // выталкиваем в главную строку  все символы
				str+=stack.back();
				stack.pop_back();
			}
		 stack.pop_back(); //Удаляем открывающую скобку из стека
		}
		
	word_last=word; //Присваиваем значение текущего символа для проверки в последующем цикле
	
		/*cout << "Numb:" << i++ << endl; // Распечатка пошаговых действий
		cout << "Word:  |" << word << endl;
		cout <<"STR:| "  << str <<"|  SRA:|" << stack << endl;*/
	}
	while(!stack.empty()){ //При окончании строки выталкиваем все символы из стека
		str+=' ';
		str+=stack.back();
		stack.pop_back();
}

	for( int i=0; i<str.length();i++){ // Проходим циклом финальную строку для возврата требуемых символов
		if(str[i]=='.')
			str[i]='*';
		if(str[i]==',')
			str[i]='-';
		}
		
	cout <<"ИТОГ:     ___  " <<  str << endl;
	return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string str,stack;

char word, word_last;

while(cin>>word){

if((word>=48)&&(word<=57)){ //если символ это число

if((word_last>=48)&&(word_last<=57)){ // Проверка, является ли предыдущий символ - числом

str+=word; //Если да , то просто добавляем его, тем самым не разрушая число

}

else{

str+=' '; // В противном случае добавляем пробел и добавляем символ в главную строку

str+=word;

}

if(((word>=42)&&(word<=47))||(word==94)){ //если символ это операнд

if(word=='*'){ //Замена умножения

word='.';

}

if(word=='-'){ //Замена минуса

word=',';

}

if(stack.empty()){ // Если стэк пустой - то просто кладем символ в стэк

stack+=word;

}

else{ // Если стэк не пуст

if((stack.back()>=word)||(stack.back()==word-1)||(stack.back()==word+1)){ // Если верхний элемент стэка имеет больший приоритет

while((stack.back()>=word)||(stack.back()==word-1)||(stack.back()==word+1)){ //выталкиваем все элементы из стэка

str+=' '; //До тех пор, пока приоритет верхнего элемента не будет

str+=stack.back(); //ниже входящего символа

stack.pop_back();

}

stack+=word;

}

else{ // если же верхний элемент ниже приоритетом - то просто кладем символ в стэк

stack+=word;

}

if(word=='('){ //Если символ - открывающая скобка

stack+=word; //добавляем ее в стэк

}

if(word==')'){ //Если встречающийся символ - закрывающая скобка

while(stack.back()!='('){ // пока в стеке не встретится открывающая скобка

str+=' '; // выталкиваем в главную строку все символы

str+=stack.back();

stack.pop_back();

}

stack.pop_back(); //Удаляем открывающую скобку из стека

}

word_last=word; //Присваиваем значение текущего символа для проверки в последующем цикле

/*cout << "Numb:" << i++ << endl; // Распечатка пошаговых действий

cout << "Word: |" << word << endl;

cout <<"STR:| " << str <<"| SRA:|" << stack << endl;*/

}

while(!stack.empty()){ //При окончании строки выталкиваем все символы из стека

str+=' ';

str+=stack.back();

stack.pop_back();

}

for( int i=0; i<str.length();i++){ // Проходим циклом финальную строку для возврата требуемых символов

if(str[i]=='.')

str[i]='*';

if(str[i]==',')

str[i]='-';

}

cout <<"ИТОГ: ___ " << str << endl;

return 0;

}

ССЫЛКА

Моменты которые следовало бы объяснить:

1) Зачем мы проверяем, является ли предыдущий символ числом, если данный тоже число?

Эта проверка помогает нам определить, сколько цифр имело наше число. Без данной проверки, например, выражение: [latex]34*2-1[/latex] будет иметь вид не [latex]34 2 * 1 — [/latex] , а [latex]3 4 2 * 1 — [/latex]. В этом случае возникает двоякость при чтении выражения. Преобразовывая обратно можно предположить, что исходное выражение было [latex]3*42-1[/latex].

2) Зачем мы делаем замену символам умножения и вычитания, в случае когда читаемый символ это оператор?

Причина состоит в том, что нам требуется правильно контролировать приоритеты операций. Если распечатать номера символов то мы увидим следующее:

numb: 40  (  numb: 41  )
numb: 42  *  numb: 43  +
numb: 44  ,  numb: 45  - 
numb: 46  .  numb: 47  /

numb: 40 ( numb: 41 )

numb: 42 * numb: 43 +

numb: 44 , numb: 45 -

numb: 46 . numb: 47 /

А по своему приоритету, операции сортируются так:

 Приоритеты:
 • ^    высокий 
 • * /  средний 
 • + -  низкий  
 • ( )  самый низкий

Приоритеты:

• ^ высокий

• * / средний

• + - низкий

• ( ) самый низкий

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

В общем, детали реализации состоят в том, что к строке stack мы обращаемся через функции, как к стеку символов. В общем — программа просто реализует описанный выше алгоритм.

Реализация через массив char

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

int main() {
	char str[100]; //строку меняем на массив символов
	vector<char> stack; // строку меняем на вектор символов
	char word, word_last;
	int n=0, i=0; // переменные для помещения элементов в массив и пошаговой распечатки
	while(cin>>word){   
		if((word>=48)&&(word<=57)){ //если символ это число
			if((word_last>=48)&&(word_last<=57)){ // Проверка, является ли предыдущий символ - числом
				str[n++]=word; //Если да , то просто добавляем его, тем самым не разрушая число
			}
			else{
				str[n++]=' '; // В противном  случае добавляем пробел и добавляем символ в главную строку
				str[n++]=word;
				}
			}
			
		if(((word>=42)&&(word<=47))||(word==94)){ //если символ это операнд
			if(word=='*'){  //Замена умножения
				word='.';
				}
			if(word=='-'){ //Замена минуса
				word=',';
				}
			if(stack.empty()){ //  Если стэк пустой - то просто кладем символ в стэк
				stack.push_back(word);
				}
			else{	 // Если стэк не пуст
				if((stack.back()>=word)||(stack.back()==word-1)||(stack.back()==word+1)){ 
					while((stack.back()>=word)||(stack.back()==word-1)||(stack.back()==word+1)){ 
						str[n++]=' ';			// Если  верхний элемент стэка имеет больший приоритет 					
						str[n++]=stack.back();	//выталкиваем все элементы из стэка							
						stack.pop_back();    	//lо тех пор, пока приоритет верхнего элемента не будет
					}							//ниже входящего символа
					stack.push_back(word);
				}
				else{ // если же верхний элемент ниже приоритетом - то просто кладем символ в стэк
					stack.push_back(word);
				}
			}
		}
		
		if(word=='('){ //Если символ - открывающая скобка
			stack.push_back(word);  //добавляем ее в стэк
		}
		
		if(word==')'){    //Если встречающийся символ - закрывающая скобка
			while(stack.back()!='('){ // пока в стэке не встретится открывающая скобка 
				str[n++]=' ';        // выталкиваем в главную строку  все символы
				str[n++]=stack.back();
				stack.pop_back();
			}
		 stack.pop_back(); //Удаляем открывающую скобку из стека
		}
		
	word_last=word; //Присваиваем значение текущего символа для проверки в последующем цикле
	
		//cout << "Numb:" << i++ << endl; // Распечатка пошаговых действий
		//cout << "Word:  |" << word << endl;
	}
	while(!stack.empty()){ //При окончании строки выталкиваем все символы из стека
		str[n++]=' ';
		str[n++]=stack.back();
		stack.pop_back();
}
	str[n]='';
	int len=strlen(str);
	for( int i=0; str[i]!='';i++){ // Проходим циклом финальную строку для возврата требуемых символов
		if(str[i]=='.')
			str[i]='*';
		if(str[i]==',')
			str[i]='-';
		}
		
	cout <<"ИТОГ:     ___  " <<  endl;
	for(int i=0; str[i]!=''; i++){
		cout << str[i];
	}
	cout << endl;
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

char str[100]; //строку меняем на массив символов

vector<char> stack; // строку меняем на вектор символов

char word, word_last;

int n=0, i=0; // переменные для помещения элементов в массив и пошаговой распечатки

while(cin>>word){

if((word>=48)&&(word<=57)){ //если символ это число

if((word_last>=48)&&(word_last<=57)){ // Проверка, является ли предыдущий символ - числом

str[n++]=word; //Если да , то просто добавляем его, тем самым не разрушая число

}

else{

str[n++]=' '; // В противном случае добавляем пробел и добавляем символ в главную строку

str[n++]=word;

}

if(((word>=42)&&(word<=47))||(word==94)){ //если символ это операнд

if(word=='*'){ //Замена умножения

word='.';

}

if(word=='-'){ //Замена минуса

word=',';

}

if(stack.empty()){ // Если стэк пустой - то просто кладем символ в стэк

stack.push_back(word);

}

else{ // Если стэк не пуст

if((stack.back()>=word)||(stack.back()==word-1)||(stack.back()==word+1)){

while((stack.back()>=word)||(stack.back()==word-1)||(stack.back()==word+1)){

str[n++]=' '; // Если верхний элемент стэка имеет больший приоритет

str[n++]=stack.back(); //выталкиваем все элементы из стэка

stack.pop_back(); //lо тех пор, пока приоритет верхнего элемента не будет

} //ниже входящего символа

stack.push_back(word);

}

else{ // если же верхний элемент ниже приоритетом - то просто кладем символ в стэк

stack.push_back(word);

}

if(word=='('){ //Если символ - открывающая скобка

stack.push_back(word); //добавляем ее в стэк

}

if(word==')'){ //Если встречающийся символ - закрывающая скобка

while(stack.back()!='('){ // пока в стэке не встретится открывающая скобка

str[n++]=' '; // выталкиваем в главную строку все символы

str[n++]=stack.back();

stack.pop_back();

}

stack.pop_back(); //Удаляем открывающую скобку из стека

}

word_last=word; //Присваиваем значение текущего символа для проверки в последующем цикле

//cout << "Numb:" << i++ << endl; // Распечатка пошаговых действий

//cout << "Word: |" << word << endl;

}

while(!stack.empty()){ //При окончании строки выталкиваем все символы из стека

str[n++]=' ';

str[n++]=stack.back();

stack.pop_back();

}

str[n]='';

int len=strlen(str);

for( int i=0; str[i]!='';i++){ // Проходим циклом финальную строку для возврата требуемых символов

if(str[i]=='.')

str[i]='*';

if(str[i]==',')

str[i]='-';

}

cout <<"ИТОГ: ___ " << endl;

for(int i=0; str[i]!=''; i++){

cout << str[i];

}

cout << endl;

return 0;

}

ССЫЛКА

В общем, реализация не особо отличается от предыдущей. Алгоритм тот же, детали и идеи те же. Разница лишь в используемых инструментах. Теперь, вместо строки типа string мы используем массив символов. И как следствие, нам требуется ввести переменную ( в нашей программе — n) которая будет контролировать номер ячейки в которую будет присваиваться символ. Так же, после все обработки, требуется вставить дополнительно символ окончания строки ». После этого можно обращаться и форматировать строку, по нашей надобности.

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

Related Images:

А400

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

Задача: Дана действительная квадратная матрица порядка [latex]n[/latex]. Получить [latex]{ x }_{ 1 }{ x }_{ n }+{ x }_{ 2 }{ x }_{ n-1 }+ \dots +{x }_{ n }{ x }_{ 1 }[/latex] , где [latex]{x }_{ k }[/latex] — наибольшее значение элементов [latex]k[/latex]-й строки данной матрицы.

Числа

Результат

Числа

Результат

1 1 1 15 5 5 56 6 6 6

2 2 2 3

1.25 99 45 4.2 5.20.3 0 0.2

86.44

1 2 3 4 19 8 4 3 10 50 9 2 1

1 2 1 1 1

3 1 2 0 5

2576

0 0 0 0 05 9 10008 72 1777799 98 100 10 100

0 0 0 0 0

9.842 8 7 66 54

1000

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

#include <iostream>
using namespace std;

int main() {
	int n; // размер матрицы
	cin >> n;
	double x[n][n]; //объявление матрицы как двухмерного массива
	for (int i=0; i<n; i++) // ввод данных
		for(int j=0; j<n; j++)
			cin >> x[i][j];
			
	/*for(auto &row : x){  //распечатка массива (если понадобится)
		for(auto e:row)
			printf("%.2lf   ", e);
		cout << "\n";
	}
	cout << endl;*/
	double y[n]; //массив в который будут определятся максимумы строк
	
	for (int i=0; i<n; i++){ //находим максимум каждой строки и кладем его в 
		y[i]=x[i][0]; //         соответствующую ячейку массива y
		for(int j=1; j<n; j++)
		 	y[i]= (y[i]>x[i][j])? y[i]:x[i][j];
		
	}
	int str=0, end=n-1; //переменные для контроля симметричности относительно средней строки
	double result=0; // переменная для определения результата
	
	for (int i=0; i<n; i++){ // перемножаем нужные элементы и суммируем
		result+=y[str+i]*y[end-i]; 
		//cout << result << "\t"; //печать суммы каждого шага
	}
	
	cout << result << endl; // вывод результата на экран
	
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n; // размер матрицы

cin >> n;

double x[n][n]; //объявление матрицы как двухмерного массива

for (int i=0; i<n; i++) // ввод данных

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

cin >> x[i][j];

/*for(auto &row : x){ //распечатка массива (если понадобится)

for(auto e:row)

printf("%.2lf ", e);

cout << "\n";

}

cout << endl;*/

double y[n]; //массив в который будут определятся максимумы строк

for (int i=0; i<n; i++){ //находим максимум каждой строки и кладем его в

y[i]=x[i][0]; // соответствующую ячейку массива y

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

y[i]= (y[i]>x[i][j])? y[i]:x[i][j];

}

int str=0, end=n-1; //переменные для контроля симметричности относительно средней строки

double result=0; // переменная для определения результата

for (int i=0; i<n; i++){ // перемножаем нужные элементы и суммируем

result+=y[str+i]*y[end-i];

//cout << result << "\t"; //печать суммы каждого шага

}

cout << result << endl; // вывод результата на экран

return 0;

}

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in=new Scanner(System.in);
		int n; // размер матрицы
		n=in.nextInt();
		double x[][]=new double[n][]; //объявление матрицы как двухмерного массива
		for (int i=0; i<n; i++){
			x[i]=new double[n];
		}
		for (int i=0; i<n; i++){ // ввод данных
			for(int j=0; j<n; j++)
				x[i][j]=in.nextDouble();
		}
	double y[]=new double[n]; //массив в который будут определятся максимумы строк
	
	for (int i=0; i<n; i++){ //находим максимум каждой строки и кладем его в 
		y[i]=x[i][0]; //         соответствующую ячейку массива y
		for(int j=1; j<n; j++)
		 	y[i]= (y[i]>x[i][j])? y[i]:x[i][j];
		
	}
	int str=0, end=n-1; //переменные для контроля симметричности относительно средней строки
	double result=0; // переменная для определения результата
	
	for (int i=0; i<n; i++){ // перемножаем нужные элементы и суммируем
		result+=y[str+i]*y[end-i]; 
		//cout << result << "\t"; //печать суммы каждого шага
	}
	
	System.out.println(result); // вывод результата 
	
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in=new Scanner(System.in);

int n; // размер матрицы

n=in.nextInt();

double x[][]=new double[n][]; //объявление матрицы как двухмерного массива

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

x[i]=new double[n];

}

for (int i=0; i<n; i++){ // ввод данных

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

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

}

double y[]=new double[n]; //массив в который будут определятся максимумы строк

for (int i=0; i<n; i++){ //находим максимум каждой строки и кладем его в

y[i]=x[i][0]; // соответствующую ячейку массива y

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

y[i]= (y[i]>x[i][j])? y[i]:x[i][j];

}

int str=0, end=n-1; //переменные для контроля симметричности относительно средней строки

double result=0; // переменная для определения результата

for (int i=0; i<n; i++){ // перемножаем нужные элементы и суммируем

result+=y[str+i]*y[end-i];

//cout << result << "\t"; //печать суммы каждого шага

}

System.out.println(result); // вывод результата

}

Суть задачи: находим максимум каждой строки определяем их в отдельный массив. Затем перемножаем симметричные относительно середины массива элементы и суммируем их.

P.S. Простите, таблицу я так и не смог нормально отрегулировать….

Ссылка C++

Ссылка Java

Related Images:

А136ж

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

Задача: Даны натуральное число [latex]n[/latex], действительные числа [latex]{ a }_{ 1 },\dots ,{ a }_{ n }[/latex]

Вычислить: [latex]{ a }_{ 1 }-{ a }_{ 2 }+{ a }_{ 3 }-\dots +{ (-1) }^{ n+1 }{ a }_{n }[/latex]

(В этой задаче не требуется хранение исходных последовательностей значений)

n	[latex]{ a }_{ 1 },\dots ,{ a }_{ n }[/latex]	Sum
5	7 4 3 3 3	6
10	1 1 2 2 3 3 4 4 5 6	-1
15	66 456 3334 23 0.86 -587 4332 82223 0.0008 0 -0.75 44 52 7777 43	-82108.9
5	0.0005 0.0006 0.06 0.00008 0.00003	0.05985

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

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

int main() {
	int n;
	double sum=0, p;
	cin >> n;
	for(int i=1; i<=n; i++){
		cin >> p; //вводим значение а
		sum+=(i%2)? p:p*(-1); //определяем его знак и сумируем
	    //cout << "Step" << i << "\t P: " << p << "\tSum: " << sum << "\n";  
	} // включив строку выше можно просмотреть каждый шаг программы
	cout << "Sum:" << sum ;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n;

double sum=0, p;

cin >> n;

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

cin >> p; //вводим значение а

sum+=(i%2)? p:p*(-1); //определяем его знак и сумируем

//cout << "Step" << i << "\t P: " << p << "\tSum: " << sum << "\n";

} // включив строку выше можно просмотреть каждый шаг программы

cout << "Sum:" << sum ;

return 0;

}

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in=new Scanner(System.in);
		int n;
		double sum=0, p;
		n=in.nextInt();
		for(int i=1; i<=n; i++){
			p=in.nextDouble(); //вводим значение а
			if(i%2==1)//определяем его знак и сумируем
				sum+=p;
			else
				sum+=-p;
	} 
	System.out.print("Sum: " + sum);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in=new Scanner(System.in);

int n;

double sum=0, p;

n=in.nextInt();

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

p=in.nextDouble(); //вводим значение а

if(i%2==1)//определяем его знак и сумируем

sum+=p;

else

sum+=-p;

}

System.out.print("Sum: " + sum);

}

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

Ссылка C++

Ссылка Java

Related Images:

Ю 3.31

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

Задача: Численно убедится в справедливости равенства для заданного значения аргумента [latex]x[/latex] на заданное значение погрешности [latex]\varepsilon [/latex]. вывести число итераций.

[latex]cosx=1-\frac { { x }^{ 2 } }{ 2! } +\frac { { x }^{ 4 } }{ 4! } -\dots +{ (-1) }^{ n }\frac { { x }^{ 2n } }{ (2n)! }+\dots[/latex]

x		Delta	Value	Step’s
0	[latex]0[/latex]	0.0000001	1	1
3.14	[latex]\pi[/latex]	0.00001	-1	7
1.57	[latex]\frac { \pi }{ 2 }[/latex]	0.00001	0.000795865	5
1.05	[latex]\frac { \pi }{ 3 }[/latex]	0.00001	0.497571	4
2.09	[latex]\frac { 2\pi }{ 3 }[/latex]	0.00001	-0.496189	6

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

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

int main() {
	double x, sum = 1, delta, elem = 1; 
	cin >> x >> delta;
	double co = cos(x), rs = 1 + delta;
	for (int i = 1; rs > delta; i++)
	{
		elem *= - x * x / (2 * i * (2 * i - 1)); //рекурсивно выражаем каждый элемент суммы
		sum += elem; // сумируем
		rs = fabs(co - sum); // вычисляем модуль разницы для оценки точности
		cout << "Step:" << i << " " << sum << endl; // выводим  номер шага и значение суммы на этом шаге
	}
	cout << "Value: " << sum << " ~ " << co; //выводим конечное значение

	return 0;

}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double x, sum = 1, delta, elem = 1;

cin >> x >> delta;

double co = cos(x), rs = 1 + delta;

for (int i = 1; rs > delta; i++)

{

elem *= - x * x / (2 * i * (2 * i - 1)); //рекурсивно выражаем каждый элемент суммы

sum += elem; // сумируем

rs = fabs(co - sum); // вычисляем модуль разницы для оценки точности

cout << "Step:" << i << " " << sum << endl; // выводим номер шага и значение суммы на этом шаге

}

cout << "Value: " << sum << " ~ " << co; //выводим конечное значение

return 0;

}

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in=new Scanner(System.in);
		double x, sum = 1, delta, elem = 1; 
		x=in.nextDouble();
		delta=in.nextDouble();
		double co = Math.cos(x), rs = 1 + delta;
		for (int i = 1; rs > delta; i++)
		{
			elem *= - x * x / (2 * i * (2 * i - 1)); //рекурсивно выражаем каждый элемент суммы
			sum += elem; // сумируем
			rs = Math.abs(co - sum); // вычисляем модуль разницы для оценки точности
			System.out.printf("Step: %d  %8.6f  \n", i, sum); // выводим  номер шага и значение суммы на этом шаге
		}
		System.out.printf("Value:  %8.6f ~  %8.6f", sum, co); //выводим конечное значение
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.lang.Math;

class Main

{

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

{

Scanner in=new Scanner(System.in);

double x, sum = 1, delta, elem = 1;

x=in.nextDouble();

delta=in.nextDouble();

double co = Math.cos(x), rs = 1 + delta;

for (int i = 1; rs > delta; i++)

{

elem *= - x * x / (2 * i * (2 * i - 1)); //рекурсивно выражаем каждый элемент суммы

sum += elem; // сумируем

rs = Math.abs(co - sum); // вычисляем модуль разницы для оценки точности

System.out.printf("Step: %d %8.6f \n", i, sum); // выводим номер шага и значение суммы на этом шаге

}

System.out.printf("Value: %8.6f ~ %8.6f", sum, co); //выводим конечное значение

}

Ссылка на Java

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

Related Images:

Ю4.6

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

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

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

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

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

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

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

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

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n, m;

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

double A[n], B[n];

double coq, s1, s2, s3, deg;

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

cin >> A[j];

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

cin >> B[j];

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

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

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

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

}

coq=s1/sqrt(s2*s3);

deg=acos(coq);

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

return 0;

}

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

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

import java.util.*;

import java.lang.*;

import java.io.*;

import java.lang.Math;

class Main

{

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

{

Scanner in=new Scanner(System.in);

int n, m;

n=in.nextInt();

double A[]=new double[n];

double B[]=new double[n];

double coq, s1, s2, s3, deg;

s1=0;

s2=0;

s3=0;

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

A[j]=in.nextDouble();

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

B[j]=in.nextDouble();

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

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

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

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

}

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

deg=Math.acos(coq);

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

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

}

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

Ссылка C++

Ссылка на Java

Related Images:

A114ж

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

Задача:

Вычислить [latex]\prod _{ i=2 }^{ 100 }{ \frac { i+1 }{ i+2 } } ;[/latex]

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

#include <iostream>
using namespace std;

int main() {
	double p=1.0;
	for(int i=2; i<=100; i++){
		p*= (i+1.0)/(i+2.0);
	}
	cout << "Результат: " <<  p;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double p=1.0;

for(int i=2; i<=100; i++){

p*= (i+1.0)/(i+2.0);

}

cout << "Результат: " << p;

return 0;

}

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

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double p=1.0;
		for(int i=2; i<=100; i++){
			p*= (i+1.0)/(i+2.0);
		}
		System.out.print("Результат: "+ p);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

double p=1.0;

for(int i=2; i<=100; i++){

p*= (i+1.0)/(i+2.0);

}

System.out.print("Результат: "+ p);

}

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

Результат = 0.0294118. ( Это и есть 1/34).

(«Математический хак» о котором написал Игорь Евгеньевич, есть сокращение этих сомножителей, а именно:

[latex] \frac { 3 }{ 4 } \cdot \frac { 4 }{ 5 } \cdot \frac { 5 }{ 6 } \cdot \cdot \cdot \cdot \frac { 101 }{ 102 } =\frac { 3 }{ 102 } =\frac { 1 }{ 34 } =0.02941176; [/latex]

Related Images:

A59б

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

Задача:

Для задачи (А.59(б)

Даны действительные числа

Определить, принадлежит ли точка с координатами x, y заштрихованной области.

X	Y	Ответ
-0.65	-0.75	Yes
-0.95	-0.59	No
700	8	No
0	0	No
0.56	0.75	Yes
1,0011	1,0012	No
0.6	0	Yes

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

#include <iostream>
using namespace std;

int main() {
	double x, y, r;
	printf("Please, whrite  x and y: \n");
	scanf("%lf   %lf", &x, &y );
	r=(x*x)+(y*y);
    printf((r >= 0.25) && (r <= 1.0) ? "Yes" : "No");
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double x, y, r;

printf("Please, whrite x and y: \n");

scanf("%lf %lf", &x, &y );

r=(x*x)+(y*y);

printf((r >= 0.25) && (r <= 1.0) ? "Yes" : "No");

return 0;

}

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

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		double x, y, r;
		x=in.nextDouble();
		y=in.nextDouble();
		r=(x*x)+(y*y);
		System.out.printf((r >= 0.25) && (r <= 1.0) ? "Yes" : "No");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

double x, y, r;

x=in.nextDouble();

y=in.nextDouble();

r=(x*x)+(y*y);

System.out.printf((r >= 0.25) && (r <= 1.0) ? "Yes" : "No");

}

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

Если точка лежит на самой окружности, мы считаем что она принадлежит нужной нам области.

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

Related Images:

Ю1.8

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

Задача:

Среднегодовая производительность труда

За первый год производительность труда на предприятии возросла на [latex]p[/latex]₁[latex]%[/latex], за второй и третий — соответственно на [latex]p[/latex]₂[latex]%[/latex] и [latex]p[/latex]₃[latex]%.[/latex] Найти среднегодовой прирост производительности (в процентах).

P₁(%)	P₂(%)	P₃(%)	Р (среднегодовой прирост производительности) (%)
50	68	34	50.03
0	25	75	29.81
-25	25	78	18.61
0	-25	0	-9.14
1.4	43	0.7	13.45

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

#include <iostream>
#include <math.h>
using namespace std;
 
int main() {
  double p1, p2, p3, p, a;
  printf("Plese, write percentages of productivity: \n ");
  scanf("%lf %lf %lf", &p1, &p2, &p3);
  a=(p1/100+1)*(p2/100+1)*(p3/100+1);
  a=pow(a,1.0/3);
  p=100*(a-1);
  printf("Productivity: %.2lf%%", p);
  return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

double p1, p2, p3, p, a;

printf("Plese, write percentages of productivity: \n ");

scanf("%lf %lf %lf", &p1, &p2, &p3);

a=(p1/100+1)*(p2/100+1)*(p3/100+1);

a=pow(a,1.0/3);

p=100*(a-1);

printf("Productivity: %.2lf%%", p);

return 0;

}

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		double p1, p2, p3, p, a;
		p1=in.nextDouble();
		p2=in.nextDouble();
		p3=in.nextDouble();
		a=(p1/100+1)*(p2/100+1)*(p3/100+1);
		a=Math.pow(a,1.0/3);
		p=100*(a-1);
		System.out.printf("Productivity: %8.2f", p);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.lang.Math;

class Main

{

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

{

Scanner in = new Scanner(System.in);

double p1, p2, p3, p, a;

p1=in.nextDouble();

p2=in.nextDouble();

p3=in.nextDouble();

a=(p1/100+1)*(p2/100+1)*(p3/100+1);

a=Math.pow(a,1.0/3);

p=100*(a-1);

System.out.printf("Productivity: %8.2f", p);

}

Алгоритм задачи предельно прост.

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

Предположим, что производительность труда в году, предшествующему увеличению, это [latex]a[/latex], тогда в следующем году прирост будет вычисляться по формуле [latex]a\cdot \left( \frac { { p }_{ n } }{ 100 } +1 \right)[/latex], где [latex]{ p }_{ n }[/latex] это показатель прироста производительности за соответствующий год.

Учитывая, что для каждого следующего года показатель [latex]a[/latex] это производительность за предыдущий год, мы получим формулу:

[latex]p=\left( \sqrt [ 3 ]{ (\frac { { p }_{ 1 } }{ 100 } +1)\cdot (\frac { { p }_{ 2 } }{ 100 } +1)\cdot (\frac { { p }_{ 3 } }{ 100 } +1) } -1 \right) \cdot 100[/latex].

Подставляя в формулу соответствующие значения мы с легкостью получим результат.

Related Images:

Ю2.8

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

Задача

Пройдет ли кирпич со сторонами [latex]a[/latex], [latex]b[/latex] и [latex]c[/latex] сквозь прямоугольное отверстие со сторонами [latex]r[/latex] и [latex]s[/latex]? Стороны отверстия должны быть параллельны граням кирпича.

A	B	C	R	S	Ответ
10	8	7	4	3	Impossible
1	9	8	5	9	Possible
5	5	5	8	2	Impossible
4.5	4	4	5	5	Possible
0.5	3.4	0.8	4	2.5	Possible

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

#include <iostream>
using namespace std;

int main() 
{
	double a, b, c, r, s; 
	bool x = false; // Переменная, с помощью которой мы  увидим невозможность выполнения задачи
	cout << "Write size of brick: \n";
	cin >> a >> b >> c;
	cout << "Write size of  slot: \n";
	cin >> r >> s;
		
	if ((((a < r) && (b < s)) || ((b < r) && (a < s)))||    //Проверка трех вариантов расположения кирпича
			(((b < r) && (c < s)) || (( c < r) && (b < s)))||
			(((a < r) && (c < s)) || ((c < r) && (a < s))))
		x=true;
		
	printf( x? "Possible" : "Impossible");
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

double a, b, c, r, s;

bool x = false; // Переменная, с помощью которой мы увидим невозможность выполнения задачи

cout << "Write size of brick: \n";

cin >> a >> b >> c;

cout << "Write size of slot: \n";

cin >> r >> s;

if ((((a < r) && (b < s)) || ((b < r) && (a < s)))|| //Проверка трех вариантов расположения кирпича

(((b < r) && (c < s)) || (( c < r) && (b < s)))||

(((a < r) && (c < s)) || ((c < r) && (a < s))))

x=true;

printf( x? "Possible" : "Impossible");

return 0;

}

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		double a,b,c,r,s;
		boolean x=false;
		System.out.println("Write size of brick:");
		a=in.nextDouble();
		b=in.nextDouble();
		c=in.nextDouble();
		System.out.println("Write size of  slot: ");
		r=in.nextDouble();
		s=in.nextDouble();
		if ((((a < r) && (b < s)) || ((b < r) && (a < s))) || (((b < r) && (c < s)) || (( c < r) && (b < s)))||
			(((a < r) && (c < s)) || ((c < r) && (a < s))))
		x=true;
		if(x)
		System.out.println("Possible");
		else
		System.out.println("Impossible ");
	}
}

class Main

{

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

{

Scanner in = new Scanner(System.in);

double a,b,c,r,s;

boolean x=false;

System.out.println("Write size of brick:");

a=in.nextDouble();

b=in.nextDouble();

c=in.nextDouble();

System.out.println("Write size of slot: ");

r=in.nextDouble();

s=in.nextDouble();

if ((((a < r) && (b < s)) || ((b < r) && (a < s))) || (((b < r) && (c < s)) || (( c < r) && (b < s)))||

(((a < r) && (c < s)) || ((c < r) && (a < s))))

x=true;

if(x)

System.out.println("Possible");

else

System.out.println("Impossible ");

}

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