Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
maksvolf96
3 / 3 / 2
Регистрация: 18.05.2014
Сообщений: 203
#1

Ошибка во время выполнения программы - C++

21.01.2015, 01:11. Просмотров 545. Ответов 6
Метки нет (Все метки)

Здравствуйте, есть задача

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

http://www.cyberforum.ru/cpp-beginners/thread2115748.html
Входные данные
В первой строке входных данных записано два числа N и M (1NM20000 ). Во второй строке записано N упорядоченных по неубыванию целых чисел — элементы первого списка. В третьей строке записаны M целых неотрицательных чисел - элементы второго списка. Все числа в списках - целые 32-битные знаковые.

Выходные данные
Программа должна вывести M строчек. Для каждого числа из второго списка нужно вывести номер его первого и последнего вхождения в первый список. Нумерация начинается с единицы. Если число не входит в первый список, нужно вывести одно число 0.

Примеры
входные данные
10 5
1 1 3 3 5 7 9 18 18 57
57 3 9 1 179
выходные данные
10 10
3 4
7 7
1 2
0

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

вот код

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
#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    int N,K, help;
    cin >> N >> K;
 
    vector <int> m1;
    vector <int> m2;
 
    struct container
    {
        int s;
        int f;
    };
 
    vector <container> contV;
 
    container cnt;
 
    cnt.s=-1;
    cnt.f=-1;
 
    for(int i=0;i<1000000;i++)
        contV.push_back(cnt);
 
 
    for (int i=0;i<N;i++)
    {
        cin >> help;
        m1.push_back(help);
    }
 
    for (int i=0;i<K;i++)
    {
        cin >> help;
        m2.push_back(help);
    }
 
//бинарный поиск для нахождения начального индекса элемента из 2 массива
    for (int v:m2)
    {
        int l=0;
        int r=N-1;
 
        while(l<r)
        {
            int avgI=(l+r)/2;
            if(v>m1[avgI])
               l=avgI+1;
            else
               r=avgI;
        }
        
        if(v==m1[l])
            contV[v].s=l+1;
        else{
            contV[v].s=0;
            contV[v].f=0;
        }
    }
 
//линейных поиск для нахождения конечного индекса элемента из 2 массива
    for (int v:m2)
        for (int i=0;i<m1.size();i++)
        if(v==m1[i])
            contV[v].f=i+1;
 
    for (int v:m2)
        if(contV[v].f!=0)
           cout << contV[v].s << " " <<contV[v].f << endl;
           else cout << 0 << endl;
 
}
Прошу указать косяк или написать нормальный код через цельный бинарник. Спасибо
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.01.2015, 01:11
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Ошибка во время выполнения программы (C++):

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

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

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

Во время выполнения программы результат не выводится. Где ошибка?
Здравствуйте. Помогите, пожалуйста, найти ошибку в коде. Задание звучит так....

Ошибка во время выполнения программы (структуры, массивы структур, указатели на структуру)
Работаю вот с таким кодом: #include&lt;iostream&gt; #include&lt;cstdio&gt;...

6
rikimaru2013
C++ Game Dev
2471 / 1140 / 348
Регистрация: 30.11.2013
Сообщений: 3,709
21.01.2015, 03:36 #2
Цитата Сообщение от maksvolf96 Посмотреть сообщение
Прошу указать косяк
C++
1
2
 for(int i=0;i<1000000;i++)
        contV.push_back(cnt);
Мне просто интересно зачем 8ГБ ОЗУ вам.
0
maksvolf96
3 / 3 / 2
Регистрация: 18.05.2014
Сообщений: 203
21.01.2015, 20:05  [ТС] #3
Что не так? Это такой способ решения, сложность получается O(N*K) + logN , вроде того, по времени проходит, поясните, я не так давно на ++
0
zss
Модератор
Эксперт С++
6952 / 6514 / 4135
Регистрация: 18.12.2011
Сообщений: 17,180
Завершенные тесты: 1
21.01.2015, 20:10 #4
C++
1
2
vector <container> contV(100000);
fill(contV.begin(),100000,cnt);
А в качестве m1 и m2 лучше взять multiset.
Они будут сразу упорядоченны.
Поиск вести функцией find.
Вот пример из Мюссера.
Подробнее не могу - гриппом болею
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
// Finding all anagram groups in a given dictionary of words
#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <iterator>
#include <functional>
using namespace std;
 
typedef multimap<string, string> multimap_1;
typedef multimap_1::value_type PS;
typedef multimap_1::const_iterator PSi;
 
typedef pair<PSi, PSi> PPS;
 
int main() {
  cout << "Anagram group finding program:\n"
    << "finds all anagram groups in a dictionary.\n\n";
 
  cout << "First, enter the name of the file containing\n"
       << "the dictionary: " << flush;
  string dictionary_name; 
  cin >> dictionary_name;
  ifstream ifs(dictionary_name.c_str());
  if (!ifs.is_open()) {
    cout << "Eh? Could not open file named "
         << dictionary_name << endl;
    exit(1);
  }
 
  cout << "\nReading the dictionary ..." << flush;
 
  // Copy words from dictionary file to 
  // a multimap:
  typedef istream_iterator<string> string_input;
  multimap_1 word_pairs;
  for (string_input in(ifs); in != string_input(); ++in) {
    string word = *in;
    sort(word.begin(), word.end());
    word_pairs.insert(PS(word, *in));
  } 
 
  cout << "\nSearching " << word_pairs.size() 
    << " words for anagram groups..." << flush;
 
  // Set up the map from anagram group sizes to lists of
  // groups of that size:
  typedef map<int, list<PPS>, greater<int> > map_1;
  map_1 groups;
 
  // Find all the anagram groups and save their 
  // positions in the groups map:
  cout << "\n\nThe anagram groups are: " << endl;
  PSi j = word_pairs.begin(), finis = word_pairs.end(), k;
  while (true) {
    // Make j point to the next anagram 
    // group, or to the end of the multimap:
    j = adjacent_find(j, finis,
                      not2(word_pairs.value_comp()));
    if (j == finis) break;
    
    k = find_if(j, finis, 
                bind1st(word_pairs.value_comp(), *j));
    multimap_1::size_type n = distance(j, k);
    if (n > 1)
      // Save the positions j and k delimiting the anagram
      // group in the list of groups of size n:
      groups[n].push_back(PPS(j, k)); 
 
    // Prepare to continue search at position k:
    j = k;
  }
 
  // Iterate through the groups map to output the anagram
  // groups in order of decreasing size:
  map_1::const_iterator m;
  for (m = groups.begin(); m != groups.end(); ++m) {
 
    cout << "\nAnagram groups of size "
      << m->first << ":\n";
 
    list<PPS>::const_iterator l;
    for (l = m->second.begin(); 
         l != m->second.end(); ++l) {
      cout << "   ";
      j = l->first;  // Beginning of the anagram group 
      k = l->second; // End of the anagram group
      for (; j != k; ++j)
        cout << j->second << " ";
      cout << endl;
    }
  }
  return 0;
}
0
castaway
Эксперт С++
4926 / 3033 / 453
Регистрация: 10.11.2010
Сообщений: 11,089
Записей в блоге: 10
Завершенные тесты: 1
21.01.2015, 20:11 #5
Цитата Сообщение от maksvolf96 Посмотреть сообщение
Что не так?
Зачем тебе миллион одинаковых объектов? Ты уверен что память под них выделяется успешно?
0
rikimaru2013
C++ Game Dev
2471 / 1140 / 348
Регистрация: 30.11.2013
Сообщений: 3,709
21.01.2015, 20:24 #6
Цитата Сообщение от maksvolf96 Посмотреть сообщение
Это такой способ решения
Если это нужно для решения задачи - решение не правильное. Если это способ тестирования - перебор! Создайте ну 500-1000 объектов - сделайте замер времени вначале перед вызовом метода поиска и после. Узнаете за сколько он отработал - запустите несколько раз. Профит.

