АЛФАВИТ

[wpoms.]

Вы не находите странным, что некоторые "почти равные" числа записываются абсолютно по-разному? Например, в десятичной системе счисления числа `29` и `30` отличаются всего на единицу, но их запись не содержит ни одной общей цифры. Во избежание такой ситуации код АЛФАВИТ предлагает запись чисел последовательностью нулей и единиц: Десятичная система счисления: `|0|1|2|3|4|5|6|7|8` АЛФАВИТ: `| 0 | 1 | 11 | 10 | 110 | 111 | 101 | 100 | 1100` Правило построения следующего числа в коде АЛФАВИТ таково: в предыдущем числе нужно изменить крайний правый символ, если это возможно, если нет — приписать слева единицу. (a) Какому числу в десятичной системе счисления соответствует запись в АЛФАВИТе `111111`? (b) Какое число следует за ним в этом коде? (c) Опишите алгоритм, рассчитывающий для каждого числа в коде АЛФАВИТ число, следующее за ним.

@темы: Теория чисел

Comments

[Adjirranirr]

если это возможно

Это всегда возможно. Если имеется ввиду «если для получения предыдущего числа цифра не менялась», то возникают вопросы по формальному описанию соответствия десятичных цифр строкам АЛФАВИТа — `6 != 5 + 1`, в частности.

Или я чего-то не понимаю в действии оператора `+ 1`?

[Дилетант]

Adjirranirr, надо полагать, что действия с числами мы в АЛФАВИТе не производим. Это только средство записи. Как иероглифы. Нули и единицы не имеют никакой семантики. Здесь чистый синтаксис.

[Adjirranirr]

Если считать, что первые 8 неотрицательных целых чисел не подчиняются правилам `+1`, то тогда `9 = 8 + 1 = 1101`, `10 = 9 + 1 = 11101`, `11 = 10 + 1 = 11100`. Тогда вторая справа цифра всегда будет нулем, т.к. она инвариантна по действию оператора `+1`.

[Дилетант]

если это возможно
Это всегда возможно.

Это мой корявый перевод. (

[Adjirranirr]

Здесь чистый синтаксис.

Тем не менее, претензия на взаимное соответствие слов АЛФАВИТа натуральным числам есть.
У нас есть достаточно данных для построения строгой аксиоматики над этими словами — `1 \in `АЛФАВИТ^*, `S(n) \in`АЛФАВИТ^*, вполне упорядоченность (откуда — индукция). Так что формализация эквивалентна аксиомам Пеано или построению непредельных ординалов.

[Дилетант]

Что-то тут нечисто...
Получается, вопросы (а) и (b) не имеют смысла...

[Adjirranirr]

Если не смотреть на тот факт, что `6 != 5 + 1`, и строить формализацию от нуля с заданной функцией следования, то получится примерно следующее:

(без оптимизации кода, VS C++ 2012, /O2)

#include <fstream>
#include <string>
using namespace std;

inline string operator++ (string &A) {
	int L = A.length ();
	int P = A [L - 1] == '1' ? 1 : 0;
	if ((L + P) % 2) {
		A [L - 1] = P ? '0' : '1';
	}
	else {
		A = "1" + A;
	}
	return A;
}

void main () {
	string A;
	A = "0";
	ofstream F ("out.txt");
	for (int i = 0; i < 1024; i++) {
		F << i << ": " << A << endl;
		A++;
	}
	F.close ();
}

Вывод:

0: 0
1: 1
2: 11
3: 10
4: 110
5: 111
6: 1111
7: 1110
8: 11110
9: 11111
10: 111111
11: 111110
12: 1111110
13: 1111111
14: 11111111
15: 11111110
16: 111111110
17: 111111111
18: 1111111111
19: 1111111110
20: 11111111110
21: 11111111111
22: 111111111111
23: 111111111110
24: 1111111111110
25: 1111111111111
26: 11111111111111
27: 11111111111110
28: 111111111111110
29: 111111111111111
30: 1111111111111111
31: 1111111111111110
32: 11111111111111110

[Adjirranirr]

Для формального описания оператора `+1` достаточно заметить, что `(n + 1) + 1 = 1 \oplus \hat(n)`, где `\hat(n)` обозначает изменение последнего символа, а `\oplus` — конкатенацию строк.
Тогда `(((n + 1) + 1) + 1) + 1 = 11 \oplus n`; тогда последний символ нужно менять в том и только в том случае, когда `\text{len} (n) + \text{ld} (n)` четно; `\text{len} (\cdot)` и `\text {ld} (\cdot)` — функции, возвращающие длину строки `n` и ее крайний правый символ соответственно.

[Дилетант]

Нет. Кажется, я поняла, как звучит условие.

в предыдущем числе нужно изменить крайний правый символ, если это возможно, если нет — приписать слева единицу.

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

Приношу извинения за неверный перевод.

[Adjirranirr]

Вот теперь стало интереснее =)

Приношу извинения за неверный перевод.

Ничего страшного.

[Trotil]

в предыдущем числе нужно изменить крайний правый символ

Пример алфавита не удовлетворяет этому требованию.
Алфавит в задаче - пример кода, в котором соседние числа отличаются только одним битом.
Переход из N битных слов в N+1 битные осуществляется только тогда, когда N-битные комбинации исчерпаны.

Вообще говоря, существует много способов написать такой код, но есть один с определённой закономерностью (именно он дан в примере). И он даже специальное название имеет в АТК.
Практическое применение этого кода - допустим, у нас есть N бинарных переключателей. Нужно проверить все комбинации, при этом минимизировать число переключений.

[Adjirranirr]

Ну это код Грэя в первозданном виде, без нулей на ведущих позициях.

Переход из N битных слов в N+1 битные осуществляется только тогда, когда N-битные комбинации исчерпаны.

А вот это я доказать не смог =) Полнота (т.е. равенство АЛФАВИТ = {0, 1}^*) сразу ведет к симметричности относительно «предельных» чисел (т.е. таких, после которых идет переход длины) с изменением ведущего бита; откуда формула для преобразования бинарного представления в код: Gray (n) = n ⊕ [n / 2]. Отсюда уже несложно получить формулу обратного преобразования — n = Gray (n) ⊕ [Gray (n)/2] ⊕ ... ⊕ [Gray (n)/2^k].

[Trotil]

Ну это код Грэя в первозданном виде

я знаю.

А вот это я доказать не смог

доказать исходя из каких условий? В коде Грея это выполняется. А условие в данной задаче не соответствует примеру, следовательно - где-то неточность.

[Adjirranirr]

Условие просто не подправлено.

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

В такой формулировке это код Грэя, а вот доказать соответствие у меня пока не получилось.