Вычисление наибольшего простого делителя решетом Эратосфена

#c #алгоритм #динамические_массивы

Когда х>996 отказывается работать, помогите пожалуйста.
Собственно, код:

#include 
#include 

int main()
{
int x, p, i, q, max, min;
scanf ("%d", &x);

int *a = (int*)malloc(abs(x)+1 * sizeof(int));

for (i=0; i<=abs(x); i++)
    a[i] = i;

a[1]=0;

for (p=2; p<=abs(x); p++){
        for (q=p*2; q<=abs(x); q+=p)
            a[q]=0;
}

max=0;

if (x>=0){
    for(i=0; i<=abs(x); i++)
        if((a[i]!=0) && (abs(x)%a[i]==0))
            if (a[i]>max)
                max=a[i];

printf("%d", max);
free(a);
}

else{

min=abs(x);

for(i=0; i<=abs(x); i++)
        if((a[i]!=0) && (abs(x)%a[i]==0))
            if (a[i]

Ответы
Ответ 1

Не понимаю, что значат в этой программе отрицательные значения x, но в любом случае
abs(x) вычислять надо 1 раз. Ошибка случается оттого, что вы выделяете память так

int *a = (int*)malloc(abs(x)+1 * sizeof(int));


а надо 

int *a = (int*)malloc((abs(x)+1) * sizeof(int));


Код можно оптимизировать - максимальный делитель определить еще при построении решета.

#include 
#include 
#include 

int main()
{
    int x, p, i, q, max, min;
    scanf ("%d", &x);
    bool b=true;
    if (x<0) b=false;

    x=abs(x);
    int *a = (int*)malloc((x+1) * sizeof(int));

    for (i=0; i<=x; i++)
        a[i] = i;

    a[1]=0;
    max=0;
    min=0;
    for (p=2; p<=x; p++){
        if (a[p]==p)
            for (q=p*2; q<=x; q+=p)
            {
                a[q]=0;
                if(q==x) max=p;
                if(q==x&&min==0) min=p;
            }
    }

    if (b){
        printf("%d", max);
        free(a);
    }

    else{
        printf ("%d", -min);
        free(a);
    }
    _getch();
}

проблемы с памятью

#c #указатели #память #динамические_массивы

Доброго времени суток! Приведу пример кода, в котором укажу лишь те места, где выделяется
непосредственно память. Заранее удалю все места, где я эту память освобождаю, чтобы
вы, как более опытные программисты в Си, чем я, начинающий, указали мне, как лучше
следует с ней обращаться, а главное - показали, из-за чего всё-таки у меня программа
в процессе выполнения вылетает с ошибкой .exe вызвал срабатывание точки останова.

Итак, сам код:

    void func(int *intArray, int mode, int length, int **p, int **hufTemp, 
    int *num)
    {
    int *intPtrTemp;
    int *intListTemp, *intListIndexes;
    int *intPtrLength, *intPtrLength_Temp;
    int *intPtrBlCount; 
    int *intPtrNextCode;
    int *intPtrHuffmanTree;
    int *intDictHuffmanTree;
    int count = 0 , max = 0;



    intPtrTemp = (int*)malloc(length * sizeof(int));
    memset(intPtrTemp, 0, length * sizeof(int));
    memcpy(intPtrTemp, intArray, length * sizeof(int));

    // процесс вычисления count
    intListTemp = (int*)malloc(count * sizeof(int));
    intListIndexes = (int*)malloc(count * sizeof(int));
    memset(intListTemp, 0, count * sizeof(int));
    memset(intListIndexes, 0, count * sizeof(int));

    intPtrLength = (int*)malloc(count * sizeof(int));
    memset(intPtrLength, 0, count * sizeof(int));
    memcpy(intPtrLength, intListTemp, count * sizeof(int));

    intPtrLength_Temp = (int*)malloc(count * sizeof(int));
    memset(intPtrLength_Temp, 0, count * sizeof(int));
    memcpy(intPtrLength_Temp, intPtrLength, count * sizeof(int));

    // процесс вычисления max
    memcpy(intPtrLength_Temp, intPtrLength, count * sizeof(int));
    intPtrBlCount = (int*)malloc((max + 1)*sizeof(int));
    memset(intPtrBlCount, 0, (max + 1) * sizeof(int));

    intPtrNextCode = (int*)malloc((max + 1) * sizeof(int));
    memset(intPtrNextCode, 0, (max + 1) * sizeof(int));

    intPtrHuffmanTree = (int*)malloc(count * sizeof(int));
    memset(intPtrHuffmanTree, 0, count * sizeof(int));

    intDictHuffmanTree = (int*)malloc(count * sizeof(int));
    memset(intDictHuffmanTree, 0, count * sizeof(int));

    memcpy(*p, intPtrLength, count * sizeof(int));
    memcpy(*hufTemp, intDictHuffmanTree, count * sizeof(int));

    *num = count;
}
void main()
{
    char **dictFirstHuffmanTree;
    int intHuffmanTree_Init[19];
    int *p, *_intHuffmanTree, count = 0;

    // вычисление элементов массива intHuffmantree_Init
    p = (int*)malloc(sizeof(int));
    _intHuffmanTree = (int*)malloc(sizeof(int));

    func(intHuffmanTree_Init, 1, 19, &p, &_intHuffmanTree, &count);
    dictFirstHuffmanTree = (char**)malloc(count * sizeof(char*));
    getchar();
}


Пара важных моментов.
1. Функция содержится в файле test1.c. Дёргаю я её из файла test2.c. 
2. Если всё писать в одном файле, вот так как я представил (т.е. без освобождения
памяти), то всё прекрасно работает.
    

Ответы

Ответ 1

Как минимум:

p = (int*)malloc(sizeof(int));


Теперь p указывает на блок в 4 байта (ну, чтоб не писать sizeof(int), пусть 32-разрядная
программа).

Передаете его в функцию. Значение p не меняется, теперь это *p - раз в функцию передан
адрес p. И в этот блок вы копируете незнамо сколько памяти:

memcpy(*p, intPtrLength, count * sizeof(int));


Если count больше 1, вы выходите за рамки выделенного блока и перезаписываете служебные
структуры менеджера памяти.

Я не говорю, что это единственная ошибка, но дальше я не смотрю - пока что нет смысла...

И вы как, ничего не освобождаете выделенного? Устраиваете себе утечку памяти?

Возвращение массива функцией

#cpp #массивы #функции #динамические_массивы

Есть код. В функции double f(double x[], int n) делается вычисление нескольких функций
с несколькими переменными. Несколько переменных мы передадим в виде массива double
x[], int n - количество элементов массива; к примеру, пусть будут вычислятся две функции
- я их решил записать в массив double g[n], так как мне надо, что бы функция возвращала
оба вычисления функции: g[0] = x[0] + x[1]; g[1] = x[0] * x[1]. Как вернуть массив
g[n], и каким быть должно обращение к функции (в примере кода сразу в функции memcpy)?
Что не так, поправьте. 
Пример кода.

#include 

using namespace std;

double f(double x[], int n) 
{
    double g[n];
    g[0] = x[0] + x[1];
    g[1] = x[0] * x[1];
    return /* Что? */;
}

main() 
{
    int n = 2;
    double a[2], b[2];
    for (int i = 0; i < n; i++)
    {
        cout << " a[" << i << "] = ";
        cin >> a[i];
    }
    memcpy(b, f(a, n), sizeof(a));
    for (int i = 0; i < n; i++) cout << " b[" << i << "] = " << b[i];
    return 0;
}



    

Ответы

Ответ 1

Возвращать массив как таковой нельзя. Можно вернуть указатель на него - но тогда
массив не должен быть локальной переменной! (Кстати, в C++ нельзя объявлять массив
с размером, неизвестным во время компиляции.)

Поэтому нужно иначе..

Выделить массив динамически, и вернуть (только потом не забыть освободить память!)

int * g = new int[n];
...
return g;


Использовать, скажем, вектор (наилучший вариант):

std::vector g(n);
...
return g;


Можно обернуть массив в структуру, но опять же, нужно знать размер во время компиляции:

struct Array {
    int g[10];
}

...

Array f()
{
    Array g;
    g.g[0] = 5;
    ...
    return g;
}


Но лучше всего - использовать готовый вектор, тем более что у вас количество элементов
заранее не известно, так что std::array<> вам не подойдет.

PS Ну и, конечно, вариант с передачей возвращаемого массива в функцию:

int g[10];
... f(..., int* g)
{
    // работа с g[i]
    ...
}

...

f(...,g);

Как реализовать динамический массив? C++

#cpp #динамические_массивы #выделение_памяти

Есть программа сортировки одномерного массива из 25 элементов. Как сделать программу,
которая могла бы сортировать одномерный массив любой размерности? Если вас не затруднит,
объясните, как правильно выделять память под динамический массив, пользоваться указателями
и оператором "&" для получения значения по указанному адресу, спасибо за помощь, вот
код для массива из 25 элементов.     

#include 
#include 
#include 
#include 

using namespace std;
int main(void) {
char *locale = setlocale(LC_ALL, "");


     << "Введите массив А, состоящий из 25 целых чисел." << endl
     << "Программа  определит и выведет на экран максимальный нечетный элемент массива."
<< endl
     << "Ожидание ввода..." << endl;

 int N=25;


int k, max;

// Объявляем массив на 25 целых чисел и заполняем его с клавиатуры
int A(N){};
for (int i = 0; i < N; i++) {
    k = (i+1);
    cout << k << " элемент = ";
    cin >> A[i];

}


max = A[0];
for (int i = 1; i < N; i++) {
    if (i%2 == 0){
        if (max < A[i]) {
            max = A[i];
            k = (i+1);
        }
    }
}
cout << "Максимальный нечетный " << k <<" элемент массива = " << max << endl << "==================================="
<< endl << endl;

cout << "Вывод массива до сортировки" << endl;

    for (int i = 0; i < N; i++) {
        cout << A[i] << ' ';
    }
    cout << endl << endl;

    for (int i = 0; i < N-1; i++) {
    int mindex = i;

    int tmp = 0;

    for (int j=i+1; j < N; j++) {
        if (A[j] < A[mindex]) {
            mindex = j;
        }
    }
    if (i != mindex) {
        tmp = A[i];
        A[i] = A[mindex];
        A[mindex] = tmp;
    }
}
cout << "Вывод массива после сортировки" << endl;
for (int i = 0; i < N; i++) {
    cout << A[i] << ' ';
}
cout << endl;



return 0;
}


Код с вектором

 #include 
 #include 
 #include 
 #include 
 #include 

  using namespace std;
  int main(void)
 {
char *locale = setlocale(LC_ALL, "");

cout << "Введите массив А, состоящий из N целых чисел." << endl
     << "Программа  определит и выведет на экран максимальный нечетный элемент массива."
<< endl
     << "Ожидание ввода N..." << endl;

 int N;
 cin >> N;

int max, k;

// Объявляем массив на 25 целых чисел и заполняем его с клавиатуры
vector  A[N];
for (int i = 0; i < N; i++) {
    k = (i+1);
    cout << k << " элемент = ";
    cin >> A[i];

}


max = A[0];
for (int i = 1; i < N; i++) {
    if (i%2 == 0){
        if (max < A[i]) {
            max = A[i];
            k = (i+1);
        }
    }
}
cout << "Максимальный нечетный " << k <<" элемент массива = " << max << endl << "==================================="
<< endl << endl;


cout << "Вывод массива до сортировки" << endl;

    for (int i = 0; i < N; i++) {
        cout << A[i] << ' ';
    }
    cout << endl << endl;

    for (int i = 0; i < N-1; i++) {
    int mindex = i;

    int tmp = 0;

    for (int j=i+1; j < N; j++) {
        if (A[j] < A[mindex]) {
            mindex = j;
        }
    }
    if (i != mindex) {
        tmp = A[i];
        A[i] = A[mindex];
        A[mindex] = tmp;
    }
}
cout << "Вывод массива после сортировки" << endl;
for (int i = 0; i < N; i++) {
    cout << A[i] << ' ';
}
cout << endl;
return 0;
}


Спасибо всем кто помог. Вот код через указатели.

  #include 
  #include 
  #include 

  using namespace std;
  int main(void)
  {
  char *locale = setlocale(LC_ALL, "");

  cout << "Введите массив А, состоящий из N целых чисел." << endl
  << "Программа  определит и выведет на экран максимальный нечетный элемент 
 массива." << endl
 << "Ожидание ввода N..." << endl;

  int N;
  cin >> N;

   int max, k;


   int *A = new int[N]();
   for (int i = 0; i < N; i++) {
    k = i+1;
    cout << k << " элемент = ";
    cin >> A[i];

    }


    max = A[0];
    for (int i = 1; i < N; i++) {
    if (i%2 == 0){
      if (max < A[i]) {
        max = A[i];
        k = (i+1);
      }
    }
  }
cout << "Максимальный нечетный " << k <<" элемент массива = " << max << 
endl << "===================================" << endl << endl;


cout << "Вывод массива до сортировки" << endl;

for (int i = 0; i < N; i++) {
    cout << A[i] << ' ';
}
cout << endl << endl;

for (int i = 0; i < N-1; i++) {
int mindex = i;

int tmp = 0;

for (int j=i+1; j < N; j++) {
    if (A[j] < A[mindex]) {
        mindex = j;
    }
}
if (i != mindex) {
    tmp = A[i];
    A[i] = A[mindex];
    A[mindex] = tmp;
}
  }
        cout << "Вывод массива после сортировки" << endl;
    for (int i = 0; i < N; i++) {
     cout << A[i] << ' ';
     }
     cout << endl;
     delete [] A;
     return 0;
     }

    

Ответы

Ответ 1

Память под "голый" массив неизвестного размера в С++ можно выделить так

int *A = new int[N];


Элементы такого массива будут изначально содержать "мусор". В вашем коде вам фактически
не нужна изначальная инициализация элементов массива, но если вам так больше нравится,
вы можете сделать

int *A = new int[N]();
// или
int *A = new int[N]{};


В этих вариантах содержимое массива будет изначально обнулено.

Когда такой массив становится ненужным, память следует освободить через

delete[] A;


Остальной код при этом менять не нужно.



Однако, если уж вам нужен "голый" массив, то лучше поступить так

#include 
...

std::unique_ptr A(new int[N]);


С таким указателем/массивом можно работать обычным образом (т.е. A[i]), но память
будет освобождена автоматически.


Ответ 2

Раз тег с++ стоит, так будем делать по с++сному.

Вначале в самом верху добавим ещё один инклуд

#include 


вектор - это то, что обычно нужно, когда хочется расширяющийся массив (массив произвольного
размера).

Вместо int N = 25; пишем int N; cin >> N;
Вместо int A[N]; пишем так vector A(N);

Все, готово!

Очистка памяти динамического массива строк

#c #динамические_массивы

Доброго времени суток. Есть такая задача. Вводится строка, программа должна разбить
ее на лексемы, сохранить их в массив data, выполнить какие-то операции и потом успешно
завершится. С алгоритмом проблем нет, но вот очистка памяти не работает. Если что,
точно известно: количество слов точно не может быть более 25, длина слова - не более
20 символов. 

int main()
{
    char* string = (char*)malloc(sizeof(char) * 500);
    fgets(string, 500, stdin);

    char** data = (char**)malloc(sizeof(char*) * 25);
    for (int i = 0; i < 25; i++)
    {
        data[i] = (char*)malloc(sizeof(char) * 20);
    }

    int length = 0;
    data[length] = strtok(string, " ");
    length++;

    while (data[length - 1] != NULL)
    {
        data[length] = strtok(NULL, " ");
        length++;
    }

    //Do Something

    for (int i = 0; i < length; i++)
    {
        free(data[i]);
    }
    free(data);
    free(string);
    return 0;
}

    

Ответы

Ответ 1

Как только вы делаете вот этот финт:

data[length] = 


т.е. присваиваете указателю новое значение, старое, указывающее на выделенную память,
теряется. Получается утечка памяти.

А затем вы пытаетесь удалять то, что не выделяли.

Или просто используйте массив указателей, или, если выделяете память для хранения
слов - копируйте слова в выделенную память.

Update
Вариант 1:

int main()
{
    ...
    char** data = (char**)malloc(sizeof(char*) * 25);
    for (int i = 0; i < 25; i++) data[i] = NULL;

    int length = 0;
    for(char * с = strtok(string, " ");c;c = strtok(NULL, " "))
    {
        data[length++] = c;
    }
    //Do Something

    free(data);
    free(string);
}


Вариант 2:

int main()
{
    ...
    char** data = (char**)malloc(sizeof(char*) * 25);
    for (int i = 0; i < 25; i++) data[i] = (char*)malloc(sizeof(char) * 20);

    int length = 0;
    for(char * с = strtok(string, " ");c;c = strtok(NULL, " "))
    {
        strcpy(data[length++],c);
    }
    //Do Something

    for (int i = 0; i < 25; i++)
    {
        free(data[i]);
    }
    free(data);
    free(string);
}


Я бы все же добавил проверки на количество слов и длину... Мало ли кто что обещает...


Ответ 2

Для копирования выдаваемого strtok() слова в динамическую память проще всего использовать
функцию strdup

#ifndef _GNU_SOURCE
#define _GNU_SOURCE // for getline() with gcc -std=c11, c99 etc...
#endif

#include 
#include 
#include 

char **
get_25words (char *s, size_t *nw)
{
  char **w = (__typeof__(w))malloc(sizeof(char *) * 25); // type cast for c++

  for (*nw = 0; *nw < 25; (*nw)++, s = 0) {
    char *t = strtok(s, " ");
    if (t)
      w[*nw] = strdup(t);
    else
      break;
  }

  return w;
}


int
main (int ac, char *av[])
{
  char *s = 0;
  size_t sz;

  while (getline(&s, &sz, stdin) > 0) {
    size_t nw;
    char **w = get_25words(s, &nw);

    printf("found %zu words\n", nw);
    for (size_t i = 0; i < nw; i++) {
      printf("%s\n", w[i]);
      free(w[i]);
    }
    free(w);
  }

  free(s);
}


А читать строки неопределенной длины очень удобно функцией getline

Python 3.6 - парсинг файла и заполнение массива

#python #python_3x #парсер #динамические_массивы

Добрый день! Пишу 2D игру на Python 3.6 и возникла проблема создания массива.
Python я начал изучать совсем недавно. Смысл такой - функция должна парсить файл
карты и заполнять массив. Структура карты простая, в зависимости от символа другая
функция загружает спрайт, например '=' - это кирпичная стена, но все это должно считываться
из массива, который я пока не понял, как делать. Пример файла карты:

LevelsCount:2
LevelName:Name
LevelNum:1
LevelType:Green
{
==d=====================
=0000000000000000000000=
=0000000000000000000000=
=0000000000000000000000=
=0000000000000000000000=
=0000000000000000000000=
=0001111122211111000000=
=0000000000000000000000=
========================
}


Уровень из файла карты должен считываться в трехмерный (?) массив от "{" до "}",
причем выборочно, если укажу '1' в параметр функции, то считываться только LevelNum:1.
Каждая строка является новым элементом массива и каждый символ является элементом массива,
чтобы при доступе получить, к примеру: 

==d=====================


blocks[0][0] - '=' или blocks[0][2] - 'd', где [0] это номер строки, а [2] - номер
символа в строке.
Вот функция, которую я не могу написать правильно:

def parse_levelpack(chapt, lvl):
    lvl_file = open('pack/levels/Chapter' + str(chapt) + '.mapf', 'r')
    y_block = -1
    x_block = -1
    global levelCount
    line = lvl_file.readline()
    while line:
        line = line.replace('\n', '')
        line = lvl_file.readline()
        if line.find('{') > -1:
            y_block = y_block + 1
            x_block = -1
            blocks_array[y_block].append([])
            lvl_file.readline()
            if not line == '}':
                lvl_file.readline()
                x_block = x_block + 1
                blocks_array[x_block].append([])
                blocks_array[y_block][x_block].append(line[x_block])
    lvl_file.close()


chapt - часть, добавляется к имени файла, lvl - чтобы из файла карты выбрать нужный
уровень, например, LevelNum:1.
    

Ответы

Ответ 1

Парсер простой, поэтому думаю автор сам его допилит, а я покажу пример парсера локаций:

def fill_blocks(text_or_list):
    blocks = []

    if type(text_or_list) == str:
        line_list = text_or_list.splitlines()
    else:
        line_list = text_or_list

    for line in line_list:
        line = line.strip()
        if not line:
            continue

        row = [x for x in line]
        blocks.append(row)

    return blocks


def get_text_level_blocks(text):
    text_level_blocks = []

    start_block = False
    blocks_text = None

    for line in text.splitlines():
        line = line.strip()
        if not line:
            continue

        if line == '{':
            start_block = True
            blocks_text = []
            continue

        elif line == '}':
            start_block = False
            text_level_blocks.append(blocks_text)
            continue

        # Если не кирпич
        elif not line.startswith('='):
            continue

        # Дальше ищем символ стартового блока
        if not start_block:
            continue

        blocks_text.append(line)

    return text_level_blocks


if __name__ == '__main__':
    text = """\
==d=====================
=0000000000000000000000=
=0000000000000000000000=
=0000000000000000000000=
=0000000000000000000000=========
=000000000000000000000000000000=
=0001111122211111000000=========
=0000000000000000000000=
========================
"""
    blocks = fill_blocks(text)
    print(''.join(blocks[0]))
    print(blocks[0][0])
    print()

    many_level_text = """\
{
==d=====================
=0000000000000000000000=
=0000000000000000000000=
=0000000000000000000000=
=0000000000000000000000=========
=000000000000000000000000000000=
=0001111122211111000000=========
=0000000000000000000000=
========================
}
...
{
==d=====================
=0000000000000000000000=
=0000000000000000000000=
=0000000000000000000000=
=0000000000000000000000=
=0000000000000000000000=
=0001111122211111000000=
=0000000000000000000000=
========================
}  
"""

    text_level_blocks = get_text_level_blocks(many_level_text)
    print(len(text_level_blocks))

    level_block = text_level_blocks[0]
    blocks = fill_blocks(level_block)
    print(''.join(blocks[0]))
    print(blocks[0][0])
    print()

    all_levels_block = []

    for level_block in text_level_blocks:
        blocks = fill_blocks(level_block)
        all_levels_block.append(blocks)

    print(''.join(all_levels_block[0][4]))
    print(''.join(all_levels_block[1][4]))
    print(all_levels_block[0][0][2])
    print(all_levels_block[1][0][2])


Консоль:

==d=====================
=

2
==d=====================
=

=0000000000000000000000=========
=0000000000000000000000=
d
d


Ответ 2

Чтобы найти все {} блоки в файле, можно регулярное выражение использовать:

import re
from pathlib import Path

blocks = re.findall("(?s){(.*)}", Path('chart.mapf').read_text())


Чтобы превратить каждый блок в двухмерный список:

blocks3D = [block.strip().splitlines() for block in blocks]


Для проверки: blocks3D[0][-3][9] это символ расположенный в первом блоке, на третьей
с конца строчке, на десятой позиции ('2'). 

В этом случае строчки типом str представлены — неизменяемы. Если хочется по одному
символу изменять, можно матрицу создать со списками вместо строк:

blocks3D = [list(map(list, block.strip().splitlines())) for block in blocks]

Сформировать масcив и поместить него все неповторяющиеся числа

#cpp #массивы #динамические_массивы

Дан массив целых чисел X=(x1,x2,...,xn). Сформировать массив Y=(y1,y2,...,ym), поместив
в него в порядке убывания все различные (неповторяющиеся) числа, входящие в массив X.

Пытался вот так, но не корректно работает: 

void transferElements ()
{
    for (i = 0; i < size; i++)
    {
        f = 1;
        for (j = 0; j < size; j++)
        {
            if (X[i] == X[j])
            {
                f = 0;              
                break;
            }
            if (f == 1)
            Y[i] = X[i];
        }
    }
}

    

Ответы

Ответ 1

Huricane, в отличии от примера Timur Yalimov попробую решить задачу вообще без внешних
функций (типа qsort):

Основная логика в следующем:

Мы просматриваем все элементы и ищем каждый раз максимальное, но меньше максимального
на прошлом этапе поиска максимального

Таким образом - каждый этап мы будем находить одно уникальное число в порядке убывания

int transferElements(int* x, int x_size, int* y)
{
    int y_size = 0;

    int x_max = INT_MAX; // максимально возможное число int ~ +2.000.000.000

    for (int i = 0; i < x_size; i ++)
    {
        // определить максимальное число в массиве x, не превышающее x_max
        int x_local_max = INT_MIN; // минимально возможное число int ~ -2.000.000.000

        for (int j = 0; j < x_size; ++j)
        {
            if ((x[j] > x_local_max) && (x[j] < x_max))
                x_local_max = x[j];
        }

        // записать найденное число в выходной массив
        if (x_local_max > INT_MIN)
            y[y_size++] = x_local_max;

        // снизить границу максимальных чисел
        x_max = x_local_max;
    }

    return y_size;
}


Недостаток - алгоритм не оптимален и в массиве не должно быть числа MAX_INT (мы его
изначально как критерий используем)

От второго недостатка ты можешь избавиться уже сам

P.S.

а твой алгоритм не работает ну потому что он и не должен работать - например у тебя
только проверка на равно есть (а значит больше-меньше ты не определяешь) и запись только
в Y (а значит никак не воздействушь на X)

P.P.S.

чуть-чуть оптимальнее сделал - когда не находятся новые числа, не надо делать дальнейшие
проверки - можно прервать цикл

int transferElements(int* x, int x_size, int* y)
{
    int y_size = 0;

    int x_max = INT_MAX; // максимально возможное число int ~ +2.000.000.000

    for (int i = 0; i < x_size; i ++)
    {
        // определить максимальное число в массиве x, не превышающее x_max
        int x_local_max = INT_MIN; // минимально возможное число int ~ -2.000.000.000

        for (int j = 0; j < x_size; ++j)
        {
            if ((x[j] > x_local_max) && (x[j] < x_max))
                x_local_max = x[j];
        }

        // завершить обработку, если новых чисел не найдено
        if (x_local_max <= INT_MIN)
            break;

        // записать найденное число в выходной массив
        y[y_size++] = x_local_max;

        // снизить границу максимальных чисел
        x_max = x_local_max;
    }

    return y_size;
}


Ответ 2

Попробуйте так:

#include 
#include 

#define SIZE (7)

int compare(const void * x1, const void * x2)   

{
   return ( *(int*)x2 - *(int*)x1 );            
}

int Task(int * arr, int * res)

{
    qsort(arr, SIZE, sizeof(int), compare);

    int res_cnt = 0;

    for (int i = 0; i < SIZE; i++)

    {
       if ((arr[i] != arr[i + 1] && arr[i] != arr[i] - 1 && i != 0) || (i == 0)) 

        {
           res[res_cnt++] = arr[i];
        }  
    }

    return res_cnt;
}


int main()

{

    int array[SIZE]  = { 1, 0, 50, 50, 20, 20, 300 };
    int result[SIZE] = { 0 };
    int result_size = Task(array, result);
}


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


Ответ 3

Способ №1 (доводим ваш пример кода до рабочего состояния):

using value_type = int;

int CompFunc(const void * a, const void * b)
{
    if ( *static_cast(a) > *static_cast(b) )
        return -1;
    else
        if ( *static_cast(a) < *static_cast(b))
            return 1;
        else
            return 0;
}

size_t TransferElement(value_type *x, size_t size, value_type *y)
{
    if ( size == 0 )
        return 0;

    size_t ySize = 0;
    bool flag;

    for ( size_t i = 0; i != size; ++i )
    {
        flag = true;
        for ( size_t j = 0; j != ySize; ++j )
            if ( x[i] == y[j] )
            {
                flag = false;
                break;
            }
        if ( flag )
        {
            y[ySize] = x[i];
            ++ySize;
        }
    }
    qsort(y, ySize, sizeof(value_type), CompFunc);
    return ySize;
}




Способ №2 (Немного оптимизируем ваш алгоритм):

size_t TransferElements(value_type *x, size_t size, value_type *y)
{
    if ( size == 0 )
        return 0;

    for ( size_t i = 0; i != size; ++i )
        y[i] = x[i];
    qsort(y, size, sizeof(value_type), CompFunc);

    value_type controlVal = y[0];
    size_t ySize = 1;

    for ( i = 1; i != size; ++i )
        if ( controlVal != y[i] )
        {
            controlVal = y[i];
            y[ySize] = controlVal;
            ++ySize;
        }
    return ySize;
}


Сложность первого способа O(N^2), сложность второго O(N) (без учёта сортировки).
Однако второй способ требует, чтобы размер массива y был таким же как и x.



Способ №3 (по мотивам комментария @Harry):

typedef vector vect_type;
vect_type x, y;
//...
y = x;
sort(y.begin(), y.end(), greater());
auto last = unique(y.begin(), y.end());
y.erase(last, y.end());

Проблема с освобождением памяти в деструктор c++

#cpp #динамические_массивы

Пишу свой класс математических матриц, храню все в double**. Все работало нормально,
пока не решил заняться деструктором. Теперь при вызове какого либо оператора или функции
мне вылетает исключение: "Ошибка доступа к чтению". Я уже понял из-за чего она вылетает. 
Вот мой типичный код:

Matrix Matrix::operator+ (Matrix M)
{
    Matrix Temp(Rows, Columns);
    for (unsigned i(0); i < Rows; i++)
        for (unsigned j(0); j < Columns; j++)
            Temp[i][j] = M[i][j] + Element[i][j];
    return Temp;
}


Когда он возвращает Temp, он уничтожает все элементы, и Temp не доходит до конца.
Вот деструктор:

Matrix::~Matrix()
{
    for (unsigned i(0); i < Rows; i++)
        delete[] Element[i];
    delete[] Element;
}


Подскажите как мне правильно сделать деструктор.
    

Ответы

Ответ 1

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

Пример кода по правилу copy-and-swap idiom:

class Matrix {
public:
    Matrix(size_t rows = 0, size_t columns = 0) 
        : rows_(rows), columns_(columns),
          pMat(rows || columns ? new double[rows * columns] : nullptr) 
    {}
    Matrix(Matrix const & obj) 
        : rows_(obj.rows_), columns_(obj.columns_),
          pMat(obj.rows_ || obj.columns_ ? 
              new double[obj.rows_ * obj.columns_] : nullptr)
    {
        std::copy(obj.pMat, obj.pMat + obj.rows_ * obj.columns_, pMat);
    }
    Matrix(Matrix&& obj) noexcept
        : Matrix()
    {
        swap(*this, obj);
    }
    ~Matrix() {
        delete[] pMat;
    }

    friend void swap(Matrix& first, Matrix& second) {
        using std::swap;

        swap(first.rows_, second.rows_);
        swap(first.columns_, second.columns_);
        swap(first.pMat, second.pMat);
    }

    Matrix const & operator= (Matrix obj) {
        swap(*this, obj);
        return *this;
    }

private:
    double** pMat;
    size_t rows_;
    size_t columns_;
};

Как динамически создать массив, не зная количества его элементов? [дубликат]

#c #массивы #динамические_массивы #malloc

        
             
                
                    
                        
                            На этот вопрос уже даны ответы здесь:
                            
                        
                    
                
                        
                            Как создать динамический массив?
                                
                                    (3 ответа)
                                
                        
                                Закрыт 2 года назад.
            
                    
В цикле читаю некоторый блок данных по частям различных размеров. Требуется учитывать
размеры этих частей - думаю загонять их в массив. Как создать этот массив, если я не
знаю сколько частей будет? Возможно ли реализовать такое в языке С стандартными методами? 
    

Ответы

Ответ 1

Вам нужно будет использовать функцию realloc, определенную в заголовке ,
если  окажется, что выделенной памяти или количества элементов в динамически размещенном
массиве недостаточно.

Другой подход - это использовать список, который вы либо сами напишите, либо возьмете
чью-то готовую реализацию. В стандарте C списки не определяются.

“Структура данных «Массив» имеет фиксированный размер”. Это всегда так?

#массивы #структуры_данных #динамические_массивы

В статье про структуру данных связанный список, автор пишет про недостатки массива:


  1) The size of the arrays is fixed: So we must know the upper limit on
  the number of elements in advance...


и тут же во втором пункте, как мне кажется, он это опровергает


  2) Inserting a new element in an array of elements is expensive...


Т.е. сначала говорится, что массив – это фиксированный набор данных, а затем говорится
о добавлении. Как это понимать или автор имеет ввиду уже разновидность массива – динамический
массив?
    

Ответы

Ответ 1

Важно различать элемент и место под элемент. Массив не всегда весь заполнен, но даже
незаполненная часть занимает память1. Фиксировано в массиве число мест. Элементов в
массиве ненулевой длины может не быть.

Из-за особенностей хранимого типа может быть невозможно иметь в массиве ячейку без
значения, но это лишь техническая деталь — если значение не имеет смысла, для алгоритма
его всё равно что нет. И следить за такой ситуацией можно, храня где-то неподалёку
число "полезных элементов", если вы заполняете массив последовательно от начала (что
бывает не всегда).



Во втором пункте говорится о дороговизне вставки элемента в произвольное место с
сохранением существующих элементов массива и порядка их следования2.

Чтобы её осуществить когда место занято, нужно все элементы, начиная с запрашиваемого
места и вверх по индексам до конца заполненной части массива, переместить на одно место
вперёд. Худший случай — вставка в начало, когда необходимо сдвинуть вперёд всю заполненную
часть массива.

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

Нет, динамические массивы тут ни при чём.



1 если не используется трюков вроде разрежения, но с ними это уже не тот примитивный
массив, о котором речь

2 в пределах двух частей, на которые вставляемный элемент этот массив разделяет

Определения макросов

#c #динамические_массивы #макросы #макрос

По ходу выполнения лабораторных я наткнулся на задание, где нужно было просто написать
программу для подсчета произведения матриц, при этом выделяя память динамически. Звучит
довольно просто, но в конце я обнаружил это 


  Создать определения макросов, которые подсчитывают, сколько раз в программе произошло
использование функций динамического выделения и освобождения памяти, а также объем
выделенной и освобожденной памяти.


В методичке ничего не написано кроме пояснений про #define, #if и т.д. Хотелось бы
иметь хоть какое-то представление, о чем речь идет)
    

Ответы

Ответ 1

Похоже, что от вас хотят что-то вроде

int total   = 0;
int mallocs = 0;
int frees   = 0;

#define  malloc(s) (mallocs++, total += (s), malloc((s)))
#define  free(s)   (frees++, free((s)))

int main(int argc, const char * argv[])
{
    char * c = malloc(200);
    char * v = malloc(2000);
    free(c);

    printf("Alloc %d bytes in %d mallocs; frees: %d times\n", total, mallocs,frees);
}

Изменить размер массива динамически

#c_sharp #массивы #динамические_массивы

Например есть такой массив, как изменить его размер с 4 на другое число?    

int[] array = new int[4];

    

Ответы

Ответ 1

Вы подходите неправильно. Если вам нужно менять размер контейнера, вы должны вместо
массива использовать List.

Вы не сможете изменять размер, добавляя неинициализированные элементы, но вы сможете
добавить элемент в конец при помощи Add, в начало или середину при помощи Insert, или
удалять по индексу при помощи RemoveAt.


Ответ 2

В вашем примере управляемый массив.
Напрямую - никак, только через аллокацию (выделение памяти) нового массива. Например
есть метод Array.Resize, внутри он создает новый массив заданного размера, копирует
в него содержимое старого массива и возвращает ссылку на новый массив.



Если очень сильно нужно изменить размер неуправляемого массива без аллокации нового
- можно воспользоваться нативным классом (функция HeapReAlloc) из моего вопроса: Инспекция
класса для работы с HeapAlloc

Как выделить память для массива функций

#cpp #ооп #функции #динамические_массивы

class name {
    public:
    name(int);
    double(*act)(double);

    double f1(double);
    double f2(double);
    double f3(double);
};

name::name(int i) {
    this->act = new (double[i](double));
}



error: creating array of functions



Вот так ругается компилятор. Как можно реализовать такой динамический массив?
    

Ответы

Ответ 1

Если говорить про обычные функции:

int foo1(float)
{
    return 1;
}

int foo2(float)
{
    return 2;
}

int foo3(float)
{
    return 3;
}

int main()
{
    // в типе должна быть описана сигнатура необходимой функции
    using fun_type = int(*)(float); // int - возвращаемый тип
    // float - аргумент, (*) - означает что мы хотим создать указатель на функцию

    // создали массив указателей на функции
    // поместили адреса фукций foo1, foo2, foo3
    fun_type funs[] = { &foo1, &foo2, &foo3 };

    // вызываем функцию (в данном случае foo1)
    int result = funs[0](10.0f);

    return 0;
}


Однако в вашем случае необходимы не просто указатели на функцию, а указатели на методы
класса. Это другие сущности и, настолько они особенны, что даже не поддаются void*.
Но такая проблема также решается:

