Комментарии 44
В задаче №2 требуется случайно выбрать число из потока, размер которого неизвестен.
Судя по формулировке задачи, наш алгоритм не детерминирован, а может пользоваться генератором случайных чисел.
Формально доказать корректность как-то лень, но на небольших примерах (размер потока 1,2, или 3) вроде получается равномерное распределение.
Судя по формулировке задачи, наш алгоритм не детерминирован, а может пользоваться генератором случайных чисел.
Тогда, можно предложить такое решение
Занумеруем числа из потока от 1.
У нас есть ячейка, в которой будем хранить кандидата на финальный результат.
При получении очередного n-го числа из потока с вероятностью 1/n заменим число в ячейке на число из потока.
То есть, первое число генератора всегда кладём в ячейку (вероятность замены = 1), второе — с вероятностью 1/2, следующее — с 1/3, и т.д…
Когда поток закончен, результат — число из ячейки.
У нас есть ячейка, в которой будем хранить кандидата на финальный результат.
При получении очередного n-го числа из потока с вероятностью 1/n заменим число в ячейке на число из потока.
То есть, первое число генератора всегда кладём в ячейку (вероятность замены = 1), второе — с вероятностью 1/2, следующее — с 1/3, и т.д…
Когда поток закончен, результат — число из ячейки.
Формально доказать корректность как-то лень, но на небольших примерах (размер потока 1,2, или 3) вроде получается равномерное распределение.
Теоретическое обоснование
Пусть метод работает для первых n чисел, то есть для каждого из этих чисел вероятность выпадения 1/n.
Добавим следующее (n+1) число по предложенной схеме. Вероятность его выпадения будет 1/(n+1). Вероятность того, что останется предыдущее число — n/(n+1), что по формуле условной вероятности даёт для каждого из предыдущих чисел вероятность (1/n)*(n/(n+1)) = 1/(n+1).
Таким образом индукция работает. Поскольку для первого числа предложенный метод даёт правильную вероятность (1), то и для каждого следующего он будет работать.
Добавим следующее (n+1) число по предложенной схеме. Вероятность его выпадения будет 1/(n+1). Вероятность того, что останется предыдущее число — n/(n+1), что по формуле условной вероятности даёт для каждого из предыдущих чисел вероятность (1/n)*(n/(n+1)) = 1/(n+1).
Таким образом индукция работает. Поскольку для первого числа предложенный метод даёт правильную вероятность (1), то и для каждого следующего он будет работать.
Не верно. Если перезаписывать число, то вероятность того, что в ячейке осталось первое число будет 1/(n!) короче, нулевое
Ответ
Вероятность выбора каждого элемента = 1 / (n — i)
Не знаю зачем вообще дополнительная память.
Пример:
10 элементов
Вероятность выбрать первый элемент 1\10 — нормальное распределение
Получаешь следующий элемент и его выбираешь уже с вероятностью 1\9, так как элементов осталось 9
…
То есть, в каждом выборе гарантируется нормальное разспределение
Не знаю зачем вообще дополнительная память.
Пример:
10 элементов
Вероятность выбрать первый элемент 1\10 — нормальное распределение
Получаешь следующий элемент и его выбираешь уже с вероятностью 1\9, так как элементов осталось 9
…
То есть, в каждом выборе гарантируется нормальное разспределение
Откуда у вас взялся факториал?
Первый шаг: вероятность для первого числа 1.
Второй шаг: вероятность записи нового числа 1/2, оставить старое (1-1/2) = 1/2
Третий шаг: (1-1/3) = 2/3
Четвёртый шаг: (1-1/4) = 3/4
…
(n-1)-й шаг: (1-1/(n-1)) = (n-2)/(n-1)
n-й шаг: (1-1/n) = (n-1)/n
Комбинируя условные вероятности получаем
1 * 1/2 * 2/3 * 3/4… * (n-2)/(n-1) * (n-1)/n = 1/n
Первый шаг: вероятность для первого числа 1.
Второй шаг: вероятность записи нового числа 1/2, оставить старое (1-1/2) = 1/2
Третий шаг: (1-1/3) = 2/3
Четвёртый шаг: (1-1/4) = 3/4
…
(n-1)-й шаг: (1-1/(n-1)) = (n-2)/(n-1)
n-й шаг: (1-1/n) = (n-1)/n
Комбинируя условные вероятности получаем
1 * 1/2 * 2/3 * 3/4… * (n-2)/(n-1) * (n-1)/n = 1/n
Третья задача.
Я буду пользоваться «жадным» алгоритмом, забирая числа от больших к меньшим (чтобы не беспокоиться о Ai+1 на момент рассмотрения Ai).
Пусть у нас есть последовательность: 1 (x5), 2 (x6), 3 (x2), 4.
Стоит ли мне брать четвёрку? Если я её возьму, получу 4, но потеряю две тройки.
Если я не возьму четвёрку, я должен брать 2 тройки (иначе какой смысл отказываться от четвёрки), но беря 2 тройки, я теряю 6 двоек, и т.д. Полный перебор затягивает меня к экспоненциальную яму.
Значит, нужно применить обычное динамическое программирование.
Обозначим S(N) — наибольшая сумма, которую можно взять из последовательности, рассматривая числа не более чем N. Обозначим K(N) — количество чисел «N» в последовательности.
Тогда, если я решил взять число N, то число N-1 мне не доступно, но это не затрагивает все числа меньше N-1: S1(N)=N*K(N) + S(N-2).
А если я решил отказаться от N, то к моей сумме ничего не прибавляется S2(N) = S(N-1).
Поскольку вариантов всего 2, то S(N) = max(S1(N), S2(N)).
Вычислим рекуррентно S(i) от 1 до макс. числа в последовательности, и запомним булевский признак T(N)=true, если S1 > S2 на шаге N (это обозначает, брать число N в ответ или нет).
Печатаем ответ в обратном порядке: перебираем i от максимального N до 1, если T(i) = true, печатаем число i, если T(i) = false, не печатаем.
Я буду пользоваться «жадным» алгоритмом, забирая числа от больших к меньшим (чтобы не беспокоиться о Ai+1 на момент рассмотрения Ai).
Пусть у нас есть последовательность: 1 (x5), 2 (x6), 3 (x2), 4.
Стоит ли мне брать четвёрку? Если я её возьму, получу 4, но потеряю две тройки.
Если я не возьму четвёрку, я должен брать 2 тройки (иначе какой смысл отказываться от четвёрки), но беря 2 тройки, я теряю 6 двоек, и т.д. Полный перебор затягивает меня к экспоненциальную яму.
Значит, нужно применить обычное динамическое программирование.
Обозначим S(N) — наибольшая сумма, которую можно взять из последовательности, рассматривая числа не более чем N. Обозначим K(N) — количество чисел «N» в последовательности.
Тогда, если я решил взять число N, то число N-1 мне не доступно, но это не затрагивает все числа меньше N-1: S1(N)=N*K(N) + S(N-2).
А если я решил отказаться от N, то к моей сумме ничего не прибавляется S2(N) = S(N-1).
Поскольку вариантов всего 2, то S(N) = max(S1(N), S2(N)).
Вычислим рекуррентно S(i) от 1 до макс. числа в последовательности, и запомним булевский признак T(N)=true, если S1 > S2 на шаге N (это обозначает, брать число N в ответ или нет).
Печатаем ответ в обратном порядке: перебираем i от максимального N до 1, если T(i) = true, печатаем число i, если T(i) = false, не печатаем.
Понятно, что настоящее решение сложнее. Т.к. если в последовательности есть очень большие числа, то не нужно циклами бегать по не заполненным промежуткам между ними, а длинные последовательности нулей в S(N) не нужно хранить, заменив массив S(N) на словарь. Но это уже детали реализации.
Если бы задачу давали на соревнованиях типа TopCoder, чтобы завалить невнимательных, наверняка были бы тесты и с отрицательными числами (в условии же не сказано, что все числа положительны), которые не надо выбирать, чтобы не ухудшать себе результат :)
Вопрос 1
8 -> 5 (3, 5, 0)
5 -> 3 (3, 2, 3)
3 -> 8 (6, 2, 0)
5 -> 3 (6, 0, 2)
8 -> 5 (1, 5, 2)
5 -> 3 (1, 4, 3)
3 -> 8 (4, 4, 0)
5 -> 3 (3, 2, 3)
3 -> 8 (6, 2, 0)
5 -> 3 (6, 0, 2)
8 -> 5 (1, 5, 2)
5 -> 3 (1, 4, 3)
3 -> 8 (4, 4, 0)
Вопрос 2
Здесь неполное условие. Могут ли люди пересекать мост одновременно во встречном направлении? Если да, то можно уложиться в 15 минут:
A+D переходят в одну сторону (8 минут)
A+C переходят навстречу друг-другу (5 минут)
A+B переходят в одну сторону (2 минуты)
A+D переходят в одну сторону (8 минут)
A+C переходят навстречу друг-другу (5 минут)
A+B переходят в одну сторону (2 минуты)
Задача 1
Считаем количество нулей, единиц и двоек, затем выводим нужное количество (сортировка подсчётом).
Задача 3
Начинаем выбирать с максимального значения, таким образом на каждом шаге будет удаляться только max(Ai) и max(Ai)-1, если такое существует.
В задаче 3 неверный перевод и форматирование. Удаляются не «все вхождения элементов на единицу меньше и на единицу больше (Ai-1) и (Ai+1) при их наличии и сам элемент», а по одному вхождению Ai-1 (если такое есть), Ai+1 (если такое есть) и сам элемент Ai.
Удаляются именно значения Ai-1 и Ai+1, а не Ai-1 и Ai+1.
Здесь неполное условие. Могут ли люди пересекать мост одновременно во встречном направлении?
Нет, во встречном направлении не могут, фонарь всего один.
Тогда так
A + B — 2 минуты
A обратно — 1 минута
C + D — 8 минут
B обратно — 2 минуты
A + B — 2 минуты
A обратно — 1 минута
C + D — 8 минут
B обратно — 2 минуты
A + B — 2 минуты
Неплохо.
И как же так получается, что ушли
а потом
?
Откуда там взялся B, когда туда ушли с фонарём C + D?
Здесь никак не вложится, так как обратное время тоже учитывается, и даже, если всех будет переводить А (ведь обратно фонарь-то всё равно нужно нести и ему быстрее всего идти обратно), то получается так:
A+D=8
A=1 (обратно)
A+C=5
A=1 (обратно)
A+B=2
Итого 8+1+5+1+2=17.
C + D — 8 минут
а потом
B обратно — 2 минуты
?
Откуда там взялся B, когда туда ушли с фонарём C + D?
Здесь никак не вложится, так как обратное время тоже учитывается, и даже, если всех будет переводить А (ведь обратно фонарь-то всё равно нужно нести и ему быстрее всего идти обратно), то получается так:
A+D=8
A=1 (обратно)
A+C=5
A=1 (обратно)
A+B=2
Итого 8+1+5+1+2=17.
С фонарем решается без встречного движения.
По задаче 3 — спасибо, замечания приняты.
Первая
8->5 (3, 5, 0)
5->3 (3, 2, 3)
3->8 (6, 2, 0)
5->3 (6, 0, 2)
8->5 (1, 5, 2)
5->3 (1, 4, 3)
3->8 (4, 4, 0)
5->3 (3, 2, 3)
3->8 (6, 2, 0)
5->3 (6, 0, 2)
8->5 (1, 5, 2)
5->3 (1, 4, 3)
3->8 (4, 4, 0)
первая: да, соортировка подсчётом, только считать можно n-1 элементов, то есть 0 и 1 тогда количество 2 знаем потому что знали изначальный размер массива.
вторая: генерируем число 1<=x<= n, если x == 1 то выбираем число из потока, вероятность этого 1/n
вторая: генерируем число 1<=x<= n, если x == 1 то выбираем число из потока, вероятность этого 1/n
вторая: генерируем число 1<=x<= n, если x == 1 то выбираем число из потока, вероятность этого 1/n
А если n заранее не известно?
тогда нельзя. сравни ситуации когда генератор выдаёт n и 2n. Ты получаешь первое число которое надо выбрать с вероятностью 1/n или 1/2n ты не знаешь с какой.
а не, я вру, оказывается можно.
вариант от qw1 работает для любых n.
нагляднее будет вариант от qw1 с деревом вероятностей
значение в ячейке сохраняем с вероятностью (n-1)/n то есть меняем с 1/n
пусть будет поток a,b,c,d
1) кладём a(100%)
2) с вероятностью 50% меняем на b: a (50%), b (50%)
3) с вероятностью 33% меняем значение на с: a (50%*66%), b (50%*66%), с(2 * 50% * 33%) -> a(33%) b
4) с вероятностью 25% меняем значение на d. а будет с веростностью 1/2*2/3*3/4 = 1/4 и т.д
при этом не надо считать дроби.
Изменить с вероятностью n значит что выпадает 1 при равномерном распределении [1..n]
но тогда надо считать n, и у нас, о ужас, будет две переменные заместо одной требуемой для O(1). В одну «ячейку памяти» два значения можно впихнуть написав одно число в 1/2 верхних битах, другое в нижних.
вариант от qw1 работает для любых n.
нагляднее будет вариант от qw1 с деревом вероятностей
значение в ячейке сохраняем с вероятностью (n-1)/n то есть меняем с 1/n
пусть будет поток a,b,c,d
1) кладём a(100%)
2) с вероятностью 50% меняем на b: a (50%), b (50%)
3) с вероятностью 33% меняем значение на с: a (50%*66%), b (50%*66%), с(2 * 50% * 33%) -> a(33%) b
4) с вероятностью 25% меняем значение на d. а будет с веростностью 1/2*2/3*3/4 = 1/4 и т.д
при этом не надо считать дроби.
Изменить с вероятностью n значит что выпадает 1 при равномерном распределении [1..n]
но тогда надо считать n, и у нас, о ужас, будет две переменные заместо одной требуемой для O(1). В одну «ячейку памяти» два значения можно впихнуть написав одно число в 1/2 верхних битах, другое в нижних.
Второй вопрос
AB->(2 min)
<-A(1 min)
CD->(8 min)
<-B(2 min)
AB->(2 min)
1 + 2 + 8 + 2 + 2 = 15
<-A(1 min)
CD->(8 min)
<-B(2 min)
AB->(2 min)
1 + 2 + 8 + 2 + 2 = 15
Ну что же, попробуем (устроится в Google/Microsoft/Etc):
1) Задача Ледяного Бака
Переливаем 5л из 8л бака в 5л бак
Переливаем 3л из 5л бака в 3л бак
Переливаем 3л из 3л бака в 8л бак
Переливаем 2л из 5л бака в 3л бак
Переливаем 5л из 8л бака в 5л бак
Переливаем 1л из 5л бака в 3л бак
Переливаем 3л воды из 3л бака в 8л бак
Собственно задача решена, 4 л в 8л баке и 4л в 5л баке.
А почему вода ледяная, какое отношение к задаче имеет температура жидкости? Риторика.
2) Задача Светильника и Моста
Ответ, да все указанные персоны могут пересечть мост менее чем за 15 минут.
Персоны «A» и «B» пересекают мост совместно за 2 минуты.
Затем, персоны «C» и «D» пересекают мост за 8 минут.
Итого 10 минут на пересечение моста при указанных идеальных условиях.
3) Сортировка массива состоящего из значений 0,1,2.
Возможно, неверно интерпретирована задача или есть более оптимальные методы ее решения, но в общем случае имеет быть следующее решение — выборочная сортировка на языке pascal
4) Выбрать произвольное/случайное значение из потока используя ограниченное место хранения
Пропуск. Не смог определить искомый результат — «вероятность 1/n».
5) Максимизировать сумму выбранных чисел
Дано объяснение с примерами, но не указан искомый результат?! Либо пропущены данные.
Теперь можно и подсмотреть что у других…
1) Задача Ледяного Бака
Переливаем 5л из 8л бака в 5л бак
Переливаем 3л из 5л бака в 3л бак
Переливаем 3л из 3л бака в 8л бак
Переливаем 2л из 5л бака в 3л бак
Переливаем 5л из 8л бака в 5л бак
Переливаем 1л из 5л бака в 3л бак
Переливаем 3л воды из 3л бака в 8л бак
Собственно задача решена, 4 л в 8л баке и 4л в 5л баке.
А почему вода ледяная, какое отношение к задаче имеет температура жидкости? Риторика.
2) Задача Светильника и Моста
Ответ, да все указанные персоны могут пересечть мост менее чем за 15 минут.
Персоны «A» и «B» пересекают мост совместно за 2 минуты.
Затем, персоны «C» и «D» пересекают мост за 8 минут.
Итого 10 минут на пересечение моста при указанных идеальных условиях.
3) Сортировка массива состоящего из значений 0,1,2.
Возможно, неверно интерпретирована задача или есть более оптимальные методы ее решения, но в общем случае имеет быть следующее решение — выборочная сортировка на языке pascal
for i:= 0 to n-1 do
..for j:= i+1 to n-1 do
....if a[i]>a[j] then swap(a[i],a[j]);
4) Выбрать произвольное/случайное значение из потока используя ограниченное место хранения
Пропуск. Не смог определить искомый результат — «вероятность 1/n».
5) Максимизировать сумму выбранных чисел
Дано объяснение с примерами, но не указан искомый результат?! Либо пропущены данные.
Теперь можно и подсмотреть что у других…
Затем, персоны «C» и «D» пересекают мост за 8 минут.
Итого 10 минут на пересечение моста при указанных идеальных условиях.
C и D падают с моста, поскольку светильник остался на другой стороне.
Ice Bucket Challenge — это отсылка к соответствующему флешмобу.
Задача с мостом и фонарём вполне решаема, и ответ в ней — «Да».
Сортировку пузырьком здесь не стоит использовать, лучше сортировку подсчётом, так как набор возможных значений заранее известен и ограничен.
Задача с мостом и фонарём вполне решаема, и ответ в ней — «Да».
Сортировку пузырьком здесь не стоит использовать, лучше сортировку подсчётом, так как набор возможных значений заранее известен и ограничен.
Таких легких задач еще не было.
Вопрос 1. Такие вопросы мы решали в 5 классе.
Вопрос 2. Такой вопрос был мне задан в ЕПАМе. Самые тормознутые должны идти вместе.
Задача 1. Если не применять «избыточную» оптимизацию, то легко решается в 2 прохода, считаем кол-во 0,1,2 и за второй проход расставляем по местам. Но можно решать за 1 проход, но сильно это ничего не ускорит, а вот код окажется намного сложней.
Задача 2. Такая задача была в одной из книг Шилдта. Я её сам не решил. Но ответ знаю.
Задача 3. Если я все правильно понял, то при выборе 3-ки во втором примере мы потеряем всего одну двойку и 1 четверку, а не все двойки. Т.е. удаляются не все элементы равные значению, а только один из них. Если так, что решение — каждый раз выбирать наибольший из оставшихся элементов.
Вопрос 1. Такие вопросы мы решали в 5 классе.
Вопрос 2. Такой вопрос был мне задан в ЕПАМе. Самые тормознутые должны идти вместе.
Задача 1. Если не применять «избыточную» оптимизацию, то легко решается в 2 прохода, считаем кол-во 0,1,2 и за второй проход расставляем по местам. Но можно решать за 1 проход, но сильно это ничего не ускорит, а вот код окажется намного сложней.
Задача 2. Такая задача была в одной из книг Шилдта. Я её сам не решил. Но ответ знаю.
Задача 3. Если я все правильно понял, то при выборе 3-ки во втором примере мы потеряем всего одну двойку и 1 четверку, а не все двойки. Т.е. удаляются не все элементы равные значению, а только один из них. Если так, что решение — каждый раз выбирать наибольший из оставшихся элементов.
Т.е. удаляются не все элементы равные значению, а только один из нихУдаляются все элементы с соседним значением. В условие задачи внесено изменение:
Нужно удалять элементы со значением (Ai)+1 и (Ai)-1, а не на позиции А(i-1) и А(i+1)К сожалению, автор поправил русскую часть (которую никто не читает), но не поправил английскую.
Но это можно было сразу понять, разбирая второй пример, в котором есть 3 двойки, и все три ушли в результат.
Но можно решать за 1 проход, но сильно это ничего не ускорит, а вот код окажется намного сложней.Как это, в один проход? Одним циклом, пока читаем вход, сразу выводим результат?
Прошу прощения, что долго не отвечал. Не было времени.
Там конечно получается не чистый 1 проход, скорее полтора прохода.
Чистый 1 проход получился бы если в задаче были только 0 и 1.
Правда у такого варианта есть косяк: если массив нулевой длинный, или же если там одни 0 или 1, то выход за пределы массивы. Но это можно пофиксить либо добавив по 1 проверке в цикле, либо добавить (и запомнить) единицу и ноль в массив, а после уже вернуть в начальное значение.
А так 1 проход: каждое значение (индекс) читается не больше 1 раза, и записывается не более 1 раза, за исключение чтения элементов «при встрече» индексов.
Задача с 0,1,2 немного сложнее, но думаю вам самим будет интересно решить её по аналогии.
Там конечно получается не чистый 1 проход, скорее полтора прохода.
Чистый 1 проход получился бы если в задаче были только 0 и 1.
public static void sort01(int[] _array){
int leftIndex =0;
int rightIndex = _array.length-1;
while(true){
while(_array[leftIndex]==0){
leftIndex++;
}
while(_array[rightIndex]==1){
rightIndex--;
}
if(leftIndex>=rightIndex){
return;
}
_array[leftIndex]=0;
_array[rightIndex]=1;
leftIndex++;
rightIndex--;
}
}Правда у такого варианта есть косяк: если массив нулевой длинный, или же если там одни 0 или 1, то выход за пределы массивы. Но это можно пофиксить либо добавив по 1 проверке в цикле, либо добавить (и запомнить) единицу и ноль в массив, а после уже вернуть в начальное значение.
А так 1 проход: каждое значение (индекс) читается не больше 1 раза, и записывается не более 1 раза, за исключение чтения элементов «при встрече» индексов.
Задача с 0,1,2 немного сложнее, но думаю вам самим будет интересно решить её по аналогии.
Задача с 0,1,2 немного сложнее, но думаю вам самим будет интересно решить её по аналогии.Не вижу аналогии. Здесь есть 2 фиксированные точки — начало массива и конец, откуда растут непрерывные блоки 0 и 1. От какой точки будет расти третий блок, мы не знаем, пока не проведём подсчёт.
Мы имеем 3 указателя. index1 -движение слева направо, index2 -движение справа налево (самый правый элемент, который !=2), index0- самый левый элемент, который не равен 0.
Пример. 0001102122 (жирным выделены указатели)
Смотрим на что указывает указатель index1, в примере это 0.
Если это ноль, то меняем значение index0 и index1 местами, и сдвигаем оба индекса на 1. Резальтат: 0000112122
Если же index1 указывает на 1, то просто сдвигаем его влево на 1, если указывает на 2, то меняем местами значения в ячейках index1 и index2, и уменьшаем index2 на 1.
Вот рабочий код, немного запутанный, после каждого обновления индекса приходится делать проверку, чтобы не выйти за приделы массива.
Здесь каждый элемент массива читается 1 раз. Правда каждый элемент массива может быть изменён 2 раза. Поэтому это скорее полтора прохода.
Пример. 0001102122 (жирным выделены указатели)
Смотрим на что указывает указатель index1, в примере это 0.
Если это ноль, то меняем значение index0 и index1 местами, и сдвигаем оба индекса на 1. Резальтат: 0000112122
Если же index1 указывает на 1, то просто сдвигаем его влево на 1, если указывает на 2, то меняем местами значения в ячейках index1 и index2, и уменьшаем index2 на 1.
Вот рабочий код, немного запутанный, после каждого обновления индекса приходится делать проверку, чтобы не выйти за приделы массива.
public static void sort012(int[] _array){
int index0 = 0;
int index1 = 0;
int index2 = _array.length-1;
int val1 = _array[index1];
int val2 = _array[index2];
while((val1==0)&&(index1<index2)){
index1++;
val1 = _array[index1];
}
while((val2==2)&&(index1<index2)){
index2--;
val2 = _array[index2];
}
index0 = index1;
if(index1>=index2){
return;
}
//
while(true){
if(val1==0){
if(index1!=index0){
_array[index0] = 0;
_array[index1] = 1;
}
index0++;
index1++;
if(index1>index2){
return;
}
val1 = _array[index1];
continue;
}
if(val1==2){
_array[index2] = val1;// =2
_array[index1] = val2;
val1 = val2;
index2--;
if(index1>index2){
return;
}
val2 = _array[index2];
while(val2==2){
index2--;
if(index1>index2){
return;
}
val2 = _array[index2];
}
continue;
}
while(val1==1){
index1++;
if(index1>index2){
return;
}
val1 = _array[index1];
}
}
}
public static void main(String[] _a){
//int[] ar = {0,1,2,0,1,2,0,0,2,2,1,2,0,1,1,0,2,2};
int[] ar = {2,1,0,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0};
sort012(ar);
for(int i:ar){
System.out.println(i);
}
}Здесь каждый элемент массива читается 1 раз. Правда каждый элемент массива может быть изменён 2 раза. Поэтому это скорее полтора прохода.
А в первой задаче не про принцип «если мы знаем элементы массива, то сортировка нам не нужна»? То есть за один проход мы с помощью трех переменных можем создать сортированный массив, а не сортировать существующий?
Объясните плиз, про генератор случайных. То ли лыжи не едут, то ли я не понимаю в чём сложность.
буфер?
Есть реальный поток данных. Если он бесконечен, то вероятность выбрать любое из чисел должна быть нулевой. Если он конечен, то у него есть длина n. Если она меньше нашего объёма буфера, то возвращаем из генератора число от 1 до n с равной вероятностью. Если больше — то возвращаем случайный момент времени из диапазона когда велась трансляция, и ровно в этот момент хватаем последнее попавшее в буфер число. Если скорость передачи не фиксирована, то просто знаем сколько раз наполнится буфер, и считаем два числа random%N и N%databuffer. Так как каждое из них независимое, то и вероятность равна для всех.
Всё просто, есть генератор случайных чисел. Длина последовательности (n) заранее неизвестна. Необходимо получить одно случайно выбранное с вероятностью (1/n) число из этой последовательности. При этом можно использовать только фиксированное количество памяти, довыделять память в дальнейшем нельзя. Поскольку генератор случайный, то повторить последовательность тоже нельзя.
Спасибо, понял. Но случай вопиющий (система с ограничениями на память — скорее всего контроллер, и на них я бы ожидал задокументированную длину пакетов со всех сторон...).
Более реальный случай под ту же математическую логику — нужно делать наложенное изображение из нескольких слайдов-слоёв. Слайды загружаются поочерёдно, и неисвестно, сколько их будет всего. Как обеспечить равномерное наложение слоёв?
Более реальный случай под ту же математическую логику — нужно делать наложенное изображение из нескольких слайдов-слоёв. Слайды загружаются поочерёдно, и неисвестно, сколько их будет всего. Как обеспечить равномерное наложение слоёв?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Выпуск#14: ITренировка — актуальные вопросы и задачи от ведущих компаний