Тестовое задание на Junior C++ dev

@Мимино · Регистрация: 22.05.2013

Author24 — интернет-сервис помощи студентам

Доброго времени суток.
Неделю назад ради интереса отправил свое резюме в одну компанию, куда требуются с++ юниоры. Получил от них тестовое задание. Я ожидал, что они мне откажут (опыта то у меня действительно мизер), но хотелось бы узнать у более опытных людей, какое решение задач "ожидает" компания от соискателя для продолжения с ним отношений.
Далее идет 4 задачи и мой вариант решения каждой из них.

1. Распечатать произвольное число в двоичной системе исчисления.

Описание.
Написать функцию, принимающую на вход произвольное целочисленное значение и возвращающую строку, содержащую его представление в двоичной системе исчисления.

Декларация.
voidNumberAsBinary(
char* _result,// строка с результатом
unsignedint _number// произвольное число
)

Ожидаемый результат.
Например, для числа 13 данная функция должна вернуть строку "1101".

Проверка работы.
Решение должно демонстрировать работу функции на примере 10 случайных чисел в диапазоне 0 до 512.

C++

#include <iostream>
#include <stdlib.h>
#include <time.h>
using std::cout;
using std::endl;
 
void numberAsBinary(char *_result, unsigned int _number); 
 
int main()
{
    setlocale(LC_ALL, "Russian");
    char *result = new char[11];
    unsigned int number;
    
    srand((unsigned)time(NULL));
    for (int i = 1; i <= 10; i++)
    {
        number = rand() % 513;
        numberAsBinary(result, number);
        cout << "Число " << number << " в двоичной системе счисления равно " << result << endl;
    }
 
    delete [] result;
    system("pause");
    return 0;
}
 
void numberAsBinary(
char *_result,
unsigned int _number
    )
{
    static int i;
    i = 0;
 
    if (_number != 1)
        numberAsBinary(_result, _number / 2);
 
    _result[i] = (_number % 2) + '0';
    i++;
    _result[i] = '\0';
}

2. Сгенерировать неупорядоченный массив целых чисел от 1 до N.

Описание.
Написать функцию, принимающую на вход произвольное целочисленное значение и возвращающую массив, содержащий последовательность чисел от 1 до этого значения, в котором каждое число последовательности находится в заведомо случайной позиции.

Декларация.
void GenerateRandomArray(
int * _result, // возвращаемыймассив
unsignedint _maxValue// максимальное число в последовательности
)

Ожидаемый результат.
Например, 2 последовательных запуска данной функции с параметром 7 могут сгенерировать последовательности вида
{2, 5, 7, 3, 4, 1, 6}
{5, 1, 3, 4, 6, 2, 7}

Проверка работы.
Решение должно демонстрировать работу функции на примере 4 случайных чисел в диапазоне от 5 до 15.

C++

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <iomanip>
using std::cout;
using std::endl;
 
void generateRandomArray(int *_result, unsigned int _maxValue);
 
int main()
{
    setlocale(LC_ALL, "Russian");
    unsigned int maxValue;
    
    srand((unsigned)time(NULL));
    for (int i = 1; i <= 4; i++)
    {
        maxValue = 5 + rand() % 11;
        int *result = new int[maxValue];
        generateRandomArray(result, maxValue);
    
        cout << "Неупорядоченные числа от 1 до " 
             << std::setw(2) << maxValue << ": ";
        for (unsigned int i = 0; i < maxValue; i++)
            cout << result[i] << ' ';
        cout << endl;
        delete [] result;
    }
 
    system("pause");
    return 0;
}
 
void generateRandomArray(
int *_result, 
unsigned int _maxValue
    )
{
    int ind1, ind2, tmp;
 
    for (unsigned int i = 0, j = 1; i < _maxValue; i++, j++)
        _result[i] = j;
 
    for (int i = 1; i <= 20; i++)
    {
        ind1 = rand() % _maxValue;
        ind2 = rand() % _maxValue;
        tmp = _result[ind1];
        _result[ind1] = _result[ind2];
        _result[ind2] = tmp;
    }
}

3. Сортировка массива.

Описание.
Написать функцию, принимающую в качестве параметра массив неупорядоченных целых чисел (сгенерированный с помощью функции из задачи 2) и выполняющую его сортировку.

Декларация.
voidSort(
int* _values,// сортируемый массив
unsignedint _count// количество элементов в массиве
)

Ожидаемый результат.
Например, массив вида {2, 5, 7, 3, 4, 1, 6} будет преобразован данной функцией в {1, 2, 3, 4, 5, 6, 7}.

Проверка работы.
Решение должно демонстрировать работу функции на примере результатов, полученных при решении задачи 2 (последовательностей, сгенерированных для 4 случайных чисел в диапазоне от 5 до 15).

C++

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <iomanip>
using std::cout;
using std::endl;
 
void generateRandomArray(int *_result, unsigned int _maxValue);
void Sort(int *_values, unsigned int _count);
 
 
int main()
{
    setlocale(LC_ALL, "Russian");
    unsigned int maxValue;
    
    srand((unsigned)time(NULL));
    for (int i = 1; i <= 4; i++)
    {
        maxValue = 5 + rand() % 11;
        int *result = new int[maxValue];
        generateRandomArray(result, maxValue);
    
        cout << "Неупорядоченные числа от 1 до " 
             << std::setw(2) << maxValue << ": ";
        for (unsigned int i = 0; i < maxValue; i++)
            cout << result[i] << ' ';
        cout << endl;
 
        Sort(result, maxValue - 1);
 
        cout << "Упорядоченные числа от 1 до " 
             << std::setw(2) << maxValue << ":   ";
        for (unsigned int i = 0; i < maxValue; i++)
            cout << result[i] << ' ';
        cout << endl << endl;
 
        delete [] result;
    }
 
    system("pause");
    return 0;
}
 
void generateRandomArray(
int *_result, 
unsigned int _maxValue
    )
{
    int ind1, ind2, tmp;
 
    for (unsigned int i = 0, j = 1; i < _maxValue; i++, j++)
        _result[i] = j;
 
    for (int i = 1; i <= 20; i++)
    {
        ind1 = rand() % _maxValue;
        ind2 = rand() % _maxValue;
        tmp = _result[ind1];
        _result[ind1] = _result[ind2];
        _result[ind2] = tmp;
    }
}
 
void Sort(
int *_values,
unsigned int _count
    )
{
    int i = 0, j = _count; 
    int temp, p;
 
    p = _values[_count >> 1]; 
 
    do
    {
        while (_values[i] < p) i++;
        while (_values[j] > p) j--;
 
        if (i <= j) 
        {
            temp = _values[i];
            _values[i] = _values[j];
            _values[j] = temp;
            i++;
            j--;
        }
 
    } while (i <= j);
 
    if (j > 0) 
        Sort(_values, j);
    if (_count > (unsigned)i)  
        Sort(_values+i, _count-i);
}

4. Определить недостающее число в неупорядоченной последовательности целых чисел.

Описание.
Написать функцию, принимающую в качестве параметра массив неупорядоченных целых чисел(сгенерированный с помощью функции из задачи 2) и определяющую значение последнего элемента в массиве без доступа к нему.

Декларация.
intGetMissingValue(
constint * _values,// неупорядоченный массив целых чисел от 1 до _count
unsignedint _count// количество элементов в массиве
)

Ожидаемый результат.
Например, для последовательности {5, 7, 8,3, 1, 9, 2, 6, 4} данная функция должна вернуть 4.

Проверка работы.
Решение должно демонстрировать работу функций на примере результатов, полученных при решении задачи 2 (последовательностей, сгенерированных для 4 случайных чисел в диапазоне от 5 до 15).

C++

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <iomanip>
using std::cout;
using std::endl;
 
void generateRandomArray(int *_result, unsigned int _maxValue);
void Sort(int *_values, unsigned int _count);
int getMissingValue(const int *_values, unsigned int _count);
 
 
int main()
{
    setlocale(LC_ALL, "Russian");
    unsigned int maxValue;
    
    srand((unsigned)time(NULL));
    for (int i = 1; i <= 4; i++)
    {
        maxValue = 5 + rand() % 11;
        int *result = new int[maxValue];
        generateRandomArray(result, maxValue);
    
        cout << "Неупорядоченные числа от 1 до " 
             << std::setw(2) << maxValue << ": ";
        for (unsigned int i = 0; i < maxValue; i++)
            cout << result[i] << ' ';
 
        cout << endl << "Значение последнего элемента:     " 
             << getMissingValue(result, maxValue) << endl;
 
        Sort(result, maxValue - 1);
 
        cout << "Упорядоченные числа от 1 до " 
             << std::setw(2) << maxValue << ":   ";
        for (unsigned int i = 0; i < maxValue; i++)
            cout << result[i] << ' ';
        cout << endl << endl;
 
        delete [] result;
    }
 
    system("pause");
    return 0;
}
 
void generateRandomArray(
int *_result, 
unsigned int _maxValue
    )
{
    int ind1, ind2, tmp;
 
    for (unsigned int i = 0, j = 1; i < _maxValue; i++, j++)
        _result[i] = j;
 
    for (int i = 1; i <= 20; i++)
    {
        ind1 = rand() % _maxValue;
        ind2 = rand() % _maxValue;
        tmp = _result[ind1];
        _result[ind1] = _result[ind2];
        _result[ind2] = tmp;
    }
}
 
void Sort(
int *_values,
unsigned int _count
    )
{
    int i = 0, j = _count; 
    int temp, p;
 
    p = _values[_count >> 1]; 
 
    do
    {
        while (_values[i] < p) i++;
        while (_values[j] > p) j--;
 
        if (i <= j) 
        {
            temp = _values[i];
            _values[i] = _values[j];
            _values[j] = temp;
            i++;
            j--;
        }
 
    } while (i <= j);
 
    if (j > 0) 
        Sort(_values, j);
    if (_count > (unsigned)i)  
        Sort(_values+i, _count-i);
}
 
int getMissingValue(
const int *_values,
unsigned int _count
    )
{
    unsigned int checkSum = 0, sum = 0;
 
    for (unsigned int i = 0; i < _count - 1; i++)
    {
        checkSum += i + 1;
        sum += _values[i];
    }
 
    return checkSum + _count - sum;
}

@gray_fox · 26.07.2013, 22:15

Olivеr, у них же там свои прототипы, с С-строками и указателями...

@nonedark2008 · 26.07.2013, 22:39

Нуу, так как нет определенных условий, то первую задачу можно решить используя std::bitset в несколько строк. Ну или по хорошему вначале посчитать кол-во лидирующих нулей, выделить память под массив, а далее побитовыми операциями достать нужные биты.
Со вторым я солидарен - нужно создать массив и перемешать его.
Третье - числа в диапазоне от 5 до 15? Тут тупо можно использовать любой алгоритм, но наверно эффективнее будет сортировка вставками, хотя по хорошему было бы родить алгоритм, который для мелких значений сортирует вставками, а для больших например быстрой или слиянием.
Ну в четвертом тоже все просто - уже рассказали.

@Thinker · 26.07.2013, 22:45

Сообщение от nonedark2008

первую задачу можно решить используя std::bitset в несколько строк. Ну или по хорошему вначале посчитать кол-во лидирующих нулей, выделить память под массив, а далее побитовыми операциями достать нужные биты.

массив то зачем еще здесь, сразу забракуют

Сообщение от nonedark2008

Третье - числа в диапазоне от 5 до 15? Тут тупо можно использовать любой алгоритм, но наверно эффективнее будет сортировка вставками, хотя по хорошему было бы родить алгоритм, который для мелких значений сортирует вставками, а для больших например быстрой или слиянием.

как раз таки эффективной будет сортировка подсчетом в два прохода по массиву

@TimeToWork · 26.07.2013, 23:19

Оставлю и я свой комментарий, хотя, возможно, что-то из этого уже прозвучало.

Задача 1. Наверняка для проверки представления о работе с битами. Твоё решение было бы нормальным, если бы вместо рекурсии сделать обычный цикл, всё же на скорость это влияет катастрофически.

Задача 2. Это даже близко не рандом. Контрпример к твоему решению - запусти свою программу для массива на 1000 элементов, 20 перестановок на неё не особо то и повлияют.

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

Задача 4. Стандартная олимпиадная задачка, решается в 4 строчки. Не пишу ответ, дабы не портить никому кайф. Маленькая подсказка

Кликните здесь для просмотра всего текста

сложность алгоритма О(N)

Судя по результатам теста ТС 2 задачи из 4 завалил (вторая и 4ая). А при 50% результате отказ действительно предсказуем. Как-никак, а опыт имеет огромное значение, если действительно хотите работать по данной специальности - нужно больше практиковаться.

@nonedark2008 · 26.07.2013, 23:25

Сообщение от Thinker

массив то зачем еще здесь, сразу забракуют

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

Сообщение от Thinker

как раз таки эффективной будет сортировка подсчетом в два прохода по массиву

Для этой сортировки понадобятся два временных массива, что ИМХО не хорошо. Или если брать простой алгоритм пдсчета, то это та же фигня, что просто взять массив и заполнить сразу его числами от 1 до N(самый быстрый алгоритм получается - массив любой длины сортируется в один проход ^_^).

@Мимино · 26.07.2013, 23:30 **[ТС]**

Сообщение от TimeToWork

Как-никак, а опыт имеет огромное значение, если действительно хотите работать по данной специальности - нужно больше практиковаться.

Конечно же

Вот только чтобы получить больше опыта, нужно куда то устроиться в подмастерье... а чтобы это сделать, нужно больше опыта

Преподавателя у меня нет, универ я закончил 5 лет назад и из головы уже многое повылетало. Не буду же я на форуме по каждой задаче спрашивать оптимальные алгоритмы решения. Курсы не признаю вовсе

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

@nonedark2008 · 26.07.2013, 23:32

Сообщение от Мимино

Не буду же я на форуме по каждой задаче спрашивать оптимальные алгоритмы решения.

Ну дык, а книжки умные кто будет читать? Вооружись Корменом и Кнутом, прочитай - будешь сам оптимальные алгоритмы придумывать.

@Мимино · 26.07.2013, 23:36 **[ТС]**

Сообщение от nonedark2008

Ну дык, а книжки умные кто будет читать? Вооружись Корменом и Кнутом, прочитай - будешь сам оптимальные алгоритмы придумывать.

Читаю, читаю... не просто так же сижу

но на это нужно время, а "копилочка" безработного не резиновая

Помимо чтения надо же и писать что то, причем много.

@ForEveR · 26.07.2013, 23:38

Оптимальность... Оптимальность далеко не всегда важна. Зависит от задач, зависит от компании, зависит, в конце концов, от предметной области. Чаще всего лучше написать красивый, понятный код, нежели писать swap через битовые операции.

@nonedark2008 · 26.07.2013, 23:45

Сообщение от ForEveR

Чаще всего лучше написать красивый, понятный код

Хороший программист легко напишет оптимальный алгоритм красиво и понятно. Я, например, считаю, что оптимальность очень важна. Одно дело когда ты пишешь поиск подстроки прямым поиском в несколько строк, а другое - когда тот же поиск, но алгоритмом Боуера и Мура. Второе выглядит многим красивее...
Мне кажется, что красота кода, его понятность и его оптимальность - понятия схожи, и одно без другого как-то и не встречаются.

@kamre · 26.07.2013, 23:54

Не по теме:

Сообщение от Мимино

универ я закончил 5 лет назад и из головы уже многое повылетало

Почему тогда за C++ взялся сразу? Может стоило на .NET/Java посмотреть, там junior-ом должно быть проще устроиться.

@Мимино · 26.07.2013, 23:57 **[ТС]**

Сообщение от kamre

Не по теме:

Почему тогда за C++ взялся сразу? Может стоило на .NET/Java посмотреть, там junior-ом должно быть проще устроиться.

Мне он с универа еще очень нравился

Проще/сложнее меня не пугает, главное - удовольствие.

@nonedark2008 · 27.07.2013, 00:02

Сообщение от Мимино

Проще/сложнее меня не пугает, главное - удовольствие.

Тут я с тобой солидарен =) А еще C++ хорош своей креативностью, любой баг в программе подпирается костылем, цвет, размер, форма и позиция которого подбираются на любой вкус ^_^

@ovner · 27.07.2013, 00:03

Сообщение от kamre

Не по теме:

Почему тогда за C++ взялся сразу? Может стоило на .NET/Java посмотреть, там junior-ом должно быть проще устроиться.

я тоже сейчас изучаю с++, может мне забить на него и посмотреть на Java/C# ?

@ForEveR · 27.07.2013, 00:07

Сообщение от nonedark2008

Хороший программист легко напишет оптимальный алгоритм красиво и понятно. Я, например, считаю, что оптимальность очень важна. Одно дело когда ты пишешь поиск подстроки прямым поиском в несколько строк, а другое - когда тот же поиск, но алгоритмом Боуера и Мура. Второе выглядит многим красивее...
Мне кажется, что красота кода, его понятность и его оптимальность - понятия схожи, и одно без другого как-то и не встречаются.

Я вероятно соглашусь вцелом, но не соглашусь в частностях. Хороший программист знает что и где выбрать. Где-то удобнее простой поиск подстроки, где-то удобнее алгоритмом Боуера и Мура, где-то удобнее использовать регулярные выражения, а где-то этот поиск вообще не нужен.

Хороший программист легко напишет оптимальный алгоритм красиво и понятно.

Ну и да, в большинстве случаев, хороший программист не будет изобретать велосипед, а воспользуется проверенными средствами (читай библиотеками).

@nonedark2008 · 27.07.2013, 00:11

Сообщение от ovner

я тоже сейчас изучаю с++, может мне забить на него и посмотреть на Java/C# ?

Лучше хорошо допилить один язык, остальные пойдут намного проще. Вначале я неплохо в школе выучил C, после него C++ пошел легко. Далее Java - один хрен что и C++, а C# - считай содран с Явы. А дальше совсем все просто пошло: Python, Фортран, Хаскел, Лисп, Асма. За пару дней запоминаешь синтаксис языка и его особенности и уже можно писать что-либо осмысленное.

Добавлено через 1 минуту

Сообщение от ForEveR

Хороший программист знает что и где выбрать. Где-то удобнее простой поиск подстроки, где-то удобнее алгоритмом Боуера и Мура, где-то удобнее использовать регулярные выражения, а где-то этот поиск вообще не нужен.

Это как раз и называется поиском оптимального решения для конкретной задачи.

@ForEveR · 27.07.2013, 00:14

nonedark2008,

Сообщение от ForEveR

Одно дело когда ты пишешь поиск подстроки прямым поиском в несколько строк, а другое - когда тот же поиск, но алгоритмом Боуера и Мура. Второе выглядит многим красивее...

Кажется вы немножко себе противоречите. Впрочем, пустое. В целом, вы сказали все верно.

@nonedark2008 · 27.07.2013, 00:17

Не по теме:

Сообщение от ForEveR

Кажется вы немножко себе противоречите.

Есть немного =)

@Thinker · 27.07.2013, 08:03

Сообщение от nonedark2008

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

судя по прототипу функции
void numberAsBinary(char *_result, unsigned int _number);
результат сразу помещать в строку result, дополнительные массивы вряд ли приветствуются.

Сообщение от nonedark2008

Для этой сортировки понадобятся два временных массива, что ИМХО не хорошо.

откуда там два временных массива? там только массив count из 11 элементов всего. а вообще стоило пару сортировок прислать с комментариями.

Сообщение от TimeToWork

Задача 4. Стандартная олимпиадная задачка, решается в 4 строчки.

стандартная детская задачка, решается в две строчки кода. При оценке ее сложности можно O-большим не пользоваться, чтобы подчеркнуть, что сложность алгоритма W(N) < N.

@BigLow · 29.07.2013, 22:26

Сообщение от Мимино

3. Сортировка массива.

Сообщение от Мимино

Решение должно демонстрировать работу функции на примере результатов, полученных при решении задачи 2 (последовательностей, сгенерированных для 4 случайных чисел в диапазоне от 5 до 15).

Что-то мне кажется что эта задача с подвохом. У нас уже есть перемешанный массив с числами от 1 до N.
И теперь нужно произвести его сортировку. Но тогда можно и таким способом

C++

void Sort(
    int *_values,  // сортируемый массив
    unsigned int _count  // количество элементов в массиве
    )
{
  for (unsigned int i=0;  i!=_count;  ++i)
    _values[i]=i+1;
}

В результате получим массив 1 2 3 4 5 ... N

@gray_fox What a waste! 1607 / 1299 / 180 Регистрация: 21.04.2012 Сообщений: 2,727
	26.07.2013, 22:15	41
	Olivеr, у них же там свои прототипы, с С-строками и указателями... 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	26.07.2013, 22:39	42
	Нуу, так как нет определенных условий, то первую задачу можно решить используя std::bitset в несколько строк. Ну или по хорошему вначале посчитать кол-во лидирующих нулей, выделить память под массив, а далее побитовыми операциями достать нужные биты. Со вторым я солидарен - нужно создать массив и перемешать его. Третье - числа в диапазоне от 5 до 15? Тут тупо можно использовать любой алгоритм, но наверно эффективнее будет сортировка вставками, хотя по хорошему было бы родить алгоритм, который для мелких значений сортирует вставками, а для больших например быстрой или слиянием. Ну в четвертом тоже все просто - уже рассказали. 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	26.07.2013, 22:45	43
	Сообщение от nonedark2008 первую задачу можно решить используя std::bitset в несколько строк. Ну или по хорошему вначале посчитать кол-во лидирующих нулей, выделить память под массив, а далее побитовыми операциями достать нужные биты. массив то зачем еще здесь, сразу забракуют Сообщение от nonedark2008 Третье - числа в диапазоне от 5 до 15? Тут тупо можно использовать любой алгоритм, но наверно эффективнее будет сортировка вставками, хотя по хорошему было бы родить алгоритм, который для мелких значений сортирует вставками, а для больших например быстрой или слиянием. как раз таки эффективной будет сортировка подсчетом в два прохода по массиву 0

@TimeToWork 4 / 4 / 0 Регистрация: 13.04.2013 Сообщений: 25
	26.07.2013, 23:19	44
	Оставлю и я свой комментарий, хотя, возможно, что-то из этого уже прозвучало. Задача 1. Наверняка для проверки представления о работе с битами. Твоё решение было бы нормальным, если бы вместо рекурсии сделать обычный цикл, всё же на скорость это влияет катастрофически. Задача 2. Это даже близко не рандом. Контрпример к твоему решению - запусти свою программу для массива на 1000 элементов, 20 перестановок на неё не особо то и повлияют. Задача 3. Сортировка. Много кода, не стал вчитываться. Возможно там и всё хорошо. Но, в любом случае, основным критерием выступает не сделанная сортировка, а метод, который употребил человек. По этому вопросу пример куча, и то, разобрался ли опрашиваемый в более быстрых и интересных способах реализации задачи, или сделал "в лоб", очень многое показывает о его стремлении к красивому. Задача 4. Стандартная олимпиадная задачка, решается в 4 строчки. Не пишу ответ, дабы не портить никому кайф. Маленькая подсказка Кликните здесь для просмотра всего текста сложность алгоритма О(N) Судя по результатам теста ТС 2 задачи из 4 завалил (вторая и 4ая). А при 50% результате отказ действительно предсказуем. Как-никак, а опыт имеет огромное значение, если действительно хотите работать по данной специальности - нужно больше практиковаться. 1

@Мимино 190 / 160 / 35 Регистрация: 22.05.2013 Сообщений: 455 Записей в блоге: 1
	26.07.2013, 23:30 [ТС]	46
	Сообщение от TimeToWork Как-никак, а опыт имеет огромное значение, если действительно хотите работать по данной специальности - нужно больше практиковаться. Конечно же Вот только чтобы получить больше опыта, нужно куда то устроиться в подмастерье... а чтобы это сделать, нужно больше опыта Преподавателя у меня нет, универ я закончил 5 лет назад и из головы уже многое повылетало. Не буду же я на форуме по каждой задаче спрашивать оптимальные алгоритмы решения. Курсы не признаю вовсе Но я не собираюсь опускать руки. Надеюсь, толк из меня будет вскоре 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	26.07.2013, 23:25	45
	Сообщение от Thinker массив то зачем еще здесь, сразу забракуют Ну дык нужно же где-то хранить битовый результат, хотя все на усмотрение программиста. Сообщение от Thinker как раз таки эффективной будет сортировка подсчетом в два прохода по массиву Для этой сортировки понадобятся два временных массива, что ИМХО не хорошо. Или если брать простой алгоритм пдсчета, то это та же фигня, что просто взять массив и заполнить сразу его числами от 1 до N(самый быстрый алгоритм получается - массив любой длины сортируется в один проход ^_^). 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	26.07.2013, 23:32	47
	Сообщение от Мимино Не буду же я на форуме по каждой задаче спрашивать оптимальные алгоритмы решения. Ну дык, а книжки умные кто будет читать? Вооружись Корменом и Кнутом, прочитай - будешь сам оптимальные алгоритмы придумывать. 0

@Мимино 190 / 160 / 35 Регистрация: 22.05.2013 Сообщений: 455 Записей в блоге: 1
	26.07.2013, 23:36 [ТС]	48
	Сообщение от nonedark2008 Ну дык, а книжки умные кто будет читать? Вооружись Корменом и Кнутом, прочитай - будешь сам оптимальные алгоритмы придумывать. Читаю, читаю... не просто так же сижу но на это нужно время, а "копилочка" безработного не резиновая Помимо чтения надо же и писать что то, причем много. 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	26.07.2013, 23:38	49
	Оптимальность... Оптимальность далеко не всегда важна. Зависит от задач, зависит от компании, зависит, в конце концов, от предметной области. Чаще всего лучше написать красивый, понятный код, нежели писать swap через битовые операции. 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	26.07.2013, 23:45	50
	Сообщение от ForEveR Чаще всего лучше написать красивый, понятный код Хороший программист легко напишет оптимальный алгоритм красиво и понятно. Я, например, считаю, что оптимальность очень важна. Одно дело когда ты пишешь поиск подстроки прямым поиском в несколько строк, а другое - когда тот же поиск, но алгоритмом Боуера и Мура. Второе выглядит многим красивее... Мне кажется, что красота кода, его понятность и его оптимальность - понятия схожи, и одно без другого как-то и не встречаются. 0

@kamre
	26.07.2013, 23:54 #51
	Не по теме: Сообщение от Мимино универ я закончил 5 лет назад и из головы уже многое повылетало Почему тогда за C++ взялся сразу? Может стоило на .NET/Java посмотреть, там junior-ом должно быть проще устроиться. 0

@Мимино 190 / 160 / 35 Регистрация: 22.05.2013 Сообщений: 455 Записей в блоге: 1
	26.07.2013, 23:57 [ТС]	52
	Сообщение от kamre Не по теме: Почему тогда за C++ взялся сразу? Может стоило на .NET/Java посмотреть, там junior-ом должно быть проще устроиться. Мне он с универа еще очень нравился Проще/сложнее меня не пугает, главное - удовольствие. 1

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	27.07.2013, 00:02	53
	Сообщение от Мимино Проще/сложнее меня не пугает, главное - удовольствие. Тут я с тобой солидарен =) А еще C++ хорош своей креативностью, любой баг в программе подпирается костылем, цвет, размер, форма и позиция которого подбираются на любой вкус ^_^ 0

@ovner 7 / 7 / 5 Регистрация: 06.10.2012 Сообщений: 140
	27.07.2013, 00:03	54
	Сообщение от kamre Не по теме: Почему тогда за C++ взялся сразу? Может стоило на .NET/Java посмотреть, там junior-ом должно быть проще устроиться. я тоже сейчас изучаю с++, может мне забить на него и посмотреть на Java/C# ? 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	27.07.2013, 00:07	55
	Сообщение от nonedark2008 Хороший программист легко напишет оптимальный алгоритм красиво и понятно. Я, например, считаю, что оптимальность очень важна. Одно дело когда ты пишешь поиск подстроки прямым поиском в несколько строк, а другое - когда тот же поиск, но алгоритмом Боуера и Мура. Второе выглядит многим красивее... Мне кажется, что красота кода, его понятность и его оптимальность - понятия схожи, и одно без другого как-то и не встречаются. Я вероятно соглашусь вцелом, но не соглашусь в частностях. Хороший программист знает что и где выбрать. Где-то удобнее простой поиск подстроки, где-то удобнее алгоритмом Боуера и Мура, где-то удобнее использовать регулярные выражения, а где-то этот поиск вообще не нужен. Хороший программист легко напишет оптимальный алгоритм красиво и понятно. Ну и да, в большинстве случаев, хороший программист не будет изобретать велосипед, а воспользуется проверенными средствами (читай библиотеками). 0

@nonedark2008 1394 / 1023 / 325 Регистрация: 28.07.2012 Сообщений: 2,813
	27.07.2013, 00:11	56
	Сообщение от ovner я тоже сейчас изучаю с++, может мне забить на него и посмотреть на Java/C# ? Лучше хорошо допилить один язык, остальные пойдут намного проще. Вначале я неплохо в школе выучил C, после него C++ пошел легко. Далее Java - один хрен что и C++, а C# - считай содран с Явы. А дальше совсем все просто пошло: Python, Фортран, Хаскел, Лисп, Асма. За пару дней запоминаешь синтаксис языка и его особенности и уже можно писать что-либо осмысленное. Добавлено через 1 минуту Сообщение от ForEveR Хороший программист знает что и где выбрать. Где-то удобнее простой поиск подстроки, где-то удобнее алгоритмом Боуера и Мура, где-то удобнее использовать регулярные выражения, а где-то этот поиск вообще не нужен. Это как раз и называется поиском оптимального решения для конкретной задачи. 1

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	27.07.2013, 00:14	57
	nonedark2008, Сообщение от ForEveR Одно дело когда ты пишешь поиск подстроки прямым поиском в несколько строк, а другое - когда тот же поиск, но алгоритмом Боуера и Мура. Второе выглядит многим красивее... Кажется вы немножко себе противоречите. Впрочем, пустое. В целом, вы сказали все верно. 0

@nonedark2008
	27.07.2013, 00:17 #58
	Не по теме: Сообщение от ForEveR Кажется вы немножко себе противоречите. Есть немного =) 0

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	27.07.2013, 08:03	59
	Сообщение от nonedark2008 Ну дык нужно же где-то хранить битовый результат, хотя все на усмотрение программиста. судя по прототипу функции void numberAsBinary(char _result, unsigned int _number); результат сразу помещать в строку result, дополнительные массивы вряд ли приветствуются. Сообщение от nonedark2008* Для этой сортировки понадобятся два временных массива, что ИМХО не хорошо. откуда там два временных массива? там только массив count из 11 элементов всего. а вообще стоило пару сортировок прислать с комментариями. Сообщение от TimeToWork Задача 4. Стандартная олимпиадная задачка, решается в 4 строчки. стандартная детская задачка, решается в две строчки кода. При оценке ее сложности можно O-большим не пользоваться, чтобы подчеркнуть, что сложность алгоритма W(N) < N. 0