среда, 17 ноября 2010 г.

1.2. “Массивы”

А.Шень “Программирование. Теоремы и задачи”

1.2.1 (Обнуление массива) 
Вариант 1:
  1. int mas[max_size] = {0};

Вариант 2:

  1. int mas[max_size];
  2. memset(mas,0,sizeof(int) * max_size);
1.2.2 (Подсчет количества объектов) 
  1. int mas[max_size];
  2. . . .
  3. int zeroesAmount = 0;
  4. for (int i=0;i<max_size;i++)
  5.   zeroesAmount += mas[i] == 0 ? 1 : 0;
1.2.3 (Копирование массивов) 
  1. int a[max_size],b[max_size];
  2. . . .
  3. memcpy(b,a,max_size * sizeof(int));
1.2.4 (Максимальный элемент) 
Вариант 1:
  1. int a[max_size];
  2. int max_value = mas[0];
  3. for (int i=1; i<max_size; i++)
  4.   maxValue = max(max_Value,mas[i]);

Вариант 2: 

  1. int mas[max_size];
  2. . . .
  3. int posMaxValue = 0;
  4. for (int i=1; i<max_size; i++)
  5.   posMaxValue = mas[i] > mas[posMaxValue] ? i : posMaxValue;

В общем случае второй вариант является более предпочтительным. Потому что он отвечает сразу на два вопроса.

1.2.5 (Количество различных элементов в неубывающем массиве)
 

  1. int mas[max_size];
  2. . . .
  3. int posMaxValue = 0;
  4. for (int i=1; i<max_size; i++)
  5.   posMaxValue = mas[i] > mas[posMaxValue] ? i : posMaxValue;

1.2.6 (см. 1.2.5 в произвольном массиве. Сложность O(N*N))
Сортировка выбором + 1.2.5

1.2.7 (см. 1.2.5 в произвольном массиве. Сложность О(N*logN))
 
Пирамидальная или Быстрая сортировка + 1.2.5

1.2.8 (см. 1.2.5 в произвольном массиве. Элементы массива в интервале [0,K]. Сложность O(N + K))
Сортировка подсчетом + 1.2.5

1.2.9 Количество прямоугольных единичных подматрицы
Решение

1.2.10 (Реверс массива)

  1. void reverse(vector<int> &mas, int l, int r)
  2. {
  3.   while (l<r)
  4.     swap(mas[l++],mas[r--]);
  5. }

1.2.11 (Массив X = AB, где A и B – подмассивы. Реверснуть подмассивы и получить X = BA) 

Функция reverse из 1.2.10. m – индекс последнего элемента подмассива A.

  1.   reverse(mas,0,m);
  2.   reverse(mas,m+1,mas.size()-1);
  3.   reverse(mas,0,mas.size()-1); 

1.2.12 (Схема Горнера)
  1. int res = a[0];
  2. for (int i=0;i<n-1;i++)
  3.   res = res * x + a[i+1];

1.2.17 (Количество уникальных общих элементов в двух строго возрастающих массивах)
  1. vector<int> a,b;
  2. . . .
  3. int commonAmount = 0;
  4. int posA = 0, posB = 0;
  5. while (posA < a.size() && posB < b.size())
  6. {
  7.   if (a[posA] == b[posB])
  8.   {
  9.     commonAmount++;
  10.     posA++;
  11.     posB++;
  12.   }
  13.   else if (a[posA] < b[posB])
  14.     posA++;
  15.   else
  16.     posB++;
  17. }

Данная задача имеет похожую природу, что и процедура слияния двух массивов в MergeSort

1.2.18 (Количество уникальных общих элементов в двух неубывающих массивах)

  1. vector<int> a,b;
  2. . . .
  3. int commonAmount = 0;
  4. int posA = 0, posB = 0;
  5. while (posA < a.size() && posB < b.size())
  6. {
  7.   if (a[posA] < b[posB])
  8.     posA++;
  9.   else if (a[posA] > b[posB])
  10.     posB++;
  11.   else
  12.   {
  13.     posA++; posB++;
  14.     while (posA < a.size() && a[posA] == a[posA-1])
  15.       posA++;
  16.     while (posB < b.size() && b[posB] == b[posB-1])
  17.       posB++;
  18.     commonAmount++;
  19.   }
  20. }

1.2.19 (Количество различных уникальных элементов в двух неубывающих массивах)
Решение
 
1.2.20 (Объединить два упорядоченных массива в один)
Модификация функции merge в
MergeSort
 

1.2.21 (Пересечение двух неубывающих массивов)
Решение

1.2.22
1.2.23
 
1.2.24
1.2.25
1.2.26
1.2.27
1.2.28
1.2.29
1.2.31
1.2.32
1.2.33 (Голландский флаг)
1.2.34
1.2.35
1.2.36

Комментариев нет:

Отправить комментарий