Здравствуйте, Erop, Вы писали:

E>Не уверен, что это тут было, и не уверен, что это именно для программистов.
E>Но задам.

E>Мы разрабатываем свой стандарт QR-кода.

E>Наш QR-код размера NxN -- это квадратик из N x N пикселей. каждый пиксель чёрный или белый.
E>Трудность состоит в том, что когда мы сканируем код, мы не знаем, какой стороной повёрнут квадрат. Возможны все 4 варианта (0, 90, 180 и 270 градусов)
E>Вопрос? Сколько разных уникальных чисел можно закодировать таким кодом, так, что бы считываемое число не зависело от ориентации квадрата.

Без учета поворота можно закодировать M_0=2^(n*n) комбинаций.
Число симметричных по отношению к повороту на 180 градусов:
для четных n, M_180(n)=2^(n*n/2) (заполняем информацией только половину клеток)
Для нечетный n, M_180(n)=2^((n*n-1)/2 +1) (отдельно учитываем центральный бит).
Обобщаем: M_180(n)=2^(((n*n)+1*(n%2))/2)

Аналогично:
M_90(n)=2^(n*n/4) , если n%2==0
M_90(n)=2^((n*n-1)/4+1) , если n%2==1
M_90(n)=2^(((n*n)+3*(n%2))/4 ) , в общем случае.

Общее M, которое мы можем закодировать:
M(n) = ( M_0(n) — M_180(n) ) /4 + (M_180(n) — M_90(n))/2 + M_90(n)
Если все подставить, то получится последовательность приведенная watchmaker -ом, наверное.
Численно совпадает:
2, 6, 140, 16456, 8390720, 17179934976L, 140737496748032L, 4611686019501162496L, 604462909807864344215552L

Здравствуйте, Qulac, Вы писали:

Q>Здравствуйте, Erop, Вы писали:

E>>Не уверен, что это тут было, и не уверен, что это именно для программистов.
E>>Но задам.

E>>Мы разрабатываем свой стандарт QR-кода.

E>>Наш QR-код размера NxN -- это квадратик из N x N пикселей. каждый пиксель чёрный или белый.
E>>Трудность состоит в том, что когда мы сканируем код, мы не знаем, какой стороной повёрнут квадрат. Возможны все 4 варианта (0, 90, 180 и 270 градусов)
E>>Вопрос? Сколько разных уникальных чисел можно закодировать таким кодом, так, что бы считываемое число не зависело от ориентации квадрата.

Q>Не зависить будет, если квадрат будет состоять из одинаковых четвертинок, тогда как не поверни — будет одинаково выглядеть.

Не-а. Достаточно поместить orientation mark, чтобы понимать где точка отсчёта. Например, 2х2 на углах.

Здравствуйте, Pzz, Вы писали:


Pzz>Я понимаю, как закодировать (N^2 — 3) бита. Теорпредел, вроде, (N^2 — 2). Но как отбить еще один бит, как-то не придумувается, придумывается только, как полбита отбить (т.е., (N^2 — 3)*3 вариантов)

Откуда следует, что ответ -- степень двойки?

6 для N == 2 как бы намекает, что это не так

Здравствуйте, Chorkov, Вы писали:

C>M(n) = ( M_0(n) — M_180(n) ) /4 + (M_180(n) — M_90(n))/2 + M_90(n)
C>Если все подставить, то получится последовательность приведенная watchmaker -ом, наверное.
C>Численно совпадает:
C>2, 6, 140, 16456, 8390720, 17179934976L, 140737496748032L, 4611686019501162496L, 604462909807864344215552L

Ну да. Я решал как-то так же. Только на мой вкус тут не хватает аргументации в защиту того, что ещё больше нельзя. Но она довольно очевидная, IMHO.

Здравствуйте, Erop, Вы писали:

Pzz>>Я понимаю, как закодировать (N^2 — 3) бита. Теорпредел, вроде, (N^2 — 2). Но как отбить еще один бит, как-то не придумувается, придумывается только, как полбита отбить (т.е., (N^2 — 3)*3 вариантов)

E>Откуда следует, что ответ -- степень двойки?

E>6 для N == 2 как бы намекает, что это не так

Я, как всегда, невнимателен, и к тому моменту, когда писал ответ, был уверен, что вопрос звучит, сколько битов можно закодировать.

А разных чисел, мой ответ 2^(N^2 — 3) * 3

Для N == 2 сходится

Здравствуйте, Pzz, Вы писали:

Pzz>А разных чисел, мой ответ 2^(N^2 — 3) * 3

Pzz>Для N == 2 сходится

Для 1 не особо сходится

А для 3 получается 192?

А как закодировать?

Здравствуйте, Erop, Вы писали:

R>>До меня только теперь дошло, о чем ты спрашивал в корневом сообщении. Ну так это же просто.придир. Считать лень.
E>Ещё хорошо бы доказать, что больше нельзя.
E>Ну и хорошо бы проверить, что хотя бы для N == 1 и N == 2 формула работает

Два дня у меня чесались руки, наконец-то добрался. Итак, поехали.

Число уникальных изображений матрицы монохромных пикселей размера NxN, о котором спрашивается в задаче, задается общей формулой:



где n₁ — полное количество избражений, не обладающих поворотной симметрией (формально: имеющих ось симметрии 1-го порядка):



n₂ — полное количество избражений, имеющих ось симметрии 2-го порядка):

Для четных N:


Для нечетных N:


n₄ — полное количество избражений, имеющих ось симметрии 4-го порядка):

Для четных N:


Для нечетных N:


Подставляя выражения для n₁, n₂ и n₄ в общую формулу, после упрощения получим итоговые выражения:

Для четных N:


Для нечетных N:


Если очень хочется, обе формулы без особого труда можно слить в одну.

Вместо доказательства проверка :

N	x
0	1
1	2
2	6
3	140
4	16456
5	8390720
6	17179934976
7	140737496748032

Здравствуйте, rg45, Вы писали:


R>Два дня у меня чесались руки, наконец-то добрался. Итак, поехали.

Я решал так же.
Но это решение уже выше кто-то дал.

Чего на мой вкус тут не хватает -- обоснования того, что нельзя больше.

Здравствуйте, Erop, Вы писали:

E>Чего на мой вкус тут не хватает -- обоснования того, что нельзя больше.

Обоснование очень простое — все варианты, которые мы отбросили, гарантированно являются повторениями и это ясно уже из самого решения. Здесь если и стоит о чем-то беспокоиться, так об обратной проблеме — а все ли мы отсекли, что нужно было, или, может, провтыкали что-нибудь. Но, имхо, здесь все просто, как чугунная сковородка.

Здравствуйте, Erop, Вы писали:

E>Чего на мой вкус тут не хватает -- обоснования того, что нельзя больше.

Я, кажется, понял твою мысль. Ты имеешь в виду, что, возможно, что при N, больших какого-то определенного значения, может стать выгодным жертвовать тремя угловыми пикселами, как об этом говорилось здесь

Автор: Brice Tribbiani
Дата: 01.02.18

? А может и не стать. Да, интересно, надо обмозговать.


[Upd]: Да, но нет! Жертвование пикселами никогда не будет выигрышным. Из формул, выведенных здесь

Автор: rg45
Дата: 03.02.18

видно, что тот подход обеспечивает оценку "снизу":



В то время как, жертвуя тремя пикселами, мы всегда будем иметь ровно



Лично для меня это далеко неочевидный и просто поразительный вывод: отбрасывание части изображений, обладающих поворотной симметрией 2-го и 4-го порядков ВСЕГДА урезает результат в меньшей степени, чем отбрасываение каких-то несчастных трех пикселей!

Здравствуйте, Erop, Вы писали:

E>Не уверен, что это тут было, и не уверен, что это именно для программистов.
E>Но задам.

E>Мы разрабатываем свой стандарт QR-кода.

E>Наш QR-код размера NxN -- это квадратик из N x N пикселей. каждый пиксель чёрный или белый.
E>Трудность состоит в том, что когда мы сканируем код, мы не знаем, какой стороной повёрнут квадрат. Возможны все 4 варианта (0, 90, 180 и 270 градусов)
E>Вопрос? Сколько разных уникальных чисел можно закодировать таким кодом, так, что бы считываемое число не зависело от ориентации квадрата.

На всякий случай комментарий немного в сторону: надо понимать, что процесс считывания QR может быть подвержен ошибкам (начиная с той же ошибки приграничной дискретизации: серое — это чёрное или белое?) Поэтому для практического применения не забудьте про встроенный в QR-код контроль целостности данных. Иначе trash in — trash out.

Здравствуйте, Mr.Delphist, Вы писали:

MD>На всякий случай комментарий немного в сторону: надо понимать, что процесс считывания QR может быть подвержен ошибкам (начиная с той же ошибки приграничной дискретизации: серое — это чёрное или белое?) Поэтому для практического применения не забудьте про встроенный в QR-код контроль целостности данных. Иначе trash in — trash out.

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

Здравствуйте, watchmaker, Вы писали:

W>Короче говоря, с первого взгляда любому ясно, что это последовательность A047937

И поэтому странно, что этюд задал не nikov, а Erop!

Здравствуйте, Кодт, Вы писали:

W>>Короче говоря, с первого взгляда любому ясно, что это последовательность A047937

К>И поэтому странно, что этюд задал не nikov, а Erop!

Я такой способ решения -- поискать в гугле, практикую только на работе