e-olymp 2663. Сортировка пузырьком

28/01/2020 by Даниил Кадочников

Условие

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

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

В первой строке содержится количество элементов $n$ ($1 \leqslant n \leqslant 1000$) в массиве. Во второй строке — сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10$^$9$.

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

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

Тесты

№	Ввод	Вывод
1	3 1 3 2	1
2	2 2 1	1
3	4 4 1 5 3	3
4	5 5 4 1 100000 7	4
5	6 6 5 4 3 2 1	15

Решение

Используем простой алгоритм пузырьковой сортировки: проходим по массиву циклом, если два элемента стоят не в том порядке, то меняем их местами. Так как задача состоит в том, чтобы вывести число обменов, при каждом обмене прибавляем к счётчику $1$. При каждом выполнении цикла по j ставится на место хотя бы 1 элемент, поэтому с каждым полным проходом его длина сокращается на $1$.

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

#include <iostream>
using namespace std;
int n;

int main() {
    cin >> n;
    int arr[n];

    for(int i=0; i<n; i++) cin >> arr[i];
    int counter=0;
    for(int u=0; u<n;u++) {
        for(int j=1; j<(n-u); j++) {
            if((arr[j]<arr[j-1])) {
                
                int prev;
                prev = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = prev;
                counter++;            
            }
        }
    }
    cout << counter;
    return 0;
}

#include <iostream>

using namespace std;

int n;

int main() {

cin >> n;

int arr[n];

for(int i=0; i<n; i++) cin >> arr[i];

int counter=0;

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

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

if((arr[j]<arr[j-1])) {

int prev;

prev = arr[j-1];

arr[j-1] = arr[j];

arr[j] = prev;

counter++;

}

cout << counter;

return 0;

}

Ссылки

решение на e-olymp
код на ideone

Related Images:

e-olymp 8963. Наименьшие влево

19/01/2020 by Даниил Кадочников

Условие

Задан массив из [latex]n[/latex] целых чисел. Переместить все минимальные элементы в начало массива, не меняя порядок других.

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

В первой строке записано натуральное число [latex]n[/latex]. В следующей строке записаны [latex]n[/latex] целых чисел. Все числа по модулю не превышают [latex]100[/latex].

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

Выведите элементы обновленного массива.

Тесты

№	Ввод	Вывод
1	7 6 -3 -7 4 -7 -4 5	-7 -7 6 -3 4 -4 5
2	2 100 -100	-100 100
3	6 -2 -2 7 3 99 -2	-2 -2 -2 7 3 99
4	5 1 1 1 1 1	1 1 1 1 1

Решение

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

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

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

int main()
{
    int n;
    cin >> n;
    vector <int> v, v2;
    int x;
    while(cin>>x) v.push_back(x);
    int min = v[0];
    for(int q=1; q<n; q++) {
        if(v[q]<min) min = v[q];
    }

    int min_counter = 0;
    for(int w=0; w<n; w++) {
        if(v[w] == min) min_counter++;
    }

    for(int e=0; e<min_counter; e++) v2.push_back(min);
    for(int r=0; r<n; r++) {
        if(v[r]!=min) v2.push_back(v[r]);
    }
    for(int t=0; t<n; t++) cout << v2[t] << " ";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

int n;

cin >> n;

vector <int> v, v2;

int x;

while(cin>>x) v.push_back(x);

int min = v[0];

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

if(v[q]<min) min = v[q];

}

int min_counter = 0;

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

if(v[w] == min) min_counter++;

}

for(int e=0; e<min_counter; e++) v2.push_back(min);

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

if(v[r]!=min) v2.push_back(v[r]);

}

for(int t=0; t<n; t++) cout << v2[t] << " ";

return 0;

}

Ссылки

решение на E-olymp
код на ideone

Related Images:

e-olymp 2098. Переворачиватель

30/12/2019 by Даниил Кадочников

Условие

Заданы [latex]n[/latex] чисел. Выведите их в обратном порядке.

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

Сначала задано число [latex]n[/latex] ([latex]0 \lt n \lt 100[/latex]), за ним идут [latex]n[/latex] целых чисел.

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

Выведите заданные [latex]n[/latex] чисел в обратном порядке.

Тесты

№	Ввод	Вывод
1	7 2 4 1 3 5 3 1	1 3 5 3 1 4 2
2	1 5	5
3	10 1 1 1 9999 5 -1 7 3 0 9	9 0 3 7 -1 5 9999 1 1 1

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

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int arr[n];
    for(int i=0; i<n; i++) cin >> arr[i];
    for(int u=n-1; u>-1; u--) cout << arr[u] << " ";
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int arr[n];

for(int i=0; i<n; i++) cin >> arr[i];

for(int u=n-1; u>-1; u--) cout << arr[u] << " ";

return 0;

}

Решение

Введём переменную [latex]n[/latex], затем создадим массив из [latex]n[/latex] элементов. С помощью цикла for от [latex]0[/latex] до [latex]n[/latex] запишем в него числа. Теперь с помощью другого цикла от [latex]n-1[/latex] до [latex]-1[/latex] выводим их в обратном порядке.

Related Images:

e-olymp 1966. Большой плюс

08/12/2019 by Даниил Кадочников

Условие

На сайте в таблице результатов соревнований, проводимых по правилам ACM (Association for Computing Machinery), верно решённая задачка оценивается плюсом. Но он какой-то маленький. Выведите большой плюс из звёздочек.

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

Целое число [latex]n[/latex] ([latex]1 \leqslant n \leqslant 100[/latex]).

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

Выведите соответствующий большой квадратный «плюс» из точек и звёздочек — см. примеры входных и выходных данных.

№

Ввод

Вывод

.*.
***
.*.

.*.

***

.*.

..*..
..*..
*****
..*..
..*..

..*..

*****

..*..

Решение

Задача задана немного нетривиально: не указано, каким образом число [latex]n[/latex] должно влиять на выходные данные. Однако по приведённым в условии примерам легко понять, что [latex]2n+1[/latex] — это ширина и высота плюса из звёздочек.

Печатать будем по строкам, для этого создадим главный цикл. Существует два случая: когда нужно вывести полную строку звёздочек (если [latex]u=n[/latex], то есть мы находимся в середине плюса) и когда нужно вывести обычную строку, состоящую из [latex]2n[/latex] точек и звёздочки посередине. В первом случае распечатываем [latex]2n+1[/latex] звёздочек. Во втором с помощью условия в цикле выводим звёздочку, если [latex]i=n[/latex] (центр строки), при других [latex]i[/latex] точки.

Тесты

№

Ввод

Вывод

....*....
....*....
....*....
....*....
*********
....*....
....*....
....*....
....*....

....*....

*********

....*....

......*......
......*......
......*......
......*......
......*......
......*......
*************
......*......
......*......
......*......
......*......
......*......
......*......

......*......

*************

......*......

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

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    for(int u=0; u<n*2+1; u++) {
        if(u==n) {
            for(int j=0; j<n*2+1; j++) cout << '*';
        }
        else {
            for(int i=0; i<n*2+1; i++) {
                if(i==n) cout << '*';
                else cout << '.';
            }
        }
        cout << endl;
    }   
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

for(int u=0; u<n*2+1; u++) {

if(u==n) {

for(int j=0; j<n*2+1; j++) cout << '*';

}

else {

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

if(i==n) cout << '*';

else cout << '.';

}

cout << endl;

}

return 0;

}

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

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

Author Archives: Даниил Кадочников

e-olymp 2663. Сортировка пузырьком

Условие

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

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

Тесты

Решение

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

Ссылки

Related Images:

e-olymp 8963. Наименьшие влево

Условие

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

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

Тесты

Решение

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

Ссылки

Related Images:

e-olymp 2098. Переворачиватель

Условие

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

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

Тесты

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

Решение

Related Images:

e-olymp 1966. Большой плюс

Условие

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

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

Решение

Тесты

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

Related Images: