Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Полезные задачи, упражнения, тесты по ...
Форум на CrossPlatform.RU > Курилка > Трёп
kwisp
Давайте делиться интересными задачами по программированию, встречающимися, к примеру, на собеседованиях и не только. Тестами и упражнениями по языкам и разделам программирования.

П.С.
столкнулся с тем что интересных и полезных задач и упражнений на закрепление знаний скудно мало....
вот сейчас ищу полезные задачи по stl и пока безуспешно....
Алексей1153
kwisp, вот совсем недавно встретилась простая на первый взгляд задача : в C++ есть функция strstr, которая ищет подстроку в строке. Понадобился аналог для байтовых массивов (существует не везде реализованная функция memmem, но в арсенале C++ студии её не оказалось)

Собственно, реализовать наибольшую скорость поиска )
kwisp
Цитата(Алексей1153 @ 10.9.2010, 15:17) *
о в арсенале C++ студии её не оказалось

не понял. поясни пожалуйста что такое С++ студия?

Алексей1153,
по моему задача элементарная для std::vector<char> и find.
к чему реализовывать что то?
Алексей1153
kwisp, не студиЯ , а студиИ .

Ну реализуй, только char тут ни при чём, тогда уж unsigned char :) Про zero-terminator забудь тоже

а, да, забыл уточнить - искать надо в заданных массивах, это не обязательно вектор. Это может быть, к примеру, маппинг файла. Копировать сначала 500 метровый файл в озу некузяво было бы :)

вот я о чём только что подумал (точно!) - можно же переопределить аллокатор у вектора, а потом выделить размер в точности как у исходного буфера. Тогда поиском можно из STL воспользоваться. Только я никогда не переопределял, надо узнать, как это делается ))
kwisp
Цитата(Алексей1153 @ 10.9.2010, 15:44) *
не студиЯ , а студиИ .

так что это такое?
Цитата(Алексей1153 @ 10.9.2010, 15:44) *
искать надо в заданных массивах, это не обязательно вектор.

по-моему вектор полностью совместим с массивом.
Цитата(Алексей1153 @ 10.9.2010, 15:44) *
Это может бысь маппинг файла, к примеру. Копировать сначала 600 метровый файл в озу некузяво было бы

ну там есть своя технология работы с громадными файлами.
igor_bogomolov
Цитата(kwisp)
Давайте делиться интересными задачами по программированию, встречающимися, к примеру, на собеседованиях и не только. Тестами и упражнениями по языкам и разделам программирования.

Есть такой интересный ресурс http://www.quizful.net/. Иногда прохожу там тестики. Сейчас зашел и с удивлением обнаружил там тест по Qt. Прошел его минуты за три и даже умудрился ответить не правильно. К сожалению не получится дать ссылку на вопрос, поэтому скопирую

Слоты(slots) в отличие от сигналов(signals) могут быть ещё:
virtual
public
protected
private
Угадайте правильный ответ. Удивлю всех - это public :lol:
Цитата(пояснение к ответу на вопрос)
Пояснение: Сигналы всегда public ( public signals: ), также они не могут быть объявлены virtual.

И еще из комментариев к вопросу (видимо от автора теста)
Цитата
Это вопрос на основы Qt - начинающие в хэдэрах не копаются. Вопрос составлен на основе официальной документации и работ сотрудников Qt. Вот Вам, udjin, вопрос: "Если сигналы таки защищённые , то как они передаются между разными объектами? " На мой взгляд, они реализованы как protected для внутренних нужд и , видимо , со своими ухищрениями, а само поведение и характер синалов больше всего соответствует спецификатору public.
Но не смотря на это ресурс не плохой.

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

--------------------------------------------------------------------------------------------

По теме, не знаю будет ли кому интересно, но мне однажды для теста по одной удаленной вакансии дали такой тест
Раскрывающийся текст
#include <string>

using namespace std;


class Base
{
public:
    Base(const string& rs) { base_s = rs;}
    ~Base() {};

    virtual void f() {};
    virtual double f() {};

    int x(int i) {};
    int x(double i) {};

    const string base_s;
    string just_string;
}


class Derived : Base
{
public:
    Derived ()
        : Base( Der_s = "Derived" )
        , s1(base_s)
        , s2(s1)
        , s3(s2)
    {
        v();
        cout << Grand_s;

        buffer = (char*)new char[100];
                
        try {
            string str = new string;
        }
        catch (bad_alloc mem)
        {
            cout << "issue";
            throw;        
        }
    };

    string Der_s;

    virtual int f() {};

    int x(const string&) {};

    virtual Derived operator=(const Derived& der)
    {
        s2 = der.s2;
        s1 = der.s1;
        s3 = der.s3;
        Der_s = der.Der_s;
    }

