Студопедия КАТЕГОРИИ: АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Hапечатать все последовательности длины N из чисел 1,2..MСтр 1 из 15Следующая ⇒
ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ ЗАДАЧИ И РЕШЕНИЯ ЧАСТЬ 1 Задача №1
У продавца и покупателя имеется неограниченное кол-во монет достоинством (1,2,5,10,20,50,100,200,500 к примеру). Покупатель купил товар на сумму n. Hужно найти минимальное кол-во монет, которые будут использованы при расплате. Деньги может давать как покупатель, так и продавец. Рассмотрим кольцо многочленов над некоторым полем. Пусть I некоторый идеал в этом кольце, порожденный многочленами g1, g2, ..., gn. При этом набор G={g1, g2, ..., gn} называется базисом (или системой образующих) идеала 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}. Результатом будет редуцированный базис, в котором старшие термы любых двух элементов не делятся один на другой. Доказано, что Для построения базисов Грёбнера Бухбергер придумал алгоритм, который теперь носит его имя. IK> и каким именно образом они используются ? Пусть достоинства монет 1=c0, c1, ..., cm-1. Любую сумму вида (k0-km)*c0 + (k1-km+1)*c1 + ... + (km-1-k2m-1)*cm-1, где все ki, i=0..2m-1 неотрицательны, которые мы будем кодировать мономами x0^{k0}x1^{k1}...x2m-1^{k2m-1}. Пусть I - идеал, порожденный мономами соответствующими нулевой сумме. Утв 1. Базисом I является набор многочленов x0^{ci}-xi, x1^{ci}xm+i-1, i=0..m-1. Доказательство индукцией по m. [skipped] Пусть G - базис Грёбнера идеала I относительно deglex. Пусть нам дана сумма s. Редуцируем многочлен x0^s относительно G. Утв 2. Результатом этой редукции будет многочлен x0^{k0}x1^{k1}...x2m-1^{k2m-1}, причем в каждой паре (ki,km+i), i=0..m-1 не более одного числа отлично от нуля и s = (k0-km)*c0 + (k1-km+1)*c1 + ... + (km-1-k2m-1)*cm-1 и есть искомое минимальное по числу монет представление суммы s. Доказательство от противного. [skipped] IK> Каков собственно алгоритм? Алгоритм простой: Если нужно решить несколько задач для одного и того же набора номиналов, но разных сумм, то базис Грёбнера нужно построить только один раз (это самая трудоемкая операция), и затем очень быстро проводить редукцию для каждой из сумм. {$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) Всего таких перестановок будет 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]) endend; Основная программа: 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 Hапечатать все последовательности длины N из чисел 1,2..M
First = (1,1,...,1) Last = (M,M,...,M) Всего таких последовательностей будет M^N (докажите!). Чтобы понять. как должна действовать процедура Next, начнем с примеров. Пусть N=4,M=3. Тогда: Next(1,1,1,1) -> (1,1,1,2) Next(1,1,1,3) -> (1,1,2,1) Next(3,1,3,3) -> (3,2,1,1) Теперь можно написать общую процедуру Next: procedure Next; begin {найти i: X[i]<M,X[i+1]=M,...,X[N]=M}; X[i]:=X[i]+1; X[i+1]:=...:=X[N]:=1end; Если такого i найти не удается, то следующей последовательности нет - мы добрались до последней (M,M,...,M). Заметим также, что если бы членами последовательности были числа не от 1 до M, а от 0 до M-1, то переход к следующей означал бы прибавление 1 в M-ичной системе счисления. Полная программа на Паскале выглядит так: program Sequences; type Sequence=array [byte] of byte; var M,N,i:byte; X:Sequence; Yes:boolean; procedure Next(var X:Sequence;var Yes:boolean); var i:byte; begin i:=N; {поиск i} while (i>0)and(X[i]=M) do begin X[i]:=1;dec(i) end; if i>0 then begin inc(X[i]);Yes:=true end else Yes:=false end; begin write('M,N=');readln(M,N); for i:=1 to N do X[i]:=1; repeat for i:=1 to N do write(X[i]);writeln; Next(X,Yes) until not Yes end.
Опишем рекурсивную процедуру Generate(k), предъявляющую все последовательности длины N из чисел 1,...,M, у которых фиксировано начало X[1],X[2],...,X[k]. Понятно, что при k=N мы имеем тривиальное решение: есть только одна такая последовательность - это она сама. end; Основная программа теперь выглядит очень просто: program SequencesRecursion; type Sequence=array [byte] of byte; var M,N:byte; X:Sequence; procedure Generate(k:byte); ............ begin write('M,N=');readln(M,N); Generate(0) end.Задача №4
|
||
Последнее изменение этой страницы: 2018-04-12; просмотров: 209. stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда... |