Тема 1.3. Массивы

Цель.

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

Основные понятия.

Массив – упорядоченное множество однотипных элементов, занимающих смежные участки оперативной памяти. Они используются в тех случаях, когда элементы последовательности должны обрабатываться не в том порядке, в котором поступают в программу, или каждый элемент должен обрабатываться (просматриваться) несколько раз. Имя массива ассоциируется с адресом начала массива (первого элемента). Этот адрес является постоянным. Основная операция над массивами – операция доступа к элементу []. Можно использовать значение элемента и можно его изменять. Используя адреса можно обращаться к элементам массива с помощью операции * и операции адресной арифметики.

Ввод и вывод массивов осуществляется поэлементно (для символьных строк – см. ниже).

Ключевые слова.

Массив, индекс, элемент, счётчик, адрес, указатель, NULL, случайное число.

ПРИМЕР 1.

Дан массив целых чисел из N элементов. Для заданных номеров k1 иk2 (1 <= k1 <=k2 <=N) переставить элементы массива отk1-го доk2-го в обратном порядке.

Алгоритм.

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

Решение.

// C++

# include <iostream>

# include <cstdlib>

using namespace std;

const int N = 10000;

int main () // основная часть программы – главная функция

{

setlocale (LC_ALL, "RUS");

cout << "Переворот части массива." << endl;

cout << "Введите количество, а в следующей строке числа." << endl;

int a [N], n;

cin >> n;

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

cin >> a [i];

cout << "С какой позицию по какую: ";

int k1, k2;

cin >> k1 >> k2;

k1--, k2--;

for ( int i=k1, j=k2; i < j; i++, j-- )

swap (a [i], a [j]);

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

cout << a [i] << " ";

cout << endl;

system ("PAUSE");

return 0;

}

// C#

using System;

class Program

{

static void Main (string [] args)

{

Console.WriteLine ("Переворот части массива.");

Console.WriteLine ("Введите количество, а в следующей строке числа.");

int n = int.Parse (Console.ReadLine ());

int [] a = new int [n];

string ss = Console.ReadLine (); // все числа в одной строке

string [] s = ss.Split (' '); //| через один пробел

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

a [i] = int.Parse (s [i]);

Console.WriteLine ("С какой позицию по какую: ");

int k1 = int.Parse (Console.ReadLine ());

int k2 = int.Parse (Console.ReadLine ());

k1--, k2--;

for ( int i=k1, j=k2; i < j; i++, j-- )

{

int temp = a [i];

a [i] = a [j];

a [j] = temp;

}

for ( int i=0; i < n; i++ ) // печатаем числа в одну строку

Console.Write (a [i] + " ");

Console.ReadKey ();

}

}

ПРИМЕР 2.

Заполнить массив случайными целыми числами в диапазоне от 0 до 999 и распечатать его.

Решение.

// C++

# include <iostream>

# include <cstdlib>

using namespace std;

const int N = 1000;

int main ()

{

setlocale (LC_ALL, "RUS");

cout << "Заполнение массива случайными числами." << endl;

cout << "Введите количество элементов." << endl;

int * a, n;

cin >> n;

a = new int [n];

srand (time (0));

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

a [i] = rand () % N;

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

cout << a [i] << " ";

cout << endl;

system ("PAUSE");

return 0;

}

// C#

using System;

class Program

{

static void Main (string [] args)

{

Console.WriteLine ("Заполнение массива случайными числами.");

Console.WriteLine ("Введите количество элементов.");

int n = int.Parse (Console.ReadLine ());

int [] a = new int [n];

// заполнение случайными числами

Random rnd = new Random(DateTime.Now.Millisecond);

//создание генератора случайных чисел и инициализация текущим временем

for ( int i=0; i < a.GetLength (0); i++ )

a [i] = rnd.Next ();

// GetLength(i) возращает длину массива по i-му измерению

for ( int i=0; i < n; i++ ) // печатаем числа в одну строку

Console.Write (a [i] + " ");

Console.ReadKey ();

}

}

Задачи для обязательного решения

1.3.1.1. В массиве переставить элементы в обратном порядке, т.е поменять местами 1-й и последний, 2-й и предпоследний и т.д. В первой строке задаётся размер массива, во второй – сам массив.

Исходные данные:

8

1 3 2 5 7 4 6 8

Результат:

8 6 4 7 5 2 3 1

1.3.1.2. В целочисленном массиве переставить 1-ю и 2-ю половинки (количество элементов чётно). В первой строке задаётся размер массива, во второй – сам массив.

Исходные данные:

8

1 3 2 5 7 4 6 8

Результат:

7 4 6 8 1 3 2 5

1.3.1.3. В целочисленном массиве поменять первые К элементов и оставшиеся. В первой строке задаётся размер массива, во второй – сам массив, в третьей – число К.

Исходные данные:

8

1 3 2 5 7 4 6 8

3

Результат:

5 7 4 6 8 1 3 2

1.3.1.4. Поменять самый большой и самый маленький местами в целочисленном массиве. В первой строке задаётся размер массива, во второй – сам массив.

Исходные данные:

8

3 2 1 5 7 4 6 8

Результат:

3 2 8 5 7 4 6 1

1.3.1.5. Сдвинуть все элементы массива на 1 позицию вперед циклически. В первой строке задаётся размер массива, во второй – сам массив.

Исходные данные:

8

1 3 2 5 7 4 6 8

Результат:

3 2 5 7 4 6 8 1

1.3.1.6. Сдвинуть все элементы на 1 позицию назад циклически. В первой строке задаётся размер массива, во второй – сам массив.

Исходные данные:

8

1 3 2 5 7 4 6 8

Результат:

8 1 3 2 5 7 4 6

1.3.1.7. линейный поиск элемента по значению. Найти и напечатать номер элемента с заданным значением. Если такого нет, то напечатать -1. Нумерация с 0. В первой строке задаётся размер массива, во второй – сам массив, в третьей – искомое значение.

Исходные данные:

8

1 3 2 5 7 4 6 8

5

Результат:

3

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

Исходные данные:

11

1 3 0 2 5 0 0 7 4 6 8

Результат:

1 3 2 5 7 4 6 8 0 0 0

1.3.1.9. Сжать упорядоченный массив (удалить повторяющиеся значения). В конец поместить нули. В первой строке задаётся размер массива, во второй – сам массив.

Исходные данные:

11

1 3 3 3 5 6 6 6 6 7 8

Результат:

1 3 5 6 7 8 0 0 0 0 0

1.3.1.10. Для каждого элемента напечатать в отдельной строке количество положительных и отрицательных чисел, стоящих перед ним. В первой строке задаётся размер массива, во второй – сам массив.

Исходные данные:

5

1 0 -1 0 1

Результат:

0 0

1 0

1 0

1 1

1 1

1.3.1.11. В целочисленном массиве найти значение, которое встречается чаще других. В первой строке задаётся размер массива, во второй – сам массив.

Исходные данные:

11

2 3 0 2 5 0 0 7 4 6 8

Результат:

0

1.3.1.12. В целочисленном массиве найти значение (любое), которое ни разу не встречается. В первой строке задаётся размер массива, во второй – сам массив.

Исходные данные:

11

1 3 0 2 5 0 0 7 -4 6 8

Результат:

-1

1.3.1.13. Проверить, что в массиве целых чисел все элементы различные. Напечатать «ДА» или «НЕТ». В первой строке задаётся размер массива, во второй – сам массив.

Исходные данные:

11

1 3 0 2 5 0 0 7 4 6 8

Результат:

НЕТ

1.3.1.14. Проверить, что в массиве из nцелых чисел встречаются все числа от 1 доnи ровно по одному разу. Напечатать «ДА» или «НЕТ». В первой строке задаётся размер массива, во второй – сам массив.

Исходные данные:

8

1 3 2 5 7 4 6 8

Результат:

ДА

1.3.1.15. Вычислить и напечатать количество различных элементов в заданном целочисленном массиве. В первой строке задаётся размер массива, во второй – сам массив.

Исходные данные:

11

1 3 0 2 5 0 0 7 4 6 8

Результат:

9

1.3.1.16. Заполнить массив случайными целыми числами в диапазоне от -10 до 10 и распечатать его. Размер массива вводится.

Исходные данные:

11

Результат:

-2 3 0 2 5 0 0 7 4 6 8

1.3.1.17. Заполнить массив случайными вещественными числами в диапазоне от -10 до 10 и распечатать его с точностью 3 знака. Размер массива вводится.

Исходные данные:

3

Результат:

-2.123 3.010 2.507

Задачи для самостоятельного решения

1.3.2.1. Рассматриваются все числа от 1 до n. Сколько раз встречается каждая цифра от 0 до 9 во всех этих числах вместе взятых? Вводится натуральное n. Нужно вывести 10 строк по одному числу: количество нулей, единиц и т.д. девяток.

Исходные данные:

17

Результат:

2

9

2

2

2

2

2

2

1

1

1.3.2.2. Вычисление мультиномиального коэффициента (K₁+K₂ +...+K_n)! /K₁! /K₂!... /K_n! В первой строке задаётся количествоn, во второй – сами числаK_1,K₂,...K_n. Все числаK_1,K₂,...K_n- не отрицательные целые числа.

Исходные данные:

3

1 2 3

Результат:

60

1.3.2.3. Написать программу вычисления и печати через пробел всех простых чисел от 1-го (число 2) до К-го

Исходные данные:

13

Результат:

2 3 5 7 11 13 17 19 23 29 31 37 41

1.3.2.4. Написать программу вычисления и печати всех простых чисел от 2 до заданного nметодом решета Эратосфена. В первой строке задаётся число n.

Исходные данные:

13

Результат:

2 3 5 7 11 13

1.3.2.5. Написать программу, которая для заданного массива натуральных чисел печатает их наибольший общий делитель. В первой строке задаётся размер массива, во второй – сам массив.

Исходные данные:

5

12 4 16 8 6

Результат:

2

1.3.2.6. Написать функцию, которая вычисляет и печатает все пары простых чисел-близнецов от 2 до заданного N (их значения отличаются на 2, например, 17 и 19). Пары печатать в отдельных строках.

Исходные данные:

13

Результат:

2 3

3 5

5 7

11 13

1.3.2.7. Написать программу перевода целого числа из десятичной в другую систему счисления и печати его. В первой строке задаётся натуральное число и основание новой системы счисления.

Исходные данные:

1302 8

Результат:

2426

1.3.2.8. Написать программу перевода дробного числа из одной заданной системы счисления в другую и печати его.

1.3.2.9. Напечатать треугольник Паскаля из n строк (значение n вводится).

Исходные данные:

4

Результат:

1

1 1

1 2 1

1 3 3 1

…

1.3.2.10. Для набора целых чисел X1,X2,… …,Xn найти целое значение А такое, что сумма (|X1-A| + |X2-A| + … … + |Xn-A|) минимальна, т.е. такую точку А, до которой сумма расстояний от заданных точек минимальна.В первой строке задаётся размер массива, во второй – сам массив.

Исходные данные:

5

1 7 6 1 2

Результат:

2

1.3.2.11. в подстановке (перестановке 1…n) найти все элементарные циклы.В первой строке задаётся число n, во второй – сама перестановка.

Исходные данные:

5

2 5 4 3 1

Результат:

1 2 5

3 4

1.3.2.12. Дан массив целых чисел. Переставить его элементы так, чтобы они образовывали наименьшее число строго возрастающих цепочек. Каждую цепочку выводить в отдельной строке. Одно число также является возрастающей цепочкой. В первой строке задаётся размер массива, во второй – сам массив.

Исходные данные:

7

3 1 5 3 1 7 1

Результат:

1 3 5 7

1 3

1

1.3.2.13. В массиве из nцелых чисел найти и напечатать элемент, на который делятся все остальные (или напечатать слово «НЕТ»). В первой строке задаётся размер массива, во второй – сам массив.

Исходные данные:

8

1 3 2 5 7 4 6 8

Результат:

1

1.3.2.14. В массиве из nнатуральных чисел найти и напечатать элемент, который делится на все остальные (или напечатать слово «НЕТ»). В первой строке задаётся размер массиваn, во второй строке – сам массив.

Исходный массив:

8

1 3 2 5 7 4 6 8

Результат:

НЕТ

1.3.2.15. Секретное сообщение. На секретную базу в Арктике поступила шифровка – последовательность из n десятичных цифр. Она содержит номер секретной базы в Антарктиде, который является последовательностью из k десятичных цифр. При этом для того, чтобы отличить его от ненужной Вам информации, он повторен в шифровке хотя бы два раза (возможно, эти два вхождения перекрываются). Написать программу, которая по шифровке и длине номера секретной базы определяет, содержит ли шифровка номер базы. Учтите, что у базы может быть несколько номеров, и все они могут быть переданы в шифровке. Первая строка содержит два целых числа: n (1 ≤ n ≤ 10⁵) и k (1 ≤ k ≤ 5) – длину шифровки и длину номера секретной базы соответственно. Вторая строка содержит n цифр – шифровку. Цифры в шифровке не разделяются пробелами. Вывести «YES», если шифровка содержит номер секретной базы, и «NO» в противном случае.

Исходные данные:

13 2 0123400056789

Результат:

YES

1.3.2.16. Сверхпростые числа. Простым числом будем называть натуральное число, большее единицы и делящееся только на единицу и на само себя. Выпишем все простые числа в порядке возрастания и i-ое в этом порядке число обозначим pi (число 2 при этом будет иметь номер 1). Так, например, p₁= 2, p₂= 3, p₃= 5, p₅₂= 239. Скажем, что число p_iявляется сверхпростым, если i = p_kдля некоторого k. Иными словами, сверхпростое число — это простое число, номер которого в списке простых чисел, упорядоченном по возрастанию, является простым числом. Дано натуральное число k (1 ≤ k ≤ 500). Упорядочим все сверхпростые числа по возрастанию. Найдите k-ое сверхпростое число в этом порядке.

Исходные данные:

100

Результат:

3911

1.3.2.17. Дан массив вещественных чисел x₁,x₂,x₃,..,x_N(N=5000). Написать программу, которая вычислит произведение сумм (x₁)(x₂+x₃)(x₄+x₅+x₆)..., где в каждой следующей скобке на одно слагаемое больше, чем в предыдущей, а в последней - все оставшиеся.

Продвинутые задачи

1.3.3.1. Генерировать все перестановки чисел 1…nв лексикографическом порядке по заданному натуральному числуn.

Исходные данные:

3

Результат:

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

1.3.3.2. Найти номер заданной перестановки в лексикографическом порядке. В исходных данных в первой строке задаётся число n, а во второй строке сама перестановка.

Исходные данные:

3

3 1 2

Результат:

5

1.3.3.3. Найти перестановку длины n по её номеру k. Исходные данные число n и номер перестановки k.

Исходные данные:

3 4

Результат:

2 3 1

1.3.3.4. найти следующую перестановку для заданной перестановки чисел 1…n, В первой строке задаётся длина перестановкиn, во второй строке – сама перестановка.

Исходные данные:

3

2 1 3

Результат:

2 3 1

1.3.3.5. найти следующую перестановку для заданной перестановки массива (могут быть одинаковые элементы). В первой строке задаётся длина n, во второй строке – сама перестановка.

Исходные данные:

4

3 1 2 1

Результат:

3 2 1 1

1.3.3.6. В целочисленном массиве найти отрезок с наибольшей суммой и напечатать эту сумму. В первой строке задаётся размер массива n, во второй строке – сам массив.

Исходные данные:

8

1 3 0 -4 2 6 -5 2

Результат:

8

1.3.3.7. Генерировать ряд Фаррея для заданного n – возрастающая последовательность правильных несократимых дробей со знаменателем не большим, чем n. Число n вводится.

Исходные данные:

5

Результат:

1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5

1.3.3.8. Генерировать все цепочки из 0 и 1 длины n. Число n вводится.

Исходные данные:

3

Результат:

000

001

010

011

100

101

110

111

1.3.3.9. генерировать все цепочки из 0 и 1 длины n, в которых нет двух нулей подряд. Число n вводится.

Исходные данные:

3

Результат:

010

011

101

110

111

1.3.3.10. Генерировать все цепочки из 0 и 1 длины n, в которых количество 0 больше чем количество 1. Число n вводится.

Исходные данные:

3

Результат:

000

001

010

100

1.3.3.11.Новобранцы. В одну шеренгу построены новобранцы. Некоторые из них повернуты лицом налево (0), другие – направо (1). По команде кругом для некоторого отрезка все новобранца из этого отрезка поворачиваются в противоположную сторону. За какое наименьшее число команд можно сделать так, чтобы они были повёрнуты в одну сторону. В первой строке задаётся число новобранцев в строю n. Во второй строке записано n чисел 0 и 1 без пробелов. Вывести одно число - ответ на задачу.

Исходные данные:

5

01010

Результат:

2

Примечание. По первой команде развернуть 1 человека на 2-й позиции вправо, по второй команде развернуть 4-го.