www.chms.ru - вывоз мусора в Балашихе 

Динамо-машины  Обратные коды 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 [ 126 ] 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189

на данную группу из р разрядов множителя по сравнению с соответствующей группой из р - 1 разрядов.

Рассмотрим сначала те комбинации из р цифр, в которых левая цифра есть 0.

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

Легко убедиться также, что если вторая цифра больше /2, то количество суммирований-вычитаний при переходе от группы из р - I разрядов к группе из р разрядов должно увеличиться на 1. Действительно, если старшая цифра в группе из р - 1 разрядов больше /2, то, каковы бы ни были остальные разряды этой группы, в ее оптимальном представлении должна обязательно присутствовать единица, передаваемая в следующий по весу разряд. Если в группы объединяется по (р - 1) разрядов, то эта единица добавляется к следующей группе из (р - 1) разрядов. При этом вероятности всех комбинаций в этой следующей группе, кроме комбинации 00...О, сохраняются неизменными, комбинация 00...О становится невозможной, но зато с той же вероятностью может появиться комбинация 1..00...0 (для которой также не требуется ни одного суммирования или вычитания); поэтому математическое ожидание количества суммирований-вычитаний при умножении на следующую группу разрядов не изменяется от того, что в нее передается единица из предыдущей группы. Однако когда мы, переходя от группы из р - 1 разрядов к группе из р разрядов, приписываем к ней слева один разряд и ставим в этот разряд цифру laquo;О raquo;, то передаваемая в этот разряд из младших разрядов единица потребует лишнего суммирования при умножении на группу из р разрядов (в последнем из р циклов умножения). Попытка изменить способ преобразования младших разрядов с тем, чтобы не было передачи единицы в старший (р-й) разряд, привела бы к тому, что в (р - 1)-м цикле умножения количество суммирований-вычитаний возросло бы по крайней мере на 1.

Итак, если левая из р цифр есть О, то в /2 случаях (в комбинациях 00..., 01..., 02..., О () ...) количество сумми-



рований-вычитаний такое же, как при умножении на соотг ветствующую группу из р - 1 цифр; в п/2 - 1 случаях (в комбинациях О ()... ,0(-Ц:). О (п-1),..) оно

нЗ 1 больше, чем для соответствующих групп из р-1 цифр; последний из возможных случаев - когда левая из р цифр есть О, а следующая за ней цифра в точности равна /г (т. е.

когда имеем комбинацию О . . - требует особого рассмотрения.

Если р = 2, то при умножении на группу из р цифр

laquo;О raquo; требуется такое же количество суммирований-вычи-

таний, как при умножении на соответствующую группу из р - 1 разрядов (при этом р - 1 = 1; соответствующая группа из р - 1 разрядов представляет собой просто 1 разряд, в котором записана цифра /г и при умножении на который требуется /г суммирований; при умножении

на группу из р = 2 цифр laquo;О у raquo; тоже требуется /г суммирований). Если р gt;2, то изменение количества суммирований-вычитаний при переходе от группы из р - 1 разрядов вида 72- к группе из р разрядов вида О. . . зависит от следующей цифры. Аналогично предыдущему можно показать, что в laquo;/г - 1 случаях (в комбинациях 0-0..., и , г,п и-4 ч

и-у 1 .. . IJy-2~- - ) количество суммировании при умножении на группу из р разрядов остается таким же, как при умножении на соответствующую группу из р - 1 разрядов,

в /2 случаях (в комбинациях 0 plusmn;...fiJL

0(r-1). ..) она возрастает на 1, а в одном случае -

для комбинации О y~~2~ -требуется особое рассмотрение. В частности, при р = 3 умножение на группу разрядов laquo;О Y raquo; требует столько же суммирований-вычитаний, как умножение на соответствующую группу из

, п п - 2

р-1 разрядов laquo;у-2- raquo;; при р gt;-3 изменение в ко-



личестве суммирований-вычитаний для комбинаций вида О у .. зависит от четвертой цифры. Приведенное рассуждение можно продолжить и дальше.

Теперь выпишем все те комбинации, начинающиеся с О, для которых количество суммирований-вычитаний больше на 1, чем для соответствующих комбинаций из р - 1 разрядов. Сюда войдут:

- комбинации вида О . . . , О . . . , . . ., 0{п--1) . . . ; их суммарная вероятность равна

- комбинации вида. О -g- у. . . , О у- * О у(п- 1)... ; их суммарная вероятность у ;

иге - 2 п иге - 2и--2 -комбинации вида О у-g-у. . -Оу---g- . . .,

. .., О -к- {п - 1)... ; их суммарная вероят-.

ность (у - l)-; и т. д.

Таким образом, комбинации, начинающиеся с О, в общей сложности внесут в разность Ар - Лp iследующую величину: при р четном

при р нечетном

Aa-(l-i)i+4.+(l-)i+-+l-,?-

Отсюда для любого р gt; 2 можно записать

Д(о) = пР+-п gt;~п+1-(-1Г(п-1) 2(,г2-1)иР

Рассмотрим далее комбинации, начинающиеся с цифры 1. Нетрудно показать, что в тех случаях, когда в комбинациях, начинающихся с цифры О, количество суммирований-вычитаний при переходе от групп по р - 1 разрядов



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 [ 126 ] 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189