Everything_is_bad, На этом уровне - пару циклов написать - разницы никакой между питоном и с++ нет. Берется пример из интернета, в нужное место вставляются почти такие же for циклы.
Василий Банников, Ну в этом случае логика точно такая же. Выбираем ту букву, которая оставит меньше всего неизвестности. По каждой позиции смотрим, сколко там каждая буква встречается и выбираем максимум. Среди всех позиций выбираем минимум.
Timur, Возможно в пузырьке оптимизация: если ничего не свапнули ни разу, то можно из внешнего цикла выходить.
Потом, может это проблема бенчмарка. Вы как меряли? Запускали 1000 раз и брали среднее? Игнорировали ли вы самые медленные и самые быстрые запуски? Вы уверены, что у вас там JIT не дает задержки, которой нет у стандартной реализации пузырька?
Грамотно померять скорость работы, собственно, реализации - довольно сложная задача.
alex_agaphe , я смотрю вы вопрос поменяли и код добавили.
Вы делаете не то, что я вам ответил. Вы берете для всех состояний {i, w, w} и смотрите куда может пойти i-ая гирька. Но так нельзя делать, потому что эти состояния независимы. ДП же говорит, можно ли собрать вот такие веса и куда класть последнюю гирю при этом. Но оно не говорит, что все эти состояния должны быть вместе. Каждое из них говорит о каком-то решении, но эти решения могут быть исключающими: одно требует первую гирю во в первую кучу класть, другое - в третью.
Более того, вот если у вас i=0 - вы пытаетесь понять, куда класть первую гирю. Но вы одной гирей никак веса w+w в двух кучах не наберете никогда. Т.е. у вас часть этих состояний еще и невозможны.
Вот в dp[n-1][w/3][w/3] у вас лежит правильное значение - куда класть последнюю гирю. Вот это вы знаете. Отметьте ее в нужную кучу. Если там было 0, то гиря лежит в третьей куче. Если ее выбросить из рассмотрения, то получится, что у вас осталось n-1 гиря, с теми же весами. И вы в dp[n-2][w/3][w/3] знаете, где лежит предпоследняяг гиря. Если же dp[n-1][w/3][w/3] == 1, то последняя гиря должна быть в первой куче, а значит, после ее выкидывания вам надо смотреть на dp[n-2][w/3-a[-1]][w/3] чтобы понять, где лежит предпоследняя гиря.
В итоге вам надо написать цикл по i от N-1 до 0, завести 2 переменные для текущих весов (начать с w/3, w/3, а не w,w). Вы по dp[i][w1][w2] понимаете, куда класть i-ую гирю, и вычитаете ее из веса нужной кучки: w1, если в dp был 1, w2, если там был 2.
Вова, Я бы не замахивался на фреймворк сразу. Начните с малого. Напишите просто программу, которая рисует текст в произвольном месте, рисует прямоугольник. Потом вместе - получается кнопочка. Собирайте библиотеку подобных функций рисования.
Потом начинайте думать о композиции элементов вместе. Тут направшивается ООП подход. Просто скопируйте с других фреймворков, они тут примерно все одинаковые. Не знаю книг про дизайн такого, но просто посмотрите интерфейс в других библиотеках, в том же winapi. Компоненты имеют координаты и образуют иерархию, более нижние рисуются после верхних, поверх них.
Для обработки нажатий алгоритм простой - компонент сначала запускает проверку в детях, потом проверяет сам, было ли событие по его области ответственности, и если да - то вызывает callback. Самый верхний - корневой компонент должен принимать события о клике от системы. Не знаю, как тач в адруинке работает, возможно у вас как в игре будет цикл обработки событий, где вы опрашиваете устройства на предмет нажатий и передаете это в корневой объект GUI.
Очень странная затея. Зачем вам писать свой собственный фереймворк? Особенно декстопный? Какая перед вами задача стоит?
Вам хочется написать GUI приложение без всяких сторонних фреймворков? Допустим, потому что они тяжелые? В этом случае вам не стоит упарываться в создание фреймворка и просто написать свое GUI приложение используя напрямую функции операционной системы - winAPI (GDI или DirectX) или wayland/x, в зависимости от того, под что вы пишите. Да, под каждую платфорому вам придется писать практически весь GUI отдельно.
Даже если вы планируете писать несколько приложений, у вас разработка фреймворка не окупится никак, быстрее и легче будет написать каждое с нуля, возможно копируя какие-то куски кода.
Тогда задача нужна что-то вроде "есть шляпа, где 28 шаров, по 7 каждого из 4 цветов. Вы тянете оттуда 4 шара. Какова вероятность, что они все разноцветные?"
floppa322, Почему на 7^4 будет а не C(10, 4), потому что у вас могут быть исходы {3,3,4,7} и {3,4,7,3}, если у вас 4 события могут произойти независимо в один из 7 дней. Два события могут выпасть на среду, но это могут быть первое и второе, а могут быть первое и четвертое. Это разные исходы. Порядок элементов важен. А, если у вас сочетание с повторениями, то порядок был бы не важен.
Так это же как раз то, что я пытаюсь избежать. Если я правильно понял о чём речь
В алгоритме случайного перемешивания же у вас выплняется swap i-ого значения с j = RandInt()%(i+1). Можно не делать swap, если вам важны только первые k элементов. Сгенерировали j, если j
> Ну просто все возможные исходы это все наборы из 7 элементов по 4 элемента, но с повторениями, то есть не только {3, 1, 7, 2}, а ещё и {7, 2, 3, 3}, например. А благоприятные наборы это то же самое, но без повторов, например {2, 1, 7, 6}
Все равно не понял, как вы счаете вероятность через генерацию случайного объекта. По идее вам надо сгенерировать любые возможные объекты (в задаче из условия у вас не сочетания с повторениями, а просто 7^4 всех слов из алфавита с 7 буквами длины 4). Проверять их на "хорошесть" и увеличивать на 1 счетчик хороших исходов. И всегда увеличивать счетчик попыток. Ответ - счетчик хороших делить на количество попыток. Генерировать при этом хорошие исходы уметь вам совсем не надо.
floppa322, перечитал ваш вопрос, понял. У вас формула неправильная. Всего вариантов 7^4. Каждый независимый эксперимент может выпасть на любой день недели. Хороших же вариантов 4! С(7,4) - выбрали какие дни выпали и в каком порядке. Так что правильная вероятность будет 4!*35/2401 = ~0.34.
Я, правда, так и не понял, как вы считаете вероятность через генерацию сочетания. Но возможно проблема в том, что вам важен еще и порядок элементов в сочетании. Ибо это разные события, когда первый эксперимент выпал на понедельник, а второй - на вторник и когда первый выпал на вторник, а первый - на понедельник. Поэтому после генерации сочетания вам надо полученные 4 элемента случайно перетасовать. Ну, или, действительно, вам лучше подойдет вариант через случайную перестановку массива: сгенерируйте массив от 1 до 7, перемешайте его и берите первые 4 элемента. Тут как раз будет 4! С(7,4) вариантов.
Для чего собственно и нужен массив текущих местоположений гирь.
Что значит текущих положений гирь? Такое текущее положение может быть в переборе, где у вас одно состояние рассматривается в каждый момент времени и чуть чуть туда-сюда меняется. Если у вас ДП, то у вас куча состояний и для каждого из них есть "местоположение гирь".
Если стостояние {сколько гирек обработали, сколько весит первая кучка, сколько весит вторая кучка} (как у автора вопроса), то достаточно хранить одно только число - в какой кучке лежит последняя из обработанных гирек. Чтобы восстановить все гири, надо эту последнюю выкинуть из рассмотрения, вычев ее из нужной кучки и повторить операцию уже в новом состоянии. Именно это описанно у меня в ответе ниже.
Но там все-равно есть трехмерный массив для всех стостояний.
Или вы предлагаете сделать его четырехмерным и хранить еще для каждой гирьки, где она лежит - куб из "текущих местоположений гирек"?
Именно это. Еще можно сделать ваш array глобальным, тогда все тоже компилируется.