P.S. В код не вникал я уверен никто как и я после строки в 8 ГБ ОЗУ.
0
maksvolf96
3 / 3 / 2
Регистрация: 18.05.2014
Сообщений: 203
21.01.2015, 21:04  [ТС] #7
По поводу 8 гб озу, в задаче нет ограничения на элементы массива, поэтому я взял что-то большое. Вообще задачу сдал еще вчера вот таким кодом

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
/*#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    int N,K, help;
    cin >> N >> K;
 
    vector <int> m1;
    vector <int> m2;
 
    struct container
    {
        int s;
        int f;
    };
 
    vector <container> contV;
 
    container cnt;
 
    cnt.s=-1;
    cnt.f=-1;
 
    for(int i=0;i<1000000;i++)
        contV.push_back(cnt);
 
 
    for (int i=0;i<N;i++)
    {
        cin >> help;
        m1.push_back(help);
    }
 
    for (int i=0;i<K;i++)
    {
        cin >> help;
        m2.push_back(help);
    }
 
//бинарный поиск для нахождения начального индекса элемента из 2 массива
    for (int v:m2)
    {
        int l=0;
        int r=N-1;
 
        while(l<r)
        {
            int avgI=(l+r)/2;
            if(v>m1[avgI])
               l=avgI+1;
            else
               r=avgI;
        }
 
        if(v==m1[l])
            contV[v].s=l+1;
        else{
            contV[v].s=0;
            contV[v].f=0;
        }
    }
 
//линейных поиск для нахождения конечного индекса элемента из 2 массива
    for (int v:m2)
        for (int i=0;i<m1.size();i++)
        if(v==m1[i])
            contV[v].f=i+1;
 
    for (int v:m2)
        if(contV[v].f!=0)
           cout << contV[v].s << " " <<contV[v].f << endl;
           else cout << 0 << endl;
 
}
*/
 
 
#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    int N,K, help;
    cin >> N >> K;
 
    vector <int> m1;
    vector <int> m2;
 
    struct container
    {
        int s;
        int f;
    };
 
    vector <container> contV(K);
 
    container cnt;
 
    for (int i=0;i<N;i++)
    {
        cin >> help;
        m1.push_back(help);
    }
 
    for (int i=0;i<K;i++)
    {
        cin >> help;
        m2.push_back(help);
    }
 
//бинарный поиск для нахождения начального индекса элемента из 2 массива
int k1=-1;
    for (int v:m2)
    {
        int l=0;
        int r=N-1;
 
        while(l<r)
        {
            int avgI=(l+r)/2;
            if(v>m1[avgI])
               l=avgI+1;
            else
               r=avgI;
        }
 
        if(v==m1[l]){
                k1++;
            contV[k1].s=l+1;
        }
        else{
            k1++;
            contV[k1].s=0;
            contV[k1].f=0;
        }
    }
 
//линейных поиск для нахождения конечного индекса элемента из 2 массива
int k2=-1;
 
    for (int v:m2)
    {
        int ff=0;
        for (int i=0;i<m1.size();i++)
        {
            if(v==m1[i]){
                    ff=i+1;
            }
        }
           if(ff!=0)
           {
            k2++;
            contV[k2].f=ff;
           }
 
           else{
            k2++;
           }
    }
    for (container st:contV)
        if (st.f!=0)
        cout << st.s << " " << st.f << endl;
        else
            cout << 0 << endl;
 
 
}
0
21.01.2015, 21:04
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.01.2015, 21:04
Привет! Вот еще темы с решениями:

Время выполнения программы
Здравствуйте.Я до сих пор новичок в программировании,сразу скажу,и тонкостей не...

Определить время выполнения программы
Господа как засеч време выполнение программы? Заранее всем огромное спасибо!!!

Посчитать время выполнения программы
В среде visual studio 2012 можно? или в коде написать что нужно, подскажите

Уменьшить время выполнения программы
#include &lt;iostream&gt; using namespace std; int main() { int n; ...


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

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru