Счётчик Кнута - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:13:10Z

rollbackEdits.php mass rollback

94.16.121.91 в 06:02, 1 сентября 2022

2022-09-01T06:02:38Z

83.102.218.99: /* Пример */

2021-03-17T13:03:37Z

‎Пример

217.66.152.112: Опечатка. Слово "дувумя" исправлено на "двумя".

2019-10-23T11:11:17Z

Опечатка. Слово "дувумя" исправлено на "двумя".

Arthurii: 2 поправки орфографии.

2019-07-10T15:07:41Z

2 поправки орфографии.

Arthurii: Поправка грамматики.

2019-07-10T15:05:03Z

Поправка грамматики.

Arthurii: 3 поправки языка.

2019-07-10T15:02:55Z

3 поправки языка.

Дмитрий Мурзин: Дмитрий Мурзин переименовал страницу Счетчик Кнута в Счётчик Кнута: Ёфикация

2019-01-31T20:50:49Z

Дмитрий Мурзин переименовал страницу Счетчик Кнута в Счётчик Кнута: Ёфикация

DmitryGM: Поправил степень двойки

2018-09-21T21:24:38Z

Поправил степень двойки

Shersh: /* Инвариант с нулем */

2014-06-15T22:10:35Z

‎Инвариант с нулем

← Предыдущая		Версия 16:13, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|id=knuth_counter		\|id=knuth_counter

← Предыдущая		Версия 06:02, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|id=knuth_counter		\|id=knuth_counter

@@ Строка 58: / Строка 58: @@
 ==== Пример ====
-В таблице можно увидеть как будет изменятья представление при применении данных правил десять раз к нулю (представления чисел от <tex>0</tex> до <tex>9</tex>):
+В таблице можно увидеть как будет изменяться представление при применении данных правил десять раз к нулю (представления чисел от <tex>0</tex> до <tex>9</tex>):
 {| class="wikitable"

@@ Строка 105: / Строка 105: @@
 {{Определение
 |id=regular_rr
-|definition= Назовем представление '''регулярным''' (англ. ''regular''), если между дувумя разрядами равными <tex>b</tex> есть хотя бы один разряд отличный от <tex>b-1</tex>.
+|definition= Назовем представление '''регулярным''' (англ. ''regular''), если между двумя разрядами равными <tex>b</tex> есть хотя бы один разряд отличный от <tex>b-1</tex>.
 }}

@@ Строка 110: / Строка 110: @@
 {{Определение
 |id=fixup
-|definition= Операция '''исправления''' (англ. ''fix'') разряда <tex>d_i=b</tex> в регулярном ИП увеличивает <tex>d_{i+1}</tex> на <tex>1</tex> и устанавливает <tex>d_i</tex> в <tex>0</tex>, образуая новое регуляроне ИП, представляющее то же число, что и <tex>d</tex>.
+|definition= Операция '''исправления''' (англ. ''fix'') разряда <tex>d_i=b</tex> в регулярном ИП увеличивает <tex>d_{i+1}</tex> на <tex>1</tex> и устанавливает <tex>d_i</tex> в <tex>0</tex>, образуя новое регулярное ИП, представляющее то же число, что и <tex>d</tex>.
 }}

@@ Строка 100: / Строка 100: @@
 {{Определение
 |id=b_ary_rr
-|definition=В общем случае подобное представление называется '''<tex>b</tex>-ричными избыточными представлением''' ('''ИП''', англ. ''b-ary redundant representation''), которое похоже на представление в счетчике Кнута, но основание системы может быть произвольным, то есть <tex>d_i \in \{0,1,\dotsc ,b\}</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot b^i = N</tex>, где <tex>b</tex>  {{---}} основание. Оно позволяет прибавить единицу к любому разряду, то есть увеличить число на <tex>b^i</tex> за <tex>O(1)</tex>
+|definition=В общем случае подобное представление называется '''<tex>b</tex>-ричным избыточным представлением''' ('''ИП''', англ. ''b-ary redundant representation''), которое похоже на представление в счетчике Кнута, но основание системы может быть произвольным, то есть <tex>d_i \in \{0,1,\dotsc ,b\}</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot b^i = N</tex>, где <tex>b</tex>  {{---}} основание. Оно позволяет прибавить единицу к любому разряду, то есть увеличить число на <tex>b^i</tex> за <tex>O(1)</tex>
 }}

@@ Строка 28: / Строка 28: @@
 ==== Инвариант с нулем ====
-Проблемой может оказаться появление двух последовательных двоек, при этом перое правило может породить
+Проблемой может оказаться появление двух последовательных двоек, при этом первое правило может породить
 тройку. То есть недопустима следующая ситуация:
@@ Строка 38: / Строка 38: @@
 Причем количество единиц между двойками может быть любое, в итоге это приведет к появлению тройки.
-Однако если между любой парой двоек всегда будет находится хотя бы один
+Однако если между любой парой двоек всегда будет находиться хотя бы один
-<tex>0</tex>, то такой ситуации не возникнет. Покажем, что что этот инвариант
+<tex>0</tex>, то такой ситуации не возникнет. Покажем, что этот инвариант
 поддерживается после инкремента, рассмотрев возможные ситуации:
 : Число двоек не изменяется

← Предыдущая	Версия 20:50, 31 января 2019
(нет различий)

@@ Строка 6: / Строка 6: @@
 {{Определение
 |id=knuth_counter
-|definition= Неотрицательное целое число <tex>N</tex> в '''избыточной двоичной системе счисления''' записывается в виде последовательности разрядов <tex>(d_n d_{n-1} \dotsc  d_2 d_1)</tex>, где <tex>n</tex> обозначает количество разрядов в числе, <tex>d_i</tex>  {{---}} <tex>i</tex>&ndash;й разряд числа <tex>(1 \leqslant i \leqslant n)</tex>, причем <tex>d_i \in \{0,1,2\}</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot 2^i = N.
+|definition= Неотрицательное целое число <tex>N</tex> в '''избыточной двоичной системе счисления''' записывается в виде последовательности разрядов <tex>(d_n d_{n-1} \dotsc  d_2 d_1)</tex>, где <tex>n</tex> обозначает количество разрядов в числе, <tex>d_i</tex>  {{---}} <tex>i</tex>&ndash;й разряд числа <tex>(1 \leqslant i \leqslant n)</tex>, причем <tex>d_i \in \{0,1,2\}</tex> и <tex>\sum\limits_{i=1}^n d_i \cdot 2^{i-1} = N.
 </tex>
 }}