Форум программистов, компьютерный форум CyberForum.ru

Не могу отловить крайние случаи - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.94
oPean
0 / 0 / 0
Регистрация: 30.09.2015
Сообщений: 44
30.09.2015, 19:36     Не могу отловить крайние случаи #1
Всем привет. Зарегистрировался на одном из многочисленных онлайн курсов по С++. Не могу "сдать" проверяющему сервису две задачи уже достаточно долго.
Условие первой:
Кликните здесь для просмотра всего текста
Напишите функцию, которая принимает на вход целочисленную матрицу M (другими словами, просто двумерный целочисленный массив) размера rows×cols, и возвращает транспонированную матрицу MT (тоже двумерный целочисленный массив) размера cols×rows. Если в M на пересечении i-ой строки и j-ого столбца стояло число x, то на пересечении j-ой строки и i-ого столбца в матрице MT тоже будет стоять число x, или другими словами MT[j][i]=M[i][j].

Обратите внимание, что вам неизвестно, каким именно способом выделялась память для массива M. Выделять память под массив MT можете любым удобным вам способом. Изменять исходную матрицу нельзя.

Требования к реализации: при выполнении этого задания вы можете определять любые вспомогательные функции. Вводить или выводить что-либо не нужно. Реализовывать функцию main не нужно.

Мой код:
C++
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdlib>
 
using namespace std;
int **m = 0;
int **mt = 0;
int rows =3, cols = 5;
int main() {
    
    int ** transpose(const int * const * m, unsigned rows, unsigned cols);
    
    transpose(m, rows, cols);
    for (int i = 0; i != cols; ++i) {
        for (int j = 0; j != rows; ++j)
            cout << mt[i][j] << " ";
        cout << endl;
    }
    void free_array2d(int **m, int rows, int cols);
    return 0;
}
 
 
int ** transpose(const int * const * m, unsigned rows, unsigned cols){
    
    int ** create_array2d(int rows, int cols);
    m=create_array2d(rows, cols);
    mt = create_array2d(cols, rows);
    int count = 0;
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j)
            cout << m[i][j] << " ";
        cout << endl;
    }
    for (int i = 0; i != cols; ++i) {
        for (int j = 0; j != rows; ++j)
            mt[i][j] = m[j][i];
    }
    
    return mt;
}
 
 
int ** create_array2d(int rows, int cols) {
 
        int ** m = new int*[rows];
        m[0] = new int[rows*cols];
        for (size_t i = 1; i != rows; i++)
            m[i] = m[i - 1] + cols;
        int count = 0;
        for (int i = 0; i != rows; ++i) {
            for (int j = 0; j != cols; ++j){
                m[i][j] = count;
                count++;
            }
        }
 
    
    return m;
}
Условие второй:
Кликните здесь для просмотра всего текста
Напишите функцию поиска первого вхождения шаблона в текст. В качестве первого параметра функция принимает текст (C-style строка), в которой нужно искать шаблон. В качестве второго параметра строку-шаблон (C-style строка), которую нужно найти. Функция возвращает позицию первого вхождения строки-шаблона, если он присутствует в строке (помните, что в C++ принято считать с 0), и -1, если шаблона в тексте нет.

Учтите, что пустой шаблон (строка длины 0) можно найти в любом месте текста.

Требования к реализации: при выполнении данного задания вы можете определять любые вспомогательные функции, если они вам нужны. Вводить или выводить что-либо не нужно. Реализовывать функцию main не нужно.


Мое решение(возможно довольно кривое, т.к. давно пытаюсь сдать, кучу костылей натыкал):
C++
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
using namespace std;
 
const char text[] = "";
const char pattern[] = "";
unsigned Strlen(const char *str);
int len_text = Strlen(text);
int len_pattern = Strlen(pattern);
int Strstr(const char *text, const char *pattern);
 
int main() {
    cout << Strstr(text, pattern);
    return 0;
}
 
int Strstr(const char *text, const char *pattern) {
    
    if (len_text < len_pattern) return -1;
    if ((len_text == 0) && (len_pattern == 0)) return 0;
    if ((len_text == 0) && (len_pattern != 0)) return -1;
    if ((len_text != 0) && (len_pattern == 0)) return 0;
    int j = 0;
    int i = 0;
    if ((len_text == 1) && (len_pattern == 1)) {
        if (*text == *pattern) { return 0; }
        else { return -1; }
    }
    else {
        for (i = 0; i < len_text; i++) {
            if (text[i] == pattern[j])
            {
                j++;
            }
            else
            {
                if (j > 0) i -= j;
                j = 0;  
            }
 
            if (j == len_pattern)
            {
                return i - len_pattern + 1;
            }
        }
    }
    if (i == len_text - len_pattern + 1) return -1;
 
    return -1;
}
 
unsigned Strlen(const char *str) {
    int count1 = 0;
    while (*str != 0) {
        str++;
        count1++;
 
    }
    return count1;
}
В идеале, подскажите как их исправить, ибо я уже задолбался с ними.
Но если просто укажите, на каких входных данных проги лажают, тоже хорошо будет.
P.S. само собой, функцию main на проверку не отправляю. При проверке обе программы компилируются, но на одном из тестов выдают неверный ответ.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
vodaspbru
0 / 0 / 0
Регистрация: 17.10.2015
Сообщений: 3
17.10.2015, 17:01     Не могу отловить крайние случаи #21
Всем здравия!
Тоже не получается решить эту задачу (последнюю). Проваливается на третьем тесте. А что там за тесты, известно только авторам.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
oPean
0 / 0 / 0
Регистрация: 30.09.2015
Сообщений: 44
17.10.2015, 19:21  [ТС]     Не могу отловить крайние случаи #22
vodaspbru, допиши все недостающие методы из шаблоны, скомпилируй и быстро поймёшь.

А вот дальше какая то херня будет, мечусь между 3 задачами, ничерта не выходит.
vodaspbru
0 / 0 / 0
Регистрация: 17.10.2015
Сообщений: 3
18.10.2015, 05:24     Не могу отловить крайние случаи #23
Хм... Методом тыка собрал и скомпилировал.
И даже тест прошел.
C++
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <limits.h>
 
struct Number;
struct BinaryOperation;
 
struct Visitor {
    virtual void visitNumber(Number const * number) = 0;
    virtual void visitBinaryOperation(BinaryOperation const * operation) = 0;
    virtual ~Visitor() { }
};
 
struct Expression
{
    virtual double evaluate() const = 0;
    virtual void visit(Visitor * vistitor) const = 0;
    virtual ~Expression() {}
};
 
struct Number : Expression
{
    Number(double value) { this->value=value; }
    double evaluate() const{ return value; }
 
    double get_value() const { return value; }
 
    void visit(Visitor * visitor) const { visitor->visitNumber(this); }
 
private:
    double value;
};
 
struct BinaryOperation : Expression
{
    enum {
            PLUS = '+',
            MINUS = '-',
            DIV = '/',
            MUL = '*'
        };
    BinaryOperation(Expression const * left, char op, Expression const * right) : left(left), op(op), right(right)
    {  }
    ~BinaryOperation() {
            delete left;
            delete right;
        }
 
    double evaluate() const
{
        double left = this->left->evaluate();
        double right = this->right->evaluate();
        switch (op)
        {
        case PLUS: return left + right;
        case MINUS: return left - right;
        case DIV: return left / right;
        case MUL: return left * right;
        }
        return 0.0;
    }
 
    Expression const * get_left() const { return left; }
    Expression const * get_right() const { return right; }
    char get_op() const { return op; }
 
    void visit(Visitor * visitor) const { visitor->visitBinaryOperation(this); }
 
private:
    Expression const * left;
    Expression const * right;
    char op;
};
 
struct PrintVisitor : Visitor {
    void visitNumber(Number const * number)
    {
        std::cout << number->get_value() << " ";
    }
 
    void visitBinaryOperation(BinaryOperation const * bop)
    {
        std::cout << '(';
        bop->get_left()->visit(this);
        std::cout << bop->get_op() << " ";
        bop->get_right()->visit(this);
        std::cout << ')';
    }
};
 
int main() {
    Expression * l = new Number(7);
      Expression * r = new Number(2);
      BinaryOperation evo = BinaryOperation(l, '/', r);
      Visitor *v = new PrintVisitor;
      evo.visit(v);
 
  return 0;
}
oPean
0 / 0 / 0
Регистрация: 30.09.2015
Сообщений: 44
19.10.2015, 00:34  [ТС]     Не могу отловить крайние случаи #24
Собственно, очередной "затык". Совершенно не понимаю, как это реализовать. Подкиньте идею, пожалуйста.
Кликните здесь для просмотра всего текста
В этой задаче вам требуется реализовать оператор [] для уже известного вам класса String. Однако на этот раз оператор должен реализовывать нестандартное поведение: оператор нужно реализовать таким образом, чтобы для объекта str класса String можно было писать str[i][j] и это выражение возвращало подстроку начинающуюся в позиции i (считая с 0) и заканчивающуюся в позиции j (не включая).

Например:

C++
1
2
3
String const hello("hello");
String const hell = hello[0][4]; // теперь в hell хранится подстрока "hell"
String const ell  = hello[1][4]; // теперь в ell хранится подстрока "ell"
Обратите внимание, что i может равняться j, в этом случае результатом должна быть пустая строка. Гарантируется, что i никогда не будет больше j, и они не будут выходить за пределы длины строки.
Требования к реализации: При выполнении задания вы можете создавать любые методы/конструкторы или даже структуры/классы, если они вам нужны. Реализовывать методы, которые уже объявленны в шаблоне, не нужно они уже реализованы. При выполнении задания не вводите и не выводите что-либо. Реализовывать функцию main не нужно.


Добавлено через 4 часа 9 минут
И ещё одна проблема. Где тут утечка памяти? Комментил всё, кроме конструктора, всё равно выдает сообщение об утечке...не понимаю, что не так. Expression заменил на int, чтобы уж совсем упростить и исключить проблемы с ним. Собственно, смотреть можно начиная с класса SharedPtr.
C++
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <cstddef>
#include <iostream>
 
#include <vld.h>
 
struct Expression
{
    virtual double evaluate() const = 0;
    virtual ~Expression() {}
 
};
 
struct Number : Expression
{
    Number(double value)
    : value(value)
    {}
    ~Number() { }
    double evaluate() const {
        return value;
    }
private:
    double value;
};
 
struct BinaryOperation : Expression
{
 
    BinaryOperation(Expression const * left, char op, Expression const * right)
    : left(left), op(op), right(right)
    { }
 
    double evaluate() const {
 
        if (op == '+') return left->evaluate() + right->evaluate();
        if (op == '-') return left->evaluate() - right->evaluate();
        if (op == '*') return left->evaluate() * right->evaluate();
        if (op == '/') return left->evaluate() / right->evaluate();
    }
    ~BinaryOperation() {
        delete left;
        delete right;
    }
private:
    Expression const * left;
    Expression const * right;
    char op;
};
 
struct SharedPtr
{
    // реализуйте следующие методы
    //
    std::size_t count() const {
        if (stored) {
            return stored->count;
        }
        return 0;
    }
    /*Expression* get() const {
    return stored->ptr_;
    }*/
 
    //void reset(Expression *ptr = 0) {
    //  this->~SharedPtr();
    //  new (this) SharedPtr(ptr);
    //}
 
    /*Expression& operator*() const { return *get(); }
    Expression* operator->() const { return stored->ptr_; }*/
 
    //SharedPtr() : stored(0) {}
 
    explicit SharedPtr(int * const ptr) : stored(new storage(ptr)) {}
 
    //SharedPtr(SharedPtr const& other) : stored(other.stored) {
    //  increment();
    //}
 
    //SharedPtr & operator =(SharedPtr const& other) {
    //  if (stored != other.stored) {
    //      decrement();
    //      stored = other.stored;
    //      increment();
    //  }
    //  return *this;
    //}
 
    ~SharedPtr() {
        decrement();
    }
private:
    /*void increment() {
    if (stored) {
    ++stored->count;
    }
    }*/
 
    void decrement() {
        if (stored && (--stored->count == 0)) {
            delete stored->ptr_;
            delete stored;
            stored = 0;
        }
    }
 
    struct storage {
 
        explicit storage(int * const ptr) : ptr_(ptr), count(1) {}
        
        int * ptr_;
        std::size_t    count;
    };
 
    storage * stored;
 
};
 
int main() {
    int a = 10;
    int * b = &a;
    SharedPtr a1(b);
    std::cout << a1.count() << std::endl;
    if (_CrtDumpMemoryLeaks())
        std::cout << "memory leak is detected" << std::endl;
    else
        std::cout << "no memory leaks" << std::endl;
    return 0;
}
Fulcrum_013
 Аватар для Fulcrum_013
393 / 566 / 60
Регистрация: 14.12.2014
Сообщений: 4,769
Завершенные тесты: 2
19.10.2015, 06:06     Не могу отловить крайние случаи #25
Цитата Сообщение от oPean Посмотреть сообщение
Совершенно не понимаю, как это реализовать. Подкиньте идею, пожалуйста.
Делаешь один вспомогательный класс. Его оператор [] возвращает порезанную строку. А оператор [] основного класса конструктит объект этого вспомогательного класс и засовывает ему указатель на строку и номер символа начиная с которого резать, и его же и возвращает.

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

Не по теме:

Цитата Сообщение от UltraPenguin Посмотреть сообщение
Трюки с define вообще отличаются простотой и извращенностью. Обозначит какой-нибудь обиженный сотрудник где-нибудь в дебрях кода
Код C++Выделить код
1
#define true false
или
Код C++Выделить код
1
#define int64_t int32_t
, и устроит всем хардпати по отладке.
Это хардпати? Не смешите мою подпись

oPean
0 / 0 / 0
Регистрация: 30.09.2015
Сообщений: 44
19.10.2015, 18:56  [ТС]     Не могу отловить крайние случаи #26
Fulcrum_013, спасибо, вроде более-менее понятно, сейчас буду пробовать.

Может ещё подскажешь, что не так с памятью? Я покопался, вроде утекает из reset, переписал вот на такую:
C++
1
2
3
4
5
6
7
8
    void reset(int *ptr = 0) {
        if (stored && (--stored->count == 0)) {
            delete stored->ptr_;
            delete stored;
            stored = 0;
        }
        storage stored(ptr);
    }
Сам повызывал её, пишет что всё ок. Но задание не принимается, по причине утечки памяти.

Описание функции из задачи:
reset — метод заставляет SharedPtr освободить старый указатель, а вместо него захватить новый (например, чтобы переиспользовать SharedPtr), но освобождает память, только если счетчик ссылок после декремента равен 0.
Fulcrum_013
 Аватар для Fulcrum_013
393 / 566 / 60
Регистрация: 14.12.2014
Сообщений: 4,769
Завершенные тесты: 2
19.10.2015, 20:37     Не могу отловить крайние случаи #27
Цитата Сообщение от oPean Посмотреть сообщение
SharedPtr
Они unsafe не пользуй их. Только и ведут что к утечкам памяти.
А если по входу в Reset stored->count не равен 1?
Да еще stored->count вроде как функция а не свойство, как ты адрес функции декриментируешь и компилятор при этом не ругается? Норамльный компилятор должен трехэтажным матом обложить по этому поводу, и даже по поводу того чего ему делать - адрес брать или вызывать.
oPean
0 / 0 / 0
Регистрация: 30.09.2015
Сообщений: 44
19.10.2015, 20:52  [ТС]     Не могу отловить крайние случаи #28
Fulcrum_013, да это задание такое на Stepic'е, реализовать SharedPtr определённым образом. За последние три дня убил столько времени(безрезультатно), что хочется уже бросить, тем более что этот материал всё равно в обозримом будущем не пригодится.

А если по входу в Reset stored->count не равен 1?
Ммм...я так понимаю, отдельно должно идти ?
C++
1
 if(stored->count>1) --stored->count;
На такой декримент VS2013 не ругается, да и в main вроде манипуляции с объектами производятся. Но не буду утверждать, что это правильно, в голове каша.
Fulcrum_013
 Аватар для Fulcrum_013
393 / 566 / 60
Регистрация: 14.12.2014
Сообщений: 4,769
Завершенные тесты: 2
19.10.2015, 21:02     Не могу отловить крайние случаи #29
Ну вообще то вот так должно быть по идее
if(stored->count()>1)
а то адрес функции он всегда больше 1
А не, там еще вложенная структура с таким полем... ну и намутли.. черт ногу сломит...
Lenchik854
0 / 0 / 0
Регистрация: 10.12.2013
Сообщений: 13
20.10.2015, 21:34     Не могу отловить крайние случаи #30
Цитата Сообщение от Fulcrum_013 Посмотреть сообщение
Делаешь один вспомогательный класс. Его оператор [] возвращает порезанную строку. А оператор [] основного класса конструктит объект этого вспомогательного класс и засовывает ему указатель на строку и номер символа начиная с которого резать, и его же и возвращает.

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

Не по теме:


Это хардпати? Не смешите мою подпись

примерно вот так?:
C++
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
29
30
31
32
33
34
35
36
37
38
39
40
struct String {
    String(const char *str = "");
    String(size_t n, char c);
    ~String();
 
    String(const String &other);
    String &operator=(const String &other);
 
    void append(const String &other);
 
 
 
    struct SubString{
 
        String* str_str;
        int sub_i;
 
        SubString(String* str, int i)
            :str_str(str), sub_i(i)
        {   
            
        }
 
        String operator[](int j) const
        {
           return str_str[j];
        }
    
    };
 
    SubString operator[](int i)
    {
       return SubString(this,i);
    }
 
 
 
    size_t size;
    char *str;
};
Ругается на this. Как "засунуть" ему указатель на эту строку?
Fulcrum_013
 Аватар для Fulcrum_013
393 / 566 / 60
Регистрация: 14.12.2014
Сообщений: 4,769
Завершенные тесты: 2
20.10.2015, 21:45     Не могу отловить крайние случаи #31
Цитата Сообщение от Lenchik854 Посмотреть сообщение
Ругается на this. Как "засунуть" ему указатель на эту строку?
Ну засунул ты ему его правильно return SubString(this,i);

String operator[](int j) const
{
return str_str[j];
}
а вот это что то непонятное. Тут надо вырезать из str_str символы с sub_i по j и вернуть эту вырезанную строку (новый экземпляр чтобы не запортить тот который есть нулем в [j+1]).
Lenchik854
0 / 0 / 0
Регистрация: 10.12.2013
Сообщений: 13
20.10.2015, 23:10     Не могу отловить крайние случаи #32
Как-то так?:
C++
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
struct String {
    String(const char *str = "");
    String(size_t n, char c);
    ~String();
 
    String(const String &other);
    String &operator=(const String &other);
 
    void append(const String &other);
    
    struct SubString{
 
        String* str_str;
        int sub_i;
 
        SubString(String* str, int i)
            :str_str(str), sub_i(i)
        {   
            
        }
 
        ~SubString();
 
        String operator[](int j) const
        {
           String* temp = new String[j - sub_i+1];
           for (int k=0; k < sizeof(temp); ++k)
           {
              temp[k] = str_str[sub_i+k];
           }
           temp[j+1] = "0";
           return *temp;
        }
 
    };
 
    SubString operator[](int i)
    {
       return SubString(this,i);
    }
 
    size_t size;
    char *str;
};
А что делать с памятью.Утечка будет. Как удалить созданную строку, мы ведь её возвращаем?
Fulcrum_013
 Аватар для Fulcrum_013
393 / 566 / 60
Регистрация: 14.12.2014
Сообщений: 4,769
Завершенные тесты: 2
20.10.2015, 23:19     Не могу отловить крайние случаи #33
Цитата Сообщение от Lenchik854 Посмотреть сообщение
А что делать с памятью.Утечка будет. Как удалить созданную строку, мы ведь её возвращаем?
а кроме stl сейчас вообще ничему не учат? это к тому что не temp[j+1] = "0"; а temp[k] = 0; и не sizeof(temp) которая равна 4 или 8 в зависимости от платформы, а j-i и вообще вместо этого лисапета c циклом существует strcpn.
Цитата Сообщение от Lenchik854 Посмотреть сообщение
Как удалить созданную строку, мы ведь её возвращаем?
Это ответственность вызывающего.
tekhnolife
0 / 0 / 0
Регистрация: 08.10.2015
Сообщений: 3
21.10.2015, 16:00     Не могу отловить крайние случаи #34
Lenchik854, возможно поможет решение отсюда
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.10.2015, 23:21     Не могу отловить крайние случаи
Еще ссылки по теме:

Отловить деление на ноль C++
Составить программу вычисления корня. Учесть случаи, когда корень не может быть вычислен C++
Поменять местами крайние элементы стека C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Lenchik854
0 / 0 / 0
Регистрация: 10.12.2013
Сообщений: 13
21.10.2015, 23:21     Не могу отловить крайние случаи #35
Цитата Сообщение от tekhnolife Посмотреть сообщение
Lenchik854, возможно поможет решение отсюда
Да, спасибо большое, разобралась. Очень помогло Ваше решение )))
Yandex
Объявления
21.10.2015, 23:21     Не могу отловить крайние случаи
Ответ Создать тему
Опции темы

Текущее время: 17:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru