K-периодичный массив. В данной задаче речь пойдет только о массивах, все элементы которых равны 1 и/или 2. Массив a называется k-периодичным, если его. - презентация

1 K-периодичный массив

2 В данной задаче речь пойдет только о массивах, все элементы которых равны 1 и/или 2. Массив a называется k-периодичным, если его длина делится нацело на k, и существует такой массив b длины k, что a представляет собой записанный ровно n/k раз подряд массив b. Иными словами, массив a является k-периодичным, если он имеет период длины k. Например, любой массив является n-периодичным, где n длина массива. Массив [2,1,2,1,2,1] является одновременно 2-периодичным и 6-периодичным, а массив [1,2,1,1,2,1,1,2,1] является одновременно 3-периодичным и 9-периодичным. Для заданного массива a, состоящего только из единиц и двоек, найдите наименьшее количество элементов, которые необходимо изменить, чтобы он стал k-периодичным. Если массив уже является k- периодичным, то искомое значение равно 0.

3 K-периодичный массив Входные данные В первой строке входных данных содержится пара целых положительных чисел n, k (1 k n 100), где n длина массива, а значение k делит нацело n. Вторая строка содержит последовательность элементов заданного массива a 1, a 2,..., a n (1 a i 2), a i i-й элемент массива. Выходные данные Выведите наименьшее количество элементов массива, которые надо изменить, чтобы он стал k-периодическим. Если массив уже является k-периодичным, то выведите 0.

4 Примеры Входные данныеРезультат Комментарий В первом примере достаточно заменить четвертый элемент с 2 на 1, тогда массив примет вид [2,1,2,1,2,1]. Во втором примере заданный массив уже 4-периодичный. В третьем примере достаточно каждое вхождение двойки заменить на единицу. В этом случае массив примет вид [1,1,1,1,1,1,1,1,1] этот массив одновременно 1-, 3- и 9-периодичный.

5 Алгоритм решения (рассмотрим для k=2) 1)Определим q – количество вхождений массива b в массив a 2)Посчитаем количество «2» и «1» на каждом 1 и 2 месте Для этого создаем a)Массив e, который считает количество е диниц b)Массив d, который считает количество д воек 1е места 2е места

6 3)Сравниваем значения массивов e и d Например e d a И создаем «идеальный» массив b 0 b[1]=2 2>1 -> b[2]= } для случая } => b 21

7 4)Просматриваем весь массив a, сравниваем с массивом b каждую пару чисел и считаем несовпадения.

8 Program k09; var k,n,i,q,s,j:longint; a,b,e,d:array [1..100] of longint; begin readln(n,k); for i:=1 to n do read(a[i]); q:=n div k; {определяем количество вхождений} for i:=0 to q-1 do for j:=1 to k do if a[k*i+j] = 1 then e[j]:=e[j]+1 else d[j]:=d[j]+1; {создаем массивы d и e} for j:=1 to k do if e[j]>d[j] then b[j]:=1 else b[j]:=2; {создаем «идеальный» массив b} for i:=0 to q-1 do for j:=1 to k do if a[k*i+j]b[j] then s:=s+1; {считаем замены} writeln(s); end.

9 For i:= 0 to 3-1 do for j:= 1 to 2 do 1. i = 0 1) j = 1 a[2*0 +1]ǂ1 d[1]=0+1=1 d 2) j = 2 a[ 2*0+2]=1 e[2]=0+1=1 e 1 1

10 2. i = 1 1) j = 1 a[2*1 +1]ǂ1 d[1]=1+1=2 d 2) j = 2 a[ 2*1+2]ǂ1 d[2]=0+1=1 d 2 21

11 1. i = 2 1) j = 1 a[2*2 +1]ǂ1 d[1]=2+1=3 d 2) j = 2 a[ 2*2+2]=1 e[2]=1+1=2 e 31 02

12 «1» - e «2» - d 1) 0 b[1]=2 2) 2>1 -> b[2]=1 m