ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ ЗАДАЧИ И РЕШЕНИЯ

ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ ЗАДАЧИ И РЕШЕНИЯ

ЧАСТЬ 1

Задача №1

У продавца и покупателя имеется неограниченное кол-во монет достоинством (1, 2, 5, 10, 20, 50, 100, 200, 500 к примеру). Покупатель купил товар на сумму n. Hужно найти минимальное кол-во монет, которые будут использованы при расплате. Деньги может давать как покупатель, так и продавец.

Рассмотрим кольцо многочленов над некоторым полем. Пусть I некоторый идеал в этом кольце, порожденный многочленами g₁, g₂, ..., g_n. При этом набор G={g₁, g₂, ..., g_n} называется базисом (или системой образующих) идеала I (обозначение I=< G> ).

Пусть на мономах задан линейный порядок (term order), удовлетворяющий условиям: * для любого монома a, отличного от 1, a> 1; * если a< b, то для любого монома c имеем ac< bc. Примерами таких порядков являются: лексикографический (lex); общей степени, затем лексикографический (deglex); общей степени, затем обратный лексикографический (degrevlex).

У любого многочлена f однозначно определяется старший (в смысле заданного порядка) моном (leading term), который мы будем обозначать lt(f). Можно считать, что все рассматриваемые многочлены нормированы (коэффициент при старшем мономе равен 1). Если lt(f) делится на lt(g), то многочлен f можно редуцировать относительно многочлена g - результатом будет многочлен f-(lt(f)/lt(g))*g.

Многочлен f называется редуцированным относительно G, если lt(f) не делится на lt(g) ни для какого g из G. Любой многочлен f за конечное число редукций можно привести к редуцированному относительно G многочлену. Заметим, что результат такой редукции, вообще говоря, неоднозначен.

Определение Базис G идеала I называется _базисом Грёбнера_ (стандартным базисом) относительно порядка <, если в результате любой редукции элемента f идеала I к редуцированному относительно G многочлену всегда получается 0.

Каждый элемент g из G можно редуцировать относительно набора G-{g}. Результатом будет редуцированный базис, в котором старшие термы любых двух элементов не делятся один на другой.

Доказано, что
1) любой идеал обладает базисом Грёбнера относительно любого порядка;
2) редуцированный базис Грёбнера идеала I относительно порядка < определяется однозначно с точностью до порядка следования многочленов;
2') два идеала I и J равны между собой тогда и только тогда, когда их базисы Грёбнера совпадают.

Для построения базисов Грёбнера Бухбергер придумал алгоритм, который теперь носит его имя.

IK> и каким именно образом они используются?

Пусть достоинства монет 1=c₀, c₁, ..., c_m-1. Любую сумму вида (k₀-k_m)*c₀ + (k₁-k_m+1)*c₁ +... + (k_m-1-k_2m-1)*c_m-1, где все k_i, i=0..2m-1 неотрицательны, которые мы будем кодировать мономами x₀^{k₀}x₁^{k₁}...x_2m-1^{k_2m-1}.

Пусть I - идеал, порожденный мономами соответствующими нулевой сумме.

Утв 1. Базисом I является набор многочленов x₀^{c_i}-x_i, x₁^{c_i}x_m+i-1, i=0..m-1. Доказательство индукцией по m. [skipped]

Пусть G - базис Грёбнера идеала I относительно deglex. Пусть нам дана сумма s. Редуцируем многочлен x₀^s относительно G.

Утв 2. Результатом этой редукции будет многочлен x₀^{k₀}x₁^{k₁}...x_2m-1^{k_2m-1}, причем в каждой паре (k_i, k_m+i), i=0..m-1 не более одного числа отлично от нуля и s = (k₀-k_m)*c₀ + (k₁-k_m+1)*c₁ +... + (k_m-1-k_2m-1)*c_m-1 и есть искомое минимальное по числу монет представление суммы s. Доказательство от противного. [skipped]

IK> Каков собственно алгоритм?

Алгоритм простой:
1) построить базис Грёбнера указанного идеала относительно deglex;
2) редуцировать многочлен x₀^s;
3) интерпретировать результат.

Если нужно решить несколько задач для одного и того же набора номиналов, но разных сумм, то базис Грёбнера нужно построить только один раз (это самая трудоемкая операция), и затем очень быстро проводить редукцию для каждой из сумм.

{$B-}const m=9; c: array[1..m] of integer=(1, 2, 5, 10, 20, 50, 100, 200, 500); m2=2*m; type TTerm=array[1..m2] of integer; PTermList=^TTermList; TTermList=record u, v: TTerm; next: PTermList; end; var Basis: TTermList; p, q, r, t: PTermList; i, j, k: integer; function cmp(var x, y: TTerm): integer; var t, i, dx, dy: integer; begin dx: =0; dy: =0; t: =0; for i: =1 to m2 do begin inc(dx, x[i]); inc(dy, y[i]); if t=0 then begin if x[i]> y[i] then t: =1; if y[i]> x[i] then t: =-1; end; end; if dx=dy then cmp: =t else if dx> dy then cmp: =1 else cmp: =-1; end; function S(var a, b, c: PTermList): boolean; var x, y: TTerm; i, t: integer; begin S: =False; for i: =1 to m2 do begin if a^.u[i]> b^.u[i] then t: =a^.u[i] else t: =b^.u[i]; x[i]: =t-a^.u[i]+a^.v[i]; y[i]: =t-b^.u[i]+b^.v[i]; if x[i]> y[i] then t: =y[i] else t: =x[i]; dec(x[i], t); dec(y[i], t); end; case cmp(x, y) of 1: begin c^.u: =x; c^.v: =y; end; -1: begin c^.u: =y; c^.v: =x; end; else S: =True; end; end; function Reduce(var a: PTermList): boolean; var p: PTermList; x: TTerm; i: integer; begin p: =Basis.next; repeat if a< > p then begin i: =1; while (i< =m2) and (a^.u[i]> =p^.u[i]) do inc(i); if i> m2 then begin if S(a, p, a) then begin Reduce: =true; exit; end; p: =@Basis; end; end; p: =p^.next; until (p=nil); Reduce: =false; end; procedure ReduceBasis; var p, q, t: PTermList; begin p: =@Basis; repeat q: =p; p: =p^.next; while (p< > nil) and Reduce(p) do begin q^.next: =p^.next; dispose(p); p: =q^.next; end; if p=nil then break; t: =p; while (t^.next< > nil) and (cmp(t^.next^.u, p^.u)=1) do t: =t^.next; if t< > p then begin q^.next: =p^.next; p^.next: =t^.next; t^.next: =p; end; p: =q^.next; until p=nil; end; begin Basis.next: =nil; for i: =1 to m do begin if i> 1 then begin new(p); with p^ do begin FillChar(u, SizeOf(u), 0); u[1]: =c[i]; FillChar(v, SizeOf(v), 0); v[i]: =1; next: =Basis.next; end; Basis.next: =p; end; new(p); with p^ do begin FillChar(u, SizeOf(u), 0); u[1]: =c[i]; u[m+i]: =1; FillChar(v, SizeOf(v), 0); next: =Basis.next; end; Basis.next: =p; end; write('Construct Groebner basis'); p: =@Basis; new(r); repeat q: =p^.next; while (q< > nil) do begin if (not S(p, q, r)) and (not Reduce(r)) then begin t: =@Basis; while (t^.next< > nil) and (cmp(t^.next^.u, r^.u)=1) do t: =t^.next; r^.next: =t^.next; t^.next: =r; new(r); write('.'); ReduceBasis; p: =@Basis; break; end; q: =q^.next; end; p: =p^.next; until p=nil; writeln(' Done'); with r^ do repeat FillChar(u, SizeOf(u), 0); FillChar(v, SizeOf(v), 0); write('Amount of money (0 - exit): '); readln(u[1]); if u[1]=0 then break; Reduce(r); write('Coins: '); j: =0; for i: =1 to m2 do begin for k: =1 to u[i] do if i< =m then write('+', c[i]) else write('-', c[i-m]); inc(j, u[i]); end; writeln; writeln('Total number: ', j); until false; dispose(r); p: =Basis.next; while p< > nil do begin q: =p; p: =p^.next; dispose(q); end; end.

Задача №2

Hапечатать все перестановки чисел 1..N

First = (1, 2,..., N)
Last = (N, N-1,..., 1)

Всего таких перестановок будет N! =N*(N-1)*...*2*1. Для составления алгоритма Next зададимся вопросом: в каком случае i-ый член перестановки можно увеличить, не меняя предыдущих? Ответ: если он меньше какого-либо из следующих членов (членов с номерами больше i).

Мы должны найти наибольшее i, при котором это так, т.е. такое i, что X[i]< X[i+1]>...> X[N] (если такого i нет, то перестановка последняя). После этого X[i] нужно увеличить минимально возможным способом, т.е. найти среди X[i+1],..., X[N] наименьшее число, большее его. Поменяв X[i] с ним, остается расположить числа с номерами i+1,..., N так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке:

procedure Next; begin {найти i: X[i]< X[i+1]> X[i+2]>...> X[N]}; {найти j: X[j]> X[i]> X[j+1]>...> X[N]}; {обменять X[i] и X[j]}; {X[i+1]> X[i+2]>...> X[N]}; {перевернуть X[i+1], X[i+2],..., X[N]};

end;

Теперь можно написать программу:

program Perestanovki; type Pere=array [byte] of byte; var N, i, j: byte; X: Pere; Yes: boolean; procedure Next(var X: Pere; var Yes: boolean); var i: byte; procedure Swap(var a, b: byte); {обмен переменных} var c: byte; begin c: =a; a: =b; b: =c end; begin i: =N-1; {поиск i} while (i> 0)and(X[i]> X[i+1]) do dec(i); if i> 0 then begin j: =i+1; {поиск j} while (j< N)and(X[j+1]> X[i]) do inc(j); Swap(X[i], X[j]); for j: =i+1 to (N+i) div 2 do Swap(X[j], X[N-j+i+1]); Yes: =true end else Yes: =false end; begin write('N='); readln(N); for i: =1 to N do X[i]: =i; repeat for i: =1 to N do write(X[i]); writeln; Next(X, Yes) until not Yes end.

Решение через рекурсию

Опишем рекурсивную процедуру Generate(k), предъявляющую все перестановки чисел 1,..., N, у которых фиксировано начало X[1], X[2],..., X[k]. После выхода из процедуры массив X будут иметь то же значение, что перед входом. Понятно, что при k=N мы снова имеем только тривиальное решение - саму перестановку. При k< N будем сводить задачу к k+1:

procedure Generate(k: byte); var i, j: byte; procedure Swap(var a, b: byte); var c: byte; begin c: =a; a: =b; b: =c end; begin if k=N then begin for i: =1 to N do write(X[i]); writeln end else for j: =k+1 to N do begin Swap(X[k+1], X[j]); Generate(k+1); Swap(X[k+1], X[j]) end

end;

Основная программа:

program PerestanovkiRecursion; type Pere=array [byte] of byte; var N, i, j: byte; X: Pere; procedure Generate(k: byte); ............... begin write('N='); readln(N); for i: =1 to N do X[i]: =i; Generate(0)

end.

Чтобы до конца разобраться в этой непростой программе, советуем выполнить ее на бумаге при N=3. Обратите внимание, что порядок вывода перестановок не будет лексикографическим!

Задача №3

Задача №4

Задача №5

Задача №6

На двумерной плоскости задано N точек с координатами (X₁, Y₁), (X₂, Y₂), ..., (X_n, Y_n). Написать программу, которая из этих точек выделяет вершины квадрата, содержащего максимальное число заданных точек.

Задача №7

Задан набор неповторяющихся пар (A_i, A_j), A_i, A_j принадлежат множеству А={A₁, A₂, ..., A_n}. Необходимо составить цепочку максимальной длины по правилу (A_i, A_j)+(A_j, Ak)=(A_i, A_j, A_k).

При образовании этой цепочки любая пара может быть использована не более одного раза.

Для более удобного хранения информации заведем матрицу

C[1...n, 1..n] (так называемую матрицу смежности) в которой C[i, j]=1, если в наборе есть пара (A_i, A_j) и C[i, j]=0 иначе. Будем строить все возможные цепочки (по правилу, данному в условии) и искать среди них ту, которая имеет максимальную длину. В качестве начального символа цепочки можно взять любой символ из A. Пусть это символ Ai. Ищем, просматривая строку i матрицы C слева направо элемент C[i, j]=1 (другими словами, ищем пару с первым элементом Ai). Если такого элемента не существует, то берем в качестве начала строки другой элемент множества A. Если элемент C[i, j]=1 найден, то ему соответствует пара (A_i, A_j). Помечаем ее как уже использованную полагая, например, C[i, j]=-1. Далее просматриваем слева направо строку j матрицы C в поисках еще не использованной пары (A_j, A_k) (C[j, k]=1). Присоединяем элемент Ak к имеющейся цепочке, полагаем C[j, k]=-1, ищем единичный элемент в строке k и т.д. Предположим, на некотором шаге мы получили цепочку A_i A_j A_k... A_s A_l A_p и в строке p матрицы больше нет ни одного единичного элемента. Это означает, что при таком подборе предыдущих элементов мы нашли максимальную по длине строку. Если ее длина больше длин всех найденных ранее строк, запоминаем эту строку как рекорд. После этого " отщепляем" от строки последний элемент Ap и смотрим, есть ли еще в строке l единичный элемент с индексом, большим p. Если да, то приписываем уже этот элемент к строке и пытаемся затем снова увеличить длину полученной строки, если же нет, то " отщепляем" от строки элемент A₁, в строке S ищем единичный элемент с индексом, большим l и т.д.

Останов осуществляется тогда, когда мы должны " отщепить" от строки A_i. Перебираем цепочки, начинающиеся со всех возможных элементов множества A. Находим строку максимальной длины:

Задача № 8

Имеется N городов. Для каждой пары городов (I, J) можно построить дорогу, соединяющую эти два города и не заходящие в другие города. Стоимость такой дороги A(I, J). Вне городов дороги не пересекаются.Написать алгоритм для нахождения самой дешевой системы дорог, позволяющей попасть из любого города в любой другой. Результаты задавать таблицей B[1: N, 1: N], где B[I, J]=1 тогда и только тогда, когда дорогу, соединяющую города I и J, следует строить.

Легко понять, что сеть дорог будет реализовывать некоторый связный (так как можно проехать из любого города в любой) граф без циклов (так как одно ребро из цикла можно выбросить, а связный граф останется связным). Поэтому алгоритм построения сети дорог минимальной суммарной стоимости очень прост. На каждой итерации необходимо находить дорогу минимальной стоимости, которая не образует цикла с уже выбранными дорогами на предыдущих итерациях. Основную трудность такого решения составляет проверка условия, образуют ли ребра цикл. Однако решение существенно упрощается, если рассматривать только минимальные ребра только между двумя множествами: множеством помеченных вершин и множеством непомеченных вершин. Понятно, что эти множества должно соединять хотя бы одно ребро, чтобы граф был связным. Ясно, что оно должно быть минимальным по длине. В описываемом ниже алгоритме это делается следующим образом. Для каждой вершины к из множества непомеченных вершин (а на начальном этапе это все вершины, кроме первой) определяется ближайшая вершина из множества помеченных вершин БЛИЖ[к]. На каждой итерации определяется кратчайшее ребро (i, j) между множеством помеченных вершин и множеством непомеченных вершин, используя массив БЛИЖ. Найденное ребро выбирается для системы дорог, а соответствующая вершина j считается помеченной. После этого пересчитывается массив БЛИЖ. При этом учитывается, что к изменение некоторой величины БЛИЖ[k] может произойти только тогда, когда расстояние от k до j меньше, чем от k до БЛИЖ[k].

Алгоритм

для i от 1 до N выполнятьнцфлаг[i]: =0; БЛИЖ[i]: =1кцфлаг[1]: =1; для k от 1 до N-1 выполнятьнцминрас: =бесконечность; для i от 2 до N выполнятьесли флаг[i]=0 и минрас > C[БЛИЖ[i], i]то минрас: =C[БЛИЖ[i], i]; j: =i; всеВывод ребра (БЛИЖ[j], j)флаг[j]: =1; для i от 2 до N выполнятьесли флаг[i]=0 и C[БЛИЖ[i], i]> C[i, j]то БЛИЖ[i]: =j; всекц

Задача № 9

Элементами массива a[1..n] являются неубывающие массивы [1..m] целых чисел (a: array [1..n] of array [1..m] of integer; a[1][1] < =... < = a[1][m], ..., a[n][1] < =... < = a[n][m]). Известно, что существует число, входящее во все массивы a[i] (существует такое х, что для всякого i из [1..n] найдётся j из [1..m], для которого a[i][j]=x). Найти одно из таких чисел х.

Введем массив b[1]..b[n], отмечающий начало " остающейся части" массивов a[1]..a[n].

for k: =1 to n do begin | b[k]: =1; end; eq: = true; for k: = 2 to n do begin | eq: = eq and (a[1][b[1]] = a[k][b[k]]); end; {инвариант: оставшиеся части пересекаются, т.е. существует такое х, что для всякого i из [1..n] найдётся j из [1..m], не меньшее b[i], для которого a[i][j] = х; eq < => первые элементы оставшихся частей равны} while not eq do begin | s: = 1; k: = 1; | {a[s][b[s]] - минимальное среди a[1][b[1]]..a[k][b[k]]} | while k < > n do begin | | k: = k + 1; | | if a[k][b[k]] < a[s][b[s]] then begin | | | s: = k; | | end; | end; | {a[s][b[s]] - минимальное среди a[1][b[1]]..a[n][b[n]]} | b [s]: = b [s] + 1; | for k: = 2 to n do begin | | eq: = eq and (a[1][b[1]] = a[k][b[k]]); | end; end; writeln (a[1][b[1]]);

Задача №10

Задача №11

Задача №12

Даны две строки x и y. Строка x состоит из нулей и единиц, строка y из символов A и B. Можно ли строку x преобразовать в строку y по следующему правилу: цифра 0 преобразуется в непустую последовательность букв A, а цифра 1 - либо в непустую последовательность букв A, либо в непустую последовательность букв B?

Пусть строка S₁ состоит из цифр 0 и 1 и имеет длину N, а строка S₂ (из символов A и B) - длину M.

Заведем матрицу А размера N на M, при этом строки матрицы помечаются i-ой цифрой строки S₁, а j-й столбец - j-м символом строки S₂.

Возьмем в качестве примера S₁='00110', S₂='AAAABBAA'.

Первая цифра строки S₁ (цифра 0) может быть преобразована в одну из последовательностей букв 'A', 'AA', 'AAA', 'AAAA', являющиеся префиксами строки S₂. Заносим символ 'x' в те столбцы первой строки, буквы-пометки которых соответствуют последним буквам возможных последовательностей. Таким образом, помечаются элементы A[1, 1], A[1, 2], A[1, 3] и A[1, 4].

Шаг алгоритма: будем преобразовывать очередную цифру S₁[i], которой соответствует строка i.

Находим 'x' в предыдущей строке при просмотре ее слева направо (этому столбцу соответствует последняя буква в какой-то из непустых последовательностей букв, порожденных на предыдущем шаге). Если текущую цифру можно преобразовать в последовательность букв, помечающих следующие за данным столбцы, то в этих столбцах в данной строке ставим 'x'.

Далее от места над последней помеченной ячейкой ищем в предыдущей строке 'x' и, когда находим, повторяем указанные выше операции.

Эти действия проводим далее для i=2,..., N.

Вид матрицы после N шагов:

Замечание: Можно обойтись и одномерным массивом. В самом деле, при заполнении следующей строки мы обращаемся только к элементам предыдущей строки, к каждому - по одному разу.

Алгоритм (без учета замечания) может быть следующим:

for i: =1 to N dofor j: =1 to M doA[i, j]: =' '; {инициализация}if S1[1]=0then element: ='A' {0 преобразуется в A}else element: =S2[1]; {1 - в A или в B}i: =1; while (i< =M) and (S2[i]=element) do begin {первый шаг}A[1, i]: ='x'; i: =i+1end; for i: =2 to N do beginj: =2; while j< M do begin {просмотр строки i}if A[i-1, j-1]='x'then beginif S1[i]=0then element: ='A'else element: =S2[j]; if S2[j]=elementthenwhile (j< =M) and (S2[j]=element) do beginA[i, j]: ='x'; j: =j+1; end {end for while}else j: =j+1end {end for then}else j: =j+1end {end for while}end; {end for for}if A[N, M]='x'

then writeln('Можно преобразовать') else writeln('Нельзя преобразовать'); < /P> < /DIR>

Напишите программу, использующую одномерный массив.

Задача №13.

Пусть известно, что для перемножения матрицы размера n*m на матрицу размера m*k требуется n*m*k операций. Необходимо определить, какое минимальное число операций потребуется для перемножения n матриц А₁,...А_n, заданных своими размерами n(i)*m(i).

При этом можно перемножать любые две рядом стоящие матрицы, в результате чего получается матрица нужного размера.

Замечание:

n(i) - число строк в матрице A_i

m(i) - число столбцов в матрице A_i

n(i)=m(i)+1.

Определим через F[i, j] минимальное число операций, которое требуется для перемножения группы матриц с номерами от i до j включительно. Ясно, что F[i, i]=0. Перемножение матриц в такой группе может производиться различными способами, а именно, производить сначала перемножение наилучшим способом группы от i до k, затем от k+1 до j, наконец перемножить получившиеся матрицы. Понятно, что k может быть величиной от i до j-1. Учитывая требование получить наилучший результат, величина F[i, j] определяется как

F[i, j]=max(F[i, k]+F[k+1, j]+n[i]*n[k+1]*m[j]), где k может быть величиной от i до j-1, n[i], n[k+1], m[j] определяют размеры матриц, получившихся при перемножении в группах.

для i от 1 до N выполнятьF[i, i]: =0; дляl от 1 до N-1 выполнятьдля i от 1 до N-l выполнятьнцKol: =бесконечность; j: =i+l; для k от i до j-1 выполнятьесли Kol > F[i, k]+F[k+1, j]+n[i]*n[k+1]*m[j] то Kol: =F[i, k]+F[k+1, j]+n[i]*n[k+1]*m[j]; всеF[i, j]: =Kol; кц

Задача №14

а) Из последовательности, состоящей из N чисел, вычеркнуть минимальное количество элементов так, чтобы оставшиеся образовали строго возрастающую последовательность.

б) Из заданной числовой последовательности A[1..N] вычеркнуть минимальное число элементов так, чтобы в оставшейся подпоследовательности каждый последующий элемент был больше предыдущего кроме, быть может, одной пары соседних элементов ( одного " разрыва" возрастающей подпоследовательности).

Например: A=(1, 2, 3, 2, 4, 3, 4, 6);

Задача №15

Можно, конечно, число A умножить само на себя n-1 раз, но для этого надо выполнить n-1 операцию умножения. Рассмотрим метод, требующий меньшего числа умножений (он, однако, не всегда дает минимальное число умножений).

Если n - четное, n=2m то будем вычислять Aⁿ, используя тождество A^am=(A^m)²;

если же n=2m+1, то

A^2m+1=(A^2m)*A=((A^m)²)*A.

Так(м образом, возведение A в 13 степень будет выглядеть следующим образом:

(A¹³)=((A⁶)²)*A=(((A³)²)²)*A=(((A*A*A)²)²)*A

и вычисление требует 5 операций умножения.

Используя данный метод, для возведения в степень n потребуется порядка log₂(n) операций умножения.

Программа на Паскале может выглядеть так:

var A, N: integer; function power(N: integer): integer; beginif N> 1then if odd(N) {N нечетно? }then power: =SQR(power(N div 2))*A else power: =SQR(power(N div 2))else power: =Aend; beginread(A, N); writeln(power(N));

end;

Можно ту же самую идею реализовать и по другому ( далее мы приводим выдержку из книги Д.Кнута " Искусство программирования для ЭВМ", т.2, с.482):

" Запишем n в двоичной системе счисления и заменим в этой записи каждую цифру " 1" парой букв SX, а каждую цифру " 0" - буквой S, после чего вычеркнем крайнюю левую пару букв SX. Результат, читаемый слева направо, превращается в правило вычисления xⁿ, если букву " S" интерпретировать как операцию возведения в квадрат, а букву " X" - как операцию умножения на x. Например, если n=23, то его двоичным представлением будет 10111; строим последовательность SX S SX SX SX, удаляем из нее начальную пару SX и в итоге получаем следующее правило вычисления: S SX SX SX. Согласно этому правилу, мы должны " возвести x в квадрат, затем снова возвести в квадрат, затем умножить на x, возвести в квадрат, умножить на x, возвести в квадрат и, наконец, умножить на x"; при этом мы последовательно вычисляем x², x⁴, x⁵, x¹⁰, x¹¹, x²², x²³.

Этот " бинарный метод" легко обосновать, рассмотрев последовательность получаемых в ходе вычисления показателей: если " S" интерпретировать как операцию умножения на 2, а " X" - как операцию прибавления 1 и если начать с 1, а не с x, то наше правило дает нам в соответствии со свойствами двоичной системы счисления число n".

Приведенный метод не дает минимального числа операций умножения. Для вычисления x²³ нам, по изложенному выше методу, потребуется 7 операций умножения. В действительности их необходимо только 6:

x -> x² -> x³ -> x⁵ -> x¹⁰ -> x²⁰ -> x²³.

Задача №16

Задача №17

Задача №18

Вокруг считающего стоит N человек, из которых выделен первый, а остальные занумерованы по часовой стрелке числами от 2 до N. Считающий, начиная с кого-то, ведет счет до M. Человек на котором остановился счет, выходит из круга. Счет продолжается со следующего человека и так до тех пор, пока не останется один человек.

Определить

a) номер оставшегося человека, если известно M и то, что счет начинался с первого человека;

b) номер человека c которого начинался счет, если известно M и номер оставшегося человека L.

Для решения этой задачи используем структуру данных 'список'. Каждый элемент списка указывает на следующий за ним элемент (другими словами - хранит информацию о расположении следующего элемента).

a). Заведем массив A из N ячеек - по числу людей в круге. В каждую из ячеек A[i] занесем номер стоящего следующим за i-ым человека. Первоначально A[i]=i+1, i=1,...,.N-1, A[N]=1. Начиная счет от текущего человека (человека с номером IndTek, с самого сначала IndTek=1) будем делать ход - отсчитывать M ячеек, двигаясь по кругу в поисках человека, который должен выйти из круга. С учетом определения массива A это будет выглядеть следующим образом:

{IndTek - это номер человека, с которого начинается счет} for i: =1 to M-1 do {Отсчитываем M человек, начиная с IndTek} begin IndPred: =IndTek; {в IndPred сохраняем номер текущего человека в круге} IndTek: =A[IndTek]; {и вычисляем номер следующего за ним} end;

После выполнения этого цикла в переменной IndTek будет номер человека, на котором остановился счет (т.е. номер человека, который покинул круг), а в переменной IndPred - номер предшествующего ему человека в круге.

Удалим человека с номером IndTek. Для этого мы просто изменим ссылку A[IndPred] у предшествующего ему человека так, чтобы он указывал не на IndTek, а на следующего за IndTek, т.е. на A[IndTek], и новый отсчет M-того человека начнем со следующего за удаленным:

A[IndPred]: =A[IndTek]; IndTek: =A[IndTek]; {Новый номер начального человека}

Все вышеописанные операции мы будем повторять до тех пор, пока в круге не останется одного единственного человека, т.е. до тех пор, пока A[IndTek] не станет равным IndTek, что означает, что следующим за человеком с номером IndTek является он сам.

Полностью весь фрагмент программы будет выглядеть так:

{Инициализация массива A}< P> for i: =1 to N-1 doA[i]: =i+1; A[N]: =1; {IndTek - это номер человека, с которого начинается счет}IndTek: =1; while A[IndTek] < > IndTek dobeginfor i: =1 to M-1 do {Отсчитываем M человек, начиная с IndTek}beginIndPred: =IndTek; {в IndPred сохраняем номер текущего человека в круге}IndTek: =A[IndTek]; {и вычисляем номер следующего за ним}end; A[IndPred]: =A[IndTek]; IndTek: =A[IndTek]; {Новый номер начального человека}end;

writeln('Номер последнего оставшегося человека ', IndTek);

Решения пункта b).

Будем считать, что человек с номером N+i - это то же самое, что и человек с номером i.

Предположим, что как и в пункте a), что мы начали счет с первого человека, выбрасывали из круга M-того, и последний оставшийся в круге человек имеет номер K. Очевидно, что если бы мы начали счет со второго человека, то последний оставшийся в круге человек имел бы номер K+1, ..., если с j-го, то K+j-1.

Если номер оставшегося человека L, то из равенства L=K+j-1 определяем номер j первого человека (если j< =0, то заменим j на j+N, считая как и раньше, что человек с номером N+j - это то же самое, что и человек с номером j).

Задача №19

Задана полоска длиной 2^k клеток и шириной в одну клетку. Полоску сгибают пополам так, чтобы правая половинка оказалась под левой. Сгибание продолжают до тех пор, пока сверху находится больше одной клетки. Необходимо пронумеровать клетки таким образом, чтобы после окончания сгибания полосы номера клеток в получившейся колонке были расположены в порядке 1, 2, 3, 4,..., 2^k.

Будем моделировать сложение полоски, затем пронумеруем получившуюся колонку клеток числами от 1 до 2ⁿ, после чего распечатаем числа, приписанные первой, второй, ..., 2ⁿ-ой клетке исходной полоски.

Сначала создаем двусвязный список, состоящий из 2^k элементов. Поле next будет указывать на элемент находящийся под данным, а поле last - на элемент находящийся над данным. Для верхнего элемента last=0, а для нижнего next=n+1, где n-общее число элементов. Вначале длина верхней полоски равняется n элементов, после первого сгибания их она станет n/2, после второго - n/4, и т.д. Пусть в данный момент длина верхней полоски есть cn элементов. Значит нам необходимо cn/2 правых элементов опустить под cn/2 левых. Для этого запустим цикл, который будет менять i от 1 до cn/2 и на каждом шаге помещать (cn-i+1)-ю колонку элементов под i-ю, при этом порядок элементов в (cn-i+1)-ой колонке меняется на противоположный. После каждого сгибания cn уменьшается вдвое. Так продолжаем до тех пор пока cn> 1.

Программа

{$A-, B-, D-, E+, F-, I-, L-, N-, O-, R-, S-, V-}{$M 65520, 0, 655360}uses crt; constmaxk = 13; {Максимальное значение для k}typeinput = recordlast, next, new: word; end; vark, i, j, n, cn, half: word; m: array[1..1 shl maxk] of input; Procedure concat(a, b: word); var i, j, nj: word; begini: =a; while m[i].next< > n+1 do i: =m[i].next; j: =b; while m[j].next< > n+1 do j: =m[j].next; while j< > 0 dobeginnj: =m[j].last; m[i].next: =j; m[j].last: =i; i: =j; j: =nj; end; m[i].next: =n+1; end; beginWrite('Enter k...'); readln(k); n: =1 shl k; {Определение длины полоски}for i: =1 to n do{Начальные значения}with m[i] dobeginlast: =0; next: =n+1; new: =0; end; cn: =n; while cn> 1 do {Сгибание полоски}beginhalf: =cn div 2; for i: =1 to half do concat(i, cn-i+1); cn: =half; end; j: =1; for i: =1 to n do {Нумерация клеток}beginm[j].new: =i; j: =m[j].next; end; for i: =1 to n do write(m[i].new: 5); writeln;

end.

Попробуйте найти формулу и написать программу, которая без моделирования складывания полоски по номеру клетки выдавала бы ее номер.

Задача №20

Квадрат разбит на 4^k равновеликих квадратных клеток. Квадрат перегибается поочередно относительно вертикальной (правая половина подкладывается под левую) и горизонтальной (нижняя половина подкладывается под верхнюю) оси симметрии до тех пор, пока все клетки не будут расположены друг под другом. Требуется занумеровать клетки исходного квадрата таким образом, чтобы в результате выполнения операций перегиба номера клеток, расположенных друг под другом, образовали числовую последовательность 1, 2, 3,..., 4^k, начиная с верхней клетки.

Решение этой задачи аналогично решению предыдущей задачи со сгибанием полоски с той лишь разницей, что тут будет поочередно производится два сгибания: сначала правая половина под левую, а затем нижнюю под верхнюю

{$A-, B-, D-, E+, F-, G-, I+, L-, N-, O-, R-, S-, V-, X-}{$M 16384, 0, 655360}uses crt; constmaxk = 6; typeinput = recordlast1, last2, next1, next2, new: word; end; vark, i, j, i1, i2, j1, j2, nj1, nj2, n, n1, cn, half: word; m: array[1..1 shl maxk, 1..1 shl maxk] of input; Procedure concat(a, b, c, d: word); var i1, i2, j1, j2, nj1, nj2: word; begini1: =a; i2: =b; while (m[i1, i2].next1< > n+1) and (m[i1, i2].next2< > n+1) dobegini1: =m[i1, i2].next1; i2: =m[i1, i2].next2; end; j1: =c; j2: =d; while (m[j1, j2].next1< > n+1) and (m[j1, j2].next2< > n+1) dobeginj1: =m[j1, j2].next1; j2: =m[j1, j2].next2; end; while j1< > 0 dobeginnj2: =m[j1, j2].last2; nj1: =m[j1, j2].last1; m[i1, i2].next1: =j1; m[i1, i2].next2: =j2; m[j1, j2].last1: =i1; m[j1, j2].last2: =i2; i1: =j1; i2: =j2; j1: =nj1; j2: =nj2; end; m[i1, i2].next1: =n+1; m[i1, i2].next2: =n+1; end; beginWrite('Введите k...'); readln(k); n: =1 shl k; {Определение числа клеток в одной строке или столбце}n1: =n*n; {Определение числа клеток в матрице}for i: =1 to n dofor j: =1 to n do with m[i, j] do beginlast1: =0; next1: =n+1; last2: =0; next2: =n+1; new: =0; end; cn: =n; while cn> 1 do {сгибание матрицы}beginhalf: =cn div 2; for i: =1 to half do {сгиб по вертикали}for j: =1 to cn do concat(j, i, j, cn-i+1); for i: =1 to half do {сгиб по горизонтали}for j: =1 to half do concat(i, j, cn-i+1, j); cn: =half; end; j1: =1; j2: =1; for i: =1 to n1 do {Назначение клеткам новые номера}beginm[j1, j2].new: =i; nj1: =m[j1, j2].next1; nj2: =m[j1, j2].next2; j1: =nj1; j2: =nj2; end; for i: =1 to n do {Вывод результатов}beginfor j: =1 to n do write(m[i, j].new: 8); writeln; end; end.

Задача №21

Имеется n черных и белых карточек, сложенных в стопку. Карточки раскладываются на стол в одну линию следующим образом: первая кладется на стол, вторая под низ стопки, третья- на стол, четвертая - под низ стопки и т.д., пока все карточки не будут выложены на стол. Каким должно быть исходное расположение карточек в стопке, чтобы разложенные на столе карточки чередовались по цвету: белая, черная, белая, черная и т.д.

Проще всего взять и промоделировать раскладку карточек: берем стопку из n черных и белых карточек и начинаем расклад как говорится в задаче - первая на стол, вторая под низ, третья на стол, и т.д. при этом первой выложенной карточке приписывается белый цвет, а каждой последующей - цвет, не совпадающий с цветом предыдущей карточки. Повторяет так, пока не найдем раскраску всех n карточек.

Для этой задачи возьмем такую структуру данных как список. У списка есть начало и конец, и каждый элемент его указывает на следующий за ним элемент. Будем считать, что у последнего элемента списка указатель на следующий за ним равен 0. Список можно представлять массивом. Например, если в списке 4 элемента, то массив будет выглядеть так:

т.е. за первым элементом находится A[1]=2 элемент, ..., за 4-ым - A[4]=0 (т.к. 4-ый элемент списка последний).

Пусть у нас есть указатель на начальный элемент списка и на последний (BEG и FIN соответственно). В списке n элементов.

Рассмотрим процедуру удаления элемента из начала списка (это соответствует переносу карточки на стол):

BEG: =A[BEG]; {теперь новый первый элемент списка - второй элемент старого списка}

Рассмотрим операторы перестановки элемента из начала списка в конец (это соответствует перемещению карточки сверху стопки под низ ее):

