В предыдущем сообщении написано, конечно, не само арифметическое кодирование, а пример, как можно не терять энтропию в обоих ветках (в неудачной, когда нельзя дать ответ, и в удачной, когда ответ дать можно). Арифметическое же кодирование пишется сложно и, вообще говоря, требует арифметики всё более растущей точности. На практике так конечно никто не делает, а всякие компрессоры просто принимают решение периодически (в заранее оговорённых местах) округлять числа. Для сжатия это не критично — снижается лишь его качество, но не теряется возможность распаковки. Для конвертации вероятностей такой подход плох тем, что даёт неравномерное распределение (хотя понятно, что на практике даже без всякой хитрой длинной арифметики эту неравномерность можно легко сделать порядка 2-60 , то есть практически незаметной). Либо можно в случае обнаружения такой ситуации опять же перебрасывать и начинать всё с начала — равномерность будет, а ухудшится утилизация энтропии (будем делать больше вызовов rand чем необходимо).
Короче говоря, если нужно получить много чисел, то оказывается такой кодер написать очень легко, модифицировав в предыдущем исходнике буквально пару строчек:
using ui = uint64_t;
// s = 5, d = 7template <ui s, ui d>
ui gen() {
static ui g = 1, v = 0;
constexpr ui max = std::numeric_limits<ui>::max() / s;
do {
while (g <= max) {
g *= s;
v = v * s + random<s>();
};
ui f = g / d * d;
if (v < f) {
ui r = v % d;
g /= d;
v /= d;
return r;
}
g -= f;
v -= f;
} while (1);
}
В качестве расплаты же будет выступать появление лага или задержки: настоящее арифметическое кодирование (как и все остальные идеи в этой ветке) будет стремится дать ответ как можно раньше, то есть как только можно отличить один ответ от другого. Этот же исходник сначала всегда делает несколько "холостых" вызовов random и лишь потом начинает выдавать ответ. Такое накопление энтропии и позволяет сделать ситуацию, когда нужно запускать цикл сначала, очень маловероятной.
При этом эта энтропия не теряется, при желании её можно достать обратно, ценой усложнения кода. То есть если нужно сконвертировать миллион случайных чисел по схеме 5 → 7, то сначала произойдёт 24 вызова random, потом для следующего почти миллиона чисел будет тратится в среднем log57 вызовов random на число, а для последних нескольких чисел вызовов random вообще не будет, так как можно обойтись уже накопленной энтропией в счётчиках, то есть можно не делать как раз посление 24 вызова random, которые уже были сделаны в начале.
Точные значения считать лень (они просто считаются только для первых двух алгоритмов), поэтому просто запустил несколько экспериментов по генерации 108 случайных чисел:
В общем видно, что при преобразовании 5 → 7, если следовать стратегии "бросить 2 раза, если получилось больше 21, то перебросить", получается 97% лишних вызовов по сравнению с оптимальной стратегией, где вызовов требутеся log57. Если добавить оптимизацию Кодта, то число лишних вызовов снизится до 83%. Если запоминать ещё и значение переменных между вызовами, то уже получается 28% потерь. Если же предварительно накопить энтропию, то лишних вызовов не будет вовсе — цикл do while ни разу не выполнился дважды, а потери на округлении перед return также ни разу не проявили себя — так бывает не всегда, с сумме там получается не ноль. Но, если я верно прикинул, то вероятность, что нам потребуется больше вызовов random чем арифметическому кодированию, для 108 вызовов составит примерно 7*10-11.
Здравствуйте, Sinix, Вы писали:
К>>Легко! Чем будем жертвовать — гарантией остановки или автокорреляцией? S>? По-моему тут вообще все задачи на "умеет ли человек не паниковать на собеседованиях", особенно последняя. 1..5 -> 0..4 -> base 5 -> base 25 -> отбрасываем все > 7. Для эстетов — все > 21 и отдаём остаток от деления на 7.
То есть, пожертвовали остановкой. Мы ведь можем до морковкиного заговенья ждать, пока перестанет выпадать >21 из 25. Хотя вероятность этого невезения мала.
А настоящие эстеты не выкидывают >21, а используют.
m = 1 # верхняя граница случайного числа
r = 0 # само числоwhile True:
m = m*5
r = r*5 + rand5()
s = m - m%7 # верхняя граница, при которой можно дать ответ сейчас (кратна 7)if r < s:
return r%7
m -= s
r -= s
Получаем последовательность
0 из 5 — перенесли 5 — на этом шаге гарантированно ничего не смогли выдать
21 из 25 — перенесли 4
14 из 20 — перенесли 6
28 из 30 — перенесли 2
7 из 10 — перенесли 3
14 из 15 — перенесли 1
0 из 5 — перенесли 5, ну и так далее
По сути, это арифметическое кодирование...
А жертва автокорреляцией — это запустить генератор псевдослучайных чисел (пусть даже самый тупой) и смешать его с источником 5-ричных случайных чисел.
int dummy_pseudorand7() { static int seed = 0; return (seed += 1 %= 7); }
int smart_pseudorand7() { return rand() * 7 / RAND_MAX; }
int true_rand5();
int truly_rand7() { return (some_pseudorand7() + true_rand5()) % 7; }
dummy_pseudorand7 — даёт равномерные случайные числа, но с люто бешеной автокорреляцией.
Но если true_rand5 обеспечивает белый шум, то это будет не так заметно.
xkcd-генератор "return 4" не подойдёт, потому что он заведомо неравномерный.
А вот обычный сишный rand может сгодиться. (Конечно, он будет чуточку неравномерным, поэтому рожаем свой ГПСЧ по модулю 7).
Здравствуйте, Lepsik, Вы писали:
L>3адача 1 L>Дан массив из целых чиcел. Найти такие m <= k, чтобы сумма a[m] + a[m + 1] + ... + a[k] была максимальна. Время работы должно быть порядка длины массива.
Количество проходов по массиву является спойлером задачи?
L>Задача 2 L>Дан текст, состоящий из N слов, длина которых не превосходит некоторой небольшой константы. Предложите хотя бы два способа вывести частоты вхождения слов в текст за субквадратичноe время, объясните их преимущества и недостатки.
Не, ну это предмет для собеседования. Предложите, объясните...
L>Задача 3 L>Даны числительные языка хауса:
Старое доброе датское "семь плюс полпятого двадцатижды" syvoghalvfems
Нужно покумекать, спасибо.
L>Задача 4 L>Есть генератор случайных чисел, который с равной вероятностью генерирует дискретные значения 1, 2, 3, 4 и 5. Как, имея этот генератор, получить генератор, который бы равновероятно выдавал дискретные значения 1, 2, 3, 4, 5, 6 и 7?
Легко! Чем будем жертвовать — гарантией остановки или автокорреляцией?
Здравствуйте, Кодт, Вы писали:
К>Подсказка 2:
Почему не 1?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Iso12, Вы писали:
I>saba’in da biyar: 76
75
I>đari shidda da sittin da shidda: 666
I>67: sitin da bakwai
sittin...
I>5605: hamsa da dari shidda da bigar
...biyar
Здравствуйте, Кодт, Вы писали:
К>А настоящие эстеты не выкидывают >21, а используют.
К>m = 1 # верхняя граница случайного числа
К>r = 0 # само число
К>По сути, это арифметическое кодирование...
Не знаю как там у "эстетов" принято делать, но в арифметическом кодировании ещё и энтропию между вызовами не теряют. Слишком это расточительно инициализировать старт каждый раз парой {1, 0}. Скажем, очевидно, что если нужно смоделировать честную монету, то имея генератор rand8, запускать последний можно лишь один раз на три ответа:
// s = 5, d = 7template <ui s, ui d>
ui gen() {
static ui g = 1, v = 0;
do {
while (g < d) {
g *= s;
v = v * s + random(s);
};
ui f = g / d * d;
if (v < f) {
ui r = v % d;
g /= d;
v /= d;
return r;
}
g -= f;
v -= f;
} while (1);
}
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, Lepsik, Вы писали:
L>>Это тест на сайте, для выдачи подарков. Может потом приглашают на интервью, я не в курсе
E>А ссылку не дашь? E>Я тока такое нашёл: http://www.abbyy.ru/science/students/cup/
Здравствуйте, -n1l-, Вы писали: N>Так получается мне можно брать всесь массив, что ли?
если все числа неотрицательные, то можно. в общем случае это подозрительно начинает напоминать scheduling, который NP-полный. конкретно здесь лень проверять, но, ИХМО, это любимое занятие рекрутеров — подсунуть замаскированную NP-полную задачу и с невинными глазами просить найти оптимальное решение за полиноминальное время.
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, bazis1, Вы писали:
B>>если все числа неотрицательные, то можно. в общем случае это подозрительно начинает напоминать scheduling, который NP-полный. конкретно здесь лень проверять, но, ИХМО, это любимое занятие рекрутеров — подсунуть замаскированную NP-полную задачу и с невинными глазами просить найти оптимальное решение за полиноминальное время.
E>Задача очевидно линейная...
линейная, если над ней думать на первый взгляд видишь плавающий score с локальным максимумом, который не всегда равен глобальному и думаешь "опять scheduling?".
Здравствуйте, watchmaker, Вы писали:
К>>А ты мелочный W>Можно лучше.
Так и представляется картина: учёные мужи начинают расковыривать энтропию, вычислять теоретические оценки, рядом вьётся безутешный рекрутер, а ему (тем более, ей) машут рукой и говорят "уйди не мешай мальчик (девочка)".
Дан массив из целых чиcел. Найти такие m <= k, чтобы сумма a[m] + a[m + 1] + ... + a[k] была максимальна. Время работы должно быть порядка длины массива.
Задача 2
Дан еекст, состоящий из N слов, длина которых не превосходит некоторой небольшой константы. Предложите хотя бы два способа вывести частоты вхождения слов в текст за субквадратичноe время, объясните их преимущества и недостатки.
Задача 3
Даны числительные языка хауса:
đari bakwai da hamsin da shidda 756
sitta da đari bakwai da biyar 6705
saba’a da đari biyar da sittin 7560
A. Переведите с хауса: saba’in da biyar, đari shidda da sittin da shidda
B. Запишите на хауса: 67 и 5605
Задача 4
Есть генератор случайных чисел, который с равной вероятностью генерирует дискретные значения 1, 2, 3, 4 и 5. Как, имея этот генератор, получить генератор, который бы равновероятно выдавал дискретные значения 1, 2, 3, 4, 5, 6 и 7?
К>Легко! Чем будем жертвовать — гарантией остановки или автокорреляцией?
? По-моему тут вообще все задачи на "умеет ли человек не паниковать на собеседованиях", особенно последняя. 1..5 -> 0..4 -> base 5 -> base 25 -> отбрасываем все > 7. Для эстетов — все > 21 и отдаём остаток от деления на 7.
Здравствуйте, Lepsik, Вы писали:
L>3адача 1
L>Дан массив из целых чиcел. Найти такие m <= k, чтобы сумма a[m] + a[m + 1] + ... + a[k] была максимальна. Время работы должно быть порядка длины массива.
Здравствуйте, Кодт, Вы писали: К>То есть, пожертвовали остановкой. Мы ведь можем до морковкиного заговенья ждать, пока перестанет выпадать >21 из 25. Хотя вероятность этого невезения мала. К>А настоящие эстеты не выкидывают >21, а используют.
А, так вопросы не прикладные, а на сферическую модель коня в вакууме (в хорошем смысле)? Тогда пас, мозги безнадёжно испорчены практикой
Здравствуйте, -n1l-, Вы писали:
L>>3адача 1
L>>Дан массив из целых чиcел. Найти такие m <= k, чтобы сумма a[m] + a[m + 1] + ... + a[k] была максимальна. Время работы должно быть порядка длины массива.
N>А на вход что дается?
Здравствуйте, Lepsik, Вы писали:
L>Задача 3
L>Даны числительные языка хауса:
L>đari bakwai da hamsin da shidda 756 L>sitta da đari bakwai da biyar 6705 L>saba’a da đari biyar da sittin 7560
L>A. Переведите с хауса: saba’in da biyar, đari shidda da sittin da shidda L>B. Запишите на хауса: 67 и 5605
Что-то у меня с бакваем проблемы. đari bakwai это 700, но 7000 это почему-то saba’a. Остальное вроде сходится.
Здравствуйте, Кодт, Вы писали:
К>Легко! Чем будем жертвовать — гарантией остановки или автокорреляцией?
Чем плох наивный вариант бросить 7 раз по 5, и растащить 5 раз по 7?
Здравствуйте, bazis1, Вы писали:
К>>Легко! Чем будем жертвовать — гарантией остановки или автокорреляцией? B>Чем плох наивный вариант бросить 7 раз по 5, и растащить 5 раз по 7?
Я ничего не понял, подробней можно? Что значит растащить 5 раз по 7? Лучше конкретным кодом или на примере. Выпало 1 2 3 4 5 4 3, дальше что будете делать?
Здравствуйте, bazis1, Вы писали:
B>если все числа неотрицательные, то можно. в общем случае это подозрительно начинает напоминать scheduling, который NP-полный. конкретно здесь лень проверять, но, ИХМО, это любимое занятие рекрутеров — подсунуть замаскированную NP-полную задачу и с невинными глазами просить найти оптимальное решение за полиноминальное время.
Количество проходов по массиву является спойлером.
Подсказка: какое именно количество я имел в виду?
Подсказка 2: нет, не NP-полная задача.
Здравствуйте, bazis1, Вы писали:
B>если все числа неотрицательные, то можно. в общем случае это подозрительно начинает напоминать scheduling, который NP-полный. конкретно здесь лень проверять, но, ИХМО, это любимое занятие рекрутеров — подсунуть замаскированную NP-полную задачу и с невинными глазами просить найти оптимальное решение за полиноминальное время.
Задача очевидно линейная...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Задачи в основном на знание алгоритмов
L>3адача 1
L>Дан массив из целых чиcел. Найти такие m <= k, чтобы сумма a[m] + a[m + 1] + ... + a[k] была максимальна. Время работы должно быть порядка длины массива.
L>Задача 3 L>A. Переведите с хауса: saba’in da biyar, đari shidda da sittin da shidda
saba’in da biyar: 76
đari shidda da sittin da shidda: 666
L>B. Запишите на хауса: 67 и 5605
67: sitin da bakwai
5605: hamsa da dari shidda da bigar
Здравствуйте, Кодт, Вы писали:
К>Количество проходов по массиву является спойлером. К>Подсказка: какое именно количество я имел в виду?
один на подсчет левых полусумм, один на подсчет правых? К>Подсказка 2: нет, не NP-полная задача.
А, ну да. Ладно, хорошая задача.
Здравствуйте, vsb, Вы писали:
vsb>Я ничего не понял, подробней можно? Что значит растащить 5 раз по 7? Лучше конкретным кодом или на примере. Выпало 1 2 3 4 5 4 3, дальше что будете делать?
а, нет, меня проглючило. наивный вариант плох тем, что не будет работать .
Здравствуйте, Iso12, Вы писали:
L>>Дан массив из целых чиcел. Найти такие m <= k, чтобы сумма a[m] + a[m + 1] + ... + a[k] была максимальна. Время работы должно быть порядка длины массива. I>Здесь нужно знание sweep algorithms, конкретно Kadane's algorithm
ну это выводится за пару часов в фоновом режиме при желании. я вот сначала подумал, что это NP, но потом задача засела в подсознании и постоянно выкидывала идеи, пока я вокруг горного озера с рюкзаком лазил. А что если начать с крупнейшего элемента? Нет, фигня. А что если предположить, что известен элемент, гарантированно включенный в результат? Ага, линейно сканируем влево и вправо. А можно ли как-то останавливать сканирование зараннее? Можно, если следующий элемент сумму уменьшит, и последующие за ним ее не вернут. А как это просто определить? Сканированием с другого конца и сбросом при получении отрицательной суммы. Бинго, проблема решена.
Но какой великий смысл спрашивать это на интервью, мне неведомо. ИМХО, единственное, что можно таким способом выявить, это то, что человек перед собеседованием потратил неделю на кэширование в голове основных алгоритмов, которые еще через неделю забудет.
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, Кодт, Вы писали:
К>>Подсказка 2: E>Почему не 1?
Подсказка номер два, потому что подсказка номер один была "задуматься о количестве проходов вообще".
А эта подсказка даёт ограничение сверху: "меньше expN/N проходов"
Впрочем, тут уже выкатили спойлер — статью в вике.
B>Но какой великий смысл спрашивать это на интервью, мне неведомо. ИМХО, единственное, что можно таким способом выявить, это то, что человек перед собеседованием потратил неделю на кэширование в голове основных алгоритмов, которые еще через неделю забудет.
Мне тоже не совсем понятно зачем на интервью это спрашивать, может быть ишут человека для разработки в области ИИ. Чтобы понять может человек думать или нет есть и другие способы.
Здравствуйте, Кодт, Вы писали:
К>Подсказка номер два, потому что подсказка номер один была "задуматься о количестве проходов вообще". К>А эта подсказка даёт ограничение сверху: "меньше expN/N проходов" К>Впрочем, тут уже выкатили спойлер — статью в вике.
Тоже понял так, что проходов требуется 2, а не подсказка номер 2.
Здравствуйте, bazis1, Вы писали:
B>ну это выводится за пару часов в фоновом режиме при желании. я вот сначала подумал, что это NP, но потом задача засела в подсознании и постоянно выкидывала идеи, пока я вокруг горного озера с рюкзаком лазил. А что если начать с крупнейшего элемента? Нет, фигня. А что если предположить, что известен элемент, гарантированно включенный в результат? Ага, линейно сканируем влево и вправо. А можно ли как-то останавливать сканирование зараннее? Можно, если следующий элемент сумму уменьшит, и последующие за ним ее не вернут. А как это просто определить? Сканированием с другого конца и сбросом при получении отрицательной суммы. Бинго, проблема решена.
Ну можно проще, как бы...
Как бы очевидный подход в такого рода задачах -- динамическое программирование.
Ну типа заводим состояния { текущая позиция, откуда надо начать, что бы к текущей позиции иметь максимальную сумму, ну и сама сумма по идее пригодится.}
Ну, как бы в начале имеем {0, 0, 0}
Как сделать шаг? Ну, как бы из {pos, curPosStart, curSumm} переходим или в {pos+1, curPosStart, curSumm + v[pos]} или в {pos + 1, pos +1, 0 } в зависимости от знака curSumm + v[pos]}.
Ну, как бы имеем в каждой точке лучший подотрезок с концом в этой позиции и из них надо выбрать самый хороший...
Прямое применение динамического программирования...
B>Но какой великий смысл спрашивать это на интервью, мне неведомо. ИМХО, единственное, что можно таким способом выявить, это то, что человек перед собеседованием потратил неделю на кэширование в голове основных алгоритмов, которые еще через неделю забудет.
Ну алгоритмистов ищут, видимо...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Iso12, Вы писали:
I>Мне тоже не совсем понятно зачем на интервью это спрашивать, может быть ишут человека для разработки в области ИИ. Чтобы понять может человек думать или нет есть и другие способы.
А это интервью или письменный тест?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, watchmaker, Вы писали:
W>Не знаю как там у "эстетов" принято делать, но в арифметическом кодировании ещё и энтропию между вызовами не теряют.
def randgen(N,K,randK):
''' N - целевая граница, K - исходная, randK - исходная функция ГСЧ [0..K) '''
r, m = 0, 1
while True:
while m < N or r >= m//N*N:
r, m = r*K + randK(), m*K
yield r%N
r, m = r//N, m//N
def randgen(N,N,randKgen):
''' randKgen - исходная последовательность (генератор) ГСЧ '''
r, m = 0, 1
for rk in randKgen:
r, m = r*k + rk, m*k
while r < m//N*N:
yield r%N
r, m = r//N, m//N
Как это похоже на разложение k-ричного числа в n-ричную систему!
Здравствуйте, Кодт, Вы писали:
К>На питоне это выглядит так
К>def randgen(N,K,randK):
К> ''' N - целевая граница, K - исходная, randK - исходная функция ГСЧ [0..K) '''
К> r, m = 0, 1
К> while True:
К> while m < N or r >= m//N*N:
К> r, m = r*K + randK(), m*K
К> yield r%N
К> r, m = r//N, m//N
Меня в этом коде смущает две вещи:
При N=7, K=5 и 105 итераций значение 6 выпадает в 3.7 раза чаще чем значение 0.
Значение r неограниченно растёт и начиная с некоторого момента начинает не хватать производительности при оперировании числами длиной в тысячи цифр.
Здравствуйте, watchmaker, Вы писали:
W>Меня в этом коде смущает две вещи: W>При N=7, K=5 и 105 итераций значение 6 выпадает в 3.7 раза чаще чем значение 0.
Упс!
Забыл вычитать делящуюся нацело часть
import random
def randKgen(K):
assert K > 0
while True:
yield random.randint(0,K-1)
def randNKgen(N, K, gen = None):
assert N > 0
assert K > 0
if gen is None:
gen = randKgen(K)
r, m = 0, 1
for q in gen:
while m >= N:
s = m//N*N
if r < s:
yield r%N
r, m = r//N, m//N
else:
r, m = r-s, m-s # вот это забыл сделать
r, m = r*K + q, m*K
I>>saba’in da biyar: 76 К>75
I>>đari shidda da sittin da shidda: 666 К>
I>>67: sitin da bakwai К>sittin...
I>>5605: hamsa da dari shidda da bigar К>...biyar
Здравствуйте, Iso12, Вы писали:
I>Здравствуйте, bazis1, Вы писали:
B>>Но какой великий смысл спрашивать это на интервью, мне неведомо. ИМХО, единственное, что можно таким способом выявить, это то, что человек перед собеседованием потратил неделю на кэширование в голове основных алгоритмов, которые еще через неделю забудет.
I>Мне тоже не совсем понятно зачем на интервью это спрашивать, может быть ишут человека для разработки в области ИИ. Чтобы понять может человек думать или нет есть и другие способы.
Это тест на сайте, для выдачи подарков. Может потом приглашают на интервью, я не в курсе
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Я подумал, что это на их сайте, а не у хакера...
У хакера, кстати, написано, что это таки с собеседований
Но нет худа без бобра: я, благодаря этой путанице, нашёл у них конкурс задач...
Ну и у них, оказывается, есть дорешивание старых кубков.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Lepsik, Вы писали:
L>Задача 3
L>Даны числительные языка хауса:
L>đari bakwai da hamsin da shidda 756 L>sitta da đari bakwai da biyar 6705 L>saba’a da đari biyar da sittin 7560
L>A. Переведите с хауса: saba’in da biyar, đari shidda da sittin da shidda L>B. Запишите на хауса: 67 и 5605
75, 666?
sittin da hamsin, hamsin da đari shidda da biyar?
Здравствуйте, Erop, Вы писали: E>Ну и у них, оказывается, есть дорешивание старых кубков.
Ммм, забавно.
спойлер
Задача http://codeforces.com/contest/178/problem/A1 — там линейная комбинация, для каждого k получается вектор коэффициентов повторения (за сколько шагов единичку с позиции i можно выбросить в интервал позиций [k,n]), причём даже никакого динамического программирования не нужно, ибо последовательность шагов супервозрастающая.
Задачи A2 и A3 идентичны задаче A1. Побуквенно! В чём прикол?
Здравствуйте, Кодт, Вы писали:
К>Задачи A2 и A3 идентичны задаче A1. Побуквенно! В чём прикол?
Возможно там тестовые выборки разной сложности...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Lepsik, Вы писали:
L>3адача 1
L>Дан массив из целых чиcел. Найти такие m <= k, чтобы сумма a[m] + a[m + 1] + ... + a[k] была максимальна. Время работы должно быть порядка длины массива.
java:
public class Task1 {
public final int m, k;
private Task1(int m, int k) {
this.m = m;
this.k = k;
}
public static Task1 findIntervalWithMaxSum(int array[]) {
if (array.length < 1)
throw new IllegalArgumentException();
final Branch development = Branch.newAtStart(array);
final Branch releaseCandidate = Branch.newAt(development);
while (development.isPossibleToImprove()) {
development.tryToImprove();
if (development.isBetterThan(releaseCandidate)) {
releaseCandidate.setAt(development);
}
}
Task1 release = new Task1(releaseCandidate.m, releaseCandidate.k);
return release;
}
}
class Branch {
final int array[];
int m, k; //stateint sum; //computable
//------ Start Boilerplate ------private Branch(int[] array) {
this.array = array;
}
public static Branch newAtStart(int[] array) {
Branch n = new Branch(array);
n.m = 0;
n.k = 0;
n.sum = array[0];
return n;
}
public static Branch newAt(Branch other) {
Branch n = new Branch(other.array);
n.setAt(other);
return n;
}
public void setAt(Branch other) {
if (array != other.array)
throw new IllegalArgumentException();
m = other.m;
k = other.k;
sum = other.sum;
}
//------ End Boilerplate ------boolean isBetterThan(Branch other) {
return sum > other.sum;
}
public boolean isPossibleToImprove() {
return k + 1 < array.length;
}
public void tryToImprove() {
if (sum > 0) {
expandToNext();
} else {
startFromNext();
}
}
private void startFromNext() {
k++;
m = k;
sum = array[k];
}
private void expandToNext() {
k++;
sum += array[k];
}
}
Здравствуйте, vsb, Вы писали: B>>Чем плох наивный вариант бросить 7 раз по 5, и растащить 5 раз по 7?
vsb>Я ничего не понял, подробней можно? Что значит растащить 5 раз по 7? Лучше конкретным кодом или на примере. Выпало 1 2 3 4 5 4 3, дальше что будете делать?
Сложить , взять остаток от деления на 7 и прибавить 1?
Здравствуйте, deimos, Вы писали:
D>Здравствуйте, vsb, Вы писали: B>>>Чем плох наивный вариант бросить 7 раз по 5, и растащить 5 раз по 7?
vsb>>Я ничего не понял, подробней можно? Что значит растащить 5 раз по 7? Лучше конкретным кодом или на примере. Выпало 1 2 3 4 5 4 3, дальше что будете делать?
D>Сложить , взять остаток от деления на 7 и прибавить 1?
Если сложить 7 случайных чисел от 1 до 5, это уже не будет равномерным распределением. Чаще всего будет встречаться 21, остальные числа будут реже (20 и 22 чуть реже, 19 и 23 ещё реже и тд). После взятия остатка от деления на 7 там будет полная вакханалия.
Перекуём баги на фичи!
