Задача
Дана целочисленная квадратная матрица порядка [latex]n[/latex]. Найти номера строк, элементы каждой из которых образуют образуют монотонную последовательность (монотонно убывающую или монотонно возрастающую).
*Строки матрицы нумеруются с единицы, потому их номера в выводе больше соответствующих индексов в массиве на единицу.
Тесты
| [latex]n[/latex] | Матрица | Результат | Комментарий | ||||||||||||||||
| 1 | 0 | 1 | Квадратная матрица первого порядка состоит из одного элемента, следовательно, является и монотонно возрастающей, и монотонно убывающей. | ||||||||||||||||
| 3 |
|
— | Все элементы каждой строки попарно равны. | ||||||||||||||||
| 4 |
|
2 | В прочих строках монотонность нарушается | ||||||||||||||||
| 3 |
|
2, 3 | В первой строке последовательность возрастает нестрого. |
Алгоритм решения
- Анализировать строку на монотонность можно при помощи знака разности соседних элементов. Если при движении по строке слева направо знак изменяется, последовательность не может быть монотонной (дополнительное ограничение для строгой монотонности: разность не должна равняться нулю).
- Отдельно следует рассматривать случай [latex]n \le 1[/latex]. По определению, последовательность [latex]\left\{ { a }_{ n } \right\}[/latex] — монотонна [latex]\Leftrightarrow \forall i,j\in N, j>i: a_{ i }\prec a_{ j } (a_{ i }\succ a_{ j })[/latex]. Последовательность из одного элемента имеет вид [latex]\left\{a_{n}\right\} = a_{1}[/latex], следовательно, невозможно выбрать такие [latex]i,j \in N ,j>i[/latex], чтобы выполнилось условие строгой монотонности. Рассмотренный пример является частным случаем понятия «vacuous truth», часто применяемого при доказательстве теорем.
Программный код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include <cstdio> int sign(double x){ return (x > 0) - (x < 0); } int main() { size_t n; scanf("%d", &n); double x[n][n]; for(size_t i = 0; i < n; i++) for(size_t j = 0; j < n; j++) scanf("%lf", &x[i][j]); if(n >= 1) { for(size_t i = 0; i < n; i++){ /*последовательность монотонна, если сохраняет знак разность между N-м и (N-1)-м членом последовательности.*/ int prev_sign = sign(x[i][1] - x[i][0]); //знак разности первой пары чисел bool monotonic = true; for(size_t j = 1; j < n; j++){ int new_sign = sign(x[i][j] - x[i][j - 1]); //знак разности следующей пары if(prev_sign * new_sign <= 0){ monotonic = false; j = n; } prev_sign = new_sign; //новая пара для сравнения } if(monotonic) printf("%d ", i + 1); } } else printf("1\n"); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
import java.util.*; import java.io.*; import java.math.*; class Ideone { public static void main(String args[]) { Scanner in = new Scanner(System.in); int n = in.nextInt(); double[][] x = new double[n][n]; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) x[i][j] = in.nextDouble(); if(n >= 1){ for(int i = 0; i < n; i++){ /*последовательность монотонна, если сохраняет знак разность между N-м и (N-1)-м членом последовательности.*/ double prevSign = Math.signum(x[i][1] - x[i][0]); //знак разности первой пары чисел boolean monotonic = true; for(int j = 1; j < n; j++){ double newSign = Math.signum(x[i][j] - x[i][j-1]); //знак разности следующей пары if(prevSign * newSign <= 0){ monotonic = false; j = n; } prevSign = newSign; //новая пара для сравнения } if(monotonic) System.out.println(i+1); } } else System.out.println(1); } } |
Детали реализации
- Считывание элементов строки может прекратиться в трех случаях: если монотонность сменяется с возрастания на убывание (или наоборот), или если найдены два равных соседних элемента. Для выхода из внутреннего цикла применяется присваивание [latex]j = n[/latex].
- Для корректной работы внутреннего цикла первый элемент строки считывается перед ним.
- Проверить, изменяется ли знак разности соседних элементов последовательности можно двумя способами: первый подразумевает умножение двух разностей, второй — реализацию функции signum(). Так как при умножении можно выйти за границы типа, выбран был второй способ.
Программа доступна для тестирования по ссылке: http://ideone.com/n60As6.
Реализация на Java: http://ideone.com/CnFow1
А я не согласен, что последовательность из одного элемента не может быть монотонной. Как Вы ее определяете? Скорее всего, там что-то в духе «для любой пары соседних элементов выполняется неравенство…» В случае с одним элементом пар не будет вообще, а значит неравенство не нарушится.
Мне стало интересно: в самом деле, а может ли последовательность, содержащая меньше двух элементов, быть монотонной? Сам точного ответа на этот вопрос я найти не смог, обратился к преподавателям и старшим товарищам, а те рассказали о понятии vacuous truth (http://en.wikipedia.org/wiki/Vacuous_truth) в чистой математике и помогли правильно трактовать определение.
Спасибо Вам за замечание, теперь я понимаю причины истинности факта, сначала показавшегося мне контринтуитивным.
Дополню.
Я ожидал, что Вы будете вычислять разность между текущим элементом и предыдущим. Если эта разность сменила знак, то монотонность нарушена. Смена знака проверяется, например, как знак произведения. С небольшим риском, конечно. Если произведение соседних разностей стало отрицательным, монотонности нет.
Кстати, если размер 2, то ответ можно угадать 🙂
При умножении можно выйти за границы типа, поэтому я реализовал функцию signum(). В остальном, идея та же. Предложенный Вами подход действительно позволяет сократить размер программы, спасибо за замечание.
В данном случае Вы ошибаетесь. У Вас числа принадлежат типу double. При умножении для слишком больших чисел получится +inf или -inf, а для маленьких -0 или +0. Т.е. знак сохраняется. Во втором случае к сожалению не работает прямое сравнение с нулём. Приходится делать так: copysign(1,x*y)<0
Кроме того, есть серьезное ощущение, что решение не работает, в том числе и на тестах, предложенных Вами. К примеру, на моем компьютере на тест
4
1 2 2 1
0 1 2 3
0.3 11 -2 3
0 0 1 1
Я получил ответ
2 3 4
Как минимум, ошибка состоит в том, что Вы, найдя «несоответствие», решаете не читать строку дальше. А куда тогда пойдет ввод этой строки? В следующую строку, разумеется.
Мораль такова: не нужно создавать оптимизации там, где они не нужны.
Ваша правда, «premature optimization is the root of all evil.», как говорил Дональд Кнут. Не подумал об этом, исправил.
Зачтено
Засчитана Java версия, 10 баллов.