ЗАНЯТИЕ
4
1. Массивы: определение, инициализация, обработка. Строка как массив символов.
2. Элементарные вычисления: набор задач.
3. Задачи
http://acm.uva.es/problemset:
591 (Коробка с кирпичами), 10035
(Простая арифметика), 10055 (Хашмат –
смелый воин), 10071 (Назад к школьной физике), 10300 (Экологическая премия), 10302 (Суммирование полиномов), 10370 (Больше
среднего), 10499 (Земля праведности), 11172 (Операторы сравнения).
1.
МАССИВЫ
Массивом называется индексируемый список данных одного типа.
Любой массив объявляется следующим образом:
<тип
данных> <имя>[ <размер>];
где <тип данных> – тип данных
элементов массива, <имя> – имя массива, <размер> – количество
элементов типа <тип данных>, содержащихся в массиве <имя>.
Индексация массива в языке Си начинается с
нуля. То есть первой (начальной) ячейкой является ячейка с нулевым индексом.
Последней в массиве будет ячейка с индексом <размер> – 1. Например,
директива
int
m[5];
объявляет целочисленный массив m. Он имеет 5
целочисленных ячеек, к которым можно обращаться при помощи функции
индексирования: m[0], m[1],
m[2], m[3], m[4]:
|
m[0] |
m[1] |
m[2] |
m[3] |
m[4] |
Инициализировать массив данными можно при его объявлении.
Например, директива
double
f[5] = {1.0,0.4,0.2,-4.55,10};
объявляет вещественный массив f из 5
элементов и заносит в его ячейки соответствующие значения:
|
индекс i |
0 |
1 |
2 |
3 |
4 |
|
значение f[i] |
1.0 |
0.4 |
0.2 |
-4.55 |
10.0 |
При инициализации размер массива можно не
указывать, то есть следующее объявление корректно:
double
f[] = {1.0,0.4,0.2,-4.55,10};
Пример
1.1. Создать массив m
длины 100, занести в его i - ую
ячейку значение i2 и найти
сумму значений всех ячеек.
#include <stdio.h>
int m[100];
int s, i;
void main(void)
{
for(i = 0;i < 100; i++) m[i] = i*i;
for(s = i = 0; i < 100; i++) s += m[i];
printf("%d\n",s);
}
Объявляем глобальную переменную m – массив
длины 100. В первом цикле for заносим в каждую ячейку
значение, равное квадрату ее индекса. Во втором цикле подсчитываем сумму всех
чисел в массиве.
Пример
1.2. Объявить и
инициализировать данными целочисленный, символьный и вещественный массивы. При
помощи цикла вывести данные объявленных массивов.
#include <stdio.h>
int i, m[] = {1,2,3,4,5};
char stroka[] = "This
is a cat";
double f[] = {1.0,0.4,0.2,-4.55,10};
void main(void)
{
for(i = 0; i < 5; i++) printf("%d ",m[i]);
printf("\n%s\n",stroka);
for(i = 0; i < 5; i++) printf("%lf ",f[i]);
printf("\n");
}
Массив символов называют строками.
Строки можно выводить посимвольно при помощи цикла, но такой вывод не
эффективен. Для вывода строк следует воспользоваться форматом вывода “%s”.
Запомнить!
Формат вывода строк имеет
вид “%s”.
Пример
1.3. Массив m длины 10
содержит некоторые числа. Найти наименьший элемент в массиве m длины 100.
#include <stdio.h>
int i, min;
int m[] = {6, 88, 44, 33, 3, 56, 233, 231, 6654, 34};
void main(void)
{
min = m[0];
for(i = 1; i < 10; i++)
if (m[i]
< min) min = m[i];
printf("%d\n",min);
}
В переменной min будем находить наименьший элемент массива. Присвоим изначально
ей значение m[0]. Проходим по остальным элементам массива слева направо и для
каждого значения m[i], меньшего min, полагаем min = m[i].
Упражнение
1.1. Имеется массив длины n. Найти его наименьший и наибольший элемент,
выполнив наименьшее количество сравнений.
Упражнение 1.2 [Вальядолид, 591]. Коробка с кирпичами. Играя с кирпичами, Боб выстраивает стопки разной
высоты. Алиса хочет переложить минимальное количество кирпичей так, чтобы все
стопки имели одинаковую высоту.
Вход.
Состоит из нескольких тестов. Первая строка каждого теста содержит количество
стопок n. Во второй строке следуют n чисел – высоты стопок hi
. Известно, что 1 £ n £ 50, 1 £ hi
£ 100. Общее
количество кирпичей всегда делится на количество стопок. Признак конца входных
данных n = 0.
Выход. Для каждого теста вывести его номер и сообщение ‘The minimum number of
moves is k.’, где k – минимальное количество
кирпичей которое надо переложить, чтобы уравнять стопки. После каждого теста
выводить пустую строку.
|
Пример входа |
Пример выхода |
6 |
Set #1 |
5 2 4 1 7 5 |
The minimum number of moves is 5. |
0 |
|
Упражнение 1.3 [Вальядолид, 10370]. Больше среднего. В классе учится n учеников. Известны их аттестационные оценки по 100 бальной шкале (от 0 до 100 включительно). Вычислить процент учеников, имеющих бал выше среднего.
Вход. Первая строка содержит
количество тестов. Каждый тест располагается в отдельной строке. Первым числом
каждого теста является количество учеников в классе n (1 £ n £ 1000). Далее следуют n
чисел – аттестационные оценки учеников.
Выход. Для каждого теста вывести в отдельной строке процент учеников, имеющих
бал выше среднего. Ответ округлять до 3 десятичных знаков.
|
Пример входа |
Пример выхода |
|
5 |
40.000% |
|
5
50 50 70 80 100 |
57.143% |
|
7
100 95 90 80 70 60 50 |
33.333% |
|
3
70 90 80 |
66.667% |
|
3
70 90 81 |
55.556% |
|
9
100 99 98 97 96 95 94 93 91 |
|
2. ЭЛЕМЕНТАРНЫЕ ВЫЧИСЛЕНИЯ
В этом разделе предлагается
решить набор задач, связанный с элементарными математическими вычислениями.
Упражнение
2.1 [Вальядолид, 10035]. Простая
арифметика. Вычислить
количество переносов при сложении двух целых чисел.
Вход. Каждая строка содержит два целых
числа, состоящих из не более, чем 10 знаков. Последняя строка содержит два нуля
и не обрабатывается.
Выход. Для каждого теста вывести количество переносов при сложении входных чисел
в соответствии с форматом, приведенном ниже.
|
Пример входа |
Пример выхода |
|
123 456 |
No carry
operation. |
|
555 555 |
3 carry
operations. |
|
123 594 |
1 carry
operation. |
|
0 0 |
|
Упражнение
2.2 [Вальядолид, 10055]. Хашмат – смелый воин. Хашман – смелый воин. В начале битвы он подсчитывает
разницу между числом его воинов и воинов противника. В зависимости от значения
этой разницы Хашмат решает – начинать битву или нет.
Вход. Каждая строка содержит два целых
числа – количество воинов армии Хашмата и число воинов армии его оппонента.
Входные числа не более 232.
Выход. Для каждого теста вывести положительную разницу между количеством воинов
армии Хашмата и армии врага.
|
Пример входа |
Пример выхода |
|
10 12 |
2 |
|
10 14 |
4 |
|
100 200 |
100 |
Упражнение
2.3 [Вальядолид, 10071]. Назад к школьной физике. Некоторая частица обладает постоянным ускорением. В
некоторый момент времени t ее скорость равна v. Какое расстояние пройдет частица, когда наступит момент времени 2t?
Вход. Каждая строка содержит скорость
частицы v (-100 £ v £ 100) и время t (0 £ t £ 200), за которое частица достигла этой скорости.
Выход. Для каждого теста вывести расстояние, на которое переместится
частица через время 2t.
|
Пример входа |
Пример выхода |
|
0 0 |
0 |
|
5 12 |
120 |
Упражнение
2.4 [Вальядолид, 10300]. Экологическая премия. Фермер владеет полем,
на котором пасутся животные. Известен размер поля a, количество животных
b на нем и уровень
средств производства c. Из государственного
бюджета фермер получает помощь, которая вычисляется следующим образом: за
каждое животное фермер получает количество денег, равное среднему количеству
занимаемых животным
метров
на поле, умноженному на уровень средств производства. Вычислить сумму общей
государственной помощи для
всех фермеров.
Вход. Первая строка содержит
количество тестов n (n < 20). Первая строка каждого теста
содержит число фермеров f (0 < f < 20) в стране. Следующие f строк содержат значения a,
b, c (0 £
a, b, c £ 10000) для каждого фермера.
Выход. Для каждого теста вывести сумму общей государственной помощи для всех фермеров.
|
Пример входа |
Пример выхода |
3 |
38 |
5 |
86 |
1 1 1 |
7445 |
2 2 2 |
|
3 3 3 |
|
2 3 4 |
|
8 9 2 |
|
3 |
|
9 1 8 |
|
6 12 1 |
|
8 1 1 |
|
3 |
|
10 30 40 |
|
9 8 5 |
|
100 1000 70 |
|
Упражнение
2.5 [Вальядолид, 10302]. Суммирование полиномов. Для заданного x вычислить сумму 1 + 8 + 27 + ... + x3.
Вход. Каждая строка содержит число x
(1 £ x £ 50000).
Выход. Для каждого x вывести в отдельной строке значение указанной выше
суммы.
|
Пример входа |
Пример выхода |
1 |
1 |
2 |
9 |
|
3 |
36 |
Упражнение
2.6 [Вальядолид, 10499]. Земля
праведности. При покупке - продаже товаров объем, как правило,
выступает стоимостной величиной. Например, если арбуз разделить на несколько
частей, то сумма этих частей стоит столько же, сколько и весь арбуз. Математики
предложили правительству в качестве стоимостной величины считать не объем
товара, а площадь полной поверхности.
Сфера делится на n равных
частей – долек. Какую прибыль в процентах получит математик, если он купит сферу целиком, а продаст ее
отдельно по долькам?
Вход. Каждая строка содержит значение n
(0 < n < 231) – количество равных долек на которое
разрезается сфера, n = -1
является признаком конца входных данных.
Выход. Для каждого теста вывести в отдельной строке прибыль математика в
процентах, округлив ее до ближайшего целого.
|
Пример входа |
Пример выхода |
2 |
50%
|
2 |
50%
|
-1 |
|
Упражнение 2.7 [Вальядолид,
11172]. Операторы сравнения. В задаче требуется сравнить
два числа и вывести соответствующий знак
реляционного отношения.
Вход. Первая строка содержит
количество тестов (не более 15). Каждая следующая строка содержит два
числа a и b (|a|, |b| <
1000000001).
Выход. Для каждого теста вывести соответствующий знак реляционного отношения.
|
Пример входа |
Пример выхода |
|
3 |
< |
|
10 20 |
> |
|
20 10 |
= |
|
10 10 |
|
УКАЗАНИЯ К РЕШЕНИЮ УПРАЖНЕНИЙ
Упражнение
1.1. Можно отдельно найти
наибольший и наименьший элементы, потратив на это 2*n операций. Покажем, как решить поставленную задачу за время 3*n / 2.
Заведем две переменные min и max, в которых
будем вычислять соответственно наименьший и наибольший элемент массива. Будем
просматривать входной массив слева направо, сравнивая соседние пары чисел.
Меньшее число из пары сравниваем с min,
большее – с max. Таким образом, для
одновременного нахождения минимума и максимума для двух элементов достаточно 3
сравнений. Разделив n входных чисел
на n / 2 пар, и совершив описанную
процедуру сравнения для каждой пары, найдем наименьший и наибольший элементы
всего массива за 3*n / 2 сравнений.
#include <stdio.h>
int i,min,max,mn,mx,n=11;
int m[] =
{6,88,44,33,3,56,233,231,6654,34,5};
void minmax(int
a, int b, int
*min, int *max)
{
*min = (a > b) ? b : a;
*max = (a > b) ? a : b;
}
void main(void)
{
min = max = m[0];
if (n % 2) i
= 1; else i = 0;
for(; i < n; i += 2)
{
minmax(m[i],m[i+1],&mn,&mx);
if (mn <
min) min = mn;
if (mx >
max) max = mx;
}
printf("%d
%d\n",min,max);
}
Упражнение
1.2 [Вальядолид, 591]. Коробка с кирпичами. Вычисляем общее количество кирпичей и делим его на
количество стопок. Получаем высоту уравненных стопок s. Для решения
задачи следует переложить все кирпичи со стопок, высоты которых больше s
в стопки с высотами меньше s. Количество перекладываемых кирпичей равно
Пример. Данные теста показаны на рисунке выше. Для уравнивания
стопок следует переложить 1 кирпич с первой стопки во вторую, 1 кирпич с шестой
стопки во вторую и 3 кирпича с пятой стопки в четвертую. Всего необходимо
переложить 5 кирпичей.
Реализация. Переменная c содержит номер текущего теста.
Читаем значение n, высоты стопок в массив m[50] и вычисляем общее
количество кирпичей summa.
c = 1;
while(scanf("%d",&n),n > 0)
{
summa = res = 0;
for(i = 0; i < n; i++)
{
scanf("%d",&m[i]);
summa += m[i];
}
Полученную сумму делим на n,
получаем количество кирпичей, которое должно находиться в каждой уравненной
стопке.
summa = summa / n;
Вычисляем минимальное количество кирпичей,
которое следует переложить для уравнивания стопок, и печатаем ответ. После
каждого теста выводим пустую строку.
for(i = 0; i < n; i++)
if (m[i]
> summa) res += (m[i] - summa);
printf("Set
#%d\nThe minimum number of moves is %d.\n\n",c++,res);
}
Упражнение
1.3 [Вальядолид, 10370]. Больше среднего. Вычислим средний бал, поделив сумму балов на количество
учеников. Далее вычислим количество учеников, чей бал выше среднего, а также
процентную часть, которую они составляют от всех учеников в классе.
Пример. Для первого
теста сумма балов равна 50 + 50 + 70 + 80 + 100 = 350, средний бал равен 350 /
5 = 70. Количество учеников, имеющих бал строго выше 70, равно 2 (это ученики,
получившие 80 и 100 балов). В процентном соотношении 2 ученика от 5 составляют
2 * 100 / 5 = 40%.
Реализация. Читаем количество учеников n и их оценки. Параллельно вычисляем сумму балов. Разделив сумму
балов на количество учеников, получаем средний бал average.
scanf("%d",&n); average = 0;
for(i = 0; i < n; i++)
{
scanf("%d",&a[i]);
average += a[i];
}
average /= n;
Подсчитываем количество учеников с,
чей бал строго выше среднего. Вычисляем, сколько процентов составляют с учеников от n и выводим
ответ.
c = 0;
for(i = 0; i < n; i++)
if (a[i] >
average) c++;
res = 100.0 * c / n;
printf("%.3lf%%\n",res);
Упражнение
2.1 [Вальядолид, 10035]. Простая
арифметика. Складываем два
числа в столбик, подсчитываем количество переносов.
Реализация.
Поскольку числа содержат до 10 знаков включительно, слагаемые a и b
будем держать в переменных типа long long. В переменной carry храним текущий перенос (0 или 1), в res подсчитываем общее число переносов.
long long
a, b;
int carry, res;
Читаем входные слагаемые a и b,
обнуляем carry и res. Складываем две последние цифры чисел a и b со значением
переноса. Если оно больше 9, то перенос в текущем разряде присутствует, положим
carry = 1. Иначе сбрасываем carry = 0. Делим оба слагаемых на 10,
тем самым переходя к сложению цифр следующего разряда. Процесс сложения
продолжается, пока оба числа содержат в своей записи хотя бы одну цифру.
while(scanf("%lld
%lld",&a,&b),a+b>0)
{
res = carry = 0;
while((a >
0) || (b > 0))
{
if (a%10 +
b%10 + carry > 9)
{
carry = 1; res++;
}
else carry
= 0;
a /= 10; b /= 10;
}
}
Упражнение
2.2 [Вальядолид, 10055]. Хашмат – смелый воин. Вычислим положительную разницу между количеством воинов
армий и выведем ее.
Реализация. Поскольку число воинов армий не более 232,
то их разница может не поместиться в тип int. Используем 64-битовый
целочисленный тип long long. Читаем входные значения, находим и выводим их
положительную разницу.
long long
a,b,res;
while(scanf("%lld
%lld",&a,&b) == 2)
{
res = (a < b) ? b - a : a - b;
printf("%lld\n",res);
}
Упражнение
2.3 [Вальядолид, 10071]. Назад к школьной физике. Пусть а – ускорение частицы. Путь, пройденный
частицей за время t, равен s = at2 / 2. Скорость частицы в момент времени t равна v = at. В момент t’ = 2t частица пройдет путь s = at’2 / 2 = a * 4t2
/ 2 = 2 * at * t = 2vt.
Реализация. Читаем входные значения v, t. Путь,
который пройдет частица до момента времени 2t, равен s = 2vt.
while(scanf("%d
%d", &v,&t) == 2)
printf("%d\n",2*v*t);
Упражнение
2.4 [Вальядолид, 10300]. Экологическая премия. Каждое животное в среднем занимает
a / b метров. За каждое животное фермер
получит из государственного бюджета (a / b) * c денег. Поскольку фермер владеет b животными, то за них он получит
помощь, равную (a / b) * c * b = a * c. Остается просуммировать помощь
для всех фермеров.
Пример. В первом тесте описываются данные для 5 фермеров. Сумма помощи равна 1 * 1
+ 2 * 2 + 3 * 3 + 2 * 4 + 8 * 2 = 1 + 4
+ 9 + 8 + 16 = 38.
Реализация. Читаем число тестов. Для каждого теста читаем
количество фермеров и данные про них, суммируем государственную помощь для
каждого фермера в переменной sum и выводим результат.
scanf("%d",&tests);
while(tests--)
{
scanf("%d",&f);
sum = 0;
while(f--)
{
scanf("%d
%d %d",&a,&b,&c);
sum += a * c;
}
printf("%d\n",sum);
}
Упражнение
2.5 [Вальядолид, 10302]. Суммирование полиномов. Значение суммы вычислим по формуле: 1 + 8 + 27 + ... + x3
= (1 + 2 + …. + x)2 = 
.
Пример. Для x = 3 имеем: 1 + 8 + 27 = (1 + 2 + 3)2 = 62
= 36, что верно.
Реализация. Поскольку x £ 50000,
то вычисления следует проводить в 64-битных целых числах. Объявим переменные:
long long n,res;
Основной цикл программы состоит
из чтения числа x, вычисления суммы по выше приведенной формуле и печати
результата.
while(scanf("%lld",&n)
== 1)
{
res = n * (n + 1) / 2;
res = res * res;
printf("%lld\n",res);
}
Упражнение 2.6 [Вальядолид, 10499].
Земля праведности. Стоимость целой сферы радиуса r
равна площади ее полной поверхности 4pr2. Площадь полной поверхности n
долек равна площади полной поверхности сферы плюс n площадей кругов
радиуса r: 4pr2 + pr2n.
Прибыль
математика в процентах составит
= 
= 25n %
Заметим, что при n = 1
математик не получит прибыль, так как площадь покупаемой полной поверхности
сферы равна площади продаваемой.
Пример. Рассмотрим случай n = 2. По выше приведенной
формуле вычислим прибыль. Она равна 25 * 2 % = 50%.
Реализация. Поскольку n < 231, то значение
25n может быть больше 231. Вычисления следует производить с
64 - разрядными целыми числами (числами типа long long). Читаем входное
значение n. Если оно равно 1, то прибыль составит 0 %, иначе 25n %.
long long
n;
while (scanf("%lld",&n),
n >= 0)
{
if (n == 1)
printf("0%%\n");
else
printf("%lld%%\n",25*n);
}
Упражнение
2.7 [Вальядолид, 11172]. Операторы сравнения. Для решения
задачи достаточно читать и сравнивать пары чисел a и b, после чего
выводить соответствующий символ операции сравнения.
Реализация. Читаем количество тестов tests. Для каждого теста читаем входные значения a и b.
Сравниваем их и выводим соответствующий символ операции сравнения.
scanf("%d",&tests);
while(tests--)
{
scanf("%d
%d",&a,&b);
if (a < b)
printf("<\n"); else
if (a > b)
printf(">\n"); else
printf("=\n");
}