Массивы

Обработка массивов требует от приматов внимательности и тщательности

Обработка массивов требует от приматов внимательности и тщательности

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

Размер массива обычно будет читаться из входного потока. Это вынуждает использовать динамические массивы. В качестве заготовки можно использовать такой код:

Выполнить программу
Обратите внимание, что цикл в котором вводятся или изменяются элементы массива лучше не использовать для его печати. Изменять отдельно, а печатать — отдельно. Это позволит избежать неприятных ошибок, когда в массиве оказывается совсем не то, что вы предполагали, глядя на распечатку.

При работе с массивами можно использовать расширение GNU С++ для работы с массивами переменной длины (VLA= Variable Lenght Array), которое вероятно будет введено в следующий стандарт С++ (пока входит в стандарт С, начиная с С99). Собственно, длина этих массивов конечно не изменяется в процессе работы программы. Такое название они получили из-за того, что размер массива задаётся не при помощи константного выражения, а некоторой переменной, значение которой на этапе компиляции ещё неизвестно. Например, читается с клавиатуры перед описанием (созданием) массива.
Даже в случаях, когда существует специальная переменная, хранящая количество элементов массива, в циклах желательно вычислять его, а не использовать эту переменную. Простой заготовкой для программ этого раздела может послужить следующий код:

Выполнить программу

Обратите внимание на использование типа size_t для размера и счётчика элементов массива. Этот беззнаковый целочисленный тип данных описанный в std специально определён таким образом, чтобы гарантировано подходить для любого, даже очень большого массива.

Если индекс элемента массива в вашем алгоритме не имеет какого-либо важного значения, то можно использовать так называемые циклы «for each»:

Выполнить программу

Обратите внимание на знак & в 8-й строке. Вы помните, что это означает? Да, ссылка на элемент массива. Без этого значка все изменения, которые вы будете производить с переменной а никак не отразятся на элементах массива. Это происходит потому, что переменная цикла получит только копию значений элементов массива, но не сам элемент.
Обратите внимание на описатель auto. Тип переменной а будет получен (выведен) автоматически из типа массива. Это означает, что при изменении типа массива, скажем на int или long, в циклах ничего менять не придётся.

Для проверки усвоения материала попробуем решить задачу, которая у нас была в классе.
Задача 1 Напечатайте количество каждой из прописных букв (от a до z) в монологе Гамлета из третьего акта одноименной пьесы Уильяма Шекспира.
Примечание: Не используйте перевод.

Оригинальный текст монолога Гамлета

To be, or not to be? That is the question—
Whether ’tis nobler in the mind to suffer
The slings and arrows of outrageous fortune,
Or to take arms against a sea of troubles,
And, by opposing, end them? To die, to sleep—
No more—and by a sleep to say we end
The heartache and the thousand natural shocks
That flesh is heir to—’tis a consummation
Devoutly to be wished! To die, to sleep.
To sleep, perchance to dream—ay, there’s the rub,
For in that sleep of death what dreams may come
When we have shuffled off this mortal coil,
Must give us pause. There’s the respect
That makes calamity of so long life.
For who would bear the whips and scorns of time,
Th’ oppressor’s wrong, the proud man’s contumely,
The pangs of despised love, the law’s delay,
The insolence of office, and the spurns
That patient merit of th’ unworthy takes,
When he himself might his quietus make
With a bare bodkin? Who would fardels bear,
To grunt and sweat under a weary life,
But that the dread of something after death,
The undiscovered country from whose bourn
No traveler returns, puzzles the will
And makes us rather bear those ills we have
Than fly to others that we know not of?
Thus conscience does make cowards of us all,
And thus the native hue of resolution
Is sicklied o’er with the pale cast of thought,
And enterprises of great pith and moment
With this regard their currents turn awry,
And lose the name of action.—Soft you now,
The fair Ophelia!—Nymph, in thy orisons
Be all my sins remembered.

Современный вариант монолога Гамлета
Современный вариант монолога Гамлета из одноименной пьесы.

The question is: is it better to be alive or dead? Is it nobler to put up with all the nasty things that luck throws your way, or to fight against all those troubles by simply putting an end to them once and for all? Dying, sleeping—that’s all dying is—a sleep that ends all the heartache and shocks that life on earth gives us—that’s an achievement to wish for. To die, to sleep—to sleep, maybe to dream. Ah, but there’s the catch: in death’s sleep who knows what kind of dreams might come, after we’ve put the noise and commotion of life behind us. That’s certainly something to worry about. That’s the consideration that makes us stretch out our sufferings so long. After all, who would put up with all life’s humiliations—the abuse from superiors, the insults of arrogant men, the pangs of unrequited love, the inefficiency of the legal system, the rudeness of people in office, and the mistreatment good people have to take from bad—when you could simply take out your knife and call it quits? Who would choose to grunt and sweat through an exhausting life, unless they were afraid of something dreadful after death, the undiscovered country from which no visitor returns, which we wonder about without getting any answers from and which makes us stick to the evils we know rather than rush off to seek the ones we don’t? Fear of death makes us all cowards, and our natural boldness becomes weak with too much thinking. Actions that should be carried out at once get misdirected, and stop being actions at all. But shh, here comes the beautiful Ophelia. Pretty lady, please remember me when you pray.

Решение
Выполнить программу
Этот короткий, но не самый лучший код обладает «потенциалом» — он поможет в решении следующей задачи.

Задача 2 Сосчитайте относительные частоты встречаемости букв в тексте. Частоты прописных и строчных букв следует объединить. Выведите их в порядке убывания частот.

Задача 3 На основе предыдущей составьте программу, которая считала бы относительные частоты встречаемости букв в двух различных литературных произведениях и оцените степень различия результатов по формуле [latex]\sqrt{\frac{1}{n}\sum_{i=1}^{n}{\left( x_{i} — y_{i} \right)^{2}}}[/latex].
Запустите программу для всех пар произведений из следующего списка:

  1. У.Шекспир. Гамлет (англ.)
  2. У.Шекспир. Ромео и Джульета (англ.)
  3. Слово о полку Игореве в переводе на английский язык В.Набокова
  4. В.Набоков. Прозрачные вещи (англ.)

Ответьте на вопросы:

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

Решения задач

  • A302. Количество различных цифр числа в его десятичной записи
    Опубликовал 09/05/2017 Андреев Даниил

    Задача Дано натуральное число . Сколько различных цифр встречается в его десятичной записи? Входные данные Натуральное число . Выходные данные Количество различных цифр . Тесты Входные данные Выходные ...

  • AL1
    Опубликовал 13/09/2016 Станислав Коциевский

    Условие задачи Вводится последовательность, состоящая из ...

  • e-olimp 1310. Наибольший блок
    Опубликовал 28/06/2016 Аня Шохина

    Задача Блоком строки . ...

  • e-olymp 138. Банкомат
    Опубликовал 20/09/2015 Женя Максимова

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

  • e-olymp 1503. Вписанные треугольники
    Опубликовал 26/01/2018 Мороз Дима

    Задача На границе окружности с центром в начале координат и радиусом $r$ заданы $n$ различных точек. Поскольку все точки расположены на одной ...

  • e-olymp 179. Распределение
    Опубликовал 30/12/2017 Даниил Крутоголов

    Распределение Для нападения на некоторые поселения людей, эльфов и карликов вождь Орды Оргрим Думхаммер сформировал из всех имеющих в наличии воинов ...

  • e-olymp 203. Кубики-2
    Опубликовал 02/01/2018 Данила Савчак

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

  • e-olymp 2261. Защита королевства
    Опубликовал 20/05/2018 Иван Мясоедов

    Защита королевства Теодор реализует новую стратегию игры «Оборона Царства». На каждом уровне игрок защищает королевство, которое представлено прямоугольной сеткой ячеек. В ...

  • e-olymp 239. Треугольники
    Опубликовал 19/05/2018 Андрей Святозар Чернецкий

    Задача На плоскости задано — количество ...

  • e-olymp 2670.Координаты соседей
    Опубликовал 20/06/2018 Илья Черноморец

    Задача Для клетки с координатами $\left(x, y\right)$ в таблице размером $M\times N$ выведите координаты ее соседей. Соседними называются клетки, имеющие общую ...

  • e-olymp 47. Паркет из треугольников
    Опубликовал 24/06/2018 Артем Чернобровкин

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

  • e-olymp 50. Разрезанное число
    Опубликовал 25/06/2018 Алиса Ворохта

    Задача Василий на бумажке в виде полоски написал число, кратное $d$. Его младший брат Дмитрий разрезал число на $k$ частей. Василий ...

  • e-olymp 54. Мурзик
    Опубликовал 27/06/2018 Данилов Андрей

    Задача Весна… Прекрасное время! Все, казалось бы оживает и двигается, расцветает, начинается новый проход цикла жизни. И общеизвестный Мурзик не является ...

  • e-olymp 6. Путёвки
    Опубликовал 21/12/2015 Александр Коломеец

    Постановка задачи e-olymp 6. Путёвки Туристическая фирма не успела из-за больших морозов продать ) путёвок на горнолыжные базы, срок ...

  • e-olymp 634. Вклад «Антикризисный»
    Опубликовал 26/06/2018 Яна Колчинская

    Задача Постоянные клиенты одного очень крупного банка (ООКБ) недавно получили возможность открыть новый вклад — «Антикризисный». Этот вклад отличается непростой схемой ...

  • e-olymp 7492. Будильник
    Опубликовал 07/05/2018 Георгий Мартынюк

    Задача Алиса любит свой цифровой будильник. Она устанавливает его каждый вечер. Прошлой ночью Алисе приснились ее часы. К сожалению, единственное, что ...

  • e-olymp 7809. Утренняя зарядка
    Опубликовал 25/04/2018 Валерия Ларикова

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

  • e-olymp 84. Transfer
    Опубликовал 26/05/2018 Костя Григорян

    Task Vasya has one package of mobile phone operator Ratsviyk and $S_0$ tugriks on its account. (Tugrik is the currency in ...

  • e-olymp 88. Месть Ли Чака
    Опубликовал 04/02/2018 Кирилл Волков

    Задача “Я хочу быть пиратом!” Мы напоминаем эту известную фразу Гайбраша Трипвуда из серии компьютерных игр Monkey Island («Остров Обезьян»). Гайбраш ...

  • e-olymp 9. N-значные числа
    Опубликовал 02/01/2018 Андрей Лисовой

    Задача Найти количество N ...

  • e-olymp 907. Первый не больший чем 2.5
    Опубликовал 22/04/2018 Карина Миловская

    Задача Задан массив вещественных чисел. Найти первый элемент массива, значение которого не превышает 2.5. Входные данные В первой строке задано количество элементов массива ...

  • e-olymp 921. Отрицательные элементы
    Опубликовал 13/05/2018 Иван Мясоедов

    Отрицательные элементы Задан одномерный массив вещественных чисел длины . Определить сумму и количество отрицательных элементов в массиве. Входные данные: В первой строке задано ...

  • e-olymp 922. Сдвинь элементы
    Опубликовал 15/05/2018 Иван Василевский

    Условие задачи Задан массив целых чисел длины шаг. Входные данные В первой строке задано количество ...

  • e-olymp 930. Номер мобильного телефона
    Опубликовал 09/06/2018 Томас Пасенченко

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

  • А290
    Опубликовал 08/11/2016 Сабиров Ильдар

    Задача. Даны действительные числа по правилу: если они оба отрицательны, то каждый ...

  • А404
    Опубликовал 29/06/2015 Танащук Григорій Русланович

    Задача: Даны натуральные числа -й ...

  • А409
    Опубликовал 14/03/2015 Осецимський Анатолій Вадимович

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

  • А410в
    Опубликовал 11/12/2014 Нарусевич Никита Мирославович

    Дана целочисленная матрица; Матрица Результат 4 1 4 6 -5 -120 5 7 8 7 1960 1 2 5 9 90 5 5 0 3 0   C++ 123456789101112131415161718192021222324 #include <iostream>using namespace std; int main() { int n; cin >> n; int a; for(int ...

  • А410е
    Опубликовал 25/12/2014 Носуленко Марк

    Дана целочисленная матрица . Исходя из задачи ...

  • А99
    Опубликовал 26/11/2014 Щебетовський Дмитро Геннадійович

    Задача: Пусть , b1=v, an=2bk-1+ak-1. bk=2a^2k-1+bk-1, k=2,3… Даны действительные u, v, натуральное n. Найти Е от n при k=1 (ak*bk)/(k+1)! Тесты: N U V Результат Вывод 2 4 3 64 тест пройден 1 4 2 4 тест пройден 2 1 2 4 тест ...

  • Черная пятница
    Опубликовал 06/04/2017 Курьянов Павел

    Разбор задачи с 1/8 ACM ICPC по украинскому региону 25 марта 2017. Задача. Завтра черная пятница — самая большая новогодняя распродажа. ...

  • Ю 4.24
    Опубликовал 20/10/2014 Карташов Денис Геннадійович

                                            ...

  • Ю 4.3
    Опубликовал 03/11/2014 Щебетовський Дмитро Геннадійович

    От каждого из заданных m чисел x1, x2…xm отнять их среднее арифметическое: xср=1/m*(E от m при i=1)*xi; xi=xi-xср, i=1,2,…,m. Тесты:  

  • Ю 4.37
    Опубликовал 23/11/2014 Байков Дмитро

    Задача Автостоп-2. Из пункта А в пункт В, между которыми км/ч. Навстречу ему — из ...

  • Ю4.1
    Опубликовал 03/11/2014 Янішевська Альона Русланівна

    Задача. Разделение по знаку. В массиве С(n) подсчитать количество отрицательных и сумму положительных элементов. Тесты: n Входной массив Кол-во отрицательных элементов Сумма положительных элементов Комментарий 5 1.01 3 ...

  • Ю4.10
    Опубликовал 29/10/2014 Сорокина Полина

    Задача: Найти среднее арифметическое элементов каждой строки матрицы и вычесть его из элементов этой строки. 2 3 4 6 2 5 9 10 0 2 -2 -3 1 2 4 3 -5 -2 -3 6 5 0 -8 9 -64 468 -3 1 -1.66667 1.33333 0.333333 2.33333 1.33333 -3.66667 13 30 -43 312.667 -158.333 -154.333 1 1 8 0 C++: C++ 123456789101112131415161718192021222324252627282930313233 #include <iostream>using ...

  • Ю4.12
    Опубликовал 14/09/2015 Сабиров Ильдар

    Задача: Все ненулевые элементы матрицы и подсчитать их количество. K L Матрица D Ненулевые элементы матрицы E Количество ...

  • Ю4.13
    Опубликовал 22/10/2014 Осецимський Анатолій Вадимович

    Задача. Дан массив . ...

  • Ю4.14
    Опубликовал 16/11/2014 Оніщенко Олександр

    Задача: Элементы заданного массива Тесты:   Вводимые значения Результат Комментарий 6 1 2 3 4 ...

  • Ю4.15
    Опубликовал 21/12/2014 Носуленко Марк

    Заданы массивы . Из выше написанного ясно ...

  • Ю4.16
    Опубликовал 25/11/2014 Недомовний Владислав

    Задача. Все четные элементы целочисленного массива . Подсчитать количество тех и ...

  • Ю4.17
    Опубликовал 05/11/2014 Нарусевич Никита Мирославович

    В массиве . Значение Результат 8   5 3 8 6 ...

  • Ю4.18
    Опубликовал 01/11/2014 Марченко Філіп Олександрович

    Задача: В массиве . Тесты:  Входной ...

  • Ю4.19
    Опубликовал 21/10/2014 Куленюк Денис Віталійович

    Задача. Многочлен . Найти массив коэффициентов производной этого многочлена. 2 0 0 0 0 0 0 2 17 2 3 34 2 0 2 0 -4 1 0 -4 0 Давайте вначале распишем сам многочлен : {P}_{n}(x)={a}_{n}{x}^{n} + ...

  • Ю4.21
    Опубликовал 20/12/2014 Ковальський Олександр Дмитрович

    Задача. Целочисленный массив K(n, n) заполнить нулями и единицами, расположив их в шахматном порядке. Тесты. Ввод Вывод 1 1 3 C++ 123 1 0 1 0 1 0 1 0 1 6 C++ 123456 1 0 ...

  • Ю4.22
    Опубликовал 28/10/2014 Кібакова Надія Олександрівна

    Задача Плюсы и минусы. В массиве найти число чередований знака, то есть число переходов с минуса на плюс ...

  • Ю4.23
    Опубликовал 31/10/2014 Кваша Дар`я Михайлівна

    Латинский квадрат. Латинским квадратом порядка n называется квадратная таблица размером n×n, каждая строка и каждый столбец которой содержит все числа ...

  • Ю4.25
    Опубликовал 27/10/2014 Карагяур Мілан Сергійович

    Задача: Заполнить матрицу заданного размера числами 1,2,3,4 так, чтобы по горизонтали, вертикали и диагонали не было одинаковых рядом стоящих чисел. Output 6 6 1 ...

  • Ю4.26
    Опубликовал 29/10/2014 Калачьов Андрій Сергійович

    Задача: На шахматной доске находятся король и несколько ферзей другого цвета. Проверить, находится ли король под угрозой и если да, ...

  • Ю4.27
    Опубликовал 20/10/2014 Ілларіонова Марія Валеріївна

    Задача Ю4.27. Сессия. Результаты сессии, состоящей из трёх экзаменов, для группы из . Оценка ставится по ...

  • Ю4.28
    Опубликовал 20/10/2014 Іванов Вячеслав Володимирович

    Задача: Каждый из элементов элементов этого массива. Тесты Input Output Result 2 11 7 11 9 Пройден 12 7 4 33 56 22 3 ...

  • Ю4.29
    Опубликовал 27/10/2014 Зелінський Вячеслав Олександрович

    Текущий минимум. Каждый из элементов  элементов этого массива.  Результат: 6 9 7 8 5 14 1 9 7 7 5 5 1 5 3 -2 5 -3 8 3 -2 -2 -3 -3 4 12 0 4 -7 12 0 0 -7 Код программы: C++ 123456789101112131415161718192021 #include <iostream>using namespace ...

  • Ю4.3
    Опубликовал 26/11/2014 Щебетовський Дмитро Геннадійович

    Задача: Центрирование массива. От каждого из заданных чисел x1, x2,…, xn отнять их среднее арифметическое. xср= 1/m E от m при i=1 (x1); ...

  • Ю4.31
    Опубликовал 29/10/2014 Денисова Ольга

    Задача Циклический сдвиг. Осуществить циклический сдвиг элементов массива . ри ...

  • Ю4.32
    Опубликовал 13/11/2014 Григорян Артак

    Суммы по косой. Просуммировать элементы матрицы по каждой из линий , параллельных главной диагонали. Напечатать полученные суммы. Матрица Суммы 1 2 3 4 ...

  • Ю4.33
    Опубликовал 03/11/2014 Вустянюк Ігор Дмитрович

    Задача Для заданной матрицы   \left \| A \right \| = \max_{i=1,m} \sum_{k=1}^{n} \left | ...

  • Ю4.35
    Опубликовал 03/11/2014 Бровко Ілля

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

  • Ю4.36
    Опубликовал 13/11/2014 Божик Семен

    Задача: Гидрологами исследовано течение реки в некотором сечении: произведена серия замеров от одного берега до другого перпендикулярно фарватеру, полученные данные:  — ...

  • Ю4.4
    Опубликовал 13/11/2014 Швандт Максим Альбертович

    Задача: Вычислить среднее значение наблюдений: Тесты:  k x среднее дисперсия  3  4, 5, 8 5,66666666666667  4,333333  5  2, 3, 6, ...

  • Ю4.6
    Опубликовал 04/11/2014 Царев Николай Александрович

     Задача: Угол между векторами Найти угол между векторами       используя формулу: cos\varphi =\cfrac { \left( A,B \right) }{ ...

  • Ю4.7
    Опубликовал 03/11/2014 Фесенко Катерина Володимирівна

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

  • Ю4.8
    Опубликовал 27/06/2015 Танащук Григорій Русланович

    Задача: В массиве C(m) заменить каждый третий элемент полусуммой двух предыдущих, а стоящий перед ним — полусуммой соседних с ним элементов. Тест: Количество ...

  • Ю4.9
    Опубликовал 27/11/2014 Стеблинський Ігор Віталійович

    Задача: В матрице  все ненулевые элементы заменить обратными по величине  и противоположными по знаку. Тесты: n m Введенная матрица Полученная матрица 3 4 2 0 3 6 1 0 ...

Добавить комментарий