A[FIN]: =BEG; {следующей за последним элементом - бывший первый}FIN: =BEG; {меняем ссылку на последний элемент}BEG: =A[BEG] {новый первый элемент}A[FIN]: =0 {корректировка ссылки у последнего элемента}Фрагмент программы будет выглядеть так: for i: =1 to N-1 do A[i]: =i+1; A[N]: =0; {установка ссылок в списке}BEG: =1; FIN: =N; COLOR: =1; {белый цвет = 1, черный = 0}while A[BEG]< > 0 do {пока первый элемент не является} {одновременно и последним}beginBEFORE: =BEG; {сохраняем индекс начала списка}BEG: =A[BEG]; {удаляем первый элемент из списка}A[BEFORE]: =COLOR; {раскрашиваем удаленный элемент} {в нужный цвет}COLOR: =1-COLOR; {меняем цвет}A[FIN]: =BEG; {переставляем элемент из}FIN: =BEG; {начала списка в конец}BEG: =A[BEG]; A[FIN]: =0end; A[BEG]: =COLOR; {раскрашиваем последний элемент}{списка}for i: =1 to N do {распечатка цветов}if A[i]=0then writeln('элемент', i, ' - черный')else writeln('элемент', i, ' - белый');

Задача №22

Фоpма тела задана матpицей А pазмеpности M x N. Элементы матpицы - натуpальные числа. Элемент А ( i, j ) соответствует высоте гоpизонтальной квадpатной площадки pазмеpа 1 x 1 относительно нижнего основания.Нижнее основание фоpмы горизонтально.

Объем воды равен 1.

b) В позицию (i₀, j₀) выливается объем воды V.

Для реализации данного алгоритма нам понадобится структура данных " очередь". Очередь в программировании, как и очередь в магазине, имеет начало и конец. Если приходит новый элемент, то он становится в конец очереди, если необходимо взять элемент из очереди, то он берется из ее начала. Очередь будем представлять в виде массива. Пусть у нас есть индекс первого - BEG и последнего FIN элементов очереди (если очередь пуста, то BEG=FIN+1; сначала же BEG=1, FIN=0).

Очередь опишем так: var Queue=array[1..MaxQ] of element;

Тут MaxQ - максимальное число элементов в очереди, element какой-то тип данных. В задаче ниже в качестве element можно взять такой type element = record x: byte; y: byte; end; где element - это запись, состоящая из x-овой и y-овой координаты элемента матрицы A=array[0..M+1, 0..N+1] of integer. Индексы матрицы принимают такое значение из-за того, что мы будем окаймлять матрицу нулевыми элементами (так будет проще проверять выливание за край фигуры).

С очередью можно проводить операции:

вставка в очередь InQueue,

удаление из очереди OutQueue.

Procedure InQueue (x: element); beginFIN: =FIN+1; {на первое свободное место}Queue[FIN]: =x; {ставим элемент x}end; Procedure OutQueue (var x: element); beginx: =Queue[BEG]; {берем первый элемент}BEG: =BEG+1; {и изменяем указатель}{на следующий за ним}

end;

Находим максимальный элемент D в матрице A. Пока все элементы в матрице A не станут равны D, повторяем следующую последовательность действий:

а) Находим в матрице минимальный ненулевой элемент z (если их несколько, то берем любой из них), и заносим его в очередь (очередь сначала пустая). Если этот минимальный ненулевой элемент z=D, то СТОП.

Сначала считаем, что p=D - это минимальный граничный элемент области, заполненной элементами со значением z.

б) Для каждого еще не просмотренного элемента очереди (пусть в матрице этот элемент находится в позиции (i, j)) повторяем следующее:

Для каждого соседа (сверху, снизу, справа, слева) данного элемента (i, j) проводим проверку-просмотр:

ЕСЛИ (сосед < > z) ТО P=min{P, сосед} ИНАЧЕ ЕСЛИ сосед еще не просмотрен ТО координата соседа - в очередь (в очереди появился еще один непросмотренный элемент) т.е. мы ищем минимальный окаймляющий элемент области, заполненной элементами со значением z.

Фрагмент программы поиска:

end;

Если в очереди нет больше непросмотренных элементов, то, если p< z (случай, когда данная область имеет " слив" за границы матрицы) в матрице во все просмотренные элементы из очереди заносим значение D (делаем их равными накопленному значению, чтобы больше их не рассматривать).

Если же p> z, то высчитываем, сколько воды поместится в " бассейн" с глубиной дна z и с высотой ограждающего бордюра p:

Объем = (p-z)* количество просмотренных элементов в очереди.

Добавляем полученный объем к ранее найденному объему воды, заполняющему матрицу до высоты x. Заполняем в матрице элементы, соответствующие просмотренным элементам из очереди, значением p (" Доливаем" воды в " бассейн" до уровня p). Переход на пункт а).

Суммарный полученный объем воды и является искомым.

Окаймление матрицы, упомянутое выше, может выглядеть следующим образом: матрица [1..N, 1..M] окаймляется нулями так: вводятся дополнительные нулевые 0-ая и (N+1)-ая строки и 0-ой и (M+1)-ый столбцы

var A: array[0..N+1, 0..M+1] of byte; {ввод и окаймление нулями}for i: =1 to N do beginA[i, 0]: =0; A[i, M+1]: =0; for j: =1 to M do read(A[i, j]); end; for j: =0 to M+1 do beginA[0, j]: =0; A[N+1, j]: =0; end;

Задача №23

Ханойские башни

12 3 4 5 6 7 8 9 10 Следующая ⇒