» Вопросы по программированию на C/С++

Кто разъяснит? Задача такая: сортировка отбором анализирует массив, отыскивая наименьший элемент массива. Затем этот наименьший элемент обменивается местами с первым элементом массива. Процесс повторяется для подмассива, начинающегося со второго элемента массива. В результате каждого прохода один из элементов занимает соответствующее место. Эта сортировка по производительности сравнима с пузырьковой — для массива из n элементов нужно выполнить n - 1 проход, а для каждого подмассива нужно выполнить n - 1 сравнение для определения наименьшего значения. Когда обрабатываемый подмассив будет содержать только один элемент, значит массив отсортирован. Нужно написать рекурсивную функцию selectionSort, выполняющую этот алгоритм.

Итеративную функцию я написал, а вот рекурсия никак не прет...

GOGACL
Это кто же заставил написать рекурсивный вариант? В 99% случаев (а может быть в 100% ) рекурсия работает медленней!

TeXpert

Цитата:

Ребята, вопрос: насколько знаю, к Intel Compiler есть мощная математическая библиотека. Меня интересует версия как для Unix-систем, так и для Windows. Где разжиться можно?

По этому вопросу обратитесь в соседнию ветку к фортранщикам. Это их хлеб и тут они впереди планеты всей

GOGACL
Примерно так должно быть:

Код:
void selectionSort(int *m, int start, int len)
{
    int min = start;
    for (int i = start + 1; i < len; ++i)
        if (m[min] > m[i])
            min = i;
    if (min != start)
    {
        int tmp = m[start];
        m[start] = m[min];
        m[min] = tmp;
    }
    if (start < len - 1)
        selectionSort(m, start + 1, len);
}

Labutin
спасибо, все работает, буду разбираться
А нельзя ли было в функцию передать два аргумента, в итеративном варианте именно так?

Легко
Код: void selectionSort(int *m, int len)
{
int min = 0;
for (int i = 1; i < len; ++i)
if (m[min] > m[i])
min = i;
if (min != 0)
{
int tmp = m[0];
m[0] = m[min];
m[min] = tmp;
}
if (0 < --len)
selectionSort(++m, len);
}

Qraizer
Функция тоже работает.
Получается что в данном случае нет необходимости применять рекурсию?
Данная задача была поставленна для изучения механизма рекурсии.
Но вот с этим как раз и проблема. Тема вроде легкая, но ни как не поддается...

На VC6.0 написана долго выполняющаяся процедура, периодически производящая вывод информации через
SendDlgItemMessage( hWnd, IdInfo, WM_SETTEXT, 0, (LPARAM)t );
Информация в поле вывода становится видна лишь по окончании работы процедуры, а нужно, чтобы она периодически обновлялась.
Полагаю, что нужно приостановить работу процедуры для обновления диалоговых элементов, но не знаю как. Может быть, есть какая-то функция?

alxm
Вообще-то такие процедуры лучше выполнять в отдельном треде. Тогда диалоговое окно не будет "замерзать" на время выполнения, и всё будет нормально прорисовываться.
См. API-ф-цию CreateThread (CreateThreadEx), или boost::thread.
Если юзаешь MFC и не хочешь заморачиваться с мультитредовостью - можно просто где-то внутри твоего рабочего цикла (если это цикл, конечно) вставить приблизительно такую конструкцию:

Код:
while ( ::PeekMessage( &msg, NULL, 0, 0, PM_NOREMOVE ) )
{
if ( !PumpMessage( ) )
{
::PostQuitMessage( );
break;
}
}

alxm
Код: The SendDlgItemMessage function does not return until the message has been processed.
Using SendDlgItemMessage is identical to retrieving a handle to the specified control and calling the SendMessage function

xdude
Спасибо. Второй способ заработал сразу. Но так как перерывы на вывод информации в цикле происходят редко, то обновление окна выполняется рывками (например, при перемещении окна мышью). Наверное, имеет смысл попробовать CreateThread.

TeXpert
Дык как раз таки
Цитата:

function DOES NOT return until the message has been processed

, так что с этой точки зрения все очень даже верно. Шутка в том, что текст для этого окошка установится, а вот чтобы его прорисовать - нужно еще сообщение WM_PAINT обработать, которое автоматом посылаться в очередь при обработке окошком сообщения WM_SETTEXT, а очередь сообщений начинает обрабатываться только в основном рабочем цикле приложения, до которого дело доходит только после возврата из этой самой большой и жырной процедуры.
alxm
Да, всё верно, от рывков можно избавиться только создав отдельный тред для своей процедуры.

xdude
"Другое" я как раз и имел в виду потоки завести.

xdude, как я помню, для того что бы заставить окно перерисоваться самое простое, это вызвать функцию BOOL InvalidateRect(HWND, CONST RECT*, BOOL).

veronica b
InvalidateRect пошлёт то же самое сообщение WM_PAINT.

Использовал следующие функции для конвертирования строк в Uppercase и LowerCase:

std::string ConvertToUpper(const std::string &aValue)
{
std::string result = aValue;
std::transform(aValue.begin(), aValue.end(), result.begin(), (int(*)(int))std::toupper);
return result;
}

std::string ConvertToLower(const std::string &aValue)
{
std::string result = aValue;
std::transform(aValue.begin(), aValue.end(), result.begin(), (int(*)(int))std::tolower);
return result;
}

Недавно заметил что они не работают для UTF-8 строк (кириллица)
Как правильно преобразовать std::string в Uppercase и LowerCase для UTF-8?

Abs62

Цитата:

InvalidateRect пошлёт то же самое сообщение WM_PAINT.

Абсолютно верно, но есть "маленькая" тонкость, пошлет, но минуя системную очередь! Прямо в оконную процедуру.

veronica b

Цитата:

Абсолютно верно, но есть "маленькая" тонкость, пошлет, но минуя системную очередь!

Хм. Смотрим описание:

Цитата:

Remarks
The invalidated areas accumulate in the update region until the region is processed when the next WM_PAINT message occurs or until the region is validated by using the ValidateRect or ValidateRgn function.

The system sends a WM_PAINT message to a window whenever its update region is not empty and there are no other messages in the application queue for that window.

Тут как раз сказано обратное - сообщение будет послано, только если WM_PAINT в очереди нет.
А если уж очень хочется послать напрямую, для этого надо ещё задействовать UpdateWindow:

Цитата:

The UpdateWindow function updates the client area of the specified window by sending a WM_PAINT message to the window if the window's update region is not empty. The function sends a WM_PAINT message directly to the window procedure of the specified window, bypassing the application queue. If the update region is empty, no message is sent.

Abs62

Цитата:

А если уж очень хочется послать напрямую, для этого надо ещё задействовать UpdateWindow:

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

2 нубских вопроса по C++Builder 6:
Как задать фоновое изображение надписи в форме или сделать фон надписи прозрачным?

Почему на картинке у SpeedButton появились белые точки?

Здравстуйте. Вот меня на собеседовании озадачили таким вопросом как инвертировать однонаправленный список? Т.е. у нас есть однонаправленный список, нужно сделать так, чтобы поле с указателем на следующюю структуру каждой структуры ссылался не на следующий а на предыдущий элемент списка. Я в затупе. Кроме как запомнить все адреса в обычном массивы, а потом их переназанчить я ничего не придумал. Может быть есть готовый алгоритм этого процеса без использования массива?

Примерно так:
Код: struct snode
{
/* ... */
snode *next;
};

snode* ptr;

/* ... */

if(ptr != NULL)
{
snode *ptrNext = ptr->next,
*ptrPred = NULL;

while(ptrNext!=NULL)
{
ptr->next = ptrPred;
ptrPred = ptr;
ptr = ptrNext;
ptrNext = ptr->next;
}
ptr->next = ptrPred;
}

iamrecvezitor, ваш вопрос задают на собеседовании довольно часто. Из моего опыта, я могу сказать, что очень важно нарисовать рисунок списка и через стрелки показать как меняется связи списка. Посмотрите книгу Джоэла Слопольски, "Джоэл о программировании". Там, как я помню, эта задача расматривалась и сего легкой руки стали широко использовать!

Qraizer, veronica b спасибо. Блин все так элегантно... а я там замутить пытался... мда видимо опыта явно не хватает. Кстати рисуночки то я им нарисовал, а вот реализовать это не получилось в отведенное время


Добавлено:
Qraizer
хмм.. у меня так как у вас не получилось... пришлось немного изменить

    struct ar *nextSave;
    struct ar *tail = NULL;

    current = head;
    nextSave = current->next;

while(nextSave!=NULL)
    {        
        prev = current;
        current = nextSave;
        nextSave = current->next;    
        if(current->next == NULL)
            tail = current;
        current->next = prev;
    }
    current = head;
    current->next = NULL;

Люди помогите пожалуйста, наверно децкий вопрос!
Выдает ошибку "Lvalue required" на следующей строке

Код:
(char huge *) v3 = (char huge *) (vm + 32768l);

iamrecvezitor Давай смотреть.
Цитата:

nextSave = current->next;
if(current->next == NULL)
tail = current;

Нетрудно увидеть, что current->next и nextSave равны, благодаря первому присваиванию, поэтому условие будет истинным, только если это последняя итерация цикла. Значит весь if можно смело выкинуть из цикла, а присваивание tail-у просто поставить за его концом.
Цикл у тебя имеет инвариант: в начале каждой итерации - current указывает на "новую" голову уже перевёрнутого списка, а nextSave - на остаток (хвост) ещё не перевёрнутого; в конце итерации к "новому" списку в голову добавляется указываемый предыдущим nextSave-ом, а сам nextSave перемещается дальше. Всё хорошо и правильно, за исключением того, что "новый" список не является списком - его последний элемент (бывший первый) ссылается не на NULL, а на предпоследний (бывший второй). Ты знакОм с концепцией отказоустойчивого (безопасного) программирования? Если нет, то познакомься, если да, то почему её не соблюдаешь? Конечно, NULL ему-таки присваивается
Цитата:

current = head;
current->next = NULL;

но почему-то в самом конце, а не начале. Нелогично. Кроме того, если ты разворачиваешь список, то его новая голова - это по логике head, а новый хвост - это tail. А так как у тебя эти переменные используются, согласись, смущает.
Итак, head - это голова списка. Для односвязного списка этого достаточно, т.е. tail избыточен. Даже бесполезен, наверное. Если head в "новом" списке станет хвостом, то он тоже будет безполезен, как в бывшем был бесполезен tail. Следовательно нет никакой причины иметь две переменные. Далее, current - это у тебя текущая голова (для текущей итерации) для "нового" списка. Т.к. head в цикле не используется, после цикла станет новой головой, а заNULLение хвоста списка мы вроде бы уже перенесли в начало алгоритма, получается, что и current не нужен, его вполне можно заменить head-ом.
Если теперь всё это применить к твоему тексту, то получится как раз, как у меня с точностью до замены имён переменных.
К чему это я собственно, чуть не забыл. Я не хочу сказать, что твой хуже (хотя несоблюдение логической целостности структур - это очень нехорошо), скорее, чуть сложнее и медленнее, однако мой фрагмент так же корректно отрабатывает ситуации с пустым списком, чего не скажешь о твоём. Непонятно, почему у тебя не вышло, как у меня - ведь в итоге твой текст получился эквивалентными моему.

Добавлено:
L0ST
И правильно выдаёт. Не знаю, какого типа у тебя v3, но если не char huge*, то кастование к char huge* создаёт новую неименованную временную переменную, присваиваение которой бессмысленно, т.к. в конце выражения одна будет уничтожена. Чтобы было понятнее, рассмотри такой вариант своего кода
Код: int v3;

(double) v3 = 123.456;

L0ST, а какой тип имеет переменная vm, если я правильно понял, то напиши так
v3 = (char huge *) (&vm + 32768l);
Понятно, где я исправил?
Если не пройдет, то напишите определение vm и что вы хотите получить!

Qraizer
мне пришлось немного переделать ваш текст, потому что когда я его применил у меня наотрез отказывался присваивать ссылке ptr->next(или current->next) указатель на предыдущий элемент. И ктому же он никогда не выходил из первого цикла

Цитата:

if(ptr != NULL)

На счет избыточности tail и проверки его внутри цикла согласен. А на счет избыточности current не совсем. По моему разумению head хранит голову списка(и поидее не должна изменяться, чтобы не забыть начало списка), а current это переменная, которая пробегает по текущему элементу страого списка.


Цитата:

current = head;
current->next = NULL;

Это пришлось добавить, т.к. он у меня в теле цикла не присваливал первому элементу списка current->next = NULL;
На пустой список я его не проверял...

Цитата:

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

И я том же. Когда список реверсирован, где будет его голова? А у тебя она в хвосте.
Цитата:

Это пришлось добавить, т.к. он у меня в теле цикла не присваливал первому элементу списка current->next = NULL;

Ты вообще невнимательно читал мой пост. Иначе бы не писал того, что я уже комментировал в своём прежнем посте.

P.S. Проверил свой код. Работает. Что у тебя за проблемы - не имею представления.

Блин.. переписал прогу с фортрана, так как он ужасно работает со строками, на C++.. вот теперь возникла вещь которой не было в фортране - как можно передать в функцию часть массива? не делая его копии.. в цикле или аналогично копированием памяти..
в фортране это просто, как в матлабе.. array_name(1:100) скажем.. в C++ можно так?
зачем - массив многомерный. а функция одна, скажем для записи в файл данных и вызываться может для разных массивов (разной размерности)..