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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.81
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
#1

Динамический массив с большим количеством элементов - C++

13.03.2013, 00:15. Просмотров 2994. Ответов 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]; сразу выводят ошибку, причем в обоих случая изменение типа элементов массива ничего не меняет.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.03.2013, 00:15
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Динамический массив с большим количеством элементов (C++):

Создать с помощью new динамический массив с указанным количеством элементов - C++
Так как пока что я учусь самостоятельно у меня нету проверяющего, поэтому прошу вас посмотреть все ли правильно я делаю. Задание:...

Применение массивов случайных чисел с большим количеством элементов - C++
Само задание: Создайте две функции для решения одной и той же задачи: динамическое создание и заполнение случайными числами массива...

Реализовать обработку и файловую запись/чтение массива с большим количеством элементов - C++
такую задачу поставили... имеется 600 000 элементов. Каждому элементу присвоить значение и по 300 000 записать в файл. массив такое...

Строки матрицы, с большим количеством положительных элементов расположить выше остальных - C++
В массиве А(N,M) расположить строки так, чтобы сначала шли строки, у которых положительных элементов больше, чем отрицательных, затем с...

Удалить строку с самым большим количеством слов - C++
помогите написать программу: "Удалить строку с самым большим количеством слов" (используя указатели) С++ Заранее...

Алгоритм быстрой сортировки не работает с большим количеством чисел - C++
Требовалось написать программу с алгоритмами сортировки, затем сравнить эти алгоритмы (но проблема не в этом). Все работает, кроме быстрой...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 05:10  [ТС] #46
Действительно, так намного лучше, странно, что я не додумался.
Но все равно по времени не прошло, там все намного проще оказалось.
Нужно переформулировать рекурсивное соотношение, оно сводится всего лишь к определнию четности-нечетности, так что подпрограмма не нужна. Но если бы рекурсивная формула была сложнее, то пришлось бы оставить как есть.
ValeryS
Модератор
6556 / 5022 / 464
Регистрация: 14.02.2011
Сообщений: 16,763
13.03.2013, 05:12 #47
Цитата Сообщение от luck Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
unsigned long int func(unsigned long int a)
{
   if (a==0)
   return 0;
     if (a%2==0)
      return func(a/2);
    else
     {
       a=func(a/2)+1;
        return a;
      }
}
количество единиц в двоичном представлении числа считает???
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 05:21  [ТС] #48
Нет. Вот что я пытаюсь решить.
http://codeforces.ru/problemset/problem/272/B

Добавлено через 4 минуты
Кажись я поспешил, не уверен, что эту рекурсию можно так быстро на условия if-a вместо подпрограммы разбить.
ValeryS
Модератор
6556 / 5022 / 464
Регистрация: 14.02.2011
Сообщений: 16,763
13.03.2013, 05:28 #49
Цитата Сообщение от luck Посмотреть сообщение
Нет.
так это и получается количество единиц
вот так
C++
1
2
3
4
5
6
7
8
9
10
int fnc (int n)
{
 int k=0;
  do
  {
    if(n%2) 
       k++;
  }while(n/=2);
return k;
}
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
13.03.2013, 05:31 #50
Куча глобальна в любом случае, а указатель может валяться и в стеке.
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 05:45  [ТС] #51
Вообщем не представляю что ещё можно придумать.
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
#include <iostream>
#include <stdio.h>
#include <conio.h>
#include <string.h>
using namespace std;
unsigned long int func(unsigned long int);
int main()
{
    unsigned long int i,num,res = 0;
    cin>>num;
    unsigned long int *arr = new unsigned long int[num];
    for (i=0;i<num;i++)
      scanf("%d",&arr[i]);
    for(i=0;i<num-1;i++)
      for(unsigned long int j=i+1;j<num;j++)
          if ((arr[i]==arr[j]) or (func(arr[i])==func(arr[j])))
                    res++;
    printf("%d",res);
    delete[] arr;
    return 0;
}
 
unsigned long int func(unsigned long int a)
{
    if (a==0)
        return 0;
    if (a%2==0)
       return func(a/2);
    else
    {
         a=func(a/2)+1;
         return a;
    }
}
Вот что вышло в результате. При 50к+ чисел на входных данных размером в районе 10^9 считает больше 2 секунд, что перебор. А как уменьшить, если уже проще некуда.
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
13.03.2013, 05:50 #52
Цитата Сообщение от luck Посмотреть сообщение
Нужно создать динамический массив (каждый элемент целое положительное число до 10^9), который по введенным данным создавал N элементов массива, где N может быть до 10^5.
390 кибибайт - это не много, мне однажды пришлось извращаться с массивом на 17 мебибайт.

Добавлено через 54 секунды
1 771 561 элементов по 10 байт штука.
ValeryS
Модератор
6556 / 5022 / 464
Регистрация: 14.02.2011
Сообщений: 16,763
13.03.2013, 06:03 #53
Цитата Сообщение от luck Посмотреть сообщение
А как уменьшить, если уже проще некуда.
Я же тебе показал реализацию функции никакой рекурсии
можно еще убыстрить
выбрасываем ветвление
C++
1
2
3
4
5
6
7
8
9
unsigned int fnc (unsigned int n)
{
 int k=0;
  do
  {
    k+=%2;
  }while(n/=2);
return k;
}
выбрось long простого int хватит тебе нужно до 1 000 000 000 а int считает до 4 294 967 295
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 06:12  [ТС] #54
Вроде работает (сайт codeforces упал, на тестах прогнать не могу).
k+=%2; // тут компилятор вывел ошибку, заменил на k+=k%2;
А можно подробней, что означает n/=2 и почему это тот же алгоритм =\
ValeryS
Модератор
6556 / 5022 / 464
Регистрация: 14.02.2011
Сообщений: 16,763
13.03.2013, 06:24 #55
Цитата Сообщение от luck Посмотреть сообщение
что означает n/=2
это тоже самое что n=n/2 (краткая запись)
Цитата Сообщение от luck Посмотреть сообщение
почему это тот же алгоритм =\
по шагам то пройди
если я изменю немного вторую формулу
f(0)=0;
f(2x)=f(x)+0;
f(2x+1)=f(x)+1;
то видно что это алгоритм перевода десятичного числа в двоичное путем деления на двойку
Цитата Сообщение от luck Посмотреть сообщение
k+=%2; // тут компилятор вывел ошибку, заменил на k+=k%2;
это я пропустил буковку
правильно писать
C++
1
k+=n%2;
что равносильно
C++
1
k=k+n%2
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 06:30  [ТС] #56
В любом случае, опять 25 - 11 тест завален по времени выполнения
Я правда не понял - а зачем в условии while писать выражение? В каком случае будет выход? Когда целочисленное деление n/2 приведет к 0? (то есть при n=1)
ValeryS
Модератор
6556 / 5022 / 464
Регистрация: 14.02.2011
Сообщений: 16,763
13.03.2013, 06:35 #57
вообще то там написано
ограничение по памяти на тест:256 мегабайт
он и по этому параметру непроходит
данные то как вводятся???
файл али что?
luck
0 / 0 / 0
Регистрация: 06.07.2012
Сообщений: 63
13.03.2013, 06:39  [ТС] #58
Почему не проходит? массив занимает 4 мб, остальное мелочи, по сравнению с ним.
Данные вводятся с клавиатуры (в теории), но у них там какая то система автоматического тестирования, имитирует ввод с клавы.
ValeryS
Модератор
6556 / 5022 / 464
Регистрация: 14.02.2011
Сообщений: 16,763
13.03.2013, 08:34 #59
Цитата Сообщение от luck Посмотреть сообщение
массив занимает 4 мб,
пардон умножил неправильно
здесь есть другой путь массив на 32 инта
сейчас обдумаю напишу

Добавлено через 1 час 41 минуту
короче задача решается вообще без выделения памяти
достаточно вспомнить комбинаторику(я целый час вспоминал)
количество комбинаций
n*(n-1);
а количество пар
n*(n-1)/2;

выделяем массив на 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
#include <iostream>
 
using namespace std;
unsigned int func(unsigned int);
 
int main()
{
    unsigned long long int res = 0;
    unsigned long long int arr[32]={0};
    unsigned int n,k=0;
    cin>>n;
 
    for (int i=0;i<n;i++)
    {
             cin>>k;
      arr[func(k)]++; 
    
    }
    for (int i=0;i<32;i++)
           res+=(arr[i]*(arr[i]-1))/2;
    cout<<res;
    return 0;
}
 
unsigned int func(unsigned int n1)
{
unsigned int k=0;
  do
  {
    k+=n1%2;
  }while(n1/=2);
return k;
}
проверил до 12 дальше лень
убыстрение
нет выделения памяти
функция вызывается 100000 раз а не 100000*99000
нет ветвлений

Добавлено через 5 минут
проверить не смог, лень регистрироваться
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
13.03.2013, 09:38 #60
А чаще всего мне было нужно более 2-х гигбибай (289 000 000 элементов по 10 байт штука). Вот это уже должно быть разреженным. Малышь же в 1 771 561 элементов по 10 байт был статическим.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.03.2013, 09:38
Привет! Вот еще темы с ответами:

Определить номер строки матрицы с наиболее большим количеством нулей - C++
с помощью датчика случайных чисел заполнить двоичную матрицу 5 10. определить номер строки с наиболее большим количеством нулей

Задан массив с количеством элементов n - C++
Задан массив с количеством элементов n.Сформировать 2 массива:в 1 включить элементы исходного массива с чётными номерами,а во 2 с нечётными

Массив с неизвестным количеством элементов - C++
Как задать char массив, количество элементов которого мне неизвестно? Туда может быть записано 10 элементов, а может и 25 или еще больше. ...

Как преобразовать массив в динамический? Массив вычисляет сумму элементов каждой диагонали матрицы - C++
Ошибка : Вызвано исключение по адресу 0x00BB2F4F в Проект6.exe: 0xC0000005: нарушение прав доступа при чтении по адресу 0xFDFDFE05. #...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
13.03.2013, 09:38
Ответ Создать тему
Опции темы

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