?

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: gera2
2002-09-05 04:12 am
Update: На всякий случай поясню, что под ASCII я в данном случае понимаю 8-битный код, т.е. каждая двоичная цифра заменяется на восемь.

Так вы с этого бы и начинали :).

Каждая двоичная цифра заменяется на восемь
Что в вашем понимании двоичная цифра ?

(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-09-05 04:14 am
Что в вашем понимании двоичная цифра?

Это гениальный вопрос. В анналы ;)

Ну, 0 или 1 естественно.
(Ответить) (Parent) (Thread)
[User Picture]From: gera2
2002-09-05 04:21 am

Re:

:))) Да я не про это.
Это-то ясно.
Как-то ход ваших мыслей мне не ясен.
Возьму я например цифру 3.
В бинарном виде 3 выражается как 11
Теперь 11 в виде ASCII это 31 31 ...
Теперь 31 31 можно представить как бинарное выражение от 3131, но я так понимаю вы не это хотите.
Можно бинарное от 31 и 31 в отдельности, записав каждое из них в виде восьми бит. А можно 3 отдельно и 1 отдельно. Выделив каждому по восемь бит.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-09-05 04:39 am
11 в виде ASCII это не 31 31. Это строка "11".
А при переводе её обратно в двоичный вид получается
0011000100110001.
(Ответить) (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: muchacho
2002-09-05 04:23 am
Ага. Я с самого начала бинарный код ASCII символов '0' и '1' перепутал. И даже не обратил внимания, что 0 > 1 получается... Так-с...
Отвлекли, позже пересчитаю.
(Ответить) (Parent) (Thread)
[User Picture]From: muchacho
2002-09-05 04:31 am
Тогда 2/5.
Если T - соотношение единиц и нулей, довольно просто получить T(k+1) как функцию от T(k). Далее ищем точки, куда может сойтись. И показываем, что сходится. Самое сложное было: решить квадратное уравнение - забыл, как это делается.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-09-05 04:39 am

Да, вот это правильно.
А как показывать будем?
(Ответить) (Parent) (Thread)
[User Picture]From: muchacho
2002-09-05 05:07 am
Ну, показав, что |T(k+1) - T(inf)|/|T(k) - T(inf)| <= g < 1
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-09-05 04:53 am

Кстати, а самым удивительным, возможно, оказалось, что у этого уравнения есть рациональные решения. Я этого совсем не ожидал.
(Ответить) (Parent) (Thread)
[User Picture]From: muchacho
2002-09-05 05:23 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: avva
2002-09-05 04:40 am

Неправильные у тебя, кажется, айгенвальзы. Где-то ты перемудрил.
(Ответить) (Parent) (Thread)
[User Picture]From: edgar_poe
2002-09-05 05:46 am
А что такое айгенвальз?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-09-05 05:49 am
Это я намеренно исковеркал eigenvalues. На самом деле это "собственные значения".
(Ответить) (Parent) (Thread)
[User Picture]From: edgar_poe
2002-09-05 05:58 am

Re:

Я так и подумал. Вот они где вылезли... Никогда не понимал их смысла. ;-(
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-09-05 06:07 am
Ну, здесь можно и без них обойтись, одним квадратным уравнением.
(Ответить) (Parent) (Thread)
[User Picture]From: edgar_poe
2002-09-05 06:09 am

Re:

Если не трудно, напишите, пожалуйста, каким. И как оно получено.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-09-05 06:18 am
Ближе к вечеру напишу, комментом к этой же записи. Сейчас убегаю.
(Ответить) (Parent) (Thread)
[User Picture]From: ait
2002-09-05 04:44 am
Тогда уж (x,1-x) => (3/8*x + 2/8*(1-x),...) == ( (3/8-2/8)*x + 2/8, ... ) == ( 1/8 * x + 2/8, ... )

Итого Xlim = 2/8 = 1/4
(Ответить) (Parent) (Thread)
From: ex_ilyavinar899
2002-09-05 05:43 am
(2,5) - это один eigenvector (т.е. в пределе единички и ноли будут соотноситься в пропорции 2:5). нужно найти еще один.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-09-05 05:44 am
Другого нет (точнее, он комплексный).
(Ответить) (Parent) (Thread)
From: ex_ilyavinar899
2002-09-05 05:51 am
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: edgar_poe
2002-09-05 04:52 am
Точнее так: если отношение нулей к единицам в исходном числе было у:x, то предел будет 2.5*y/x
(Ответить) (Parent) (Thread)
[User Picture]From: edgar_poe
2002-09-05 04:53 am
Получил в эксперименте.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-09-05 04:55 am
Извините, но это не точнее, а неверно ;)
Отношение стабилизируется к 1:2.5 (примерно 28.5% единиц и 71.5% нулей) независимо от начального числа.
(Ответить) (Parent) (Thread)
[User Picture]From: edgar_poe
2002-09-05 04:59 am
ОК!
А как вы получили результат? Тоже экспериментально?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2002-09-05 05:04 am
Нет, так же, как muchacho выше описывает.
(Ответить) (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)
[User Picture]From: avva
2002-09-07 02:07 pm

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

Второй корень не комплексный, а отрицательный: z=-1 и поэтому не подходит.

Да, глюк у меня, спасибо.

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

Хорошо, поправлюсь так: достаточно показать, что x/y увеличивается, если меньше 2.5, и при этом остаётся меньше 2.5. И то же самое в случае больше. Это всё равно тривиально показать рассмотением того же уравнения в виде неравенства, и легче, чем то, что Вы предлагаете.

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