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

@oPean · Регистрация: 30.09.2015

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

Всем привет. Зарегистрировался на одном из многочисленных онлайн курсов по С++. Не могу "сдать" проверяющему сервису две задачи уже достаточно долго.
Условие первой:

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

Напишите функцию, которая принимает на вход целочисленную матрицу 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 · 17.10.2015, 17:01

Всем здравия!
Тоже не получается решить эту задачу (последнюю). Проваливается на третьем тесте. А что там за тесты, известно только авторам.

@oPean · 17.10.2015, 19:21 **[ТС]**

vodaspbru, допиши все недостающие методы из шаблоны, скомпилируй и быстро поймёшь.

А вот дальше какая то херня будет, мечусь между 3 задачами, ничерта не выходит.

@vodaspbru · 18.10.2015, 05:24

Хм... Методом тыка собрал и скомпилировал.
И даже тест прошел.

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 · 19.10.2015, 00:34 **[ТС]**

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

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

В этой задаче вам требуется реализовать оператор [] для уже известного вам класса 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 · 19.10.2015, 06:06

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

Совершенно не понимаю, как это реализовать. Подкиньте идею, пожалуйста.

Делаешь один вспомогательный класс. Его оператор [] возвращает порезанную строку. А оператор [] основного класса конструктит объект этого вспомогательного класс и засовывает ему указатель на строку и номер символа начиная с которого резать, и его же и возвращает.

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

Не по теме:

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

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

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

@oPean · 19.10.2015, 18:56 **[ТС]**

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 · 19.10.2015, 20:37

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

SharedPtr

Они unsafe не пользуй их. Только и ведут что к утечкам памяти.
А если по входу в Reset stored->count не равен 1?
Да еще stored->count вроде как функция а не свойство, как ты адрес функции декриментируешь и компилятор при этом не ругается? Норамльный компилятор должен трехэтажным матом обложить по этому поводу, и даже по поводу того чего ему делать - адрес брать или вызывать.

@oPean · 19.10.2015, 20:52 **[ТС]**

Fulcrum_013, да это задание такое на Stepic'е, реализовать SharedPtr определённым образом. За последние три дня убил столько времени(безрезультатно), что хочется уже бросить, тем более что этот материал всё равно в обозримом будущем не пригодится.

А если по входу в Reset stored->count не равен 1?

Ммм...я так понимаю, отдельно должно идти ?

C++
1
 if(stored->count>1) --stored->count;

На такой декримент VS2013 не ругается, да и в main вроде манипуляции с объектами производятся. Но не буду утверждать, что это правильно, в голове каша.

@Fulcrum_013 · 19.10.2015, 21:02

Ну вообще то вот так должно быть по идее
if(stored->count()>1)
а то адрес функции он всегда больше 1
А не, там еще вложенная структура с таким полем... ну и намутли.. черт ногу сломит...

@Lenchik854 · 20.10.2015, 21:34

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

Делаешь один вспомогательный класс. Его оператор [] возвращает порезанную строку. А оператор [] основного класса конструктит объект этого вспомогательного класс и засовывает ему указатель на строку и номер символа начиная с которого резать, и его же и возвращает.

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

Не по теме:

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

примерно вот так?:

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 · 20.10.2015, 21:45

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

Ругается на this. Как "засунуть" ему указатель на эту строку?

Ну засунул ты ему его правильно return SubString(this,i);

String operator[](int j) const
{
return str_str[j];
}
а вот это что то непонятное. Тут надо вырезать из str_str символы с sub_i по j и вернуть эту вырезанную строку (новый экземпляр чтобы не запортить тот который есть нулем в [j+1]).

@Lenchik854 · 20.10.2015, 23:10

Как-то так?:

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 · 20.10.2015, 23:19

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

А что делать с памятью.Утечка будет. Как удалить созданную строку, мы ведь её возвращаем?

а кроме stl сейчас вообще ничему не учат? это к тому что не temp[j+1] = "0"; а temp[k] = 0; и не sizeof(temp) которая равна 4 или 8 в зависимости от платформы, а j-i и вообще вместо этого лисапета c циклом существует strcpn.

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

Как удалить созданную строку, мы ведь её возвращаем?

Это ответственность вызывающего.

tekhnolife · 21.10.2015, 16:00

Lenchik854, возможно поможет решение отсюда

@Lenchik854 · 21.10.2015, 23:21

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

Lenchik854, возможно поможет решение отсюда

Да, спасибо большое, разобралась. Очень помогло Ваше решение )))

Новые блоги и статьи Все статьи Все блоги /
Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .	Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .
Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .	Где деньги лежат kumehtar 02.07.2026 Это - японская подводная лодка I-52 (тип C2, кодовое имя Momi) вышла из Японии в марте 1944 года с миссией в оккупированную немцами Францию (Лорьян). Это была одна из «Янаги»-миссий по обмену. . .

@vodaspbru 0 / 0 / 0 Регистрация: 17.10.2015 Сообщений: 5
	17.10.2015, 17:01
	Всем здравия! Тоже не получается решить эту задачу (последнюю). Проваливается на третьем тесте. А что там за тесты, известно только авторам. 0

@oPean 1 / 1 / 0 Регистрация: 30.09.2015 Сообщений: 72
	17.10.2015, 19:21 [ТС]
	vodaspbru, допиши все недостающие методы из шаблоны, скомпилируй и быстро поймёшь. А вот дальше какая то херня будет, мечусь между 3 задачами, ничерта не выходит. 0

@Fulcrum_013 2083 / 1575 / 169 Регистрация: 14.12.2014 Сообщений: 13,614
	19.10.2015, 21:02
	Ну вообще то вот так должно быть по идее if(stored->count()>1) а то адрес функции он всегда больше 1 А не, там еще вложенная структура с таким полем... ну и намутли.. черт ногу сломит... 0

tekhnolife 0 / 0 / 0 Регистрация: 08.10.2015 Сообщений: 3
	21.10.2015, 16:00
	Lenchik854, возможно поможет решение отсюда 0