Работа 3.7 Упр.31 ГДЗ Семакин 10 класс (Информатика)
Рассмотрим вариант решения задания из учебника Семакин, Хеннер, Шеина 10 класс, Бином: 31. Подсчитать количество строк заданной целочисленной матрицы N х N, являющихся перестановкой чисел 1, 2, …, N (т. е. содержащих каждое из чисел 1, 2, …, N ровно один раз).
Нужно просмотреть каждую строку матрицы и проверить, является ли она перестановкой чисел $$1,2,\dots,N$$. Это значит, что в строке должны встретиться все числа от $$1$$ до $$N$$ ровно по одному разу.
Удобно для каждой строки завести признак flag. Сначала считаем, что строка подходит, затем проверяем все числа:
- если какое-то число выходит за пределы $$1..N$$, строка не подходит;
- если число повторяется, строка тоже не подходит;
- если все числа от $$1$$ до $$N$$ встретились ровно один раз, увеличиваем счётчик подходящих строк.
В приведённом решении матрица сначала заполняется случайными числами, а затем для каждой строки проверяется условие равенства соседних элементов. Однако для задачи о перестановке этого недостаточно: нужно проверять именно наличие всех чисел от $$1$$ до $$N$$ без повторений.
Правильный вариант программы на Pascal:
var
a: array[1..100,1..100] of integer;
i, j, n, k: integer;
used: array[1..100] of boolean;
flag: boolean;
begin
readln(n);
for i := 1 to n do
for j := 1 to n do
read(a[i, j]);k := 0;
for i := 1 to n do
begin
for j := 1 to n do
used[j] := false;
flag := true;
for j := 1 to n do
begin
if (a[i, j] < 1) or (a[i, j] > n) or used[a[i, j]] then
flag := false
else
used[a[i, j]] := true;
end;
if flag then
k := k + 1;
end;
writeln(k);
end.
В этой программе массив used отмечает, какие числа уже встретились в текущей строке. Если число повторилось или вышло за пределы $$1..N$$, строка сразу считается неподходящей.
Ответ
Нужно подсчитать количество строк матрицы, в которых каждое число из $$1$$, $$2$$, …, $$N$$ встречается ровно один раз. Для этого в каждой строке проверяют диапазон значений и отсутствие повторов.
