Арифметические действия

Научно-технические расчеты - простейшее применение вычислительной техники.

Э. Дейкстра

Выражения. Оператор присваивания

Выражения – это переменные, функции и константы, называемые операндами, объединенные знаками операций.

Операции могут быть унарными – с одним операндом, например, минус; могут быть бинарными – с двумя операндами, например вычитание или умножение.

Оператор присваивания записывает значения выражения в правой части в переменную из левой части.

Пример

int a;

a = 35 * 2 + 1;

int b = a + 4;

Переменная a получила во второй строке фрагмента значение 71, переменной b при инициализации присвоено значение 75.

Оператор присваивания в C/C++ может присвоить значение одного и того же выражения сразу нескольким переменным. Например, фрагмент

int a, b, c = 3;

a = b = c + 5;  // a = 8, b = 8

Арифметические операции

Основные арифметические операции в целых числах:

Знак	Описание	Пример	Значение
+	сложение	int c = 12 + 3;	c = 15
-	вычитание	int c = 12 - 3;	c = 9
*	умножение	int c = 12 * 3;	c = 36
/	деление нацело	int c = 23 / 3;	c = 7
%	получение остатка от деления	int c = 23 % 7;	c = 2

ВАЖНО: Если требуется получить результат обычного, а не целочисленного деления, то первый операнд должен быть вещественного, а не целого типа. Например,

float d;

d = 23 / 3;          // d = 7.0

d = float (23) / 3;  // d = 7.66667

Большинство арифметических и логических операторов в C/C++ поддерживают сокращенную форму записи:

a += b; // то же, что a = a + b;

a -= b; // a = a - b;

a *= b; // a = a * b;

a /= b; // a = a / b;

a %= b; // a = a % b;

a >>= b; // a = a >> b;

a <<= b; // a = a << b;

a &= b; // a = a & b;

a ^= b; // a = a ^ b;

a |= b; // a = a | b;

Задача №2. Два бандита

Бандиты Гарри и Ларри отдыхали на природе. Решив пострелять, они выставили на бревно несколько банок из-под пива (не больше 10). Гарри начал простреливать банки по порядку, начиная с самой левой, Ларри — с самой правой. В какой-то момент получилось так, что они одновременно прострелили одну и ту же последнюю банку.

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

Определите по этим данным, сколько банок не прострелил Гарри и сколько банок не прострелил Ларри.

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

В единственной строке записано 2 числа — количество банок, простреленных Гарри и Ларри соответственно.

Результат

Выведите 2 числа — количество банок, не простреленных Гарри и Ларри соответственно.

Пример

Ввод	Вывод
4  7	6  3

Источник задачи: XII командный чемпионат школьников Свердловской области по программированию (15 октября 2005 года).

Решение

Пусть Ларри прострелил X банок, а Гарри – Y банок. Т.о. всего банок ALL = X + Y - 1

#include <iostream>

using namespace std;

 

int main(int argc, char** argv) {

int x, y;

cin >> x >> y;

cout << y – 1 << " " << x – 1 << endl;

return 0;

}

Задача №3. Метро

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

Входные данные

Три числа: сначала N – общее количество станций кольцевой линии, а затем i и j – номера станции, на которой Витя садится, и станции, на которой он должен выйти. Станции пронумерованы подряд натуральными числами 1, 2, 3, …, N (1-я станция – соседняя с N-й), N не превосходит 100. Числа i и j не совпадают. Все числа разделены пробелом.

Выходные данные

Вывести минимальное количество промежуточных станций (не считая станции посадки и высадки), которые необходимо проехать Вите.

Примеры

№	Ввод	Вывод
1	100  5  6	0
2	10  1  9	1

Решение

#include <iostream>

using namespace std;

int main() {

int n, i, j, i1, j1;

cin >> n >> i1 >> j1;

i = min (i1, j1);

j = max (i1, j1);

cout << min(j - i - 1, i + n - j - 1);

}

Задача №4. Счастливый турист

Как только Счастливый Гарри въезжает в свой любимый кемпинг со всей семьей, он замечает знак: "Палаточное размещение ограничено 5 днями в течение любого 8 дневного периода. Гарри только начинает свой 20 - дневный отдых. Каково максимальное количество дней, когда Гарри может провести свой отпуск в лагере?

Сформулируем задачу в более общем виде. Пусть l, p, v (1< l < p < v) - целые числа. Палаточное размещение ограничено l днями в течение любого p-дневного периода. Счастливый Гарри начинает свой v-дневный отдых. Какое наибольшее число дней своего отпуска Гарри сможет провести в лагере?

Входные данные

Каждый тест состоит из одной строки, содержащей числа l, p и v. Все числа являются 32-битовыми знаковыми целыми.

Выходные данные

Для каждого теста вывести в одной строке количество дней, когда Счастливый Гарри может разместиться в палатке во время своего отпуска. Следуйте формату, приведенному в примере.

Пример

№	Ввод	Вывод
1	5  8  20	14
2	5  8  17	11

Решение

В общем случае задача решается формулой

days = v%p + v/p * l

Это решение не проходит при частном случае l < v < p. Например, для l = 5, v = 8, p = 6 программа выдаст 6, что неверно – правильный ответ 5. Внесём соответствующие исправления

#include <iostream>

using namespace std;

int main() {

int l, p, v, days;

cin >> l >> p >> v;

days = min(v%p, l)+ v/p * l;

cout << days;

}

Задача №5. Арифметическая прогрессия

Заданы первый и второй элементы арифметической прогрессии. Требуется написать программу, которая вычислит элемент прогрессии по ее номеру.

Входные данные

Входной файл INPUT.TXT содержит три целых числа, разделенных пробелами – первый элемент прогрессии A1 (1 ≤ A1 ≤ 1000), второй элемент прогрессии A2 (1 ≤ A2 ≤ 1000), и номер требуемого элемента N (1 ≤ N ≤ 1000).

Выходные данные

Выходной файл OUTPUT.TXT должен содержать одно целое число - N-й элемент арифметической прогрессии.

Пример

INPUT.TXT	OUTPUT.TXT
1  5  3	9

Пояснение к примеру

Здесь речь идет о следующей последовательности чисел:

       1, 5, 9, 13, 17, 21, …

В данной последовательности D = 4, поэтому A1 = 1, A2 = A1 + D = 5, A3 = A1 + 2 * D = 9, и т.д. Поскольку нам нужно было найти 3-й элемент прогрессии, то ответом на задачу является число 9.

Решение

#include <iostream>

#include <fstream>

using namespace std;

int main() {

ifstream cin("input.txt");

ofstream cout("output.txt");

int a1, a2, d, c, n;

cin >> a1 >> a2 >> n;

d = a2 - a1;

c = a1 + d * (n - 1);

cout << c;

return 0;

}

Задача №6. Обмен без третьего

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

Решение

Попытка выполнить непосредственное присваиваниене сработает:

int a = 8, b = 11;

a = b; //a = 11, b = 11

b = a; //a = 11, b = 11

Лишь немногие языки программирования, такие как Python, поддерживают множественное присваивание вида:

a, b = b, a

При этом в правой части оператора присваивания передаются копии значений b и a

Поэтому чаще всего задача обмена переменных значениями решается при помощи так называемого метода «третьего стакана[10]»

int a = 8, b = 11, c;

c = a;     // a = 8, b = 11, c = 8

a = b;     // a = 11, b = 11, c = 8

b = c;     // a = 11, b = 8

Следует отметить, что этот способ не только интуитивно понятный, но самый быстрый по времени выполнения. Однако существуют и другие, которые стоит рассмотреть при изучении языка программирования и для развития логического мышления:

#include <iostream>

int main(){

int a = 8, b = 11;

b = a + b;  // a = 8, b = 19

a = b - a;  // a = 11, b = 19

b = b - a;  // a = 11, b = 8

std::cout << a << " " << b;

return 0;

}

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

Задача №7. Бросание тела под углом к горизонту

Составить программу, которая для тела, брошенного под углом к горизонту, по введённым величинам начальной скорости V и угла α в градусах определяет: максимальную высоту H, время T подъема на максимальную высоту и дальность полёта L.

Вывести все величины с точностью до 10^-5.

Решение

Воспользуемся формулами из курса физики:

Применим библиотеки cmath и iomanip для организации вычислений и вывода с требуемой точностью.

#include <iostream> // потоковый ввод/вывод

#include <cmath>   // sin, pow, M_PI

#include <iomanip>      // параметры вывода fixed, setprecision

using namespace std;

int main(){

double v, alpha, t, h, l;

const double g = 9.80665;

cout << "Введите начальную скорость (в м/с):";

cin >> v;

cout << "Введите угол (в градусах):";

cin >> alpha;

alpha *= M_PI / 180;           // перевод в радианы

t = v * sin(alpha) / g;

l = v * v * sin(2*alpha) / g;

h = pow(v * sin(alpha), 2) / (2 * g);

cout << fixed << setprecision(5); // вывод 5 знаков после точки

cout << "Время подъема на макс. высоту (с) = " << t << endl;

cout << "Максимальная высота (м) = " << h << endl;

cout << "Дальность полёта (м) = " << l << endl;

}

Задача №8. Закон Амдала (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

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

Задача Амдала формулировалась так. Имеется n процессоров и p процентов вычислений не могут выполняться параллельно. Во сколько раз быстрее можно выполнить вычисления по сравнению с одним процессором?

Например, если n = 10, p = 50, а на одном процессоре все вычисления выполняются за время t. Тогда первая половина вычислений (50%) будет выполнена за время t/(2×10) , а вторая - за время t/2. Общее время вычислений в этом случае составит t/2 + t/20 = 11×t/20, а ускорение по сравнению с одним процессором составит 20/11 раза.

Если же n = 10, p = 25, и на одном процессоре все вычисления выполняются за время t. Тогда 75% вычислений будут выполнены за время 3×t/(4×10) , а оставшиеся 25% - за время t/4 . Общее время вычислений в этом случае составит t/4 + 3×t/40 = 13×t/40, а ускорение по сравнению с одним процессором составит 40/13 раза.

Даны числа n и p. Напишите программу, решающую задачу Амдала.

Входные данные

Входной файл INPUT.TXT содержит 2 целых числа n и p. (1 ≤ n ≤ 1000, 0 ≤ p ≤ 100).

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу с точностью, не меньшей 10^-6.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	10  50	1.818181818
2	10  25	3.076923077
3	1000  100	1.000000000

Решение

#include <fstream>

#include <iomanip>

using namespace std;

int main(){

ifstream cin("input.txt");

ofstream cout("output.txt");

int n, p;

float l;

cin >> n >> p;

l = 100.0 * n / (100 - p + p * n);

cout << fixed << setprecision(7) << l;

return 0;

}

В решении для нахождения l был использован литерал 100.0 вместо 100 для автоматического преобразования к типу с плавающей точкой. В противном случае операция деления и результат будут целочисленными.

Задача №9. Среднее число

Дано три различных числа a, b, c. Вывести среднее из них.

Входные данные

Числа a, b, c целые и по модулю не превышают 1000.

Выходные данные

Вывести среднее среди трех чисел.

Пример

Ввод	Вывод
12  145	12

Решение

Воспользуемся стандартными функциями min и max для выбора наибольшего и наименьшего из двух чисел.

#include <iostream>

using namespace std;

int main() {

int a, b, c;

cin >> a >> b >> c;

int sum = a + b + c;

int mi = min(min(a, b), c);

int ma = max(max(a, b), c);

cout << sum - mi - ma;

}

Часто для сокращения кода и улучшения его читабельности можно использовать макросы –команды прекомпилятора, которые начинаются с #define. Рассмотрим задачу, очень похожую на предыдущую.

Задача №10. Зарплата

В отделе работают 3 сотрудника, которые получают заработную плату в рублях. Требуется определить: насколько зарплата самого высокооплачиваемого из них отличается от самого низкооплачиваемого.

Входные данные

В единственной строке записаны размеры зарплат всех сотрудников через пробел. Каждая заработная плата – это натуральное число, не превышающее 10⁵.

Выходные данные

Необходимо вывести одно целое число — разницу между максимальной и минимальной зарплатой.

Примеры

№	Ввод	Вывод
1	100  500  1000	900
2	36  11  20	25

Решение

Для того чтобы решить задачу для трёх чисел, выражающих размер зарплаты a, b, c, необходимо найти max( a, b, c) – min( a, b, c)

Но шаблоны min и max в C++ предполагают использование только двух аргументов. Соответственно

min(a, b, c) = min(a, min(b, c)                  а     max(a, b, c) = max(a, max(b, c))

Очевидно, что порядок использования этих функций в точности совпадает. Это позволяет нам описать макрос F, в который можно подставлять имя функции min либо max.

#include <iostream>

#define F(f) f(a,f(b,c))

using namespace std;

int main(){

int a, b, c;

cin >> a >> b >> c;

cout << F(max) - F(min);

}

Задача №11. Золотой песок (acmp.ru)

Сотрудники завода по производству золотого песка из воздуха решили поправить свое финансовое положение. Они пробрались на склад завода, где хранился золотой песок трех видов. Один килограмм золотого песка первого вида они смогли бы продать за A1 рублей, второго вида – за A2 рублей, а третьего вида – за A3 рублей. Так получилось, что у сотрудников оказалось с собой только три емкости: первая была рассчитана на B1 килограмм груза, вторая на B2 килограмм, а третья на B3 килограмм. Им надо было заполнить полностью все емкости таким образом, чтобы получить как можно больше денег за весь песок. При заполнении емкостей нельзя смешивать песок разных видов, то есть, в одну емкость помещать более одного вида песка, и заполнять емкости песком так, чтобы один вид песка находился более чем в одной емкости.

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

Входные данные

В единственной строке записано 6 натуральных чисел A1, A2, A3, B1, B2, B3, записанных в одной строке через пробел. Все числа не превосходят 100.

Выходные данные

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

Пример

Ввод	Вывод
1  2  3  3  2  1	14

Решение

Создадим еще две группы переменных C1, C2, C3 –упорядоченные по убыванию A1, A2, A3 и D1, D2, D3 – упорядоченные по убыванию B1, B2, B3

#include <iostream>

#define F(f,x,y,z) f(x,f(y,z))

using namespace std;

int main () {

int a1, a2, a3, b1, b2, b3,

   c1, c2, c3, d1, d2, d3;

cin >> a1 >> a2 >> a3 >> b1 >> b2 >> b3;

c1 = F(max, a1, a2, a3);

c3 = F(min, a1, a2, a3);

c2 = a1 + a2 + a3 - c1 - c3;

d1 = F(max, b1, b2, b3);

d3 = F(min, b1, b2, b3);

d2 = b1 + b2 + b3 - d1 - d3;

cout << c1*d1 + c2*d2 + c3*d3;

}

Более разумным и коротким решением было бы записать наборы чисел A_i и B_i в массивы и отсортировать их по убыванию. Массивы будут рассмотрены далее в книге.

Унарные операции

К унарным, т.е. имеющим один операнд, операциям относится хорошо известный нам минус. Например,

int a = -b;

В C/C++ также очень широко используются операции ++ (инкремент – увеличение на единицу) и обратная ей – (декремент – уменьшение на единицу).

Пример

int a = 5, b = 9;

a++; // a = 6

b--; // b = 8

ВАЖНО: Инкремент и декремент являются одними из самых быстро выполняемых операций!

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

++x;

или

x++;

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

Пример

int a = 8, b = 5;

int c = ++a - b--;

Переменная c получит значение, равное разности увеличенной на 1 величины a и величины b. Затем b уменьшится на 1. Т.е. c примет значение 4, a станет равно 9, а b будет равно 4.

ВАЖНО: Обратите внимание, в C++ стирается четкая грань между операторами различных типов.

int a = 9, b = 6;

cout << a-- + ++b; //выведет 16, a получит значение 8, b - 7

Например, вторая строка фрагмента выполняет как вывод, так и арифметические действия с присваиванием в одном операторе.

В языке C++ допускается и другая форма последовательного присваивания в одной строке. Например, фрагмент

int tmp= 5;

--((tmp += 2) *= 3);

cout << tmp;

полностью эквивалентен следующему:

int tmp= 5;

tmp += 2;

tmp *= 3;

--tmp;

cout << tmp;