Указания к решению задач автотеста
В задачах 1-4 автотеста (см. файл "auto1.pdf")
дается массив A целых чисел, который считывается из файла "input.txt".
Также из этого файла считываются дополнительные параметры — целое
число M или два целых числа M и N, которые затем используются для
выделения подпоследовательности элементов из всех элементов массива.
Условия выделения подпоследовательности в каждой задаче разные
(пожалуйста, внимательно читайте условие каждой кнкретной задачи!).
Разберем подробно задачу 1. В файле "input.txt" содержатся целые числа
M N len A[0] A[1] A[2] ... A[len-1]
разделенные пробелами, Здесь числа M и N задают дробь M/N,
len — это длина массива, и A[0], A[1], ... A[len-1] —
элементы массива. Например, файл "input.txt" может содержать
следующие числа:
96 7 7 2 1 3 -11 0 20 4
Здесь первые 2 числа M=96 и N=7 задают дробь M/N=96/7,
следующая семерка задает длину массива, и далее следуют 7 элементов
массива A
2, 1, 3, -11, 0, 20, 4.
По условию задачи, в подпоследовательность должны входить элементы массива,
которые отличаются от среднего арифметического не более чем на
рациональное число M/N = 96/7. Требуется упорядочить по возрастанию
элементы подпоследовательности внутри массива A. При этом элементы массива,
не входящие в подпоследовательность, должны остаться га своих местах.
Модифицированный массив надо записать в выходной файл "output.txt".
Среднее арифметическое элементов массива A
равно (2+1+3+(-11)+0+20+4)/7 = 19/7. Абсолютные значения разности элементов
массива и среднего арифметического равны
2 1 3 -11 0 20 4
5/7 12/7 2/7 96/7 19/7 121/7 9/7
таким образом, в подпоследовательность входят все элементы массива, кроме
предпоследнего элемента 20. Выделим их красным цветом:
2 1 3 -11 0 20 4
В выходной файл "output.txt" должен быть записан модифицированный массив
-11 0 1 2 3 20 4
Заметим, что отклонение элемента -11 в точности равно M/N = 96/7,
из-за этого программа, использующая неточную вещественную арифметику,
на этом элементе спотыкается. Продемонстрируем это, используя Python3.
Сначала применим точную арифметику рациональных чисел:
>>> from fractions import Fraction
>>> MNRatio = Fraction(96, 7)
>>> mean = Fraction(19, 7)
>>> abs((-11) - mean)
Fraction(96, 7)
>>> abs((-11) - mean) <= MNRatio
True
А теперь то же самое с использованием вещественных чисел:
>>> MNRatio = 96/7
>>> mean = 19/7
>>> abs((-11) - mean)
13.714285714285715
>>> MNRatio
13.714285714285714
>>> abs((-11) - mean) <= MNRatio
False
В случае использования точной рациональной арифметики
результат правильный, но при использовании неточной вещественной
арифметики результат неверный (т.е. элемент -11 не выбирается
в подпоследовательность, хотя должен). Мораль:
опасно использовать вещестенную арифметику!
Все программы автотеста должны работать только с целочисленными типами,
в программе вообще не должно быть ключвых слов double, float,
форматов типа %lf, %f, %lg и т.п.
Как быстро и безопасно написать программу для автотеста,
подобную задаче 1
Первое.
Давайте писать программы на C++ (оставаясь по существу в рамках C),
чтобы избежать лишних и неожиданных проблем; для тех, кто предпочитает
"чистый" C, приведем и C-вариант той же программы.
Второе.
Используем только целочисленную арифметику и арифметику
рациональных дробей. Никаких вещественных переменных и фунций
не будет! В программе вообще не будет ключевых слов double и float
и вещественных переменных и выражений.
Третье.
Давайте будем хранить данные задачи — числа M, N, длину массива len
и указатель A на его элементы в глобальных переменных, чтобы избежать
многочисленных параметров, которые иначе пришлось бы передавать
функциям. Также в глобальных переменных (т.е. описанных
в начале файла вне функций) мы будем хранить
массив индексов подпоследовательности seqIdx и
длину подпоследовательности seqLen,
а также сумму sum всех элементов исходного массива,
нужную для вычисления среднего арифметического его элементов:
int M = 0;
int N = 1;
int len = 0;
int *A = nullptr;
int *seqIdx = nullptr;
int seqLen = 0;
int sum = 0;
(отметим, что при описании глобальных переменных надо
давать им начальные значения — это не обязательно, но хороший стиль).
(Вообще-то излишнее использование глобальных переменных — дурной стиль,
особенно при использовании нитей и других возможностей
параллельного программирования, но это не уровень первого семестра.)
Четвертое.
Обязательно выделим в отдельную функцию проверку условия, что элемент
x исходного массива принадлежит подпоследовательности. В задачах автотеста,
подобных задаче 1,
условие принадлежности элемента подпоследовательности зависит только
от самого числа x и не зависит от контекста. Таким образом, эта функция должна
возвращать логическое (или булевское) значение: true, если элемент x
принадлежит подпоследовательности, и false в противном случае. Прототип
этой функции выглядит так:
bool inSeq(int x);
Также выделим в отдельную функцию и алгоритм сортировки элементов
подпоследовательности (мы проводим сортировку внутри исходного массива,
не создавая вспомогательных массивов). Прототип функции сортировки:
void sortSeq();
Пятое и самое главное!
Ключевой момент во всех задачах автотеста — реализация функции
bool inSeq(int x);
выделяющей элементы подпоследовательности из всех элементов массива.
Напомним, что она вызывается, когда уже элементы массива A
считаны из файла, подсчитаны его длина и сумма его элементов, уже известны
параметры M и N и все эти элементы записаны в глобальные переменные.
Функция должна вернуть true, когда абсолютная величина
разности элемента x и среднего арифметического sum/len элементов массива
не должна превышать величины M/N (используется арифметика
рациональных чисел!). Главное соображение — всегда представлять
рациональное число как дробь, у которой знаменатель положителен.
Если отрицателен, то следует изменить знаки и числителя, и знаменателя,
чтобы знаменатель стал положительным, сама дробь при этом не изменится.
Вот реализация этой функции:
bool inSeq(int x) {
int mm = M;
int nn = N;
// Denominator of the M/N fraction must be positive
if (nn < 0) {
mm = (-mm);
nn = (-nn);
}
// |x - sum/len| <= mm/nn
int chislitel = x*len - sum;
int znamenatel = len;
if (chislitel < 0) {
// absolute value of the fraction
chislitel = (-chislitel);
}
// Fraction |x - sum/len| = chislitel/znamenatel
// chislitel/znamenatel <= mm/nn <==>
// chilsitel*nn <= znamenatel*mm
return (chislitel*nn <= znamenatel*mm);
}
Вот полный текст программы (файл "task1.cpp"):
#include <stdio.h>
#include <stdlib.h>
int M = 0;
int N = 1;
int len = 0;
int *A = nullptr;
int *seqIdx = nullptr;
int seqLen = 0;
int sum = 0;
bool inSeq(int x);
void sortSeq();
int main() {
FILE* f = fopen("input.txt", "r");
if (f == NULL) {
return -1;
}
if (
fscanf(f, "%d%d%d", &M, &N, &len) < 3 ||
N == 0
) {
fclose(f);
return -1;
}
A = new int[len];
seqIdx = new int[len];
sum = 0;
for (int i = 0; i < len; ++i) {
if (fscanf(f, "%d", A + i) < 1) {
fclose(f);
delete[] A;
delete[] seqIdx;
return -1;
}
sum += A[i];
}
fclose(f);
seqLen = 0;
for (int i = 0; i < len; ++i) {
if (inSeq(A[i])) {
seqIdx[seqLen] = i;
++seqLen;
}
}
sortSeq();
FILE *g = fopen("output.txt", "w");
if (g == NULL) {
delete[] A;
delete[] seqIdx;
return -1;
}
for (int i = 0; i < len; ++i) {
fprintf(g, "%d ", A[i]);
}
fprintf(g, "\n");
fclose(g);
delete[] A;
delete[] seqIdx;
return 0;
}
bool inSeq(int x) {
int mm = M;
int nn = N;
// Denominator of the M/N fraction must be positive
if (nn < 0) {
mm = (-mm);
nn = (-nn);
}
// |x - sum/len| <= mm/nn
int chislitel = x*len - sum;
int znamenatel = len;
if (chislitel < 0) {
// absolute value of the fraction
chislitel = (-chislitel);
}
// Fraction |x - sum/len| = chislitel/znamenatel;
// chislitel/znamenatel <= mm/nn <==>
// chilsitel*nn <= znamenatel*mm
return (chislitel*nn <= znamenatel*mm);
}
void sortSeq() {
// The simple bubble sort
bool invers = true;
while (invers) {
invers = false;
for (int i = 0; i < seqLen - 1; ++i) {
if (A[seqIdx[i]] > A[seqIdx[i+1]]) {
// swap elements
int tmp = A[seqIdx[i]];
A[seqIdx[i]] = A[seqIdx[i+1]];
A[seqIdx[i+1]] = tmp;
invers = true;
}
}
}
}
Программа проверена в дисплейном классе и успешно проходит тест.
Для любителей "чистого" языка C — вот С-вариант той же программы
(правда, мы оставили комментарии // в стиле C++, но все современные
компляторы "чистого" языка C принимают и C++ комментарии):
файл "task1.c"
Решение задачи 4 пробного автотеста
Задача 4 в целом похожа на уже разобранную задачу 1. Вот коротко ее условие
(полностью условие читайте здесь):
В файле input.txt записаны через пробел целое число M, количество элементов
массива A и далее сами элементы целочисленного массива A.
Каждый элемент в массиве A, для которого M-й бит (индексация с нуля) элемента
совпадает с M+1-м битом, заменить на количество единичных битов в представлении
данного числа. Остальные элементы массива изменяться не должны.
Модифицированный массив должен быть выведен в файл output.txt: элементы массива
должны быть разделены пробелом, количество элементов массива выводиться не
должно.
Функция main() должна вернуть 0 в случае успешно решенной задачи и отрицательное
число в случае невозможности решить задачу.
Отличие этой задачи от первой состоит в том, что здесь для выделения элементов
подпоследовательности используются поразрядные логические операции. Таких операций
в языке C/C++ четыре. Продемонстрируем их на примере. Пусть число x=41, число y=103.
Вот двоичное представление этих чисел в виде элементов типа int, размер которых
sizeof(int)==4 байта, т.е. 32 двоичных разряда:
x: 00000000000000000000000000101001
y: 00000000000000000000000001100111
В C/C++ можно использовать 4 поразрядные логческие операции:
1) поразрядное логическое сложение x|y, операция обозначается |,
2) поразрядное логическое умножение x&y, операция обозначается &,
3) поразрядное логическое отрицание ~x, операция обозначается ~,
4) поразрядное сложение по модулю 2 или XOR (eXclusive OR) x^y,
операция обозначается ^:
x: 00000000000000000000000000101001 = 41
y: 00000000000000000000000001100111 = 103
--------------------------------
x|y: 00000000000000000000000001101111 = 111
x&y: 00000000000000000000000000100001 = 33
~x: 11111111111111111111111111010110 = -42
x^y: 00000000000000000000000001001110 = 78
Кроме того, имеются операции сдвига влево и вправо. Сдвиг x вправо на k разрядов
обозначается x >> k, сдвиг влево x << k. При сдвиге влево на k позиций
правые k разрядов обнуляются. Со сдвигом вправо ситуация сложнее: если мы сдвигаем
число со знаком (например, типа int), то происходит расширение знакового разряда
(т.е. отрицательное число остается отрицательным). Например, для числа z = -103 при сдвиге
вправо на 2 разряда мы получим
z: 11111111111111111111111110011001 = -103
--------------------------------
z >> 2: 11111111111111111111111111100110 = -26
Если же мы сдвигаем вправо беззнаковое число, например, типа unsigned int,
то расширения знакового разряда не происходит. Например, для числа t = 4294967193,
имеющего в точности тот же двоичный код, что и z, но трактуемого как беззнаковое,
имеем:
t: 11111111111111111111111110011001 = 4294967193
t >> 2: 00111111111111111111111111100110 = 1073741798
Для решения задачи 4 нам достаточно всего двух операций: сдвига вправо и поразрядного
логического умножения. Напомним, что биты внутри двоичного представления нумеруются
справа налево, начиная с нуля. Таким образом, чтобы выделить k-й бит числа, достаточно
сдвинуть его на k позиций вправо и поразрядно умножить на константу 1. При этом все
разряды слова, кроме младшего, обнулятся, и мы получим единицу, если k-й разряд исходного
числа равнялся единице, и 0 в противном случае. Вот реализаций этой функции:
int bit(int w, int k) {
w >>= k;
return (w & 1);
}
Для подсчета количества ненулевых битов числа достаточно в цикле 32 раза повторить
операции: вырезать младший разряд слова, прибавить результат (0 или 1)
к счетчику и затем сдвинуть слово вправо. Вот реализация этой функции:
int numUnitBits(int w) {
int maxBits = sizeof(int)*8; // = 32
int n = 0;
for (int i = 0; i < maxBits; ++i) {
n += (w & 1);
w >>= 1;
}
return n;
}
Вот полный текст программы для задачи 4 (файл "task4.cpp"):
#include <stdio.h>
#include <stdlib.h>
int M = 0;
int len = 0;
int *A = nullptr;
bool inSeq(int x);
int bit(int w, int n);
int numUnitBits(int w);
int main() {
FILE* f = fopen("input.txt", "r");
if (f == NULL) {
return -1;
}
if (
fscanf(f, "%d%d", &M, &len) < 2 ||
M < 0 || M > 30
) {
fclose(f);
return -1;
}
A = new int[len];
for (int i = 0; i < len; ++i) {
if (fscanf(f, "%d", A + i) < 1) {
fclose(f);
delete[] A;
return -1;
}
}
fclose(f);
for (int i = 0; i < len; ++i) {
if (inSeq(A[i])) {
A[i] = numUnitBits(A[i]);
}
}
FILE *g = fopen("output.txt", "w");
if (g == NULL) {
delete[] A;
return -1;
}
for (int i = 0; i < len; ++i) {
fprintf(g, "%d ", A[i]);
}
fprintf(g, "\n");
fclose(g);
delete[] A;
return 0;
}
bool inSeq(int x) {
return (bit(x, M) == bit(x, M+1));
}
int bit(int w, int k) {
w >>= k;
return (w & 1);
}
int numUnitBits(int w) {
int maxBits = sizeof(int)*8;
int n = 0;
for (int i = 0; i < maxBits; ++i) {
n += (w & 1);
w >>= 1;
}
return n;
}
Проверим программу на следующем входе (файл "input.txt"):
2 8 -1 15 6 7 12 9 128 10
По условию, бит 2 числа должен быть равен биту 3 числа. Вот двоичные
представления этих чисел:
-1 15 6 7 12 9 128 10
11111111111111111111111111111111 1111 101 111 1100 1001 10000000 1010
Таким образом, вот выделенная последовательность, элементы обозначены красным:
-1 15 6 7 12 9 128 10
Результат в файле "output.txt":
32 4 6 7 2 9 1 10
похоже, правильный.
|