Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 25
Текст из файла (страница 25)
р(~)..., где х(1), если 1 = 1, р(1) = хЯ 9 р(1 — Ц, если 1. -. нечетное число и 4 > 1, х(1 — 1), если 1 — четное число; 0)П )= 1", если найдется число с такое, что ~ ~х(1) < с, 5)Дх )= 0" в ином случае; 1 ~, если последовательность хи такова, что с х(21 — 1) < ~~ х(21) для всех 1 = 1, 2, ..., с=с с=с 0 в ином случае; 7) с(х ) = у(1) р(2)...р(1)..., где ссс-есссг1 ~с,с 21 1, если ~ х(21 — 1) < ~ х(21), ср(1) = с=с с=с 0 в ином случае; 8) у(х ) = у(1) р(2)...р(1)..., где ~с,с21-~-1 сс/ггес 1, если ~ х(21 — 1) <;с х(21), с=с с=с 0 в ином случае; 113 у 1. Отображении последооаеаелвностед 13) 1(х ) = д(1) у(2)...у(1)..., где д(1) определяется из соотно- шений д(21) = х(21 — 1) и у(21 — 1) = х(2) — 1)'дГд(21), 1 = 1, 2, 14) ((х ") = у(1) у(2)...
у(1)..., где у(е) есть (е + 1) я цифра после запятой в двоичном разложении числа х(1)/3; 15) Дхи) = у(1) у(2)...д(1),,., где у(1) есть (31+ 2)-я цифра пос- ле запятой в двоичном разложении числа х(1+ 1)/7; 16) Дх ) = у(1)д(2)...д(1)..., где у(1) есть 2сч1-я цифра после запятой в двоичном разложении числа (2х(1+ 1) + 1) /1ос. 1.3. Через Р будем обозначать здесь подмножество всех таких слов из множества (О, Ц", в которых не встречаются две единицы подряд. Выяснить, можно ли доопределить функцию д до детерминированной, и если доопределение возможно, указать, какую-либо функцию, яв- ляющуюся доопределением функции у: 1) Дхи) = 0 при хи б Р; 2) Дхи) = х(Ц х(2)... х(1)... при хи Е Р; 3) д"(хи) = Ох ' при хи Е Р; 4) функция д" определена только на одном слово хо' —— = 11010010001...
(т.е. хо(1) = 1 лишь для 1 = 1(1 — 1)/2+ 1, 1 = 1,. 2,...) и 1(хо ) = дои — — 1010010001... (т.е. до(1) = 1 лишь при 1= [з), у =2,3, ...); 5) функция у определена только на двух словах: 0 ' и [ОЦ'', при- чем Д(Ои) = 1 и Д([ОЦ ) = 1[10)'; [О . если х е Р, (1, если хи = 1"; )О, если х ЕР, (0[Ц, если хи = 1"'; х", если хи Е Р, (0[Ц", если х = 1~; /Ох", если х" Е Р, (0[Ц", если о: = 1"; [Ох(1) х(2)...х(1)..., если хи Е Р, [00[Ц", .если х' = 1 1.4. В дереве, соответствующем функдии у из Р~', изменена п1 метка на ребре 1-го яруса, принадлежащем цепи, отвечающей входной последовательности 0". Найти вес г(1) функции у и вес г(д) вновь полученной функции д, если: 1) Дх ) = 0', 1 = 3; 2) У(хи) = х, 1 = 4; 3) у(х' ) = 00 [ОЦ, 1 = 2; 4) 1(хд ) = 0 т, 1 = 1; 5) Д(хи) = у(1) д(2)... д(1)..., где у(1) есть 1-я цифра после запя- той в двоичном разложении числа 2/3, 1 = 3; 8 Г.
П. Гаврилов, А. А. Сановсенко 114 Гв. 1У. Огранинессно-денсергсинированцые функции 1=1 где у(1) = х(1) при 1 = 1, 2., х(1 — Ц Ср х(1) с1С у(1 — Ц при 1 > 3; 2) /с(х ) = Ох(Ц Ох(2) Ох(3)... Ох(1)... (т. е, входная последовательность хи = х(Ц х(2)... х(1)... «перерабатывается» в выходную последовательность Ох(Ц Ох(2) Ох(3)..., выписанную в данном соотношении справа), /з(х ) = у(Ц у(2)... у(1)..., где О при С=1, х(<1/2<). у(1 — Ц при 1 > 2; | ~ ~ ~ ~ ~ У ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ | ~с 3) /с(х ) = х(Ц (х(Ц3ех(2))... (х(Цйех(2) и... 3ех(1))...
(те. в момент времени 1 > 2 «выход» равен х(Ц йе х(2) й ... 3е х®, а при 1 = 1 он равен х(Ц), /я(х *) = у(Ц у(2)... У(с)..., где с О, если ~ х(И) ~ 1 в ином случае; 6) /(х' ) = у(Ц у(2)... у(1)..., где у(1) есть 1-я цифра после запя- той в двоичном разложении числа 1/ьс2, 1 = 1; 7) /(х ) = у(Ц у(2)... У(1)..., где О, если 1=1,. 1=1; у(1 — Ц Юх(1), если 1 > 2, 8) /(хи) = у(ЦУ(2)...У(С)..., где у(1) = О, если 1=1, х(1) э х($ — Ц, если 1 > 2, 9) /(х ) = у(Ц у(2)... У(1)..., где 1, если 1=1, х(1) — с у(1 — Ц, если 1 > 2, 1.5.
Ц Доказать, что если изменить метку на каком-либо ребре, принадлежащем ф-му ярусу дерева, соответствующего функции / Е Е Рз „, то вес г(д) вновь полученной функции д удовлетворяет нера- венству ~г(/) — с(д)~ ( сц 2) Как может измениться вес о.-д. функции / е Рз, если в со- ответствующем ей дереве изменить метки на двух ребрах ф-го яруса? 1.6. Выяснить, эквивалентны ли д. функции /с и /з, если: Ц /с(хху ') = х(Ц х(2) х(3) х(4) х(5)...
х(2в) х(2в + Ц, .. (т, е. вход- ная последовательность х = х(Ц х(2)... х(1)... «перерабатывает- ся» в выходную последовательность х(Ц х(2) х(3) ..., выписанную в данном соотношении справа), /г(х ) — у(Ц у(2) . у(г) 8 д Отобрахсенин носледоеательноснеей 115 4) ~1(х ) = х(Ц (х(2) -+ х(Ц)(х(3) — э х(2))... (х(1) — е х(1 — Ц)... (т.е.
при б = 1 «выход» равен х(Ц, а при 1 > 2 он равен х(1) — е — е х(г — Ц)., .68(х ) = у(Ц у(2)... у(с)..., где х(1), если 1= 1, у(Х) = х(1), если 1 > 2 и х(1 — Ц = (), в остальных случаях; 5) 71(хн) = 1(х(2) о х(Ц)(х(3) — е х(Ц х(2))... (х(1) о — е х(Ц х(2) ...
х(1 — Ц) .., (т.е. при 1 = 1 «выход» равен 1, а при 1 > 2 он равен х(1) о -е х(Ц. х(2) .... х(» — 1)), ,68(хм) = у(Ц у(2)...у(1)..., г де д(1) = х(1), если 1> 2 и найдется такое 8 (1, что х(8) = О, 1 в остальных случаях; 6) Л(х~) = х(Ц1х(3)1х(5)1...1х(28 — Ц1... (т.е. входная по- следовательность х ' = х(Ц х(2)... «перерабатывается» в выходную последовательность х(Ц 1х(3) 1х(5)..., указанную в данном соотно- шении справа), 1з(х ) = у(Ц у(2)... у(1)..., х(с) при 1 = 1, д(1) = х(2[(1+ Ц/2[ — Ц ау(1 — Ц при 1 > 2; 7) 71(х~) = у(Цу(2)...у(1)..., где д(1) = 1 при 1=1, х(1) — ~ (х(1 — Ц 15 х(1). у(1 — Ц) при 1 > 2, уз(х") = 1(х(2) — ~ х(Ц)(х(3) о (х(2) — ~ х(Ц))(х(4) — ) -+ (х(2) — ) х(Ц))... (х(1) о (х(2) о х(1)))...
(т.е. при 1 = 1 «выход» совпадает с 1, при 1 = 2 — - с х(2) -+ х(Ц, а при 1 > 3 с х(1) о (х(2) — е х(Ц)), 8) д'1(х ) = у(Ц у(2)... у(1)..., где у(1) = á х(е) при 1 = 1, х(1) — ~ (х(1 — Ц вЂ” > х(б) у(1 — Ц) при 1 > 2, ез(х ) х(Ц [1] 9) 71(х~) = у(Ц у(2)... у(1)..., где д(1) = á х(с) при 1 = 1, х(1) — > (х(Ц д(1 — Ц вЂ” е х(1 — Ц) при 1 > 2, 78(х ) = х(Ц1(х(3) — о х(2))(х(4) -+ х(3))...
(х(1) -+ х(1 — Ц) .,, (т.е. при 1 = 1 «выход» совпадает с х(Ц, при 1 = 2 с 1, а при 1 > 3 с х(1) — з х(1 — Ц); 8* 116 Х'а. !7. Ограниченно-детерминированные функции 10) ~з(х ) = 01(х(2) -+ х(1))(х(3) в х(2))... (хф -+ х(1— 1))... (т.е. при 1 = 1 «выход» совпадает с О, при е = 2 -- с 1, а при Е > 3 — с х(1) -и х(е — 1)), ,(з(х") = у(1) у(2)... У(1)..., Где 0 при Ю = 1, у(1)= 1 при З=2, Я вЂ” 1)у(1 — 1) в (х(1 — 2) — ~ х($ — 1)) при 1 > 3.
1.7. Выяснить, эквивалентны ли остаточные функции (;; и (т1 д. фУнкции ( е Рз", (здесь всюдУ Д(х") = У~ = У(1)У(2) ..У(з) .. ): (х(1) при З = 1, 2, 3, Ц у(1) = (х(1) при е > 4: а) хе = 11 хе = 00101; б) хе = 010, х' = 1001; (х(Х) при й = 1, 2, 3, 2) у(1) = ~ ( х(е — 1) при 1 > 4: а) тз = 10. хз з= 011; б) хе = 111 тз = 00101; в) хаз = 0101, ха з= 1000; (х(1) при 1 нечетном, 3) УФ= ( х(е) при е четном: а) хз —— 00, хе в= 100101; б) х~~ = 101, хз з= 110; в) х~з = 0101, хе = 11111; О прн 1=1, х(1 — 1) Ю тф при 1 > 2: а) х', = 00, х, '= ИО; б) хаз = 0110, а«в = 0101; в) из = 111П, хв = 001001; 1 при в=1,2, у(Х вЂ” 2) ев у(е — 1) при З > 3: а) х~з = 10 хз = 010. б) х~з = 1110 х~ = 1011101 в) те = 11О, хе = 00101; 0 при 1=1, х(Ц -+ у(1 — 1) при з > 2: а) хз = 011, хе ~— — 1111; б) хзз — — 01111, хе —— 00111; в), = 0100, = ШО10; 7) у®= 0 при З= <'), 1=2,3,..., 1 в остальных случаях: а) хз = 101 хз = 110 б) хвз = 0101, хг — — 11011; 117 у д Отобраокенин носледооательноснеей а) х~1 = 1, хза = 0110; б) хд — — 10, ха = 00110; в) хз = 110 хо = 111101111.
(х(б), если х(1) + х(2) +... + хЯ < 1/2, 10) у®=4 (1 в ином случае: а) х~ — — 10, ха а—— 0011; б) х~~ = 111, хз — — 01111; в) х4 = 1101, ха = 10010; (О, если х(1) + х(2) +... + х([(4+ 1)/2)) < 4/3, 11) у(1) = ' 11 в ином случае: а) х з = 10, х 4 = 0110; б) х з = 110, т з = 001; в),' = 100101, т 3 = 010101; 1, если б=1 Š— 4 (б) или если 4 > 2 и ~(1 — х(4)) г < 4. х(1), х(е) 4 х(4 — 1) в ином случае: а) х~~ = 01, ха з= 11; б) х~ ~= 101, х~ ~= 0011; в) х „' = 011101, х, '= 000111; 1, если 1=1 е -1 или если 4 > 2 и 1 х(4) > 1+ ~~~ (1 — х(г)) е, 13) у(б) = 0 в ином случае: ) -з 011 -з 101, б) -з в) х" = ИОО1, = 1ОПО.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
