Версия для печати темы

Автор: kwisp 10.9.2010, 14:03

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

П.С.
столкнулся с тем что интересных и полезных задач и упражнений на закрепление знаний скудно мало....
вот сейчас ищу полезные задачи по stl и пока безуспешно....

Автор: Алексей1153 10.9.2010, 14:17

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

Собственно, реализовать наибольшую скорость поиска )

Автор: kwisp 10.9.2010, 14:38

Цитата(Алексей1153 @ 10.9.2010, 15:17)

Автор: Алексей1153 10.9.2010, 14:53

kwisp, не студиЯ , а студиИ .

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

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

вот я о чём только что подумал (точно!) - можно же переопределить аллокатор у вектора, а потом выделить размер в точности как у исходного буфера. Тогда поиском можно из STL воспользоваться. Только я никогда не переопределял, надо узнать, как это делается ))

Автор: kwisp 10.9.2010, 14:59

Цитата(Алексей1153 @ 10.9.2010, 15:44)

Цитата(Алексей1153 @ 10.9.2010, 15:44)

Цитата(Алексей1153 @ 10.9.2010, 15:44)

Автор: igor_bogomolov 10.9.2010, 15:15

Слоты(slots) в отличие от сигналов(signals) могут быть ещё:
 virtual 
 public 
 protected 
 private

#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;
}

Автор: kwisp 10.9.2010, 15:25

Алексей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 10.9.2010, 19:15

kwisp,

о, точно ) Спасибо

Автор: kwisp 19.10.2010, 16:48

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

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

Автор: AD 19.10.2010, 18:00

Цитата(kwisp @ 19.10.2010, 17:48)

Автор: Kagami 19.10.2010, 18:41

Не надо изобретать велосипед. Все это уже давно изучается в статистике и называется "выбросами". Сходу нашел вот http://forum.disser.ru/index.php?showtopic=2434 тему.

Автор: kwisp 19.10.2010, 18:51

Kagami,
не понял при чем тут

Цитата(Kagami @ 19.10.2010, 19:41)

Автор: AD 19.10.2010, 19:14

Цитата(Kagami @ 19.10.2010, 19:41)

Автор: Алексей1153 19.10.2010, 19:21

Цитата(kwisp @ 19.10.2010, 19:48)

Автор: kwisp 19.10.2010, 19:27

Цитата(Алексей1153 @ 19.10.2010, 20:21)

Автор: Алексей1153 19.10.2010, 19:44

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 19.10.2010, 19:48

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

Вот это действие удивило:

  vec[vec.size()-1]=vec[vec.size()-1];

Автор: Алексей1153 19.10.2010, 20:20

AD, я исправил - там size()-2

Цитата(AD @ 19.10.2010, 22:48)

for(DWORD dwd=1; dwd<dwdMax; dwd++)
{
  try
  {
       k=a/b;
  }
  catch(...)
  {
      k=бесконечности;
  }
}

Автор: AD 20.10.2010, 8:56

Так. Разобрал код. Есть вопросы.
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 20.10.2010, 8:58

Видно что задача требует уточнения.
Нужно удалить из интервала значения которые не вписываются в общую картину на 2-3 порядка как в большую так и в меньшую сторону.

Вопрос к Алексей1153 : Как поведет себя предложенный метод если к примеру первые 2 значения числа больше 1000 и 2000, а остальные 1 2 3 4 5. - какие значения удалятся из интервала?

Автор: AD 20.10.2010, 9:11

То есть самая первая подзадача - это найти критерий определения шума. Ну то есть, тот предел, по которому можно будет ориентироваться является ли число в последовательности шумом или нет!

Автор: Алексей1153 20.10.2010, 9:35

Цитата(AD @ 20.10.2010, 11:56)

Цитата(AD @ 20.10.2010, 11:56)

Цитата(kwisp @ 20.10.2010, 11:58)

__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  - удаляем

...

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
       |
    шаг назад. Продолжаем отсюда

Автор: kwisp 20.10.2010, 10:04

Цитата(Алексей1153 @ 20.10.2010, 10:35)

Автор: Алексей1153 20.10.2010, 10:24

kwisp, а как ты хотел Чтоб без отладки оно всё взяло и заработало ? Представь себе меандр с амплитудой 2000 у.е. По какому критерию будешь отбрасывать значения ? Ноль или амплитудные ?

Автор: kwisp 21.10.2010, 14:38

вот моя попытка.
к сожалению определить полностью автоматически лишние значения для меня оказалось очень сложно. Все же нужен критерий оценки от пользователя. Понятно что можно расширить и улучшить.
находим мат. ожидание(в данном случае = ср.арифметическому), к примеру, так:
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_

# 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;
}

Автор: Алексей1153 21.10.2010, 17:57

[offtop]
kwisp, кстати, специализацию можно не указывать тут

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

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

std::distance(first,last);
[/offtop]

Автор: kwisp 21.10.2010, 18:12

самому себе для наглядности написал.