    string s2;
    string s1;
    string s3;

    virtual v()
    {
           Der_s = "inited";
    }
    
    char* buffer;
};


class Widget: public Base
{
public:
    Widget(int i)
    {
    
    };
    Widget(Window wind) { w = wind };

    ostream& operator<<(const ostream& os)
    {
        os << s;
    };

    operator Window() { return w; }


    Widget& operator+(Widget& rw)  // what is the best - member or standalone operator?
    {
        return *this;
    }

    string s;
    Window w;
}

class Grand : public Derived
{
public:
    Grand()
    {
        for (i=0; i<10; i++);
        {
            auto_list.push_back( new Widget(i) );
        }

        auto_list.sort();

        list<auto_ptr<Widget*>>::iterator it = auto_list.begin();

        while( it < auto_list.end() )
        {
            cout << it;
        }


        widget_vector.reserve(100);
        for (int i=0; i<100; i++)
        {
            widget_vector[i] = new Widget(i);
        }

        loop_all (&widget_vector[0], widget_vector.size());
    }

    void v()
    {
        cout << Grand_s;
    }

    void loop_all(Base* der_array, size_t size)
    {
        for (int i=0; i < size; i++)
        {
            cout << *der_array;
            der_array++;        
        }
    }

    list< auto_ptr<Widget*>> auto_list;

    vector<Widget> widget_vector;

    string Grand_s;
};

int main (int argc, char* argv[])
{
    Derived der;
    der.x(1);
    
    Base* base = (Base*) 0;
    delete base;
    
    base = (Base*) 1;
    delete base;    
    
    return 0;
}
Нужно было найти как можно больше ошибок. Я часа 3-4 на это потратил :)


kwisp
Алексей1153,
с сайта sgi stl
const char S1[] = "Hello, world!";
  const char S2[] = "world";
  const int N1 = sizeof(S1) - 1;
  const int N2 = sizeof(S2) - 1;

  const char* p = search(S1, S1 + N1, S2, S2 + N2);
  printf("Found subsequence \"%s\" at character %d of sequence \"%s\".\n",
         S2, p - S1, S1);
Алексей1153
kwisp,

о, точно ) Спасибо
kwisp
в массиве значений(пусть double) необходимо удалить значений резко(более чем на 2-3 порядка) отличающиеся от соседних.

Если кому интересно предлагайте варианты.
AD
Цитата(kwisp @ 19.10.2010, 17:48) *
в массиве значений(пусть double) необходимо удалить значений резко(более чем на 2-3 порядка) отличающиеся от соседних.

Если кому интересно предлагайте варианты.

Ну блин... Задачка моя! :) Ну или родственная.
Есть множество значений. Предположим массив. Необходимо в этом массиве убрать "шумы" и найти минимальное и максимальное числа. Признак "шума" - число, отличающееся от остальных на порядок, два или более. Зависит значений в массиве. Интересен сам алгоритм. Ну и если будет какая-то общая реализация.
Kagami
Не надо изобретать велосипед. Все это уже давно изучается в статистике и называется "выбросами". Сходу нашел вот такую тему.
kwisp
Kagami,
не понял при чем тут
Цитата(Kagami @ 19.10.2010, 19:41) *
Не надо изобретать велосипед.


по приведенной ссылке кода на Си или С++ не обнаружил.
AD
Цитата(Kagami @ 19.10.2010, 19:41) *
Не надо изобретать велосипед. Все это уже давно изучается в статистике и называется "выбросами". Сходу нашел вот такую тему.

Так в том-то и дело, что теория мне известна. Знаю, что есть такое в статистике. Если бы был приведен формализованный алгоритм (даже если словесный), то вот это было бы здорово.
Алексей1153
Цитата(kwisp @ 19.10.2010, 19:48) *
в массиве значений(пусть double) необходимо удалить значений резко(более чем на 2-3 порядка) отличающиеся от соседних.

Если кому интересно предлагайте варианты.

хочется сразу спросить: а в чём подвох ? :)
kwisp
Цитата(Алексей1153 @ 19.10.2010, 20:21) *
хочется сразу спросить: а в чём подвох ?

ни в чём. кому интересно пишет варианты.
Алексей1153
Раскрывающийся текст
std::vector<double> vec;

//заполняем vec
{
    vec.push_back(0);//для удобства вычислений в дальнейшем

    //затем данные, k значений
    //...

    vec.push_back(0);//для удобства вычислений в дальнейшем

    //в начало и конец кладём болванки,
    if(vec.size()>1)
    {
        vec[0]=vec[1];
        vec[vec.size()-1]=vec[vec.size()-2];
    }

    //теперь вектор содкржит данные, окружённые болванками:
    //
    //N0 (N0 N1 N2 N3 ... Nk-3 Nk-2 Nk-1) Nk-1
}

//набор флагов (для простоты пока один флаг - один байт.
//Но можно будет разместить 8 флагов в байте, уменьшив размер вспомогательного вектора)
std::vector<BYTE> flg(vec.size(),0);

double __acc=1000;
double n_acc=1/__acc;

if(vec.size() && flg.size())
{
    DWORD dwdMax=min(vec.size(),flg.size())-1;
    double k=0;

    for(DWORD dwd=1;dwd<dwdMax;dwd++)
    {
        k=vec[dwd-1]/vec[dwd];
        if(k<0)k=-k;

        if(k>__acc || k<n_acc)
        {
            flg[dwd]=1;
        }
        else
        {
            k=vec[dwd]/vec[dwd+1];
            if(k<0)k=-k;

            if(k>__acc || k<n_acc)
            {
                flg[dwd]=1;
            }
        }
    }

    //flg[1 ... size()-2] содержит флаги элементов, которые надо удалить
}



случай переполнения я не рассматривал

можно также обойтись и без вектора флагов.

А ещё, бы просто заменял нехорошие скачки средним значением от соседних элементов, не удаляя сам элемент
AD
Что за болванки? А можно все-таки кроссплатформенные типы использовать? :) А за вариант спасибо. Правда, не все понятно. Но разобраться можно. Спасибо. Да - если, все же, прокомментируешь свой алгоритм словесно, то буду очень благодарен.

Вот это действие удивило:
  vec[vec.size()-1]=vec[vec.size()-1];
Алексей1153
AD, я исправил - там size()-2

Цитата(AD @ 19.10.2010, 22:48) *
А можно все-таки кроссплатформенные типы использовать?

DWORD и BYTE то ? ) Замени по вкусу (32 и 8-битные)

под болванками имею в виду расширение вектора данных на 1 элемент вправо и влево (добавляю конечные же значения)
это для удобства - не надо будет проверять на выход за край

проверку на переполнение сделать - это отдельная интересная задача :) Дело в том, что сделать вот так не очень хорошо - скажется на скорости
for(DWORD dwd=1; dwd<dwdMax; dwd++)
{
  try
  {
       k=a/b;
  }
  catch(...)
  {
      k=бесконечности;
  }
}

я уже придумал, как можно оптимизировать, будем считать это очередной задачей :)

AD
Так. Разобрал код. Есть вопросы.
1) Я правильно понимаю, что __acc, n_acc - пределы, по которым определяются "шумы"?
2) Сильно ли усложнит задачку следующее добавление, что пределы должны определяться в зависимости от массива/вектора?
Ну то есть для следующей последовательности (0.1, 0.15, 0.13, -0.11, 0.21, 17, -0.37654, -0.321, 0.75, -1.1, 0.54, -0.33334, -13.56, 1.45, -1.96) -13.56 и 17 являются шумами! Понятно, что какой-то предел пользователь обязан задавать, но есть ли возможность как-то его настраивать?
kwisp
Видно что задача требует уточнения.
Нужно удалить из интервала значения которые не вписываются в общую картину на 2-3 порядка как в большую так и в меньшую сторону.

Вопрос к Алексей1153 : Как поведет себя предложенный метод если к примеру первые 2 значения числа больше 1000 и 2000, а остальные 1 2 3 4 5. - какие значения удалятся из интервала?
AD
То есть самая первая подзадача - это найти критерий определения шума. Ну то есть, тот предел, по которому можно будет ориентироваться является ли число в последовательности шумом или нет!
Алексей1153
Цитата(AD @ 20.10.2010, 11:56) *
Я правильно понимаю, что __acc, n_acc - пределы, по которым определяются "шумы"?

да, __acc - это точность (1000 ~ 3 порядка) , а n_acc - величина, обратная к __acc . Это далее для сравнения "больше на 3 порядка" или "меньше на 3 порядка". Поскольку деление - операция "тяжёлая", я вынес её за цикл

Цитата(AD @ 20.10.2010, 11:56) *
Сильно ли усложнит задачку следующее добавление, что пределы должны определяться в зависимости от массива/вектора?

да ни грамма не усложнит :) Надо сделать: перед вычислением пройтись по данным, определить максимум и минимум. В зависимости от них выбрать __acc.

Цитата(kwisp @ 20.10.2010, 11:58) *
Как поведет себя предложенный метод если к примеру первые 2 значения числа больше 1000 и 2000, а остальные 1 2 3 4 5. - какие значения удалятся из интервала?

я код не тестировал. А по алгоритму, щас посмотрим:

__acc=1000;
n_acc=0.001;

исходные данные:
1055, 2055, 1, 2, 3, 4, 5

с болванками:
1055, 1055, 2055, 1, 2, 3, 4, 5, 5
       |                      |
     отсюда начинаем       здесь стоп

1)
число 1055
k1=1055/1055 ==1  , n_acc<k1<__acc> - оставляем
k2=1055/2055 ==0.513  , n_acc<k2<__acc  - оставляем

2)
число 2055
k1=1055/2055 ==0.513  , n_acc<k1<__acc> - оставляем
k2=2055/1 ==2055  , n_acc<__acc<k2  - удаляем

...


ага, дебаг показал уже два косяка:
1) условие проверяется по 2 раза. Сократить до одного раза
2) значение нельзя просто удалять. Его надо заменять на следующее, а затем шагнуть один шаг назад и продолжить оттуда:
1055, 1055, 2055, 1, 2, 3, 4, 5, 5
             |
        сейчас проверяется

1055, 1055, <2055>, 1, 2, 3, 4, 5, 5
             |
        надо удалить (заменить на следующее)

1055, 1055, <1>, 1, 2, 3, 4, 5, 5
             |
           заменили

1055, 1055, <1>, 1, 2, 3, 4, 5, 5
       |
    шаг назад. Продолжаем отсюда


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

а ещё, кстати! я у себя делал сглаживание ступенчатого сигнала, наверное такой метод тоже может подойти, сейчас скрины для примера сделаю, прикреплю

без сглаживания
Нажмите для просмотра прикрепленного файла

одна итерация
Нажмите для просмотра прикрепленного файла

10 итераций
Нажмите для просмотра прикрепленного файла
kwisp
Цитата(Алексей1153 @ 20.10.2010, 10:35) *
Тут можно попробовать заранее просмотреть данные и ориентироваться на некий уровень.

уже интереснее.
а потом еще окажется что нужно учитывать тенденцию роста функции.
Алексей1153
kwisp, а как ты хотел :) Чтоб без отладки оно всё взяло и заработало ? Представь себе меандр с амплитудой 2000 у.е. По какому критерию будешь отбрасывать значения ? Ноль или амплитудные ?
kwisp
вот моя попытка.
к сожалению определить полностью автоматически лишние значения для меня оказалось очень сложно. Все же нужен критерий оценки от пользователя. Понятно что можно расширить и улучшить.
находим мат. ожидание(в данном случае = ср.арифметическому), к примеру, так:
upthrow.h
# ifndef UPTHROW_H_
# define UPTHROW_H_

# include <algorithm>
# include <numeric>

template <class InputIterator, class T>
T expectation(InputIterator first, InputIterator last, T init)
{
return std::accumulate(first,last,init)/std::distance<InputIterator>(first,last);
}

# endif // UPTHROW_H_

или просто с использованием accumulate и distance неважно

пример использования следующий:
main.cpp
Раскрывающийся текст
# include <iostream>
# include <vector>
# include <iterator>
# include <functional>
# include <ext/functional>
# include <fstream>
# include <cmath>
# include "upthrow.h"

int main()
{
std::vector<double> V1;
std::ifstream inputFile("values");
std::copy(std::istream_iterator<double>(inputFile), std::istream_iterator<double>(), std::back_inserter(V1));
std::copy(V1.begin(), V1.end(), std::ostream_iterator<double>(std::cout, " "));// ostreambuf_iterator ???
std::cout << std::endl;

double Mx = expectation<std::vector<double>::iterator, double>(V1.begin(), V1.end(), 0.0 );
  
std::cout << "expectation: " << Mx << '\n';

V1.erase(std::remove_if(V1.begin(),V1.end(), __gnu_cxx::compose1(std::bind2nd(std::greater<double>(),
                         Mx*2.5), __gnu_cxx::compose1(std::ptr_fun(abs),
                               std::bind2nd(std::minus<double>(),
                                 Mx)))), V1.end()); // вот непосредственно и всё удаление выбросов

std::copy(V1.begin(), V1.end(), std::ostream_iterator<double>(std::cout, " "));
std::cout<< std::endl;  
return 0;
}


в данном примере критерий удаления - это разница значения элемента с мат.ожиданием больше чем 2,5 мат.ожидания, взят для примера. на самом деле придется хоть немного знать о хранимых значениях чтобы выбрать критерий правильно для своей задачи.
Алексей1153
[offtop]
kwisp, кстати, специализацию можно не указывать тут

std::distance<InputIterator>(first,last);

- она очевидна. Можно вот так

std::distance(first,last);
[/offtop]
kwisp
самому себе для наглядности написал.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Форум IP.Board © 2001-2024 IPS, Inc.