class widget
{
public:
    // имеется несколько методов с одинаковой сигнатурой
    void foo1(int);

    void foo2(int);

    void foo3(int);

    // внимание на модификатор const
    // объяснения ниже
    void foo4_c(int) const;
};

int main()
{

    // объявление массива указателей на метод класса widget
    // как и в случае с обычным указателем, этот указатель
    // просто локальная переменная
    // эти указатели не относятся к какому-нибудь конкретному объекту
    // они относятся к классу widget в целом
    void(widget::*fun_ptr[3])(int);


    // устанавливаем несколько конкретных значений
    // можно было при объявлении инициализировать списком {}
    fun_ptr[0] = &widget::foo1;
    fun_ptr[1] = &widget::foo2;
    fun_ptr[2] = &widget::foo3;

    // по поводу const в объявлении метода:
    // const является часть сигнатуры метода!
    // поэтому следующий код не скомпилируется
    // по причине разных типов указателей
    // fun_ptr[2] = &widget::foo4_c; // error!

    // для const-методов необходимо указать спецификатор const
    void(widget::*const_fun_ptr)(int) const;

    const_fun_ptr = &widget::foo4_c; // ok!

    // создается конкретный объект класса
    widget obj;

    // и указатель на динамически распределенный объект
    widget *ptr_to_obj = new widget();

    // собственно использование указателей
    // obj.* - обращение к члену указателю
    // т.к. fun_ptr массив мы указываем еще индекс
    // по которому находится нужный метод
    // необходимо взять в скобки
    (obj.*fun_ptr[0])(10);

    // для указателей на объекты используется
    // чуть-чуть другой синтаксис
    (ptr_to_obj->*fun_ptr[0])(10);

    delete ptr_to_obj;
    return 0;
}


Создать динамический массив указателей на обычную функцию не слишком сложно.

using fptr = void(*)(int);
fptr* fptrs = new fptr[10];
delete[] fptrs;


Чуть сложнее дело обстоит с указателями на методы. У меня получилось достичь необходимого
результата следующим образом:

#include 

class widget
{
public:
    void foo1(int)
    {
        std::cout << "foo1\n";
    }

    void foo2(int)
    {
        std::cout << "foo2\n";
    }

    void foo3(int)
    {
        std::cout << "foo3\n";
    }
};

int main()
{
    void(widget::*fptr)(int);

    using fptr_type = decltype(fptr);

    fptr_type* fptrs = new fptr_type[3];

    fptrs[0] = &widget::foo1;
    fptrs[1] = &widget::foo2;
    fptrs[2] = &widget::foo3;

    widget a;

    (a.*fptrs[0])(10);
    (a.*fptrs[1])(10);
    (a.*fptrs[2])(10);

    delete[] fptrs;

    std::cin.get();
    return 0;
}


Ответ 2

Вы хотите что-то вроде этого?

class Name {
public:
    Name(int);
    using func = double(*)(double);
    func* act;

};

Name::Name(int i)
{
    act = new func[i];
}


На всякий случай, исходя из набора у вас функций-членов f# - для функций-членов массив
надо объявлять иначе.

Амортизированная константа

#java #cpp #алгоритм #динамические_массивы #сложность

Может кто-нибудь объяснить, что означает амортизированная сложность алгоритма, в
частности, амортизированная константа?
Это когда для массива операция выполняется не каждый вызов, а только один раз?
    

Ответы

Ответ 1

Ну вот смотрите. Берем динамический массив. Сначала из одного элемента.

Добавляем еще один. Удваиваем массив. Итого - одно выделение, один перенос (первого
элемента). 

Еще добавление - массив становится равен 4 элементам. Выделений - 2. переносов -
3 (теперь переносим 2 элемента, + 1 ранее). Добавление четвертого элемента не требует
ни выделения, ни переноса.

Еще добавление. Массив увеличивается до 8 элементов. Теперь в массиве 8 элементов,
3 выделения памяти, 7 переносов элементов. Элементы с 6 по 8 не требуют ни выделения,
ни переноса...

...

Теперь у нас 2n элементов, n выделений памяти, 2n-1 переноса элементов.

Т.е. в среднем каждый элемент пришлось переносить 1-2-n раз, при больших n - 1 раз. 

Константа? Да. При том, что первый элемент переносился log2n раз.

А вот в среднем, т.е. амортизированно - константа.

Так более-менее понятно?

Зачем нужны динамические массивы в C++?

#cpp #указатели #динамические_массивы

В учебниках по C++ пишут, что динамические массивы нужны, когда заранее неизвестны
размеры этих массивов. Потом идет объяснение, как выделять указателями память из кучи,
затем ее надо освобождать и т.д. 

Но я попробовал сделать без указателей, вот так:

#include 
using namespace std;

int main()
{
    int size;
    cin >> size;

    int array[size];

    cout << sizeof(array)/sizeof(array[0]) << endl;

    return 0;
}


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

Ответы

Ответ 1

Это работает только в конкретном компиляторе, в котором реализовано данное расширение.
Стандартом С++ такое не предусмотрено, только С (да и то реализация не является строго
необходимой).

Это примерно как если бы вам говорили, что молоток - только для забивания гвоздей,
а вы бы возражали - а вот у меня молоток такой, что я им могу еще и шурупы вертеть.
Поверю, что у вас молоток с ручкой в виде отвертки (сам такой в школе на трудах делал
:)), но это не значит, что молоток вообще приспособлен для такой деятельности...

P.S. И еще - динамические массивы нужны не только тогда, когда количество элементов
неизвестно заранее. Но еще и для больших размеров, например, или для строго регулируемого
времени жизни - словом, неизвестный заранее размер - не единственная причина их использования.


Ответ 2

В учебниках по C++ пишут, что динамические массивы нужны, когда заранее неизвестны
размеры этих массивов


Да, это одна из причин. Но, возможно добавить какие-то ограничения в программу, чтобы
минимизировать "ущерб" от отсутствия таких массивов.


  Так в чем подвох, почему нужно делать с указателями а так, как я сделал нельзя?


Также важно время хранения этого массива. Создавая массив на стеке его время хранения
получается автоматическим, и массив будет уничтожен при выходе из функции. Что мы получаем
при динамическом выделении памяти:


Можем определиться с размером во время выполнения.
Контроль времени жизни объектов в этой памяти.
Больший объем памяти, нежели объем "стандартного" стека.


Подробнее здесь: Определение объектов в C++


  и все работает


Здесь возможны несколько вариантов.


Ваш компилятор поддерживает возможность создания таких массивов, реализуя расширения
языка, например, расширение VLA (Variable-Length Arrays) в GCC.
Компилятор поддерживает возможность RSA (Runtime-Sized Arrays), которую хотели добавить
в C++14, но так и не добавили. Но разработчики поспешили её добавить в компилятор и
Вам досталась та самая версия этого компилятора.


То есть на текущий момент возможности создавать такие массивы в языке нет.
Опять же, вполне вероятно, что лучшим вариантом будет воспользоваться одним из стандартных
контейнеров, или, хотя бы умными указателями.


Ответ 3

Допустим я хочу написать функцию создания массива по заданному размеру для заданного
указателя. Я напишу так:

int* new_array(int* p, size_t sz)
{        
    p = new int[sz];
    return p;
}


А теперь я напишу без выделения памяти в динамической области (как вы показали):

int* fudge(int* p, size_t sz)
{
    if(sz > sizeof(p) / sizeof(p[0])) {
        int m[sz];
        p = m;
    }
    return p;

}


Напишите программу использовав то одну, то другую функцию и убедитесь, что вторая
на самом деле является вздором. Вот о чем речь, когда говорится о неизвестном размере,
плюс ко всему сказанному ранее.

Как избежать двумерного массива в обработке данных?

#массивы #алгоритм #циклы #динамические_массивы

Подскажите, пожалуйста, как эффективнее решить следующее задание: некий офисный клерк
клеит на свою стеклянную дверь стикеры различных размеров. В итоге изнутри офиса и
снаружи получается разная картина из видных с одной или с другой стороны стикеров (они
могут торчать частично друг из под друга, могут быть видны полностью, а могут и вовсе
исчезнуть под всеми остальными). На вход даются следующие данные: ширина этой стеклянной
двери, количество стикеров и данные каждого стикера в следующем формате: расстояние
от левого края двери (дверь это по сути координатная плоскость с началом в (0,0)),
высота и ширина. Пример:  


  8 5
  2 3 2
  6 2 2
  3 3 2
  3 2 2
  0 2 3  


Дверь шириной 8, 5 стикеров, у первого расстояние от левого края двери 2, высота
3 и ширина 2, у остальных аналогично. На выходе необходимо получить 3 числа: количество
стикеров, видных с обеих сторон стеклянной двери, количество стикеров, видных лишь
с одной стороны (либо изнутри, либо снаружи) и количество стикеров, не видных вовсе.
Для выше приведенного примера это будет  


  4 1 0


Визуализация примера:


Я делаю это следующим образом: создаю 2 двумерных массива (дверь спереди и дверь
сзади), заполняю их нулями и "рисую" каждый стикер (занимаю место в массиве его порядковым
номером) в соответствии с актуальным положением всех стикеров, в конце прохожу массив
структур стикеров и смотрю, у кого из них есть место на двери и сколько с каждой стороны. Код:

#include 
#include 

unsigned int doorWidth = 0;
unsigned int papers = 0; // number of notes
int **mapIndoor; // door with notes as a map (inside)
int **mapOutdoor; // door with notes as a map (outside)

typedef struct {
    unsigned int xLeft;
    unsigned int height;
    unsigned int width;
    unsigned int indoor;
    unsigned int outdoor;
} note_t;

note_t *allNotes; // array of notes' data

int main() {

    if((scanf("%d %d", &doorWidth, &papers)) == 0) {
        fprintf(stderr, "Error\n");
        return -1;
    }

    allNotes = (note_t*)malloc(papers*sizeof(note_t));

    int maxHeight = 1;
    mapIndoor = (int**)malloc(maxHeight*sizeof(int*));
    mapOutdoor = (int**)malloc(maxHeight*sizeof(int*));
    for (int i = 0; i < maxHeight; i++) {
        mapIndoor[i] =(int*)calloc(doorWidth, sizeof(int));
        mapOutdoor[i] =(int*)calloc(doorWidth, sizeof(int));
    }

    for (int i = 0; i < papers; i++) {
        scanf("%d ", &allNotes[i].xLeft);
        scanf("%d ", &allNotes[i].height);
        scanf("%d ", &allNotes[i].width);
        allNotes[i].indoor = 0;
        allNotes[i].outdoor = 0;
        /*-------dynamic allocation---------*/
        if (allNotes[i].height > maxHeight) {
            int prevMax = maxHeight;
            maxHeight = allNotes[i].height;
            mapIndoor = (int**)realloc(mapIndoor, maxHeight*sizeof(int*));
            mapOutdoor = (int**)realloc(mapOutdoor, maxHeight*sizeof(int*));
            for (int k = prevMax; k < maxHeight; k++) {
                mapIndoor[k] = (int*)calloc(doorWidth, sizeof(int));
                mapOutdoor[k] = (int*)calloc(doorWidth, sizeof(int));
            }
        }
        /*-----------------------------------*/
        for (int y = 0; y < allNotes[i].height; y++) {
            for (int x = allNotes[i].xLeft; x < allNotes[i].xLeft + allNotes[i].width;
x++) {
                int prevIndoorNumber = mapIndoor[y][x];
                mapIndoor[y][x] = i+1;
                allNotes[i].indoor++;
                if (prevIndoorNumber > 0)
                    allNotes[prevIndoorNumber-1].indoor--;
                if (mapOutdoor[y][x] == 0) {
                    mapOutdoor[y][x] = i+1;
                    allNotes[i].outdoor++;
                }
            }
        }
    }

    unsigned int seenEverywhere = 0;
    unsigned int seenOnlyOnce = 0;
    unsigned int notSeen = 0;

    for (int i = 0; i < papers; i++) {
        if ((allNotes[i].indoor > 0) && (allNotes[i].outdoor > 0))
            seenEverywhere++;
        else if ((allNotes[i].indoor == 0) && (allNotes[i].outdoor == 0))
            notSeen++;
        else if (((allNotes[i].indoor > 0) && (allNotes[i].outdoor == 0)) ||
            ((allNotes[i].indoor == 0) && (allNotes[i].outdoor > 0)))
            seenOnlyOnce++;
    }

    printf("%d %d %d\n", seenEverywhere, seenOnlyOnce, notSeen);

    free(allNotes);

    for (int i = 0; i < maxHeight; i++) {
        free(mapIndoor[i]);
        free(mapOutdoor[i]);
    }
    free(mapIndoor);
    free(mapOutdoor);

    return 0;

}


Массивы  я изменяю динамически, потому что изначально неизвестна высота самого большого
стикера. Это решение работает, но оно жутко неэффективно, программа линейно зависит
от количества входных данных, и в какой то момент она не справляется с ними (например,
10 000 стикеров с шириной двери 250 000). Я понимаю, что много времени у меня занимает
обработка двумерных массивов и динамическая аллокация памяти под них, однако не могу
придумать, как их избежать. Подскажите, пожалуйста :)
    

Ответы

Ответ 1

если вы заметили что динамическая аллокация у вас занимает не малый ресурс, почему
не сделать это в рамках отдельного прохода?

То есть прочли файл в allNotes, и в этом же цикле только наметили размер дверей. 

вторым раундом по papers уже работаете с двумерными массивами - сразу выделяете нужное
пространство и размечаете.

на самом деле по количеству операций это ничего не стоит, это просто +10000 инкрементов,
в остальном без разницы сделаете вы 2 операции в одном цикле или по одной операции
в двух циклах.

Но по поводу отказа от двумерного массива надо еще подумать...

Один из вариантов развития алгоритма больше направлен на распределенное вычисление...
Так как у вас все стикеры привлекаются только к низу хочется вместо 2 мерного массива
хранить массив высот, на каждом делении ширины. И по врожденной формуле пересечения
прямоугольников вычислять какие стикеры видны на данном сечении(по сути результат это
массив номеров стикеров). Потом эти результаты можно собрать чтобы убрать дубликаты.
По сути это как раз ложиться на map reduce. То есть задачу можно маштабировать. Осталось
только более детально проработать алгоритм вычисления наложения по формуле на этапе
map. Хотя при имеющихся возможностьях (типа многоядерности) сам факт возможности маштабирования
уже может существенно повысить эффективность потребеления ресурсов для поставленной
задачи, тем самым уменьшив время обработки до приемлемых результатов даже без существенного
изменения самого подхода то есть будет не один двумерный массив, а несколько одномерных,
на каждый поток свой и каждый по нему будет возвращать не кол-во, а номера, по которым
уже достаточно просто посчитать количество, когда все потоки закончат свою работу


Ответ 2

Могу предложить решение на джаве... Рефакторинг на вашей совести, потому как написано
на быструю руку. Собственно, все ваши стикеры клеятся исключительно снизу вверх. Это
значит, что нам по сути не нужно отслеживать целую поверхность двери. Почему? Представьте,
что у вас есть стикер высотой 3, второй стикер при этом высотой 2. Даже если второй
стикер занимает всю длину двери, то третий все равно будет виден, т.к.он просто выше.
Это значит, что для того, чтобы отследить видимость одного стикера с одной стороны
двери нам достаточно иметь одномерный массив , который будет обозначать перекрытие
самого верхнего ряда. длина массива совпадет с шириной стикера. Т.е. для стикера размером
2(ширина) на 3(высота) при площади в условных 6 квадратов (2*3) нам нужно отслеживать
лишь верхних 2 квадрата, остальные 4 не имеют никакого значения. Посему в алгоритме,
который отслеживает всю поверхность двери, необходимости нет от слова совсем. Она больше
не важна. Более того, нам даже не нужно следит за всей поверхностью конкретного стикера.
Каждый стикер - экземпляр класса и он сам знает, как расчитать видимость и с какой
стороны он виден. ООП рулит)) Мало того, каждый раз, когда у стикера вызывается метод,
который позволяет вычислить, перекрывает ли его второй стикер, все вычисления происходят
поэтапно. Для начала сравнивается положение относительно края и ширина на предмет того,
пересекаются ли стикеры по ширине. Если первый результат показал, что стикеры не перекрывают
друг друга, то второй и третий шаги не выполняются. Нет смысла высчитывать полное перекрытие
или частичное перекрытие, если уже установлено, что стикеры не соприкасаются. Второй
шаг - вычисление полного перекрытия. Здесь учитывается еще и высота. И последний -
частичное перекрытие выполняется только после первых двух (если установлено, что это
именно частичное перекрытие). Только последний метод работает с массивом. Все остальные
выполняют достаточно тривиальные математические вычисления, следовательно, выполняются
очень быстро.  А до последнего очередь доходит далеко не всегда.  Одновременно у нас
есть энумератор, описывающий 3 ситуации - полное перекрытие, частичное перекрытие стикеры
не соприкасаются. Этот флаг используется, чтобы вычислить финальный результат, не перебирая
все вложенные массивы. Кроме того, если первое сравнение стикеров установило, что 2
стикер полностью перекрыл первый, то выставляется флаг , что стикер перекрыт и все
дальнейшие вычисления не производятся в силу их бессмысленности (нам все равно , что
стикер перекрыли много раз). Аналогичная ситуация , если путем многократного частичного
перекрытия стикер закрывается полностью. Флаг о полном перекрытии также высталяется
и дальнейшие действия не производятся.

import static doorsticker.OverlayEnum.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Sticker {

    private OverlayEnum overlayFirstSide = NOT_OVERLAY;
    private OverlayEnum overlaySecondSide = NOT_OVERLAY;

    private final int leftMargin, height, width;
    private final boolean []overlaying1;
    private final boolean []overlaying2;

    public Sticker(int leftMargin, int height, int width) {
        this.leftMargin = leftMargin;
        this.width = width;
        this.height = height;
        this.overlaying1 = new boolean[width];
        this.overlaying2 = new boolean[width];
    }

    private int[]createResult(){
        int[] result = new int[3];
        //all overlay for 2 sides
        if (overlayFirstSide == ALL_OVERLAY && overlaySecondSide == ALL_OVERLAY) {
            result[2]=1; 
            return result; 
        }
        //all overlay for 1 sides
        if ((overlayFirstSide==ALL_OVERLAY && overlaySecondSide!=ALL_OVERLAY) || 
                (overlaySecondSide==ALL_OVERLAY && overlayFirstSide!=ALL_OVERLAY)) 
            result[1]=1;
        // not overlay
        else result[0]=1;        
        return result;
    }

    private void compareSticker(final Sticker sticker, boolean isFirstSideComparing) {
        if (overlayFirstSide==ALL_OVERLAY && isFirstSideComparing) return;
        if (overlaySecondSide==ALL_OVERLAY && !isFirstSideComparing) return;
        boolean notOverlay = notOverlay(sticker);
        boolean fullOverlay = fullOverlay(sticker);        
        if (fullOverlay && isFirstSideComparing) overlayFirstSide=ALL_OVERLAY;
        if (fullOverlay && !isFirstSideComparing) overlaySecondSide=ALL_OVERLAY;
        if (!notOverlay && !fullOverlay) partOverlay(sticker,isFirstSideComparing);
    }


    private boolean notOverlay (final Sticker sticker) {
        int leftOverlay = leftMargin-sticker.getLeftMargin()-sticker.getWidth();
        int rightOverlay = sticker.getLeftMargin()-leftMargin-width;
        return leftOverlay>=0 || rightOverlay>=0;
    }
    private boolean fullOverlay (final Sticker sticker) {
        return leftMargin>=sticker.getLeftMargin() && 
                leftMargin+width<=sticker.getLeftMargin()+sticker.getWidth() &&
                height<=sticker.getHeight();
    }
    private void partOverlay (final Sticker sticker, boolean isFirstSideComparing) {
        if (height>sticker.getHeight()) return;
        int startOverlay = Math.max(0,sticker.getLeftMargin() - leftMargin);
        int endOverlay = width-Math.max(0,((leftMargin+width)-
                (sticker.getLeftMargin()+sticker.getWidth())));        
        if (isFirstSideComparing) overlayFirstSide=partOverlay(overlaying1, startOverlay,
endOverlay);
        else overlaySecondSide=partOverlay(overlaying2, startOverlay, endOverlay);
    }
    private OverlayEnum partOverlay(boolean [] overlaying,
            int startOverlay, int endOverlay){
        boolean chackAllOverlay = true;
        for (int i = 0; i < overlaying.length; i++) {
            if (i>=startOverlay && i stickers){

    int[] result = new int[3];

    for (int i = 0; i < stickers.size(); i++) {
        for (int j = i + 1; j < stickers.size(); j++) {
            stickers.get(i).compareSticker(stickers.get(j), true);
            stickers.get(j).compareSticker(stickers.get(i), false);
        }

    }

    for (Sticker sticker : stickers) {
        int[] stickerResult = sticker.createResult();
        result[0] = result[0] + stickerResult[0];
        result[1] = result[1] + stickerResult[1];
        result[2] = result[2] + stickerResult[2];
    }
    return result;
}

}

enum OverlayEnum{
    NOT_OVERLAY, ALL_OVERLAY, PART_OVERLAY;
}

class Main {

    public static void main(String[] args) {

        List stickers = new ArrayList<>();
        stickers.add(new Sticker(2, 3, 2));
        stickers.add(new Sticker(6, 2, 2));
        stickers.add(new Sticker(3, 3, 2));
        stickers.add(new Sticker(3, 2, 2));
        stickers.add(new Sticker(0, 2, 3));

        int[]result = Sticker.execute(stickers);

        System.out.println("RESULT: " + Arrays.toString(result));

    }

}

Способ хранения координат фишек

#cpp #массивы #visual_cpp #динамические_массивы

Пишу бота, который будет играть в простейшую игру. В начале каждого хода из файла
считывается игровое поле, которое представляет собой матрицу 8х8. В игре 4 игрока,
их фишки, соответственно, обозначены цифрами 1, 2, 3, 4 и расставлены на игровом поле.
Нужно найти все фишки каждого игрока и каким-то образом хранить местоположение (координаты)
каждой фишки. Как можно это сделать? Пробовал запоминать координаты в обычный массив
и в vector, но это не совсем удобно.
    

Ответы

Ответ 1

Есть два варианта хранения - хранение состояния игры (доски), а на ней фишек (например,
массив

int board[8][8];


в котором пустые поля обозначены нулями, а непустые - номером стоящей там фишки.

Но исходя из "Необходимо, чтобы можно было максимально просто получить доступ к координатам
выбранной фишки", вам нужен второй вариант - а именно, массив фишек с их координатами
(x,y), которые можно реализовать как стандартный pair, а можно с помощью своей
структуры типа

struct Point {
    int x,y;
};


Но, как я понимаю, вам нужно и то, и другое - чтобы, зная фишку, сразу получить возможные
ходы - например, пустая ли какая-то клетка?

Я бы просто делал класс типа Game, который бы хранил и доску, и четыре фишки, и при
каждом ходе обновлял как координаты фишки, так и состояние доски. Интерфейс такого
класса содержал бы функции для
- возврата координат фишки номер N
- возврата номера фишки на поле (x,y) (0, если пусто)
- перемещения фишки N на новое поле.

Как бы вы ни старались, сделать этот класс медленным - с 64 полями - у вас не получится.
Какое нужно внутреннее представление - смотрите сами, что вам привычнее.


Ответ 2

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


А что неудобно? Если делать массив, то нужно конвертер в наглядную форму сделать.
И будет всё очень даже удобно.

Но я бы взял пример из шахмат. Где одна ось буквами обозначается, другая цифрами.
Координаты записываются как A6, E3... и т.д. Это и очень быстрый вариант, и очень
наглядный.

Как создать динамический массив?

#c #массивы #динамические_массивы

Хочу разобраться с динамическим выделением памяти в c. Пришла в голову идея, попробовать
сделать программу, которая спрашивает у пользователя имя и записывает ввод в массив
типа char, но так чтобы массив сам выделял себе память. То есть без предварительного
выделения вида char name[30] = {0};. Я ввожу имя Магомед и массив сам выделяет себе
память на 7 символов. Как это сделать?
    

Ответы

Ответ 1

Я бы взял указатель, длину и зарезервированную длину. Примерно

char * s = malloc(16);
int size = 16;
int used = 0;


И дальше читаем по одному символу. Как только вносим его в s, тут же увеличиваем
used; как только used == size, так сразу увеличиваем массив раза в два:

s = realloc(s,size *= 2);


И все. Мы всегда знаем, сколько места имеется, сколько занято. Как в векторе в C++.


Ответ 2

Вот есть функция, которая прочитывает указанный файл посимвольно, пока не
встретит символ перевода строки или конец файла. Функция сама выделяет себе
память, а после использования строки буфер надо освободить с помощью free.
При нехватке памяти ввод обрывается и возвращаются считанные символы или NULL,
если не удалось ничего получить. Кроме того, для удобства чтения стандартного
ввода предлагается макрос.

char* get_full_line(FILE* f) {
    size_t capacity = 16;  // начальный объем массива
    char* str = malloc(capacity);
    size_t length = 0;
    if (!str) return NULL;

    int ch;
    while ((ch = fgetc(f)) != '\n' && ch != EOF) {
        if (length >= capacity) {
            char* p = realloc(str, capacity *= 4);  // коэфициент прироста
            if (!p) break;
            str = p;
        }
        str[length++] = ch;
    }
    str[length] = '\0';
    return str;
}
#define read_full_line() ( get_full_line(stdin) )


Ответ 3

А вот ещё подготовил пример приветствия. Используется функция
getline(3) из расширения библиотеки языка си.

int main()
{
    printf("Ваше имя: ");

    char* name = NULL;
    size_t capacity = 0;
    ssize_t length = getline(&name, &capacity, stdin);

    if (length > 0 && name[length - 1] == '\n') {
        name[length - 1] = '\0';  // убирает перевод строки
    }
    printf("Привет, %s!\n", name ?: "незнакомец");
    free(name);
    return 0;
}


Кроме того, в этом кусочке кода встречается ещё одно расширение GNU —
тренарный оператор без второго операнда. В этом случае, если первый операнд не
равен нулю, он будет взят в качестве результата, иначе берётся третий операнд.

Как заполняется массив в ArrayList Java

Суть задачи состоит в создании ArrayList и добавлении в него обычных массивов, которые затем необходимо заполнить данными. Появился такой вопрос, каким образом заполняются массивы в ArrayList? Конкретно непонятна запись во внутреннем цикле:
for (int i = 0; i < nums.size(); i++) { for (int j = 0; jЗдесь представлен весь код метода:
public static ArrayList createList() { ArrayList nums = new ArrayList(); nums.add(new int[5]); nums.add(new int[2]); nums.add(new int[4]); nums.add(new int[7]); nums.add(new int[0]); Random r = new Random(); for (int i = 0; i < nums.size(); i++) { for (int j = 0; j

Ответ

Метод get(i) объекта nums типа ArrayList возвращает i-ый элемент списка nums, коим является объект типа int[] – массив целых чисел. Далее, во внутреннем цикле этот массив инициализируется значениями.

Длина динамического массива

Здравствуйте. Хочу сделать програму которая находит в тексте расположение больших букв и записывает ето расположение в массив. Уже все проверил, все равно массив на еденицу меньший. В даной програме должно виводиться 0 40 76 104 123 и длина 5. Виводиться 0 40 76 104 123 и длина 4. Уже не знаю что й делать
#include #include #include #include
int main (void) { char str[] = {"London is the capital of great britain. Donald trump is a president of usa. A year consist of 365 days. Orange is a fruit. I love breaking bad."}; int *arrBig = (int*)malloc(500 * sizeof(int)); int numMasForBig = 0; for (int i = 1; i < strlen(str); i++) { if (*(str + i) >= 65 && *(str + i) <= 90) { numMasForBig++; arrBig[numMasForBig] = i; } } arrBig[0] = 0;
for (int i = 0; i < sizeof(arrBig); i++) { printf("%d ", arrBig[i]); } printf("
%d ", sizeof(arrBig));
free(arrBig); getch(); return 0; }

Ответ

sizeof(arrBig) - размер указателя, не имеет к длине массива никакого отношения.
printf("
%d ", numMasForBig + 1);