Записки разработчика

Нужно было реализовать, код вообще -то не сложен, но тем не менее . Поворот матрицы по часовой стрелке.

#include<iostream>
#define n 10
using namespace std;
int matr[n][n];
int main()
{
 for(int i=0;i<n;i++)
 for(int j=0;j<n;j++)
 cin>>matr[i][j];

 int tmp;
 for(int i=0;i<n/2;i++)
 {
 for(int j=i;j<n-1-i;j++)
 {
 tmp = matr[i][j];
 matr[i][j] = matr[n-j-1][i];
 matr[n-j-1][i] = matr[n-i-1][n-j-1];
 matr[n-i-1][n-j-1] = matr[j][n-i-1];
 matr[j][n-i-1] = tmp;
 }
 }
}

Поворот против часовой стрелки

#include<iostream>
#define n 10
using namespace std;
int matr[n][n];
int main()
{
 for(int i=0;i<n;i++)
 for(int j=0;j<n;j++)
 cin>>matr[i][j];

 int tmp;
 for(int i=0;i<n/2;i++)
 {
 for(int j=i;j<n-1-i;j++)
 {
 tmp = matr[i][j];
 matr[i][j]=matr[j][n-1-i];
 matr[j][n-1-i]     = matr[n-1-i][n-1-j];
 matr[n-1-i][n-1-j] = matr[n-1-j][i];
 matr[n-1-j][i]     = tmp;
 }
 }
}

Достаточно простая задача на нахождение простых чисел, приведу два исходника на Си / С++ для решение такой задачи. Используем знаменитый метод “Решето Эратосфена”.

Код на Си

long nn = 10000;
int mas[nn];

memset(mas, 0, sizeof(mas));

mas[0] = 1;
mas[1] = 1;
for (int i = 2; i < nn; i++)
 if (!mas[i])
 {
 for (int j = i * 2; j < nn; j += i)
 mas[j] = 1;
 }

Continue reading “Нахождение простых чисел” »

Зарегистрировался на CodeChief и сразу попался, простецкая задача на сортировку, но не тут -то было пробовал Quicksort и MergeSort оба выдавали Time Limit Exceeded. Ответ оказался прост, нужно было воспользоваться сортировкой подсчетом. Основная идея создать нулевой массив размерностью в диапазон в водимых чисел и при вводе чисел производить инкрементацию в итоге после получения данных мы уже получаем “отсортированный” массив. Алгоритм отлично работает с положительными числами, для работы с отрицательными или со структурами данных требуется его переделать. Сортировка подсчетом на вики wiki Ниже приведен код

Continue reading “Сортировка подсчетом” »

Есть два множества нужно найти их пересечение, каким образом это сделать за минимальное время. Можно для этих целей использовать STL . В этом случае нам нужно иметь два множества, обязательно отсортированных. Функция нахождения пересечения и сортировки находятся в заголовочном файле <algorithm>. Пример того как это сделать с помощью STL

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

int main () {
 int first[] = {5,10,15,20,25};
 int second[] = {50,40,30,20,10};
 vector<int> v(10);
 vector<int>::iterator it;

 sort (first,first+5);     //  5 10 15 20 25
 sort (second,second+5);   // 10 20 30 40 50

 it=set_intersection (first, first+5, second, second+5, v.begin());
 cout << "intersection has " << int(it - v.begin()) << " elements.\n";
 return 0;
}

Этот код взят с cplusplus.com. Если же вы пишете на другом ЯП и считаете что нужно знать как все выполняется то смотрим дальше. Весь код приводить не буду, первое что нужно уяснить алгоритм работает на отсортированных множествах иначе, работать не будет, если не нравится сортировать то добро пожаловать в сложность O(N^2)., нам же этого не нужно. Быстро набросанный код для этого. Тут все еще есть стандартная функция сорт, можно было бы и самому реализовать, но хотел что бы листинг был как можно компактнее, тем более что основные алгоритмы для сортировки в блоге приведены тут и тут.

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

int main () {
int first[] = {5,10,15,20,25};
int second[] = {50,40,30,20,10};
int result[10];
sort (first,first+5);
sort (second,second+5);
for(int i=0,k=0;i<sizeof(first);i++)
for(int j=0;j<sizeof(second);j++)
{
if(second[j]>first[i])
break;
if(first[i]==second[j])
{
result[k]=first[i];
k++;
break;
}
}
return 0;
}