?

Log in

No account? Create an account
задачка для программистов - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка для программистов [сент. 5, 2002|01:36 pm]
Anatoly Vorobey
Придумал задачку. Для программистов и/или математиков. Простую, так, для забавы.

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

Задание: стабилизируется ли процентное отношение нулей и единиц в пределе? Обосновать. Если да, то найти его.

Update: На всякий случай поясню, что под ASCII я в данном случае понимаю 8-битный код, т.е. каждая двоичная цифра заменяется на восемь.

Ещё update: В комментах появились правильные ответы. Я могу в комментах написать подробное элементарное решение, если кому-то надо.
СсылкаОтветить

Comments:
[User Picture]From: gera2
2002-09-05 03:54 am
ASCII 0 = 30 = 11110
ASCII 1 = 31 = 11111

итд. по кругу.
На каждые 9 единичек один нолик
(Ответить) (Thread)
[User Picture]From: avva
2002-09-05 03:57 am
Вы неправильно поняли условие. Прочтите внимательнее.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: muchacho
2002-09-05 03:57 am

Да. Обосновал. 1/2.
(Ответить) (Thread)
[User Picture]From: avva
2002-09-05 03:58 am
Не сходится. Подавайте сюда свои обоснования и вычисления.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: edgar_poe
2002-09-05 03:58 am
Поскольку кодироваться бинарным кодом будут всё время две цифры: 0 и 1, то, думаю в пределе отношение нулей и единиц будет стремиться к сумме нулей и едениц в их представлении. В '0' - 2 единицы и 6 нулей, в '1' - 3 единицы и 5 нулей. Суммируем. Получаем 5:11.
(Ответить) (Thread)
[User Picture]From: avva
2002-09-05 04:01 am

Интересная прикидка. Но неверная.
(Ответить) (Parent) (Thread)
[User Picture]From: edgar_poe
2002-09-05 04:02 am
Поправка. При каждой итерации это соотношение будет возводиться в квадрат. В итоге будем иметь одни нули в пределе.
(Ответить) (Parent) (Thread)
From: ex_ilyavinar899
2002-09-05 04:05 am
ASCII '0' = 00110000
ASCII '1' = 00110001

Let x be the fraction of '1' in the original number; y is the fraction of '0' (y=1-x).

We have a transformation (x,y) => (3/8*x + 2/8*y, 5/8*x + 6/8*y).

I am too lazy, but one can find its eigenvalues, and solve the problem.
(Ответить) (Thread)
From: ex_ilyavinar899
2002-09-05 04:21 am
I am getting two eigenvalues: 1/8 and 1. I forgot how to calculate eigenvectors, but I can imagine that there is an unstable solution to the problem that is associated with the eigenvalue 1/8, and a stable one that is associated with the eigenvalue 1.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: tsetsefly
2002-09-05 04:23 am
1:2.5
(Ответить) (Thread)
[User Picture]From: avva
2002-09-05 04:40 am

Да, это верно.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: avva
2002-09-05 09:04 am
Вот как можно более элементарное решение задачи.

Предположим, мы начинаем с числа, в котором x нулей и y единиц. При преобразовании каждый ноль заменяется на восемь цифр, представляющих код нуля в ASCII, а каждая единица - на восемь цифр, представляющих её код в ASCII. Код нуля - 00110000 (48), код единицы - 00110001 (49).

Таким образом, каждый 0 в исходном числе даёт две единиц и шесть нулей в новом, а каждая 1 в исходном числе - три единицы и пять нулей в новом. Если мы начали с x нулей и y единиц, то после преобразования мы получим 6x+5y нулей и 2x+3y единиц.

Если предположить, что в пределе отношение кол-ва нулей к кол-ву единиц стабилизируется, то отношения x/y с одной стороны и (6x+5y)/(2x+3y) с другой должны стремиться к одному и тому же числу. В пределе они будут равны; поэтому если мы приравняем эти две дроби и решим уравнение, найдя возможные значения x/y, это и будут возможные значения предела.

Таким образом, у нас есть уравнение

x/y = (6x+5y)/(2x+3y). Перемножая числитель одной стороны со знаменателем другой и наоборот, получаем

2x^2+3xy = 6xy+5y^2

2x^2-3xy-5y^2 = 0.

Делим обе части на x*y и получаем

2*(x/y) - 3 - 5(y/x) = 0.

Обозначим теперь z=x/y, тогда y/x = 1/z. z это и есть то, что мы стремимся найти.

2*z - 3 - 5(1/z) = 0.

приводим к общему знаменателю:

2z^2 - 3z - 5 = 0.

Решаем это уравнение и получаем один ответ: z=2.5 (два с половиной; второй ответ выходит комплексным и нам не подходит, т.к. отношение x/y должно быть вещественным числом). Значит, в пределе x/y = 2.5, или в переводе на проценты единиц будет примерно 28.5%, а нулей - 71.5%.

Для того, чтобы показать, что этот предел действительно существует, т.е. что отношение нулей и единиц стабилизируется в пределе, достаточно посмотреть на это уравнение как на неравенство и показать, что если начальное отношение x/y меньше 2.5, то в результате итерации оно увеличится, а если больше - уменьшится.
(Ответить) (Thread)
[User Picture]From: rydel23
2002-09-05 09:49 am

Very nice!
(Ответить) (Parent) (Thread)
[User Picture]From: edgar_poe
2002-09-05 01:31 pm

Спасибо большое!
(Ответить) (Parent) (Thread)
[User Picture]From: muchacho
2002-09-06 12:59 am

Две буквоедские поправки

Второй корень не комплексный, а отрицательный: z=-1 и поэтому не подходит. (Корни квадратного уравнения с вещественными коэффициентами всегда либо оба комплексные, либо оба вещественные)

Надо показать не то, что x/y увеличивается, если меньше 2.5, и наоборот, т.к. это может быть и расходящаяся последовательность (к примеру, если расстояние между x/y и 2.5 увеличивается), а то, что x/y сходится к 2.5 быстрее, чем члены какой-либо сходящейся геометрической прогрессии.
(Ответить) (Parent) (Thread) (Развернуть)