Форум программистов, компьютерный форум, киберфорум
Python: Решение задач
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.96/134: Рейтинг темы: голосов - 134, средняя оценка - 4.96
3 / 3 / 0
Регистрация: 23.08.2021
Сообщений: 71

Вывести все возможные варианты результата и их вероятности

23.08.2021, 18:46. Показов 28880. Ответов 65
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
По пятницам мы часто играем в популярную ролевую игру "Релиз до выходных" с коллегами. Правила этой игры довольно сложны и предполагают хорошую стратегию и планирование. Чтобы иметь представление о последствиях тех или иных ходов, часто хочется понимать, насколько вероятен тот или иной исход ситуации, с учетом разных вариантов выпадения игральных костей.

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

Выражение на входе может содержать скобки, и следующие операторы в порядке уменьшения их приоритета:

* – умножение
+ и - – сложение и вычитание
> - левый операнд больше, чем правый. Результат равен 1, если истинно, и 0 - если ложно

В качестве операндов могут выступать:

n - целые положительные числа, либо 0 (0≤n≤100 000)
dn - результат броска игральной кости, где n целое положительное число, количество граней (1≤n≤100 000). Результатом будет равномерное распределение вероятностей между всеми гранями (от 1 до n).

Входные данные (поступают в стандартный поток ввода)
Одна строка без пробелов, содержащая выражение для вычисления. Выражение гарантировано вычисляемое и не содержит синтаксических ошибок. Максимальная длина строки 200 символов.


Выходные данные (ожидаются в стандартном потоке вывода)
Одна или несколько строк, в каждой из которых есть два числа, разделенных пробелом:

1. целое – один из вариантов результата
2. вещественное - процент вероятности такого варианта с математическим округлением до 2 знаков и разделителем .
Строки на выходе должны быть отсортированы от меньшего результата к большему.

Примечание к округлению - в связи с округлением вероятностей - суммарная вероятность всех исходов может быть не равна 100%, это нормально, компенсировать это в решении не нужно.
1
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
23.08.2021, 18:46
Ответы с готовыми решениями:

Комбинаторика: вывести все возможные варианты
Вывести все возможные варианты слов, которые можно составить из первых 4-х букв английского алфавита(буквы не должны повторяться),...

Вывести все возможные варианты значений
Помогите решить следующую проблему: Имеется 14 столбцов; в ячейке каждого из столбцов может находиться одно из трех значений: 1, X или 2....

Вывести все возможные варианты перестановок от 1 до n
Здравствуйте, у меня есть массив чисел от 1 до n, нужно чтобы выводились все возможные варианты перестановок по порядку, то есть для трёх...

65
Костыли любой сложности
201 / 146 / 36
Регистрация: 27.10.2019
Сообщений: 843
23.08.2021, 21:48
duck_nukem, мб пример типа на входе имеем 2+2 программа выводит "сам решай"
0
3 / 3 / 0
Регистрация: 23.08.2021
Сообщений: 71
23.08.2021, 22:01  [ТС]
user-ganz, ну например вот
Пример 1
Ввод:

2+2
Вывод:

4 100.00

Пример 2
Ввод:

d4+2
Вывод:

3 25.00
4 25.00
5 25.00
6 25.00

Пример 3
Ввод:

d4+(d6>2)
Вывод:

1 8.33
2 25.00
3 25.00
4 25.00
5 16.67
0
Костыли любой сложности
201 / 146 / 36
Регистрация: 27.10.2019
Сообщений: 843
23.08.2021, 22:18
Цитата Сообщение от duck_nukem Посмотреть сообщение
Выражение гарантировано вычисляемое и не содержит синтаксических ошибок.
Цитата Сообщение от duck_nukem Посмотреть сообщение
d4+(d6>2)
имелось в виду д4+д6>2
инача в ответе 1 имеет ноль вероятности

если синтаксис соответстует математическому то полагаю решение есть
0
3 / 3 / 0
Регистрация: 23.08.2021
Сообщений: 71
23.08.2021, 22:26  [ТС]
user-ganz, что такое d4 и d6?
0
Костыли любой сложности
201 / 146 / 36
Регистрация: 27.10.2019
Сообщений: 843
23.08.2021, 22:29
duck_nukem,
Цитата Сообщение от duck_nukem Посмотреть сообщение
dn - результат броска игральной кости, где n целое положительное число, количество граней
ну и как бы костей с гранями (не сторонами) менее 6 не бывает

Добавлено через 58 секунд
точнее бывает, но они тогда называются фишками... но с тремя гранями точно не бывает
0
3 / 3 / 0
Регистрация: 23.08.2021
Сообщений: 71
23.08.2021, 22:55  [ТС]
user-ganz, это, что за кость, где n от 1 до 100000?
D4 и d6 это грань с 4 и 6?
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
24.08.2021, 07:13
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
import re
from itertools import product
expression = 'd4+(d6>2)'
variables = sorted(set(re.findall(r'd\d+', expression)), key=lambda x: int(x[1:]))
res = {}
for interval in product(*[range(1, int(v[1:])+1) for v in variables]):
    for x, y in zip(interval, variables):
        vars()[y] = x
    key = eval(expression)
    res[key] = res.get(key, 0) + 1
s = sum(res.values())
for k, v in res.items():
    print(f'{k} {v/s*100:.2f}')
0
3 / 3 / 0
Регистрация: 23.08.2021
Сообщений: 71
24.08.2021, 08:49  [ТС]
Цитата Сообщение от eaa Посмотреть сообщение
import re
from itertools import product
expression = 'd4+(d6>2)'
variables = sorted(set(re.findall(r'd\d+', expression)), key=lambda x: int(x[1:]))
res = {}
for interval in product(*[range(1, int(v[1:])+1) for v in variables]):
for x, y in zip(interval, variables):
vars()[y] = x
key = eval(expression)
res[key] = res.get(key, 0) + 1
s = sum(res.values())
for k, v in res.items():
print(f'{k} {v/s*100:.2f}')
2+2 не выводит 4 100
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
24.08.2021, 08:55
Цитата Сообщение от duck_nukem Посмотреть сообщение
2+2 не выводит 4 100
печаль. что теперь делать?
0
3 / 3 / 0
Регистрация: 23.08.2021
Сообщений: 71
24.08.2021, 09:09  [ТС]
Цитата Сообщение от eaa Посмотреть сообщение
печаль. что теперь делать?
не печалиться
0
0 / 0 / 0
Регистрация: 25.02.2021
Сообщений: 1
25.08.2021, 14:46
Тоже решаешь задачу с отбора headhunter, да?
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
25.08.2021, 18:54
Да тут все так решают олимпиады, конкурсы, отборы
0
0 / 0 / 0
Регистрация: 25.11.2011
Сообщений: 11
31.08.2021, 12:53
Цитата Сообщение от duck_nukem Посмотреть сообщение
2+2 не выводит 4 100
Все выводит, как вы проверяли вопрос. Но это решение все равно не засчитывает, хоть и проходит все тесты.
0
31.08.2021, 15:30

Не по теме:

И потом они программистами работают?)

0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
31.08.2021, 15:51
Цитата Сообщение от gobL1n Посмотреть сообщение
Но это решение все равно не засчитывает, хоть и проходит все тесты.
правильно, потому что это "читерство" называется
0
1 / 1 / 0
Регистрация: 02.09.2021
Сообщений: 14
02.09.2021, 13:05
Доброго времени суток.
Написал вот такой код. Я не программист прошу не судить строго за говнокод.
Проходит все тесты, но ответ не правильный. Вероятнее всего что просто медленно выполняется. Для количества вероятных ответов > 500000 работает больше 1 сек. Но статус именно "неправильный ответ"

Не могу придумать контрпример, если у кого есть идеи прошу помочь

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#s = input()
 
int_ = ['0','1','2','3','4','5','6','7','8','9']
 
s = 'd4+(d6>2)'
 
def dCount(s): # Функция возвращает число в s после 'd'. Например 'd2' -> 2 
    ds = ''
    i = s.find('d')
    while s[i+1] in int_:
        ds += s[i+1]
        i += 1
        if i == len(s)-1:
            break
    return ds
 
def rep(s,i): # Функция возвращает новую строку в которой 'd2' заменяется на i
    news = s[:s.find('d')] +str(i)+s[(s.find('d')+1+len(dCount(s))):]
    return news
 
def arithmetic_round(x): # Математическое округление до 2 знака (требование задачи)
    a = int(x*100)
    b = x*100 - a
    if b < 0.5:
        return (round(x,2))
    else:
        return (round(x+0.001,2))
 
def Upp(x): # Добивание 0. Пример 0.5 -> 0.50 (требование задачи)
    s = str(float(x))
    ss = s.split('.')
    if len(ss[1]) != 2:
        s += '0'
    return s
    
sr = [] # Список строк с заменами 'd' на значения 
srp = [] # Список вероятностей для этих строк
 
sr.append(s)
srp.append(100)
 
# Основной цикл замены
while sr[0].find('d') != -1:  
 
# В итоге мы получим список строк (sr) для всех вероятностей (Количество строк = произведение всех вероятностей)
# srp - вероятности для этих строк. Длина списка = длины списка sr
 
    temp_sr = sr
    sr = []
    temp_srp = srp
    srp = []
    t = 0
    
    for i in range(len(temp_sr)):
       
        f = int(dCount(temp_sr[i]))
        
        for j in range (1,int(dCount(temp_sr[i]))+1):
            t += 1
            sr.append(rep(temp_sr[i],j))
            srp.append(temp_srp[i]/f)
 
ans = []
 
# Вычисляем строки в новый список
for i in sr: 
    ans.append(eval(i))
 
d = []
 
# Создаем список словарей [{ответ : вероятность},...]
for i in range(len(ans)): 
    d.append({ans[i]:srp[i]})
 
rd = {}
 
# Схлопываем одинаковые ответы и суммируем вероятности, получаем новый словарь с уникальными ответами
for dictionary in d:
    for key in dictionary:
        rd[key] = 0
 
for dictionary in d:
    for key in dictionary:
        rd[key] += dictionary[key]
        
# Математически округляем и добиваем 0 после точки    
for value in rd:
    rd[value] = arithmetic_round(rd[value])
    rd[value] = Upp(rd[value])
 
# Сортируем (требование задачи)
srd = dict(sorted(rd.items()))
 
# Выводим ответ. Если строка вида '1>2' вместо False выводим 0
for key, value in srd.items():
    if key == False:
        print (str(0)+' '+value)
    elif key == True:
        print (str(1)+' '+value)
    else:
        print (str(key)+' '+value)
P.S. Не выкладывал бы, но что то вообще ничего не могу придумать
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
02.09.2021, 13:44
eval медленный
0
1 / 1 / 0
Регистрация: 02.09.2021
Сообщений: 14
02.09.2021, 14:01
Цитата Сообщение от eaa Посмотреть сообщение
eval медленный
Спасибо за комментарий, но по замерам времени, создание списка со всеми выражениями занимает на порядок больше времени чем eval(). Да и судя по статье с хабра самописная функция вычисления (использующая обратную польскую запись и все такое) может улучшить eval не более чем 10-20%. Сильно сомневаюсь, что создатели задачи ожидали самописный eval()

Если бы я точно знал что нужно оптимизировать время выполнения это одно. Однако зачем оптимизировать программу, которая выдает неверный ответ? Думаю сначала надо починить алгоритм, а я в нем найти ошибку не могу.
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
02.09.2021, 14:18
FedorPup, введите: 'd4+d4'
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
02.09.2021, 14:18
Помогаю со студенческими работами здесь

Вывести все возможные варианты разреза трубы
Вводится длина трубы, количество заготовок (1, 2, 3, 4 ил 5), которые можно вырезать из трубы, и длина каждой заготовки. Вывести все...

Вывести все возможные варианты хода конем
можете решить задачу в GDB online Compiler на шахматную доску поставили коня,виведите все возможние варианти хода конем. например:программа...

Вывести на экран все возможные варианты покупок
Нужно вывести на экран все возможные варианты покупок на 100р, допустим bull=5 cow=2.5 calf=0.5. И надо чтобы было куплено как минимум по...

Заменить все вопросительные знаки цифрами (от 1 до 9), перевести строку в число, вывести все возможные варианты
Дана строка состоящая из цифр и вопросительных знаков. Длина строки от 1 до 9 символов. Цель: заменить все вопросительные знаки цифрами (от...

Структуры. Вывести все возможные варианты покупки товаров
может кто нибудь помочь составить прогу /* с++ */ 1) С клавиатуры вводятся записи вида: товар - стринг (название товара) цена -...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru