Сегодня знакомый предложил задачу, процесс решения которой понравился. Прошу сильное не пинать, если баян )) Итак...
На фабрике работает один миллион рабочих, каждому из которых руководство выделило по персональному ящику. Вечером рабочий день заканчивается, и рабочие идут к своим ящикам, которые пронумерованы с 1 до 1`000`000, складывают в них свои вещи и отправляются домой на заслуженный отдых. Ближе к полуночи из старых цехов, домен, чердаков и т.д. появляются ровно один миллион привидений, решивших немного пошалить. Все они также пронумерованы от 1 до 1`000`000 )) Привидения действуют следующим образом:
1. Первое привидение открывает все ящики наших работяг (т.к. к сожалению, денег на замки для ящиков начальство не предоставило)
2. Привидение с порядковым номером на «груди» «2» закрывает все ящики, номера которых делятся на 2, т.е. закрывает ящики 2, 4, 6, 8 и т.д.
3. Третье привидение с порядковым номером, как мы все догадались, «3» изменяет состояние всех ящиков, которые делятся на 3. Т.е. если номер ящика делиться на 3 и был закрыт, то оно открывает его, если этот ящик был открыт – закрывает. Например, на этом шаге будут закрыты ящики: 3, 9 и открыт ящик за номером 6 и т.д.
N. Все последующие привидения с 4 по 1`000`000-е действую по тому же алгоритму, т.е. изменяют состояние ящиков, порядковые номера которых делятся на их порядковый номер.
Привидения действую быстро и бесшумно до самого утра, пока все не внесут свою лепту в процесс открывания/закрывания ящиков. И вот к утру последнее 1`000`000 привидение изменяет состояние единственного ящика, и все привидения исчезают каждое по своему углу.На утро приходят рабочие и обнаруживают, что часть ящиков открыта, а часть закрыта.
1. Сколько ящиков открыто/закрыто?
2. Как доказать, что именное указанное количество будет открыто/закрыто, без просчета каждого шага?
Дальше приходим к выводу, что кол-во '-' есть кол-во делителей. Если это кол-во чётно, значит дверь закрыта, иначе она открыта. В этом случае 3 открытых и 7 закрытых дверей. Т.е. задачка сводится к вычислению суммы такого ряда :
k = f(1) + f(2) + ... + f(1000000);, где f(i) это ф-я возвр-я кол-во делителей числа i.
K>Дальше приходим к выводу, что кол-во '-' есть кол-во делителей. Если это кол-во чётно, значит дверь закрыта, иначе она открыта. В этом случае 3 открытых и 7 закрытых дверей. Т.е. задачка сводится к вычислению суммы такого ряда : K>k = f(1) + f(2) + ... + f(1000000);, где f(i) это ф-я возвр-я кол-во делителей числа i.
Ой опять ошибся =(.
k = f(1)%2 + f(2)%2 + ... + f(1000000)%2; — кол-во открытых дверей.
И соответственно 1000000-k — кол-во закрытых дверей.
Здравствуйте, sh24, Вы писали:
S>Доброе время суток.
S>Сегодня знакомый предложил задачу, процесс решения которой понравился. Прошу сильное не пинать, если баян )) Итак...
S>На фабрике работает один миллион рабочих, каждому из которых руководство выделило по персональному ящику. Вечером рабочий день заканчивается, и рабочие идут к своим ящикам, которые пронумерованы с 1 до 1`000`000, складывают в них свои вещи и отправляются домой на заслуженный отдых. Ближе к полуночи из старых цехов, домен, чердаков и т.д. появляются ровно один миллион привидений, решивших немного пошалить. Все они также пронумерованы от 1 до 1`000`000 )) Привидения действуют следующим образом:
S>1. Первое привидение открывает все ящики наших работяг (т.к. к сожалению, денег на замки для ящиков начальство не предоставило) S>2. Привидение с порядковым номером на «груди» «2» закрывает все ящики, номера которых делятся на 2, т.е. закрывает ящики 2, 4, 6, 8 и т.д. S>3. Третье привидение с порядковым номером, как мы все догадались, «3» изменяет состояние всех ящиков, которые делятся на 3. Т.е. если номер ящика делиться на 3 и был закрыт, то оно открывает его, если этот ящик был открыт – закрывает. Например, на этом шаге будут закрыты ящики: 3, 9 и открыт ящик за номером 6 и т.д. S>N. Все последующие привидения с 4 по 1`000`000-е действую по тому же алгоритму, т.е. изменяют состояние ящиков, порядковые номера которых делятся на их порядковый номер.
S>Привидения действую быстро и бесшумно до самого утра, пока все не внесут свою лепту в процесс открывания/закрывания ящиков. И вот к утру последнее 1`000`000 привидение изменяет состояние единственного ящика, и все привидения исчезают каждое по своему углу.На утро приходят рабочие и обнаруживают, что часть ящиков открыта, а часть закрыта.
S>1. Сколько ящиков открыто/закрыто? S>2. Как доказать, что именное указанное количество будет открыто/закрыто, без просчета каждого шага?
S>Вот. Решение простое и красивое.
Ну сразу понятно, что ящик будет открытым, если количество делителей нечетно и закрыта, если четно.
А нечетное количество делителей только у полных квадратов, т.к. для каждого делителя(K) числа(N) существует другой делитель(M = N / K) этого числа, которые в произведении дают N. Но только у полных квадратов для делителя K = sqrt(N) соответствует число M = K, т.е. количество делителей нечетно.
Число открытых ящиков будет равно количеству полных квадратов в отрезке [1, N], что для нашего примера равно 1000.
N>Число открытых ящиков будет равно количеству полных квадратов в отрезке [1, N], что для нашего примера равно 1000.
Забыл самое главное: количество закрытых ящиков будет равно 1000000 — 1000 = 999000
А если обобщить задачу, то если нам дано N ящиков, то после вот этого процесса открытых ящиков будет A = sqrt(N), округленное в нижнюю сторону, а закрытых B = N — A.
Здравствуйте, Кодт, Вы писали:
S>>Сегодня знакомый предложил задачу, процесс решения которой понравился. Прошу сильное не пинать, если баян )) К>Ты зналь, ты зналь!
Перекуём баги на фичи!
, и поиск как-то не помог ((
))
