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


Презентация изнутри:

Слайд 0

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


Слайд 1

K-периодичный массив В данной задаче речь пойдет только о массивах, все элементы которых равны 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.


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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.


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


×

HTML:





Ссылка: