Подскажите по алгоритму+ математике

Есть задача: написать калькулятор, который считает вероятности каждого ответа для выражения.

На вход принимает строку во всеми обычными действиями и числами и числа dxx. Где xx максимальное возможное число. То есть например d10 - может быть любым числом от 1 до 10.

Например d2+d2 может иметь следующие значения: 1+1, 1+2, 2+1, 2+2;

2 - вероятность 25%, 3 -50%, 4 - 25%.

Надеюсь понятно написал.

Ну в общем я сделал калькулятор, который тупо все считает, записывает результат и сколько раз встречается. А потом считаю вероятность как "сколько раз встретилось"/общее количество итогов.

Но например для d100+d100*d100-d100 это уже 100000000 переборов. А на входе может быть еще сложнее выражение.

Моя программа перебором не проходит ни по памяти, ни по скорости.

Подскажите с точки зрения алгоритма, можно ли в данном случае как-то решить не перебирая всё?

Upd. вы мне ставите этот смайлик потому что сложно или потому что слишком легко и земля мне пухом что такое не стесняюсь спрашивать?

Все что тебе нужно сделать, это посчитать количество одинаковых ячеек по диагонали и разделить их на общее количество

 

 

Тень228 сказал(а):↑

Есть задача: написать калькулятор, который считает вероятности каждого ответа для выражения.

На вход принимает строку во всеми обычными действиями и числами и числа dxx. Где xx максимальное возможное число. То есть например d10 - может быть любым числом от 1 до 10.

Например d2+d2 может иметь следующие значения: 1+1, 1+2, 2+1, 2+2;

2 - вероятность 25%, 3 -50%, 4 - 25%.

Надеюсь понятно написал.

Ну в общем я сделал калькулятор, который тупо все считает, записывает результат и сколько раз встречается. А потом считаю вероятность как "сколько раз встретилось"/общее количество итогов.

Но например для d100+d100*d100-d100 это уже 100000000 переборов. А на входе может быть еще сложнее выражение.

Моя программа перебором не проходит ни по памяти, ни по скорости.

Подскажите с точки зрения алгоритма, можно ли в данном случае как-то решить не перебирая всё?

Upd. вы мне ставите этот смайлик потому что сложно или потому что слишком легко и земля мне пухом что такое не стесняюсь спрашивать?

Нажмите, чтобы раскрыть...

Какое ограничение на хх и на количество арифметических операций?

Сложение и вычитание без особых проблем ещё можно сделать, но с введением умножения всё начинает так ветвиться, что искать в этом фрактальном хаосе пересечения...

 

Но если с умножением как-то можно разобраться - деление ставит на всей задумке жирный крест. Кто напишет решение, квотните. Мне тоже интересно.

 

MoonMeUnder сказал(а):↑

Все что тебе нужно сделать, это посчитать количество одинаковых ячеек по диагонали и разделить их на общее количество

 

 

Нажмите, чтобы раскрыть...

А если выражение ((135*d25)*17-d10)-(22+d100)... что считать?

Да и смысл? Так я храню только сколько раз встречается, а так все выражение и сравнивать ещё?

PraiseMySun сказал(а):↑

Сложение и вычитание без особых проблем ещё можно сделать, но с введением умножения всё начинает так ветвиться, что искать в этом фрактальном хаосе пересечения...

 

Но если с умножением как-то можно разобраться - деление ставит на всей задумке жирный крест. Кто напишет решение, квотните. Мне тоже интересно.

Нажмите, чтобы раскрыть...

Бтв нет деления по условиям задачи, но есть больше ">" (0 или 1)

HaisTous сказал(а):↑

Какое ограничение на хх и на количество арифметических операций?

Нажмите, чтобы раскрыть...

Хх до 100, входная строка до 120 символов

Тень228 сказал(а):↑

А если выражение ((135*d25)*17-d10)-(22+d100)... что считать?

Да и смысл? Так я храню только сколько раз встречается, а так все выражение и сравнивать ещё?

Нажмите, чтобы раскрыть...

 

Тогда нужно полное описание условия задачи. А то с твоего первого поста я думал что у тебя все числа идут с приставкой d.

MoonMeUnder сказал(а):↑

 

Тогда нужно полное описание условия задачи. А то с твоего первого поста я думал что у тебя все числа идут с приставкой d.

Нажмите, чтобы раскрыть...

Думаю тут проблема не в том, что я плохо описал условия задачи. В сабже написано "все обычные числа и числа dxx". Как это можно неправильно понять?

Да даже если бы были только dxx, че бы ты там перебирал по диагонали? Это только для сложения имеет смысл, с умножением уже будут скачкИ, а когда все вместе и со скобочками? А там ещё больше/меньше действия есть.

Тень228 сказал(а):↑

Бтв нет деления по условиям задачи, но есть больше ">" (0 или 1)

Нажмите, чтобы раскрыть...

Чел, ты... Написал же "со всеми обычными действиями". И что здесь забыло ">"?

 

Реально, скинь уже нормальное условие. Не понимаю, что ты без него вообще ожидаешь получить

PraiseMySun сказал(а):↑

Чел, ты... Написал же "со всеми обычными действиями". И что здесь забыло ">"?

 

Реально, скинь уже нормальное условие. Не понимаю, что ты без него вообще ожидаешь получить

Нажмите, чтобы раскрыть...

Я описал все более чем доступно.

Будто бы мне кто-то хоть что-то хоть и не учитывая ">" предложил.

Что рассчитываю получить хз, по сути тут если и спрашивать, то максимум как лучше склепать двухстраничный лендинг автомастерской.

Хотя несколько норм челов на форум таки есть.

Цитата:

что как бы само по себе имеет неполноту, а значит не имеет вывода без подстановки

Нажмите, чтобы раскрыть...

Тут имеется ввиду что ты можешь сделать систему уравнений, по всем членам уравнения, и решить предел на множестве значений. но ты ж понимаешь это нужно свой wolfram alpha написать...и то, решене будет приближенным.

Тень228 сказал(а):↑

Я описал все более чем доступно.

Будто бы мне кто-то хоть что-то хоть и не учитывая ">" предложил.

Что рассчитываю получить хз, по сути тут если и спрашивать, то максимум как лучше склепать двухстраничный лендинг автомастерской.

Хотя несколько норм челов на форум таки есть.

Нажмите, чтобы раскрыть...

Тебе в первом же посте ответили как разабраться с построением множеств вероятностей для любой суммы и разности, пусть и без подробностей. 

PraiseMySun сказал(а):↑

Тебе в первом же посте ответили как разабраться с построением множеств вероятностей для любой суммы и разности, пусть и без подробностей. 

Нажмите, чтобы раскрыть...

ТС ж вроде говорил о свободной форме?

 

PraiseMySun сказал(а):↑

Тебе в первом же посте ответили как разабраться с построением множеств вероятностей для любой суммы и разности, пусть и без подробностей. 

Нажмите, чтобы раскрыть...

Спс, мог бы еще ответить как разобраться с вероятностью одного числа.

saw_tooth сказал(а):↑

ТС ж вроде говорил о свободной форме?

 

Нажмите, чтобы раскрыть...

Честно говоря, плохо понимаю, о чём ТС говорил, что как перебирал и в какой форме хотел вывести, пото му что при текущих условиях задача выглядит расплывчато.

 

Я просто пытаюсь выделить в тетради характер распространения вероятностей в зависимости от арифмеьического знака и пути возможной оптимизации подсчёта, не более. 

PraiseMySun сказал(а):↑

Я просто пытаюсь выделить в тетради характер распространения вероятностей в зависимости от арифмеьического знака и пути возможной оптимизации подсчёта, не более. 

Нажмите, чтобы раскрыть...

Ты все верно сказал, просто пока задача не выходит из рамок x+y ты получаешь изображение на плоскости, и оно красивое (твоя диагональ)

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

При добавлении умножения ты получишь кривые и т.д

saw_tooth сказал(а):↑

Ты все верно сказал, просто пока задача не выходит из рамок x+y ты получаешь изображение на плоскости, и оно красивое (твоя диагональ)

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

При добавлении умножения ты получишь кривые и т.д

Нажмите, чтобы раскрыть...

Сложно всё это представлять, и тем более описывать не вживую без чёткого представления. Но, насколько я представляю, количество членов не имеет особой разницы до тех пор, пока не появится умножение, потому что распределение множителя вероятностей происходит равномерным фронтом до границы диапазона вариантов сумм и разностей (не совсем так), дальше которого начинается его расширение.

 

Если плохо объясняю и ничего непонятно, могу попробовать зарисовать, как всё это происходит. Но умножение, действительно, всё портит. 

PraiseMySun сказал(а):↑

Честно говоря, плохо понимаю, о чём ТС говорил, что как перебирал и в какой форме хотел вывести, пото му что при текущих условиях задача выглядит расплывчато.

 

Я просто пытаюсь выделить в тетради характер распространения вероятностей в зависимости от арифмеьического знака и пути возможной оптимизации подсчёта, не более. 

Нажмите, чтобы раскрыть...

Что непонятно из того, что я написал? Я 10 раз перечитал. Я даже не знаю, что добавить, там максимально очевидно все написано.

Знаешь инженерные калькуляторы есть, которые принимают любые выражения с любым количеством действий, скобок и т.д.?

Вот, нужно то же самое, только ещё с учетом цифр dxxx и выводом вероятностей.

Пример выражения нужен?

Да какое угодно.

((231×d50)-d5*(13+d10)*(d10-10)+5)*30 и т.д.

Что d еще все разные не забывай.

Тень228 сказал(а):↑

Что d еще все разные не забывай.

Нажмите, чтобы раскрыть...

Что значит разыне?

По значению?

Тень228 сказал(а):↑

Что непонятно из того, что я написал? Я 10 раз перечитал. Я даже не знаю, что добавить, там максимально очевидно все написано.

Знаешь инженерные калькуляторы есть, которые принимают любые выражения с любым количеством действий, скобок и т.д.?

Вот, нужно то же самое, только ещё с учетом цифр dxxx и выводом вероятностей.

Пример выражения нужен?

Да какое угодно.

((231×d50)-d5*(13+d10)*(d10-10)+5)*30 и т.д.

Нажмите, чтобы раскрыть...

Я не понимаю, во-первых, что там может делать знак сравнения. Во-вторых, почему ты говоришь про конкретное число, если ты его нигде не получаешь - следовательно тебе интересен весь спектр возможных значений. И, в-третьих, я неуверен в условиях в целом, потому что сама задача слишком проблемная. Где ты её откопал вообще? 

saw_tooth сказал(а):↑

Что значит разыне?

По значению?

Нажмите, чтобы раскрыть...

Разный верхний порог

 

PraiseMySun сказал(а):↑

Я не понимаю, во-первых, что там может делать знак сравнения. Во-вторых, почему ты говоришь про конкретное число, если ты его нигде не получаешь - следовательно тебе интересен весь спектр возможных значений. И, в-третьих, я неуверен в условиях в целом, потому что сама задача слишком проблемная. Где ты её откопал вообще? 

Нажмите, чтобы раскрыть...

Проблемная это потому что посложнее сортировки пузырьком?

Знак сравнения сравнивает и возвращает 1 если истинно и 0 если ложно. 5>10=0, 5>2 = 1, что тоже не ясно? Разве что не уточнил, что приоритет меньше, чем у сложения и вычитания.

Что ты написал "во-вторых" я плохо понял.

Да, мне интересен весь спектр значений, и что?

Тень228 сказал(а):↑

Разный верхний порог

Разве что не уточнил, что приоритет меньше, чем у сложения и вычитания.

Нажмите, чтобы раскрыть...

Ничего что результатом алгебраических операции будет число, а результатом больше чемньше - логическое значение true/false?

Как это ложится в твою задачу то?

На одной прямой false/true и 5, 234, 34121?

saw_tooth сказал(а):↑

На самом деле представить тоже просто). Пусть частота ответов это будут градации черного

при x+y у тебя плотность распределения ответов, будет идти от значений функции по обе стороны прямой - с каждым отсчетом цвет будет все светлее и светлее

То есть что ты делаешь, ты берешь условно говоря решаешь каждую фукнцию t+y где t = N и накладываешь графики. Понять легко что будет просто меняться наклон прямой и её оффсет от 0, тоесть получится такое солнце которые тянут по диагонали от ноля.

 

При трех неизвестных ты получается куб в котором находится плоскость которая разрезает куб, на которой находится твоя черная прямая. Теперь если мы суму уберем и добавим умножение, то это будет не плоскость а криволинейная плоскость, на которой лежит прямая, в криволинейной системе координат (неевклидово)

Имея 4 коэфициента, размерность пространства так же увеличивается (пространство Минковского)...и так далее.

Нажмите, чтобы раскрыть...

Ну то есть как-то аналитически это решить не перебирая все варианты, да ещё придумать логику для компа анриал если ты не ломоносов?

 

saw_tooth сказал(а):↑

На самом деле представить тоже просто). Пусть частота ответов это будут градации черного

при x+y у тебя плотность распределения ответов, будет идти от значений функции по обе стороны прямой - с каждым отсчетом цвет будет все светлее и светлее

То есть что ты делаешь, ты берешь условно говоря решаешь каждую фукнцию t+y где t = N и накладываешь графики. Понять легко что будет просто меняться наклон прямой и её оффсет от 0, тоесть получится такое солнце которые тянут по диагонали от ноля.

 

При трех неизвестных ты получается куб в котором находится плоскость которая разрезает куб, на которой находится твоя черная прямая. Теперь если мы суму уберем и добавим умножение, то это будет не плоскость а криволинейная плоскость, на которой лежит прямая, в криволинейной системе координат (неевклидово)

Имея 4 коэфициента, размерность пространства так же увеличивается (пространство Минковского)...и так далее.

 

Ничего что результатом алгебраических операции будет число, а результатом больше чемньше - логическое значение true/false?

Как это ложится в твою задачу то?

На одной прямой false/true и 5, 234, 34121?

Нажмите, чтобы раскрыть...

??

Я же прямо там написал, что 0 или 1 будет

Не тру/фолс, а 0 или 1, числа такие есть, понимаешь?

Тень228 сказал(а):↑

Ну то есть как-то аналитически это решить не перебирая все варианты, да ещё придумать логику для компа анриал если ты не ломоносов?

Нажмите, чтобы раскрыть...

читай что такое NP полные задачи.

Тень228 сказал(а):↑

Я же прямо там написал, что 0 или 1 будет

Нажмите, чтобы раскрыть...

очевидно логические операции проще, потому что:

можно посчитать предел куска функции (для понимания роста),

продефиринцировать (для понимания где фунция растет и где спадает)

 и найти кол. максимумов и минимумов - для получения численного решения.

 

[/QUOTE]

Думай, как исключить перестановку слагаемых/множителей, как минимум. Например, если ты посчитал 1+1+3 уже нет смысла считать 1+3+1 и 3+1+1, можно сразу к результату "5" прибавить 3 повтора.

saw_tooth сказал(а):↑

читай что такое NP полные задачи.

очевидно логические операции проще, потому что:

можно посчитать предел куска функции (для понимания роста),

продефиринцировать (для понимания где фунция растет и где спадает)

 и найти кол. максимумов и минимумов - для получения численного решения.

 

Нажмите, чтобы раскрыть...

[/QUOTE]

Можно, но как бы может и не быть этого действия в примере.

А может быть несколько. И в разных местах и в скобках и т.д.