Problem Set 2: Numbers, Arrays

Task 1: Lift a Car

Даже маленькие дети знают, что если они хотят качаться на качели, так более тяжелые дети должны сесть ближе к середине. Из физики нам известно, что если детки находятся в равновесии, тогда действует закон:

F1 * r1 = F2 * r2

О существовании рычагов силы писал еще Архимед: Дайте мне точку опоры, и я переверну весь мир!.

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

r1 + r2 = 2 => r1 = 2 – r2
m1 * r1 = m2 * r2
...
r2 = 2 * m1 / (m1 + m2)

Создайте функцию float lift_a_car(const int stick_length, const int human_weight, const int car_weight) с тремя параметрами:

• const int stick_length - Длина перекладины
• const int human_weight - Вес человека
• const int car_weight - Вес авто

Функция согласно параметрам высчитает, на каком месте поместить точку опоры так, чтобы человек смог собственным весом поднять машину. Функция должна вернуть значение с точностью до 2 цифр после запятой (округлённо).

Function Call Example

printf("%.4f\n", lift_a_car(2, 80, 1400));
// prints: 0.1100
printf("%.4f\n", lift_a_car(4, 90, 1650));
// prints: 0.2100

Assessment

За задание можно получить max. 1 балл.

Task 2: Unit Price for Toilet Paper

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

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

Мерой измерения выберем как раз-таки один квадратик. Поскольку цена за один квадратик очень мала, будем рассчитывать цену за 100 квадратиков. Теперь перед нами остаётся задача, как перевести бумагу в квадратики. Простая арифметика - 10 квадратиков составляют примерно 1.17 метра.

Создайте функцию float unit_price(const float pack_price, const int rolls_count, const int pieces_count) с тремя параметрами:

• const float pack_price - Цена упаковки
• const int rolls_count - Количество рулонов
• const int pieces_count - Количество квадратиков в рулоне

Исходя из параметров, функция высчитает цену 100 квадратиков. Функция возвращает округлённый результат на 2 цифры после запятой.

Function Call Example

printf("%.4f\n", unit_price(4.79, 16, 150));
// prints: 0.2000
printf("%.4f\n", unit_price(5.63, 20, 200));
// prints: 0.1400

Assessment

За задание можно получить max. 1 балл.

Task 3: ATM

Банкомат выдает банкноты номиналом €10, €20, €50, €100 и €200. Чтобы снять деньги с банкомата, необходимо знать количество банкнот, которое выдаст банкомат. Однако в программном обеспечении вашего банкомата эта функция ещё не напрограммирована.

Ваша задача - напрограммировать функцию int bank_notes(const int price) с одним параметром:

• const int price - Необходимая сумма снятия

Функция вычисляет количество банкнот, необходимое для указанного параметра cуммы. Функция возвращает количество банкнот, которые нужны на снятие, или возвращает значение -1, если запрашиваемая сумма не может быть снята.

Function Call Example

printf("%d\n", bank_notes(540));
// prints: 5
printf("%d\n", bank_notes(5));
// prints: -1

Assessment

За задание можно получить max. 1 балл.

Task 4: Euler's Totient Function

Функция Эйлера, обозначаемая как φ (fi) - это математическая функция, которая вычисляет целые положительные числа, меньшие или равные заданному положительному числу n, которые относительно просты к n. Два числа являются относительно простыми, если их наибольший общий делитель равен 1. Другими словами, функция Эйлера φ(n) подсчитывает количество целых положительных чисел, меньших или равных n, которые не имеют общих делителей (кроме 1) с числом n.

Формула для функции Эйлера:

φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)

Где:

• φ(n) значение функции Эйлера для n.
• n целое положительное число.
• p1, p2, ..., pk являются различными простыми коэффициентами к n.

Напрограммируйте функцию int euler(const int n) для определения значения функции Эйлера для n.

Функция имеет один параметр:

• const int n - Целое положительное число

Function Call Example

printf("%d\n", euler(6));
// prints: 2
printf("%d\n", euler(12));
// prints: 4

Assessment

За задание можно получить max. 1.5 балл.

Task 5: Missing Number

Массив содержит n различных чисел из множества 0, 1, 2, ..., n. Числа образуют последовательность, которая может быть в неправильном порядке.

В этом поле не хватает только одного числа. Ваша задача - с помощью функции int find_missing_number(const int n, const int arr[]) найти недостающее число.

Функция получает на входе 2 параметра:

• const int n - Количество элементов массива.
• const int arr[] - Массив, содержащий значения последовательностей.

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

Function Call Example

int input_array[] = {3,0,1};
printf("%d\n", find_missing_number(3,input_array));
// prints: 2

Assessment

За задание можно получить max. 1 балл.

Task 6: Pascal's Triangle

На картинке изображена часть Треугольника Паскаля. Данный треугольник прославился в математике из-за своей симметрии и разных скрытых связей. Блез Паскаль думал так же ещё в году 1653 и писал, что ему не хватит одной научной работы, чтобы описать его полностью. Огромное количество связей Треугольника Паскаля с другими областями в математике сделало его таким знаменитым математическим объектом.

Схема Паскаля работает сверху вниз. Начнём единицей (ряд номер 0), под ней напишем по единице справа и слева (ряд номер 1). Последующим ряды строятся так, что по бокам пишутся единицы, а числа посередине высчитываются как сумма двух чисел в предыдущем ряду прямо над вычисляемым числом.

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

Создайте функцию unsigned long sum_squared(const int line) с параметром:

• const int line - Положительное целое число, представляющее номер ряда в Треугольнике Паскаля

Функция возвращает сумму квадратов всех коэффициентов в определённом ряду.

Function Call Example

printf("%lu\n", sum_squared(1));
// prints: 2
printf("%lu\n", sum_squared(4));
// prints: 70
printf("%lu\n", sum_squared(33));
// prints: 7219428434016265740

Assessment

За задание можно получить max. 1.5 балла.

Task 7: Min-and-Max Price

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

Вашей задачей является найти в данном массиве наименьшую и наивысшую цену.

Task 7.1: Min

Создайте функцию int array_min(const int input_array[], const int array_size) с двумя параметрами:

• const int input_array[] - На входе массив с целыми числами
• const int array_size - Величина массива, описывающая количество элементов в массиве.

Функция возвращает наименьшее значение, которое находится в массиве. Если на входе массив NULL, функция должна вернуть -1.

Task 7.2: Max

Создайте функцию int array_max(const int input_array[], const int array_size) с двумя параметрами:

• const int input_array[] - На входе массив с целыми числами
• const int array_size - Величина массива, описывающая количество элементов в массиве.

Функция возвращает наибольшее значение, которое находится в массиве. Если на входе массив NULL, функция должна вернуть -1.

Function Call Example

int input_array[] = {1,2,3,4,5};
printf("%d\n", array_min(input_array, 5));
// prints: 1
printf("%d\n", array_max(input_array, 5));
// prints: 5
printf("%d\n", array_max(NULL, 5));
// prints: -1

Assessment

За задание можно получить max. 1 балл.

Task 8: Factor Counter

Количество простых факторов (простых коэффициентов) зависит от самого числа и его разложения на простые коэффициенты. В общем случае, каждое составное число имеет единственное разложение на простые факторы. Число простых факторов данного числа будет равно числу отдельных простых чисел, составляющих его.

Чтобы получить количество уникальных простых коэффициентов данного числа, необходимо найти его разложение на простые коэффициенты. Например, имея число 12, его разложение на простые факторы равно 2 и 3.Здесь мы видим, что 12 имеет 2 различных простых фактора: 2, 2 и 3. То есть число различных факторов равно 2.

Напрограммируйте функцию int factorize_count(const int n) для определения количества различных факторов.

Функция имеет один параметр:

• const int n - Входное число для разложение.

Function Call Example

printf("%d\n", factorize_count(12));
// prints: 2

Assessment

За задание можно получить max. 1 балл.

Task 9: Marathon

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

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

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

Ваша задача - напрограммировать функцию void podium(const int n, int arr[]) для разделения блока материала таким образом, чтобы он удовлетворял условиям производства.

Функция имеет 2 параметра:

• const int n – общая высота блока материала
• int arr[] – поле размером 3 для записи индивидуальных размеров мест(часть подиума) в правильном порядке

Функция записывает высоты мест(часть подиума) в правильном порядке в массив int arr[].

Function Call Example

int heights[3];
int material = 6;
podium(material, heights);

for(int i = 0; i < 3; i++){
    printf("%d ", heights[i]);
}
printf("\n");
// prints: 2 3 1

Assessment

За задание можно получить max. 1 балл.

Minimal Requirements to Succeed

• Проект должен быть сдан и загружен в репозиторий git.kpi.fei.tuke.sk (см. ниже).
• Во время компиляции проекта не должна возникнуть ни одна ошибка! Проект будет собираться с помощью gcc со следующими параметрами:

gcc -std=c11 -Werror -Wall -lm 

• В вашей реализации не могут использоваться глобальные переменные.

Project Submission

Задание нужно сдать до 07.11.2024 (четверг). Последние тесты будут запущены в полночь этой даты.

Задание сдаётся с помощью системы контроля версий Git на сервере git.kpi.fei.tuke.sk.

Название вашего проекта должно быть точно в формате: zap-2024-id.

Сохраните иерархию файлов и директорий:

.
├── ps2
│   └── arrays.c
└── README

Значение отдельных файлов:

• README - файл, в котором указывается группа, которую вы посещаете на практиках, должна быть строго в формате:

GROUP : C1

• /ps2/arrays.c - Код решения задания 1-9

Assessment and Testing

За целый проблем сет вы можете получить max. 10 баллов, из них max. по 1 баллу за задания номер 1,2,3,5,7,8 и 9, max. по 1.5 балла за задания номер 4 и 6. Любые 2 балла вам зачтутся в счёт зачёта, остальные как бонус на экзамене. Количество полученных баллов напрямую зависит от успешности тестов, которые будут выполняться над вашей программой. Проверяться в том числе будет:

• Иерархия файлов (находятся ли в репозитории все нужные файлы).
• Функционал вашей реализации.

Сборка будет осуществляться с помощью компилятора gcc со следующими параметрами:

gcc -std=c11 -Werror -Wall -lm

Ошибкой будет считаться:

• Использование глобальной переменной.
• Ошибки во время компиляции (предупреждения трактуются как ошибки).
• Если ваша реализация не пройдёт каким-то из тестов.

Тестирование проектов будет проходить каждые 3 часа, а именно: 0300, 0600, 0900, 1200, 1500, 1800, 2100 и 2400.

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