Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Программирование на C / C++

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 5.428 RSS
←   Февраль 2014   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


За последние 60 дней ни разу не выходила


Сайт рассылки: http://prog.rusfaq.ru/C
Открыта: 14-03-2002

Автор
Калашников О.А.

Статистика

5.428 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Программирование на C / C++


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Асмик Гаряка
Статус: Советник
Рейтинг: 10660
∙ повысить рейтинг » 		Коцюрбенко Алексей aka Жерар
Статус: Советник
Рейтинг: 3995
∙ повысить рейтинг » 		CradleA
Статус: Бакалавр
Рейтинг: 2050
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / C/C++

Номер выпуска:1800
Дата выхода:13.02.2014, 23:47
Администратор рассылки:Филатов Евгений Геннадьевич (Профессионал)
Подписчиков / экспертов:64 / 47
Вопросов / ответов:1 / 1

Консультация # 187734: Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос: Нужна помощь в решение задачи на языке C++ Нужно разработать программу для реализации алгоритма сортировки подсчетом сравнений. Сортируемую последовательность необходимо генерировать из случайных чисел. Результат представить графически в виде двух наборов точек: первый ...

Консультация # 187734:

Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
Нужна помощь в решение задачи на языке C++
Нужно разработать программу для реализации алгоритма сортировки подсчетом сравнений. Сортируемую последовательность необходимо генерировать из случайных чисел. Результат представить графически в виде двух наборов точек: первый – до сортировки, второй – после, по оси ОХ откладывать порядковый номер числа в последовательности, по оси ОУ – его значение. Оценить О-сложность алгоритма.
Заранее спасибо.

Дата отправки: 04.02.2014, 21:35
Вопрос задал: Dima Fedorov (1-й класс)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Лысков Игорь Витальевич (Старший модератор):

Здравствуйте, Dima Fedorov!
Вот примерная программа.
Без потери общности принято, что всего чисел 200, каждое в диапазоне от 1 до 100
Алгоритм далеко не самый оптимальный, но вполне работоспособный.
Сложность можно оценить, как О(n2+n), т.к. приходится сравнивать каждого с каждым,
а потом формировать окончательный массив.

Код :
/*
	В методе подсчета сравнений используется вспомогательный массив, 
	который обнуляется. Организуется цикл, в котором происходит подсчет 
	для каждого элемента исходного массива количество элементов, 
	в которые меньше данного и это число записывается в вспомогательный массив 
	(если сортировка по возрастанию). 
	Затем берутся элементы из вспомогательного массива
	и уже упорядоченный массив образуется путем постановки на 
	k место упорядоченного массива элементов исходного массива.
*/

#include "stdafx.h"
#include "resource.h"

HINSTANCE	hInst;
char		*szTitle = "Sort of compare";	//заголовок окна
char		*szWindowClass = "Sort_Compare";//имя класса окна
int const	n = 200;						//количество разных чисел
int const	max = 100;						//верхний предел чисел
int const	min = 1;						//нижний предел чисел
											//указатели на массивы чисел
int			*a;								//исходный
int			*b;								//вспомогательный
int			*c;								//отсортированный
BOOL		fData = FALSE;					//признак заполненности данных

ATOM				MyRegisterClass(HINSTANCE hInstance);
BOOL				InitInstance(HINSTANCE, int);
LRESULT CALLBACK	WndProc(HWND, UINT, WPARAM, LPARAM);
void				SortCmp(int *, int *, int *, int const);

int APIENTRY WinMain(HINSTANCE hInstance,
                     HINSTANCE hPrevInstance,
                     LPSTR     lpCmdLine,
                     int       nCmdShow)
{
	MSG msg;

	MyRegisterClass(hInstance);

	if (!InitInstance (hInstance, nCmdShow)) 
	{
		return FALSE;
	}

	while (GetMessage(&msg, NULL, 0, 0)) 
	{
		TranslateMessage(&msg);
		DispatchMessage(&msg);
	}

	return msg.wParam;
}

ATOM MyRegisterClass(HINSTANCE hInstance)
{
	WNDCLASSEX wcex;

	wcex.cbSize = sizeof(WNDCLASSEX); 

	wcex.style="CS_HREDRAW" | CS_VREDRAW;
	wcex.lpfnWndProc	= (WNDPROC)WndProc;
	wcex.cbClsExtra		= 0;
	wcex.cbWndExtra		= 0;
	wcex.hInstance		= hInstance;
	wcex.hIcon			= LoadIcon(hInstance, (LPCTSTR)IDI_SORT_CMP);
	wcex.hCursor		= LoadCursor(NULL, IDC_ARROW);
	wcex.hbrBackground	= (HBRUSH)(COLOR_WINDOW+1);
	wcex.lpszMenuName	= (LPCSTR)IDC_SORT_CMP;
	wcex.lpszClassName	= szWindowClass;
	wcex.hIconSm		= LoadIcon(wcex.hInstance, (LPCTSTR)IDI_SMALL);

	return RegisterClassEx(&wcex);
}

BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
	HWND hWnd;

	hInst = hInstance; // Store instance handle in our global variable

	hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
		CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);

	if (!hWnd)
	{
		return FALSE;
	}

	ShowWindow(hWnd, nCmdShow);
	UpdateWindow(hWnd);

	return TRUE;
}

//подпрограмма сортировки методом сравнения
//параметры: адреса исходного, вспомогательного, отсортированного и количество элементов
//исходный заполнен случайными числами в диапазоне [min=1,max=100]
//вспомогательный и отсортированный массивы обнулены
void SortCmp(int *a, int *b, int *c, int const n)
{
	int	i, j;
//сравниваем каждый с каждым и подсчитываем, когда каждый элемент больше всех остальных
	for (i=0; i<n; i++)
	{
		for (j=0; j<n; j++)
		{
			if (a[j]>a[i])
				b[j]++;
		}
	}
//заполняем отсортированный массив в соответствии с полученными количествами
//учитываем, что могут быть одинаковые числа, 
//для которых будет одинаковое количество сравнений
	for (i=0; i<n; i++)
	{
		j = b[i];		//количество сравнений будет индексом, куда вставляем значение
		while(c[j]!=0)	//если уже записано (встретились одинаковые числа!)
			j++;		// то найдем индекс, где еще не занято! Одинаковые числа будут рядом!
		c[j] = a[i];	//запоминаем исходное число на соответствующем месте
	}
}

LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
	HBRUSH hBrush, hOldBrush;
	PAINTSTRUCT ps;
	HDC hdc;
	int i;

	switch (message) 
	{
		case WM_CREATE:
			srand( (unsigned)time( NULL ) );	//инициируем последовательность псевдослучайных чисел
			a = (int*)malloc(n*sizeof(int));	//запросим память под массивы чисел
			b = (int*)malloc(n*sizeof(int));
			c = (int*)malloc(n*sizeof(int));
//создадим кнопку для запуска нового расчета
			CreateWindow("button", "Start", WS_VISIBLE|WS_CHILD|BS_DEFPUSHBUTTON, 
				430, 10, 100, 25, hWnd, (HMENU)IDM_START, hInst, NULL);
			break;

		case WM_COMMAND:
			switch (LOWORD(wParam))
			{
				case IDM_START:					//новый расчет!
					for(i=0; i<n; i++)
					{							//генерируем n новых случайных чисел
						a[i] = rand()%(max-min+1)+min;	//в диапозоне [min,max]
						c[i] = b[i] = 0;		//обнуляем вспомогательный и отсортированные массивы
					}
					SortCmp(a, b, c, n);		//сортируем
					fData = TRUE;				//помечаем, что еть данные для отображения
					InvalidateRect(hWnd, NULL, TRUE);	//даем команду на перерисовку
					break;
				case IDM_EXIT:					//выход
					free(a);					//освобждаем память
					free(b);
					free(c);
					DestroyWindow(hWnd);
					break;
				default:
					return DefWindowProc(hWnd, message, wParam, lParam);
			}
			break;

		case WM_PAINT:							//рисуем на окне
			hdc = BeginPaint(hWnd, &ps);

			hBrush = CreateSolidBrush(GetSysColor(COLOR_BTNFACE));	//создаем серую кисть
			hOldBrush = (HBRUSH)SelectObject(hdc, hBrush);			//выберем

			Rectangle(hdc, 10, 10, 410, 210);	//рисуем два прямоугольника, первый - исходные числа
			Rectangle(hdc, 10, 220, 410, 420);	//второй - отсортированные
			if (fData)							//данные есть?
			{
				for(i=0; i<n; i++)				//рисуем массив черных точек
				{								//точки в один пиксель отделяем друг от друга одним пикселем
					SetPixel(hdc, 11+i*2, 11+(100-a[i])*2, RGB(0,0,0)); 
					SetPixel(hdc, 11+i*2, 221+(100-c[i])*2, RGB(0,0,0)); 
				}
			}

			SelectObject(hdc, hOldBrush);		//вернем старую кисть 
			DeleteObject(hBrush);				//удалим созданную серую кисть
			
			EndPaint(hWnd, &ps);
			break;

		case WM_DESTROY:
			PostQuitMessage(0);
			break;

		default:
			return DefWindowProc(hWnd, message, wParam, lParam);
   }
   return 0;
}

Все файлы, необходимые для проекта, который создайте в своей студии
sort_cmp.rar (20.1 кб)

Консультировал: Лысков Игорь Витальевич (Старший модератор)
Дата отправки: 09.02.2014, 22:41
Рейтинг ответа:

НЕ одобряю +1 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!

© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А. | Гладенюк А.Г.
Хостинг: Компания "Московский хостер"
Версия системы: 2011.6.36 от 26.01.2012
В избранное