0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
|
|
1 | |
Динамический массив с большим количеством элементов13.03.2013, 00:15. Показов 10552. Ответов 61
Метки нет (Все метки)
Нужно создать динамический массив (каждый элемент целое положительное число до 10^9), который по введенным данным создавал N элементов массива, где N может быть до 10^5.
unsigned long int *arr = new unsigned long int[num]; Я сделал так, но если количество элементов больше 45920, то выводит ошибку "terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc This application has requested the Runtime to terminate it in unuasual way. Please contact the application's support team for more information." IDE Qt Creator. Статические массивы типа int array[1000000]; сразу выводят ошибку, причем в обоих случая изменение типа элементов массива ничего не меняет.
0
|
13.03.2013, 00:15 | |
Ответы с готовыми решениями:
61
Создать с помощью new динамический массив с указанным количеством элементов Применение массивов случайных чисел с большим количеством элементов Сформировать новый массив С, переписав в него массив с большим количеством положительных элементов. Как преобразовать массив с большим количеством элементов в строку? |
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
|
|
13.03.2013, 04:35 [ТС] | 42 |
кажется этот - http://rutracker.org/forum/viewtopic.php?t=4038622
Добавлено через 4 минуты Без булевого массива все работает (но я не уверен, как себя поведет прога на моем компе при большом количестве элементов - по понятным причинам 60к значений с клавиатуры забить сложно). Но на тестах выходит перебор по времени выполнения на этом же самом тесте из-за вдвое большего количества итераций цикла =\
0
|
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
|
|
13.03.2013, 05:01 [ТС] | 44 |
Встретится комбинация [j][i]. Это была попытка уменьшить количества вхождений во внутренности if-a из-за двойного прохождения. Допустим есть удачная комбинация i=2;j=4. Без булева массива цикл войдет в if ещё и при i=4;j=2.
Вообщем вопрос можно оставить для теоретических исследований - алгоритм действительно
0
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
|
||||||
13.03.2013, 05:06 | 45 | |||||
если я правильно понял логику
не проще написать так
1
|
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
|
|
13.03.2013, 05:10 [ТС] | 46 |
Действительно, так намного лучше, странно, что я не додумался.
Но все равно по времени не прошло, там все намного проще оказалось. Нужно переформулировать рекурсивное соотношение, оно сводится всего лишь к определнию четности-нечетности, так что подпрограмма не нужна. Но если бы рекурсивная формула была сложнее, то пришлось бы оставить как есть.
0
|
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
|
|
13.03.2013, 05:21 [ТС] | 48 |
Нет. Вот что я пытаюсь решить.
http://codeforces.ru/problemset/problem/272/B Добавлено через 4 минуты Кажись я поспешил, не уверен, что эту рекурсию можно так быстро на условия if-a вместо подпрограммы разбить.
0
|
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
13.03.2013, 05:31 | 50 |
Куча глобальна в любом случае, а указатель может валяться и в стеке.
0
|
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
|
||||||
13.03.2013, 05:45 [ТС] | 51 | |||||
Вообщем не представляю что ещё можно придумать.
0
|
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
13.03.2013, 05:50 | 52 |
390 кибибайт - это не много, мне однажды пришлось извращаться с массивом на 17 мебибайт.
Добавлено через 54 секунды 1 771 561 элементов по 10 байт штука.
0
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
|
||||||
13.03.2013, 06:03 | 53 | |||||
Я же тебе показал реализацию функции никакой рекурсии
можно еще убыстрить выбрасываем ветвление
0
|
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
|
|
13.03.2013, 06:12 [ТС] | 54 |
Вроде работает (сайт codeforces упал, на тестах прогнать не могу).
k+=%2; // тут компилятор вывел ошибку, заменил на k+=k%2; А можно подробней, что означает n/=2 и почему это тот же алгоритм =\
0
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
|
|||||||||||
13.03.2013, 06:24 | 55 | ||||||||||
это тоже самое что n=n/2 (краткая запись)
по шагам то пройди если я изменю немного вторую формулу f(0)=0; f(2x)=f(x)+0; f(2x+1)=f(x)+1; то видно что это алгоритм перевода десятичного числа в двоичное путем деления на двойку это я пропустил буковку правильно писать
0
|
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
|
|
13.03.2013, 06:30 [ТС] | 56 |
В любом случае, опять 25 - 11 тест завален по времени выполнения
Я правда не понял - а зачем в условии while писать выражение? В каком случае будет выход? Когда целочисленное деление n/2 приведет к 0? (то есть при n=1)
0
|
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
|
|
13.03.2013, 06:39 [ТС] | 58 |
Почему не проходит? массив занимает 4 мб, остальное мелочи, по сравнению с ним.
Данные вводятся с клавиатуры (в теории), но у них там какая то система автоматического тестирования, имитирует ввод с клавы.
0
|
Модератор
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
|
||||||
13.03.2013, 08:34 | 59 | |||||
пардон умножил неправильно
здесь есть другой путь массив на 32 инта сейчас обдумаю напишу Добавлено через 1 час 41 минуту короче задача решается вообще без выделения памяти достаточно вспомнить комбинаторику(я целый час вспоминал) количество комбинаций n*(n-1); а количество пар n*(n-1)/2; выделяем массив на 32 элемента в него будем заносить количество чисел сумма единиц которых равна номеру элемента массива потом подсчитаем сумму количество пар в каждом элементе массива в общем вот код
убыстрение нет выделения памяти функция вызывается 100000 раз а не 100000*99000 нет ветвлений Добавлено через 5 минут проверить не смог, лень регистрироваться
1
|
4226 / 1795 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
13.03.2013, 09:38 | 60 |
А чаще всего мне было нужно более 2-х гигбибай (289 000 000 элементов по 10 байт штука). Вот это уже должно быть разреженным. Малышь же в 1 771 561 элементов по 10 байт был статическим.
0
|
13.03.2013, 09:38 | |
13.03.2013, 09:38 | |
Помогаю со студенческими работами здесь
60
Массив заполняется количеством элементов, большим, чем положено Организовать динамический массив с заранее неизвестным количеством элементов Создать динамический массив с количеством элементов, которое вводит пользователь Оперирование большим количеством элементов CheckBox Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |