Я сделал саму задачу, и выкладываю ее код, может кому пригодится.
Задание: Дан одномерный массив длиной N. Массив заполняется датчиком случайных чисел (лучше использовать любое распределение, кроме нормального).
Требуется:
1) отсортировать массив со случайными числами;
2) в отсортированный массив, вставить случайное число, чтобы он оставался отсортированным;
3) также на экране после выполнения программы должно появляться сообщение, о том, сколько сравнений элементов сделано программой;
4) также программа должна выдавать сколько времени потребовалось ПК на выполнение программы
Вот мои три разных способа решения задачи:
Первый:
Код:
#include <iostream>
#include <cstdlib>
#include<windows.h>
using namespace std;
int compare_count = 0;
int compare(const void* a, const void *b)
{
++compare_count;
return (*(int*)a - *(int*)b);
}
int main ()
{
DWORD t1, t2, d_time;
srand (time(NULL));
int i, N, j, k;
t1 = GetTickCount();
//Задаем количество элементов
N=rand()%100;
cout<<endl<<"Dlina massiva - N: " <<N <<endl; //N - длина одномерного массива
cout<<"\n";
//Резервируем место на диске под количество элементов
int *a = new int[N+1];// резервируем память под массив на 1 элемент больше
int size = N;
cout << "Vremennii massiv: " << endl;
for(i=0; i<N; i++)
{
a[i]=rand()%100;
cout<<a[i]<<" ";
}
cout<<"\n";
t1 = GetTickCount();
qsort(a, size, sizeof(int), compare);
cout << "\nOtsortirovannii massiv: " << endl;
for (i = 0; i < N; i++)
cout << a[i] << " ";
cout << "\n";
cout << "\nKolichestvo sravnenii: " << compare_count <<endl;
k=rand()%100;
cout<< endl << "Sluchainoe chislo - k: " << k <<endl; //k - случайное число
cout<< endl;
i=0;
while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число
i++;
for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент
a[j]=a[j-1];
a[i]=k; //вставляем на найденное место случайный элемент
cout << "Konechnii massiv: " << endl;
for (i = 0; i < N+1; i++)
cout << a[i] << " ";
cout << endl;
t2 = GetTickCount();
d_time = t2 - t1;
cout<<"\nVremia raboti: "<<d_time<<" milisek\n";
delete [] a;
system("pause");
return 0;
}
Второй:
Код:
#include <iostream>
#include <cstdlib>
#include<windows.h>
using namespace std;
int compare_count = 0;
int compare(const void* a, const void *b)
{
++compare_count;
return (*(int*)a - *(int*)b);
}
int main ()
{
DWORD t1, t2, d_time;
srand (time(NULL));
int i, N, j, k;
//Задаем количество элементов
cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива
cin>>N;
cout<<"\n";
if(N > 0)
{
//Резервируем место на диске под количество элементов
int *a = new int[N+1];// резервируем память под массив на 1 элемент больше
int size = N;
cout << "Vremennii massiv: " << endl;
for(i=0; i<N; i++)
{
a[i]=rand()%100;
cout<<a[i]<<" ";
}
cout<<"\n";
t1 = GetTickCount();
qsort(a, size, sizeof(int), compare);
cout << "\nOtsortirovannii massiv: " << endl;
for (i = 0; i < N; i++)
cout << a[i] << " ";
cout << "\n";
cout << "\nKolichestvo sravnenii: " << compare_count <<endl;
k=rand()%100;
cout<< endl << "Sluchainoe chislo - k: " << k <<endl; //k - случайное число
cout<< endl;
i=0;
while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число
i++;
for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент
a[j]=a[j-1];
a[i]=k; //вставляем на найденное место случайный элемент
cout << "Konechnii massiv: " << endl;
for (i = 0; i < N+1; i++)
cout << a[i] << " ";
cout << endl;
t2 = GetTickCount();
d_time = t2 - t1;
cout<<"\nVremia raboti: "<<d_time<<" milisek\n";
delete [] a;
}
else cout<<"Chislo elementov ne mozhet byt <=0" << endl;
system("pause");
return 0;
}
Третий:
Код:
#include <iostream>
#include<time.h>
#include<windows.h>
using namespace std;
int main ()
{
DWORD t1, t2, d_time;
srand (time(NULL));
int i, N, j, k;
//Задаем количество элементов
cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива
cin>>N;
cout<<"\n";
if(N > 0)
{
//Резервируем место на диске под количество элементов
int *a = new int[N+1];// резервируем память под массив на 1 элемент больше
cout << "Vremennii massiv: " << endl;
for(i=0; i<N; i++)
{
a[i]=rand()%100;
cout<<a[i]<<" ";
}
cout<<"\n";
cout<< endl;
t1 = GetTickCount();
int count=0;
for (i = 0; i < N - 1; i++)
{
for(j = N-1; j>i; j--)
if (a[j-1] > a[j])
{
swap(a[j], a[j-1]); count++;
}
}
cout << "Otsortirovannii massiv: " << endl;
for (i = 0; i < N; i++)
cout << a[i] << " ";
cout<< endl;
cout<<"\nKolichestvo perestanovok: "<<count;
cout<< endl;
k=rand()%100;
cout<< endl << "Sluchainoe chislo - k: " << k <<endl; //k - случайное число
cout<< endl;
i=0;
while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число
i++;
for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент
a[j]=a[j-1];
a[i]=k; //вставляем на найденное место случайный элемент
cout << "Konechnii massiv: " << endl;
for (i = 0; i < N+1; i++)
cout << a[i] << " ";
cout <<"\n";
t2 = GetTickCount();
d_time = t2 - t1;
cout<<"\nVremia raboti: "<<d_time<<" milisek\n";
delete [] a;
}
else cout<<"Chislo elementov ne mozhet byt <=0" << endl;
system("pause");
return 0;
}
Отличаются тем что в первом все задается случайно, даже длина массива, чего нет во втором и в третьем, а третье отличается от первого и второго другим способом сортировки массива и подсчета количества перестановок. А так эти три задачи почти полностью идентичны.
P.S. Если у кого есть еще какие варианты решения данной задачи пишите.
Всем спасибо за помощь в решении задачи.
