Введение
В своей предыдущей статье я описал способ нахождения делимого вероятности выпадения какой-то суммы чисел на кубиках при помощи многократной свёртки последовательности [1 1 1 1 1 1] на саму себя. Иными словами, многократное умножение в столбик (без переноса переполнившихся разрядов) последовательности/числа 111111 на саму/само себя. Почему, правда, не пишут, что умножение в столбик является прямой аналогией свёртки последовательностей — для меня загадка (может я что-то упускаю из вида — если я не прав, пожалуйста, напишите). Однако, дальше в статье я буду применять два словосочетания «свёртка последовательностей» и «умножение в столбик» совместно, т.к. первое — корректное описание операции, а второе отвечает за наглядность и простоту восприятия.
Напомню:
Так же в конце предыдущей статьи я «страшился» найти вероятности для 1000 кубиков. Вот именно этим и предлагаю заняться.
Прелюдия
Хотелось бы подчеркнуть, что и на картинке вверху, и собственно в предыдущей статье упор делался на «умножение в столбик» / свёртку последовательностей [1 1 1 1 1 1], и не затрагивалась возможность «умножить» на что-либо ещё. Вот эту оплошность хотелось бы упразднить.
Отвлекусь немного на факт, что любое натуральное число может быть представлено как сумма натуральных степеней числа 2 (Производящие функции — туда и обратно ответ на вопрос: какие грузы можно взвесить с помощью гирь в 20, 21, 22,…, 2n грамм и сколькими способам?). Приведу визуализацию:
Данное знание нам будет полезно для операций со степенями. Например, нахождение какого-то числа a63 будем представлять как: a63 = a1 + 2 + 4 + … + 32 = a1 * a2 * a4 * … * a32. То есть зная только I элемент и умея умножать/свёртывать будем пытаться найти 63-й элемент (степень 63) используя как можно меньше операций умножения/свёртки.
Для начала хотелось бы обкатать операцию свёртки последовательностей / «умножение в столбик» на уже знакомом треугольнике Паскаля. А именно попробовать найти 9-й элемент треугольника Паскаля зная только I элемент (именно [1 1]) не при помощи многократной свёртки последовательностей / «умножение в столбик» [1 1] на саму себя (дискретная свёртка или полиномиальное умножение), а представив что каждая последовательность чисел в треугольнике Паскаля соответствует степени последовательности [1 1]. Звучит наверно запутанно, так что приведу картинку из прошлой статьи, для визуализации:
Попробуем найти 9-й элемент треугольника Паскаля.
Выглядит многообещающе. Так же приложу скрипт с теми же результатами при помощи именно свёртки последовательностей.
Python. Пример. II, IV, VIII, XI элемент треугольника Паскаля
# -*- coding: utf-8 -*- import numpy convolve_out = numpy.convolve([1, 1], [1, 1]) # [1 2 1] print(convolve_out) convolve_out = numpy.convolve(convolve_out, convolve_out) # [1 4 6 4 1] print(convolve_out) convolve_out = numpy.convolve(convolve_out, convolve_out) # [ 1 8 28 56 70 56 28 8 1] print(convolve_out) convolve_out = numpy.convolve(convolve_out, [1, 1]) # [ 1 9 36 84 126 126 84 36 9 1] print(convolve_out) Визуализация алгоритма, I попытка
По аналогии с треугольником Паскаля хочется провернуть аналогичную операцию с кубиками, и найти для примера вероятность выпадения суммы костей 19 для 5 кубиков. Т.е. возьмём первоначальную последовательность [1 1 1 1 1 1] и дойдём до 5-ого кубика (степень 5) по следующей цепочке операций свёртки последовательностей / «умножение в столбик»:
a1 * a1 = a2
a2 * a2 = a4
a1 * a4 = a5
Приложу скрипт для нахождения “Сколько раз встречается значение” в “Этап I. Генерация 2-х списков/массивов: Значения (сумма выпавших костей) И Сколько раз встречается значение” при помощи свёртки последовательностей / “умножения в столбик”.
Python. Пример. Свёртка последовательностей [1 1 1 1 1 1]
# -*- coding: utf-8 -*- import numpy convolve_out = numpy.convolve([1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1]) # [1 2 3 4 5 6 5 4 3 2 1] print(convolve_out) convolve_out = numpy.convolve(convolve_out, convolve_out) # [ 1 4 10 20 35 56 80 104 125 140 146 140 125 104 80 56 35 20 10 4 1] print(convolve_out) convolve_out = numpy.convolve(convolve_out, [1, 1, 1, 1, 1, 1]) # [ 1 5 15 35 70 126 205 305 420 540 651 735 780 780 735 651 540 420 305 205 126 70 35 15 5 1] print(convolve_out) Скрипты, I попытка
В целом, как мне кажется, задумка достаточно расписана. Остаётся выложить получившейся скрипты, написанные по описанным лекалам. Простор для оптимизаций оставляю читателям.
Python
# -*- coding: utf-8 -*- def main(): c_int_side_dice: int = 6 # сколько граней у кубика c_int_dice_number: int = 1000 # кол-во кубиков c_int_number_to_find: int = 2000 # число, вероятность выпадения которого хотим найти probability = dice_probability(c_int_dice_number, c_int_number_to_find, c_int_side_dice) print(probability) # собственно поиск вероятности определённого значения def dice_probability(int_dice_number: int, int_number_to_find: int, c_int_side_dice: int) -> float: if int_number_to_find >= int_dice_number and int_number_to_find <= c_int_side_dice * int_dice_number: list_values: list[int] = [i for i in range(int_dice_number, c_int_side_dice * int_dice_number + 1)] list_interm_probability = interm_probabilities(c_int_side_dice, int_dice_number) for i in range(len(list_values)): if list_values[i] == int_number_to_find: int_out: int = list_interm_probability[i] break return int_out / (c_int_side_dice ** int_dice_number) else: # задаваемое число выходит за рамки реально возможного диапазона значений return 0.0 # возвращает список/массив: сколько раз встречается значение def interm_probabilities(int_side_dice: int, int_pow: int) -> list[int]: """ На примере int_side_dice = 6, int_pow = 5 { 1: [1, 1, 1, 1, 1, 1], 2: [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1], 4: [1, 4, 10, 20, 35, 56, 80, 104, 125, 140, 146, 140, 125, 104, 80, 56, 35, 20, 10, 4, 1] 5: [1, 5, 15, 35, 70, 126, 205, 305, 420, 540, 651, 735, 780, 780, 735, 651, 540, 420, 305, 205, 126, 70, 35, 15, 5, 1] } """ dict_interm_probability: dict[int, list[int]] = {1: [1] * int_side_dice} if int_pow == 0: print("Не поддерживается") quit() elif int_pow != 1: list_to_do = map_todo(int_pow) for elem in list_to_do: dict_interm_probability[elem[2]] = multiply_cins_orig(dict_interm_probability[elem[0]], dict_interm_probability[elem[1]]) return dict_interm_probability[int_pow] # Как добраться до интересующего значения, используя x2/+nx для степеней def map_todo(int_wanted: int) -> list[tuple[int, int, int]]: """ На примере int_wanted = 5 Степени "числа": 1 1 * 2 = 2 -> tuple(1, 1, 2) 2 * 2 = 4 -> tuple(2, 2, 4) 4 + 1 = 5 -> tuple(4, 1, 5) """ int_current_id: int = 1 int_sum: int = 1 b_ascending: bool = True list_solution: list[tuple[int, int, int]] = [] while True: if int_sum == int_wanted: break elif b_ascending and 2 * int_current_id <= int_wanted: list_solution.append( # mult_1, mult_2, result (int_current_id, int_current_id, 2 * int_current_id) ) int_current_id = 2 * int_current_id int_sum = int_current_id elif b_ascending and 2 * int_current_id > int_wanted: b_ascending = False int_sum = int_current_id int_current_id = int(int_current_id / 2) # чтобы возвращал именно integer elif not b_ascending and int_sum + int_current_id <= int_wanted: list_solution.append( # mult_1, mult_2, result (int_sum, int_current_id, int_sum + int_current_id) ) int_sum = int_sum + int_current_id int_current_id = int(int_current_id / 2) # чтобы возвращал именно integer elif not b_ascending and int_sum + int_current_id > int_wanted: int_current_id = int(int_current_id / 2) # чтобы возвращал именно integer return list_solution # "умножение" в столбик двух массивов/списков def multiply_cins_orig(list_in_1: list[int], list_in_2: list[int]) -> list[int]: int_len_2: int = len(list_in_2) list_dummy: list[list[int]] = [] for i in range(int_len_2): list_dummy.append([0] * i) # [], [0], [0, 0], [0, 0, 0] ... list_for_sum: list[list[int]] = [] i: int = -1 for elem_2 in list_in_2: i += 1 list_interm: list[int] = [elem_1 * elem_2 for elem_1 in list_in_1] list_for_sum.append(list_dummy[i] + list_interm + list_dummy[int_len_2 - i - 1]) """ [list_in_1 X elem_2[0], 0, 0, 0, 0, 0] [0, list_in_1 X elem_2[1], 0, 0, 0, 0] [0, 0, list_in_1 X elem_2[2], 0, 0, 0] [0, 0, 0, list_in_1 X elem_2[3], 0, 0] [0, 0, 0, 0, list_in_1 X elem_2[4], 0] [0, 0, 0, 0, 0, list_in_1 X elem_2[5]] """ list_out: list[int] = [] for i in range(len(list_for_sum[0])): sum_out: int = 0 for j in range(int_len_2): sum_out += list_for_sum[j][i] list_out.append(sum_out) """ [1, 3, 6, 10, 15, 21, 25, 27, 27, 25, 21, 15, 10, 6, 3, 1] """ return list_out main() JavaScript
function main(){ const c_int_side_dice = 6; // сколько граней у кубика const c_int_dice_number = 100; // кол-во кубиков const c_int_number_to_find = 300; // число, вероятность выпадения которого хотим найти let probability = dice_probability(c_int_dice_number, c_int_number_to_find, c_int_side_dice); console.log(probability); } // собственно поиск вероятности определённого значения function dice_probability(int_dice_number, int_number_to_find, c_int_side_dice){ if (int_number_to_find >= int_dice_number && int_number_to_find <= c_int_side_dice * int_dice_number){ let list_values = new Array(); let i = 0; for (let j = int_dice_number; j <= c_int_side_dice * int_dice_number; j++){ list_values[i] = j; i++; } let list_interm_probability = interm_probabilities(c_int_side_dice, int_dice_number); let int_out; for (let i = 0; i <= list_values.length; i++){ if (list_values[i] == int_number_to_find){ int_out = list_interm_probability[i]; break; } } return int_out / Math.pow(c_int_side_dice, int_dice_number); } else { // задаваемое число выходит за рамки реально возможного диапазона значений return 0.0; } } // возвращает список/массив: сколько раз встречается значение function interm_probabilities(int_side_dice, int_pow){ // На примере int_side_dice = 6, int_pow = 5 // { // 1: [1, 1, 1, 1, 1, 1], // 2: [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1], // 4: [1, 4, 10, 20, 35, 56, 80, 104, 125, 140, 146, 140, 125, 104, 80, 56, 35, 20, 10, 4, 1] // 5: [1, 5, 15, 35, 70, 126, 205, 305, 420, 540, 651, 735, 780, 780, 735, 651, 540, 420, 305, 205, 126, 70, 35, 15, 5, 1] // } let dict_interm_probability = {1: Array(int_side_dice).fill(1)}; if (int_pow == 0){ console.log("Не поддерживается"); return; } else if (int_pow != 1){ let list_to_do = map_todo(int_pow); for (let i = 0; i < list_to_do.length; i++){ dict_interm_probability[list_to_do[i][2]] = multiply_cins_orig(dict_interm_probability[list_to_do[i][0]], dict_interm_probability[list_to_do[i][1]]); } } return dict_interm_probability[int_pow]; } // Как добраться до интересующего значения, используя x2/+nx для степеней function map_todo(int_wanted){ // На примере int_wanted = 5 // Степени "числа": // 1 // 1 * 2 = 2 -> Array(1, 1, 2) // 2 * 2 = 4 -> Array(2, 2, 4) // 4 + 1 = 5 -> Array(4, 1, 5) let int_current_id = 1; let int_sum = 1; let b_ascending = true; let list_solution = new Array(); let i = 0; while (true){ if (int_sum == int_wanted){ break; } else if (b_ascending && 2 * int_current_id <= int_wanted){ list_solution[i] = [int_current_id, int_current_id, 2 * int_current_id]; // mult_1, mult_2, result i++; int_current_id = 2 * int_current_id; int_sum = int_current_id; } else if (b_ascending && 2 * int_current_id > int_wanted){ b_ascending = false; int_sum = int_current_id; int_current_id = Math.ceil(int_current_id / 2); // чтобы возвращал именно integer } else if (!b_ascending && int_sum + int_current_id <= int_wanted){ list_solution[i] = [int_sum, int_current_id, int_sum + int_current_id]; // mult_1, mult_2, result i++; int_sum = int_sum + int_current_id; int_current_id = Math.ceil(int_current_id / 2); // чтобы возвращал именно integer } else if (!b_ascending && int_sum + int_current_id > int_wanted){ int_current_id = Math.ceil(int_current_id / 2); // чтобы возвращал именно integer } } return list_solution; } // "умножение" в столбик двух массивов/списков function multiply_cins_orig(list_in_1, list_in_2){ let int_len_1 = list_in_1.length; let int_len_2 = list_in_2.length; let list_dummy = new Array(); for (let j = 0; j < int_len_2; j++){ list_dummy[j] = Array(j).fill(0); // [], [0], [0, 0], [0, 0, 0] ... } let list_for_sum = new Array(); for (let j = 0; j < int_len_2; j++){ let list_interm = new Array(); for (let i = 0; i < int_len_1; i++){ list_interm[i] = list_in_1[i] * list_in_2[j] } list_for_sum[j] = list_dummy[j].concat(list_interm, list_dummy[int_len_2 - j - 1]); } // [list_in_1 X elem_2[0], 0, 0, 0, 0, 0] // [0, list_in_1 X elem_2[1], 0, 0, 0, 0] // [0, 0, list_in_1 X elem_2[2], 0, 0, 0] // [0, 0, 0, list_in_1 X elem_2[3], 0, 0] // [0, 0, 0, 0, list_in_1 X elem_2[4], 0] // [0, 0, 0, 0, 0, list_in_1 X elem_2[5]] let list_out = new Array(); for (let i = 0; i < list_for_sum[0].length; i++){ let sum_out = 0; for (let j = 0; j < int_len_2; j++){ sum_out += list_for_sum[j][i]; } list_out[i] = sum_out; } // [1, 3, 6, 10, 15, 21, 25, 27, 27, 25, 21, 15, 10, 6, 3, 1] return list_out; } main();VBS
Option Explicit Sub main() Const c_int_side_dice = 6 'сколько граней у кубика Const c_int_dice_number = 100 'кол-во кубиков Const c_int_number_to_find = 200 'число, вероятность выпадения которого хотим найти Dim probability probability = dice_probability(c_int_dice_number, c_int_number_to_find, c_int_side_dice) MsgBox probability End Sub ' собственно поиск вероятности определённого значения Function dice_probability(int_dice_number, int_number_to_find, c_int_side_dice) If int_number_to_find >= int_dice_number And int_number_to_find <= c_int_side_dice * int_dice_number Then ReDim list_values(int_dice_number * (c_int_side_dice - 1)) Dim i, j i = 0 For j = int_dice_number To c_int_side_dice * int_dice_number list_values(i) = j i = i + 1 Next Dim list_interm_probability() interm_probabilities c_int_side_dice, int_dice_number, list_interm_probability For i = 0 To int_dice_number * (c_int_side_dice - 1) If list_values(i) = int_number_to_find Then Exit For End If Next dice_probability = list_interm_probability(i) / (c_int_side_dice ^ int_dice_number) Else 'задаваемое число выходит за рамки реально возможного диапазона значений dice_probability = 0.0 End If End Function 'возвращает список/массив: сколько раз встречается значение Sub interm_probabilities(int_side_dice, int_pow, list_out) 'На примере int_side_dice = 6, int_pow = 5 '{ ' 1: [1, 1, 1, 1, 1, 1], ' 2: [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1], ' 4: [1, 4, 10, 20, 35, 56, 80, 104, 125, 140, 146, 140, 125, 104, 80, 56, 35, 20, 10, 4, 1] ' 5: [1, 5, 15, 35, 70, 126, 205, 305, 420, 540, 651, 735, 780, 780, 735, 651, 540, 420, 305, 205, 126, 70, 35, 15, 5, 1] '} Dim j Dim list_interm_probability() ReDim list_interm_probability(int_side_dice - 1) For j = 0 To int_side_dice - 1 list_interm_probability(j) = 1 Next Dim dict_interm_probability Set dict_interm_probability = CreateObject("Scripting.Dictionary") dict_interm_probability.Add 1, list_interm_probability If int_pow = 0 Then MsgBox "Не поддерживается" Quit ElseIf int_pow <> 1 Then Dim list_to_do() map_todo list_to_do, int_pow For j = 0 To UBound(list_to_do, 2) 'MsgBox list_to_do(0, j) & vbTab & list_to_do(1, j) & vbTab & list_to_do(2, j) multiply_cins_orig _ dict_interm_probability.Item(list_to_do(0, j)), _ dict_interm_probability.Item(list_to_do(1, j)), _ list_out dict_interm_probability.Add list_to_do(2, j), list_out ' ArrOut_1 list_out Next End If End Sub 'Как добраться до интересующего значения, используя x2/+nx для степеней Sub map_todo(list_solution, int_wanted) 'На примере int_wanted = 5 'Степени "числа": '1 '1 * 2 = 2 -> Array(1, 1, 2) '2 * 2 = 4 -> Array(2, 2, 4) '4 + 1 = 5 -> Array(4, 1, 5) Dim int_current_id Dim int_sum Dim b_ascending Dim i int_current_id = 1 int_sum = 1 b_ascending = True i = -1 Do If b_ascending And 2 * int_current_id <= int_wanted Then i = i + 1 ReDim Preserve list_solution(2, i) list_solution(0, i) = int_current_id list_solution(1, i) = int_current_id list_solution(2, i) = 2 * int_current_id int_current_id = 2 * int_current_id int_sum = int_current_id ElseIf b_ascending And 2 * int_current_id > int_wanted Then b_ascending = False int_sum = int_current_id int_current_id = CInt(int_current_id / 2) 'чтобы возвращал именно integer ElseIf Not b_ascending And int_sum + int_current_id <= int_wanted Then i = i + 1 ReDim Preserve list_solution(2, i) list_solution(0, i) = int_sum list_solution(1, i) = int_current_id list_solution(2, i) = int_sum + int_current_id int_sum = int_sum + int_current_id int_current_id = CInt(int_current_id / 2) 'чтобы возвращал именно integer ElseIf Not b_ascending And int_sum + int_current_id > int_wanted Then int_current_id = CInt(int_current_id / 2) 'чтобы возвращал именно integer End If Loop Until (int_sum = int_wanted) End Sub ' "умножение" в столбик двух массивов/списков Sub multiply_cins_orig(list_in_1, list_in_2, list_in) Dim int_len_1 Dim int_len_2 int_len_1 = Ubound(list_in_1, 1) int_len_2 = Ubound(list_in_2, 1) Dim list_for_sum() ReDim list_for_sum(int_len_2, int_len_1 + int_len_2) Dim i, j, k, n For i = 0 To int_len_2 j = 0 For n = 0 To int_len_2 If i = n Then For k = 0 To int_len_1 list_for_sum(i, j) = list_in_1(k) * list_in_2(n) j = j + 1 Next Else list_for_sum(i, j) = 0 j = j + 1 End If Next Next '[list_in_1 X elem_2[0], 0, 0, 0, 0, 0] '[0, list_in_1 X elem_2[1], 0, 0, 0, 0] '[0, 0, list_in_1 X elem_2[2], 0, 0, 0] '[0, 0, 0, list_in_1 X elem_2[3], 0, 0] '[0, 0, 0, 0, list_in_1 X elem_2[4], 0] '[0, 0, 0, 0, 0, list_in_1 X elem_2[5]] 'ArrOut_2 list_for_sum Erase list_in ReDim list_in(int_len_1 + int_len_2) Dim sum_out For j = 0 To int_len_1 + int_len_2 sum_out = 0 For i = 0 To int_len_2 sum_out = sum_out + list_for_sum(i, j) Next list_in(j) = sum_out Next ' [1, 3, 6, 10, 15, 21, 25, 27, 27, 25, 21, 15, 10, 6, 3, 1] 'ArrOut_1 list_in End Sub '================================================== '<Additional_MsgBox_For_Arrays> Sub ArrOut_1(arr_in) Dim str_out Dim i For i = 0 To UBound(arr_in) If i = 0 Then str_out = arr_in(i) Else str_out = str_out & " " & arr_in(i) End If Next MsgBox str_out End Sub Sub ArrOut_2(arr_in) Dim str_out Dim i, j For i = 0 To UBound(arr_in, 1) For j = 0 To UBound(arr_in, 2) If i = 0 And j = 0 Then str_out = arr_in(i, j) ElseIf j = 0 Then str_out = str_out & vbNewLine & arr_in(i, j) Else str_out = str_out & " " & arr_in(i, j) End If Next Next MsgBox str_out End Sub '</Additional_MsgBox_For_Arrays> '================================================== mainВизуализация алгоритма, II попытка
Если быть достаточно честным, то из 3-х выложенных скриптов именно до 1000-го кубика может добраться только Python (без использования библиотеки numpy), а JavaScript и VBS выпадают в ошибку переполнение переменной. Предлагаю сделать небольшую хитрость: считать сразу вероятность выпадения внутри операции свёртки последовательностей / «умножения в столбик», вместо только делимого. Т.е. на вход сразу подавать последовательность [1/6 1/6 1/6 1/6 1/6 1/6] вместо [1 1 1 1 1 1] и, следовательно, на выходе всех операций свёртки последовательностей / «умножения в столбик» мы получим последовательность / массив / список вероятностей.
Python. Пример. Свёртка последовательностей [1/6 1/6 1/6 1/6 1/6 1/6]
Понимаю, что дроби проверять — дело не благодарное, следовательно добавляю степень 6 ** n * … — делитель вероятности. Это сделано чисто для упрощения проверки.
# -*- coding: utf-8 -*- import numpy convolve_out = numpy.convolve([1 / 6] * 6, [1 / 6] * 6) # [1 2 3 4 5 6 5 4 3 2 1] print(6 ** 2 * convolve_out) convolve_out = numpy.convolve(convolve_out, convolve_out) # [ 1 4 10 20 35 56 80 104 125 140 146 140 125 104 80 56 35 20 10 4 1] print(6 ** 4 * convolve_out ) convolve_out = numpy.convolve(convolve_out, [1 / 6] * 6) # [ 1 5 15 35 70 126 205 305 420 540 651 735 780 780 735 651 540 420 305 205 126 70 35 15 5 1] print(6 ** 5 * convolve_out) Скрипты, II попытка
До 1000-го кубика добираются все. Простор для оптимизаций оставляю читателям.
Python
# -*- coding: utf-8 -*- # import numpy # <можно_использовать_numpy> def main(): c_int_side_dice: int = 6 # сколько граней у кубика c_int_dice_number: int = 1000 # кол-во кубиков c_int_number_to_find: int = 2000 # число, вероятность выпадения которого хотим найти probability = dice_probability(c_int_dice_number, c_int_number_to_find, c_int_side_dice) print(probability) # собственно поиск вероятности определённого значения def dice_probability(int_dice_number: int, int_number_to_find: int, c_int_side_dice: int) -> float: if int_number_to_find >= int_dice_number and int_number_to_find <= c_int_side_dice * int_dice_number: list_values: list[int] = [i for i in range(int_dice_number, c_int_side_dice * int_dice_number + 1)] list_probability = get_probabilities(c_int_side_dice, int_dice_number) for i in range(len(list_values)): if list_values[i] == int_number_to_find: float_out: float = list_probability[i] break return float_out else: # задаваемое число выходит за рамки реально возможного диапазона значений return 0.0 # возвращает список/массив: вероятности выадения def get_probabilities(int_side_dice: int, int_pow: int) -> list[float]: """ На примере int_side_dice = 6, int_pow = 5 { 1: [1 / 6, 1 / 6, 1 / 6, 1 / 6, 1 / 6, 1 / 6], 2: [1 / 36, 2 / 36, 3 / 36, 4 / 36, 5 / 36, 6 / 36, 5 / 36, 4 / 36, 3 / 36, 2 / 36, 1 / 36], 4: [1 / 1296, 4 / 1296, 10 / 1296, 20 / 1296, 35 / 1296, 56 / 1296, 80 / 1296, 104 / 1296, 125 / 1296, 140 / 1296, 146 / 1296, 140 / 1296, 125 / 1296, 104 / 1296, 80 / 1296, 56 / 1296, 35 / 1296, 20 / 1296, 10 / 1296, 4 / 1296, 1 / 1296] 5: [1 / 7776, 5 / 7776, 15 / 7776, 35 / 7776, 70 / 7776, 126 / 7776, 205 / 7776, 305 / 7776, 420 / 7776, 540 / 7776, 651 / 7776, 735 / 7776, 780 / 7776, 780 / 7776, 735 / 7776, 651 / 7776, 540 / 7776, 420 / 7776, 305 / 7776, 205 / 7776, 126 / 7776, 70 / 7776, 35 / 7776, 15 / 7776, 5 / 7776, 1 / 7776] } """ dict_interm_probability = {1: [1 / int_side_dice] * int_side_dice} if int_pow == 0: print("Не поддерживается") quit() elif int_pow != 1: list_to_do = map_todo(int_pow) for elem in list_to_do: dict_interm_probability[elem[2]] = multiply_cins_orig(dict_interm_probability[elem[0]], dict_interm_probability[elem[1]]) # dict_interm_probability[elem[2]] = numpy.convolve(dict_interm_probability[elem[0]], dict_interm_probability[elem[1]]) # <можно_использовать_numpy> и не использовать multiply_cins_orig() return dict_interm_probability[int_pow] # Как добраться до интересующего значения, используя x2/+nx для степеней def map_todo(int_wanted: int) -> list[tuple[int, int, int]]: """ На примере int_wanted = 5 Степени "числа": 1 1 * 2 = 2 -> tuple(1, 1, 2) 2 * 2 = 4 -> tuple(2, 2, 4) 4 + 1 = 5 -> tuple(4, 1, 5) """ int_current_id: int = 1 int_sum: int = 1 b_ascending: bool = True list_solution: list[tuple[int, int, int]] = [] while True: if int_sum == int_wanted: break elif b_ascending and 2 * int_current_id <= int_wanted: list_solution.append( # mult_1, mult_2, result (int_current_id, int_current_id, 2 * int_current_id) ) int_current_id = 2 * int_current_id int_sum = int_current_id elif b_ascending and 2 * int_current_id > int_wanted: b_ascending = False int_sum = int_current_id int_current_id = int(int_current_id / 2) # чтобы возвращал именно integer elif not b_ascending and int_sum + int_current_id <= int_wanted: list_solution.append( # mult_1, mult_2, result (int_sum, int_current_id, int_sum + int_current_id) ) int_sum = int_sum + int_current_id int_current_id = int(int_current_id / 2) # чтобы возвращал именно integer elif not b_ascending and int_sum + int_current_id > int_wanted: int_current_id = int(int_current_id / 2) # чтобы возвращал именно integer return list_solution # "умножение" в столбик двух массивов/списков def multiply_cins_orig(list_in_1: list[int], list_in_2: list[int]) -> list[int]: int_len_2: int = len(list_in_2) list_dummy: list[list[int]] = [] for i in range(int_len_2): list_dummy.append([0] * i) # [], [0], [0, 0], [0, 0, 0] ... list_for_sum: list[list[int]] = [] i: int = -1 for elem_2 in list_in_2: i += 1 list_interm: list[int] = [elem_1 * elem_2 for elem_1 in list_in_1] list_for_sum.append(list_dummy[i] + list_interm + list_dummy[int_len_2 - i - 1]) """ [list_in_1 X list_in_2[0], 0, 0, 0, 0, 0] [0, list_in_1 X list_in_2[1], 0, 0, 0, 0] [0, 0, list_in_1 X list_in_2[2], 0, 0, 0] [0, 0, 0, list_in_1 X list_in_2[3], 0, 0] [0, 0, 0, 0, list_in_1 X list_in_2[4], 0] [0, 0, 0, 0, 0, list_in_1 X list_in_2[5]] """ list_out: list[int] = [] for i in range(len(list_for_sum[0])): sum_out: int = 0 for j in range(int_len_2): sum_out += list_for_sum[j][i] list_out.append(sum_out) """ [1 / 216, 3 / 216, 6 / 216, 10 / 216, 15 / 216, 21 / 216, 25 / 216, 27 / 216, 27 / 216, 25 / 216, 21 / 216, 15 / 216, 10 / 216, 6 / 216, 3 / 216, 1 / 216] """ return list_out main() JavaScript
function main(){ const c_int_side_dice = 6; // сколько граней у кубика const c_int_dice_number = 1000; // кол-во кубиков const c_int_number_to_find = 2000; // число, вероятность выпадения которого хотим найти let probability = dice_probability(c_int_dice_number, c_int_number_to_find, c_int_side_dice); console.log(probability); } // собственно поиск вероятности определённого значения function dice_probability(int_dice_number, int_number_to_find, c_int_side_dice){ if (int_number_to_find >= int_dice_number && int_number_to_find <= c_int_side_dice * int_dice_number){ let list_values = new Array(); let i = 0; for (let j = int_dice_number; j <= c_int_side_dice * int_dice_number; j++){ list_values[i] = j; i++; } let list_probability = get_probabilities(c_int_side_dice, int_dice_number); let float_out; for (let i = 0; i <= list_values.length; i++){ if (list_values[i] == int_number_to_find){ float_out = list_probability[i]; break; } } return float_out; } else { // задаваемое число выходит за рамки реально возможного диапазона значений return 0.0; } } // возвращает список/массив: вероятности выадения function get_probabilities(int_side_dice, int_pow){ // На примере int_side_dice = 6, int_pow = 5 // { // 1: [1 / 6, 1 / 6, 1 / 6, 1 / 6, 1 / 6, 1 / 6], // 2: [1 / 36, 2 / 36, 3 / 36, 4 / 36, 5 / 36, 6 / 36, 5 / 36, 4 / 36, 3 / 36, 2 / 36, 1 / 36], // 4: [1 / 1296, 4 / 1296, 10 / 1296, 20 / 1296, 35 / 1296, 56 / 1296, 80 / 1296, 104 / 1296, 125 / 1296, 140 / 1296, 146 / 1296, 140 / 1296, 125 / 1296, 104 / 1296, 80 / 1296, 56 / 1296, 35 / 1296, 20 / 1296, 10 / 1296, 4 / 1296, 1 / 1296] // 5: [1 / 7776, 5 / 7776, 15 / 7776, 35 / 7776, 70 / 7776, 126 / 7776, 205 / 7776, 305 / 7776, 420 / 7776, 540 / 7776, 651 / 7776, 735 / 7776, 780 / 7776, 780 / 7776, 735 / 7776, 651 / 7776, 540 / 7776, 420 / 7776, 305 / 7776, 205 / 7776, 126 / 7776, 70 / 7776, 35 / 7776, 15 / 7776, 5 / 7776, 1 / 7776] // } let dict_interm_probability = {1: Array(int_side_dice).fill(1 / int_side_dice)}; if (int_pow == 0){ console.log("Не поддерживается"); return; } else if (int_pow != 1){ let list_to_do = map_todo(int_pow); for (let i = 0; i < list_to_do.length; i++){ dict_interm_probability[list_to_do[i][2]] = multiply_cins_orig(dict_interm_probability[list_to_do[i][0]], dict_interm_probability[list_to_do[i][1]]); } } return dict_interm_probability[int_pow]; } // Как добраться до интересующего значения, используя x2/+nx для степеней function map_todo(int_wanted){ // На примере int_wanted = 5 // Степени "числа": // 1 // 1 * 2 = 2 -> Array(1, 1, 2) // 2 * 2 = 4 -> Array(2, 2, 4) // 4 + 1 = 5 -> Array(4, 1, 5) let int_current_id = 1; let int_sum = 1; let b_ascending = true; let list_solution = new Array(); let i = 0; while (true){ if (int_sum == int_wanted){ break; } else if (b_ascending && 2 * int_current_id <= int_wanted){ list_solution[i] = [int_current_id, int_current_id, 2 * int_current_id]; // mult_1, mult_2, result i++; int_current_id = 2 * int_current_id; int_sum = int_current_id; } else if (b_ascending && 2 * int_current_id > int_wanted){ b_ascending = false; int_sum = int_current_id; int_current_id = Math.ceil(int_current_id / 2); // чтобы возвращал именно integer } else if (!b_ascending && int_sum + int_current_id <= int_wanted){ list_solution[i] = [int_sum, int_current_id, int_sum + int_current_id]; // mult_1, mult_2, result i++; int_sum = int_sum + int_current_id; int_current_id = Math.ceil(int_current_id / 2); // чтобы возвращал именно integer } else if (!b_ascending && int_sum + int_current_id > int_wanted){ int_current_id = Math.ceil(int_current_id / 2); // чтобы возвращал именно integer } } return list_solution; } // "умножение" в столбик двух массивов/списков function multiply_cins_orig(list_in_1, list_in_2){ let int_len_1 = list_in_1.length; let int_len_2 = list_in_2.length; let list_dummy = new Array(); for (let j = 0; j < int_len_2; j++){ list_dummy[j] = Array(j).fill(0); // [], [0], [0, 0], [0, 0, 0] ... } let list_for_sum = new Array(); for (let j = 0; j < int_len_2; j++){ let list_interm = new Array(); for (let i = 0; i < int_len_1; i++){ list_interm[i] = list_in_1[i] * list_in_2[j] } list_for_sum[j] = list_dummy[j].concat(list_interm, list_dummy[int_len_2 - j - 1]); } // [list_in_1 X list_in_2[0], 0, 0, 0, 0, 0] // [0, list_in_1 X list_in_2[1], 0, 0, 0, 0] // [0, 0, list_in_1 X list_in_2[2], 0, 0, 0] // [0, 0, 0, list_in_1 X list_in_2[3], 0, 0] // [0, 0, 0, 0, list_in_1 X list_in_2[4], 0] // [0, 0, 0, 0, 0, list_in_1 X list_in_2[5]] let list_out = new Array(); for (let i = 0; i < list_for_sum[0].length; i++){ let sum_out = 0; for (let j = 0; j < int_len_2; j++){ sum_out += list_for_sum[j][i]; } list_out[i] = sum_out; } // [1 / 216, 3 / 216, 6 / 216, 10 / 216, 15 / 216, 21 / 216, 25 / 216, 27 / 216, 27 / 216, 25 / 216, 21 / 216, 15 / 216, 10 / 216, 6 / 216, 3 / 216, 1 / 216] return list_out; } main();VBS
Option Explicit Sub main() Const c_int_side_dice = 6 'сколько граней у кубика Const c_int_dice_number = 1000 'кол-во кубиков Const c_int_number_to_find = 2000 'число, вероятность выпадения которого хотим найти Dim probability probability = dice_probability(c_int_dice_number, c_int_number_to_find, c_int_side_dice) MsgBox probability End Sub ' собственно поиск вероятности определённого значения Function dice_probability(int_dice_number, int_number_to_find, c_int_side_dice) If int_number_to_find >= int_dice_number And int_number_to_find <= c_int_side_dice * int_dice_number Then ReDim list_values(int_dice_number * (c_int_side_dice - 1)) Dim i, j i = 0 For j = int_dice_number To c_int_side_dice * int_dice_number list_values(i) = j i = i + 1 Next Dim list_probability() get_probabilities c_int_side_dice, int_dice_number, list_probability For i = 0 To int_dice_number * (c_int_side_dice - 1) If list_values(i) = int_number_to_find Then Exit For End If Next dice_probability = list_probability(i) Else 'задаваемое число выходит за рамки реально возможного диапазона значений dice_probability = 0.0 End If End Function 'возвращает список/массив: вероятности выадения Sub get_probabilities(int_side_dice, int_pow, list_out) 'На примере int_side_dice = 6, int_pow = 5 '{ ' 1: [1 / 6, 1 / 6, 1 / 6, 1 / 6, 1 / 6, 1 / 6], ' 2: [1 / 36, 2 / 36, 3 / 36, 4 / 36, 5 / 36, 6 / 36, 5 / 36, 4 / 36, 3 / 36, 2 / 36, 1 / 36], ' 4: [1 / 1296, 4 / 1296, 10 / 1296, 20 / 1296, 35 / 1296, 56 / 1296, 80 / 1296, 104 / 1296, 125 / 1296, 140 / 1296, 146 / 1296, 140 / 1296, 125 / 1296, 104 / 1296, 80 / 1296, 56 / 1296, 35 / 1296, 20 / 1296, 10 / 1296, 4 / 1296, 1 / 1296] ' 5: [1 / 7776, 5 / 7776, 15 / 7776, 35 / 7776, 70 / 7776, 126 / 7776, 205 / 7776, 305 / 7776, 420 / 7776, 540 / 7776, 651 / 7776, 735 / 7776, 780 / 7776, 780 / 7776, 735 / 7776, 651 / 7776, 540 / 7776, 420 / 7776, 305 / 7776, 205 / 7776, 126 / 7776, 70 / 7776, 35 / 7776, 15 / 7776, 5 / 7776, 1 / 7776] '} Dim j Dim list_probability() ReDim list_probability(int_side_dice - 1) For j = 0 To int_side_dice - 1 list_probability(j) = 1 / int_side_dice Next Dim dict_interm_probability Set dict_interm_probability = CreateObject("Scripting.Dictionary") dict_interm_probability.Add 1, list_probability If int_pow = 0 Then MsgBox "Не поддерживается" Quit ElseIf int_pow <> 1 Then Dim list_to_do() map_todo list_to_do, int_pow For j = 0 To UBound(list_to_do, 2) 'MsgBox list_to_do(0, j) & vbTab & list_to_do(1, j) & vbTab & list_to_do(2, j) multiply_cins_orig _ dict_interm_probability.Item(list_to_do(0, j)), _ dict_interm_probability.Item(list_to_do(1, j)), _ list_out dict_interm_probability.Add list_to_do(2, j), list_out ' ArrOut_1 list_out Next End If End Sub 'Как добраться до интересующего значения, используя x2/+nx для степеней Sub map_todo(list_solution, int_wanted) 'На примере int_wanted = 5 'Степени "числа": '1 '1 * 2 = 2 -> Array(1, 1, 2) '2 * 2 = 4 -> Array(2, 2, 4) '4 + 1 = 5 -> Array(4, 1, 5) Dim int_current_id Dim int_sum Dim b_ascending Dim i int_current_id = 1 int_sum = 1 b_ascending = True i = -1 Do If b_ascending And 2 * int_current_id <= int_wanted Then i = i + 1 ReDim Preserve list_solution(2, i) list_solution(0, i) = int_current_id list_solution(1, i) = int_current_id list_solution(2, i) = 2 * int_current_id int_current_id = 2 * int_current_id int_sum = int_current_id ElseIf b_ascending And 2 * int_current_id > int_wanted Then b_ascending = False int_sum = int_current_id int_current_id = CInt(int_current_id / 2) 'чтобы возвращал именно integer ElseIf Not b_ascending And int_sum + int_current_id <= int_wanted Then i = i + 1 ReDim Preserve list_solution(2, i) list_solution(0, i) = int_sum list_solution(1, i) = int_current_id list_solution(2, i) = int_sum + int_current_id int_sum = int_sum + int_current_id int_current_id = CInt(int_current_id / 2) 'чтобы возвращал именно integer ElseIf Not b_ascending And int_sum + int_current_id > int_wanted Then int_current_id = CInt(int_current_id / 2) 'чтобы возвращал именно integer End If Loop Until (int_sum = int_wanted) End Sub ' "умножение" в столбик двух массивов/списков Sub multiply_cins_orig(list_in_1, list_in_2, list_in) Dim int_len_1 Dim int_len_2 int_len_1 = Ubound(list_in_1, 1) int_len_2 = Ubound(list_in_2, 1) Dim list_for_sum() ReDim list_for_sum(int_len_2, int_len_1 + int_len_2) Dim i, j, k, n For i = 0 To int_len_2 j = 0 For n = 0 To int_len_2 If i = n Then For k = 0 To int_len_1 list_for_sum(i, j) = list_in_1(k) * list_in_2(n) j = j + 1 Next Else list_for_sum(i, j) = 0 j = j + 1 End If Next Next '[list_in_1 X list_in_2[0], 0, 0, 0, 0, 0] '[0, list_in_1 X list_in_2[1], 0, 0, 0, 0] '[0, 0, list_in_1 X list_in_2[2], 0, 0, 0] '[0, 0, 0, list_in_1 X list_in_2[3], 0, 0] '[0, 0, 0, 0, list_in_1 X list_in_2[4], 0] '[0, 0, 0, 0, 0, list_in_1 X list_in_2[5]] 'ArrOut_2 list_for_sum Erase list_in ReDim list_in(int_len_1 + int_len_2) Dim sum_out For j = 0 To int_len_1 + int_len_2 sum_out = 0 For i = 0 To int_len_2 sum_out = sum_out + list_for_sum(i, j) Next list_in(j) = sum_out Next ' [1 / 216, 3 / 216, 6 / 216, 10 / 216, 15 / 216, 21 / 216, 25 / 216, 27 / 216, 27 / 216, 25 / 216, 21 / 216, 15 / 216, 10 / 216, 6 / 216, 3 / 216, 1 / 216] 'ArrOut_1 list_in End Sub '================================================== '<Additional_MsgBox_For_Arrays> Sub ArrOut_1(arr_in) Dim str_out Dim i For i = 0 To UBound(arr_in) If i = 0 Then str_out = arr_in(i) Else str_out = str_out & " " & arr_in(i) End If Next MsgBox str_out End Sub Sub ArrOut_2(arr_in) Dim str_out Dim i, j For i = 0 To UBound(arr_in, 1) For j = 0 To UBound(arr_in, 2) If i = 0 And j = 0 Then str_out = arr_in(i, j) ElseIf j = 0 Then str_out = str_out & vbNewLine & arr_in(i, j) Else str_out = str_out & " " & arr_in(i, j) End If Next Next MsgBox str_out End Sub '</Additional_MsgBox_For_Arrays> '================================================== mainПару слов о проверке
Проверку и перепроверку чьих бы то ни было слов всегда приветствую.
Однако, отмечу, что на текущий момент кроме как эмпирического (т.е. обычного сравнения результата работы описанного в текущей статье алгоритма с работой алгоритма в предыдущей статье или обычного расчёта “в лоб”) метода проверки я не располагаю каким-либо иным доказательством своей правоты, которое бы сочетало как доступность восприятия так и наглядность.
Следовательно:
Если Вы достаточно доверяете предыдущей статье — то можно сверять результат работы алгоритма в текущей статье с алгоритмом, описанным в предыдущей статье.
Если не доверяете предыдущей статье, тогда могу предложить следующее: генератор SQL запросов, считающих в лоб кубики, суммы их выпадений и их вероятности.
Python для проверок в лоб
# -*- coding: utf-8 -*- import sqlite3 import re def main() -> None: c_int_side_dice: int = 6 # сколько граней у кубика c_int_dice_number: int = 6 # кол-во кубиков str_query = select_values_and_interm_probabilities(c_int_side_dice, c_int_dice_number) if True: # Просмотр SQL кода print(str_query) else: # Прогон SQL запроса conn = sqlite3.connect(":memory:") cursor = conn.cursor() cursor.execute(str_query) return_select(cursor) cursor.close() conn.close() def select_values_and_interm_probabilities(int_side_dice: int, int_dice_number: int) -> str: str_sub_query_1: str = """ -- заводим значения сторон кубика WITH RECURSIVE step_01_insert (dice) AS ( SELECT 1 AS dice UNION ALL SELECT dice + 1 AS dice FROM step_01_insert WHERE dice < {} -- сколько граней у кубика ) """.format(int_side_dice) list_sub_query_1: list[str] = [] list_sub_query_2: list[str] = [] list_sub_query_3: list[str] = [] for i in range(int_dice_number): list_sub_query_1.append("T{}.dice AS dice_{}".format(i, i)) list_sub_query_2.append("T{}.dice".format(i)) list_sub_query_3.append("step_01_insert AS T{}".format(i)) str_sub_query_2: str = "\n".join([ "-- генерируем все возможные ситуации для {}-х кубиков".format(int_dice_number), ", step_02_spawn AS (", "SELECT", "\n, ".join(list_sub_query_1), ", " + " + ".join(list_sub_query_2) + " AS dice_sum -- Значения (сумма выпавших костей)", "FROM", "\n, ".join(list_sub_query_3), ")" ]) del list_sub_query_1, list_sub_query_2, list_sub_query_3 str_sub_query_3: str = """ -- считаем в лоб, сколько раз встречается значение , step_03_dividend (dice_sum, dividend) AS ( SELECT dice_sum -- Значения (сумма выпавших костей) , COUNT(1) AS dividend -- Сколько раз встречается значение FROM step_02_spawn GROUP BY dice_sum ) , step_04_divisor(divisor) AS ( SELECT SUM(dividend) AS divisor FROM step_03_dividend ) SELECT T1.dice_sum -- Значения (сумма выпавших костей) , T1.dividend -- Сколько раз встречается значение , CAST(T1.dividend AS REAL) / CAST(T2.divisor AS REAL) AS probability -- Вероятность FROM step_03_dividend AS T1 , step_04_divisor AS T2 ORDER BY T1.dice_sum; """ return lazy_prety_print(str_sub_query_1 + str_sub_query_2 + str_sub_query_3) def lazy_prety_print(str_in: str) -> str: list_line: list[str] = [] str_offset: str = "" for str_line_1 in str_in.split("\n"): str_line_2 = re.sub(r"^\s+", "", str_line_1) if len(str_line_2) > 0 and str_line_2[0] == ")": str_offset = str_offset[:-4] list_line.append(str_offset + str_line_2) if len(str_line_2) > 0 and str_line_2[-1] == "(": str_offset = str_offset + " " return "\n".join(list_line) def return_select(cursor: sqlite3.Cursor) -> None: column_list = [] for column in cursor.description: column_list.append(column[0]) print("\t".join(column_list)) rows = cursor.fetchall() for row in rows: column_list = [] for row_column in row: column_list.append(str(row_column)) print("\t".join(column_list)) if __name__ == "__main__": main() Результаты работы данного скрипта приведены ниже:
SQL для 3-х кубиков
-- заводим значения сторон кубика WITH RECURSIVE step_01_insert (dice) AS ( SELECT 1 AS dice UNION ALL SELECT dice + 1 AS dice FROM step_01_insert WHERE dice < 6 -- сколько граней у кубика ) -- генерируем все возможные ситуации для 3-х кубиков , step_02_spawn AS ( SELECT T0.dice AS dice_0 , T1.dice AS dice_1 , T2.dice AS dice_2 , T0.dice + T1.dice + T2.dice AS dice_sum -- Значения (сумма выпавших костей) FROM step_01_insert AS T0 , step_01_insert AS T1 , step_01_insert AS T2 ) -- считаем в лоб, сколько раз встречается значение , step_03_dividend (dice_sum, dividend) AS ( SELECT dice_sum -- Значения (сумма выпавших костей) , COUNT(1) AS dividend -- Сколько раз встречается значение FROM step_02_spawn GROUP BY dice_sum ) , step_04_divisor(divisor) AS ( SELECT SUM(dividend) AS divisor FROM step_03_dividend ) SELECT T1.dice_sum -- Значения (сумма выпавших костей) , T1.dividend -- Сколько раз встречается значение , CAST(T1.dividend AS REAL) / CAST(T2.divisor AS REAL) AS probability -- Вероятность FROM step_03_dividend AS T1 , step_04_divisor AS T2 ORDER BY T1.dice_sum;|
dice_sum |
dividend |
probability |
|
3 |
1 |
0.004629629629629629 |
|
4 |
3 |
0.013888888888888888 |
|
5 |
6 |
0.027777777777777776 |
|
6 |
10 |
0.046296296296296294 |
|
7 |
15 |
0.06944444444444445 |
|
8 |
21 |
0.09722222222222222 |
|
9 |
25 |
0.11574074074074074 |
|
10 |
27 |
0.125 |
|
11 |
27 |
0.125 |
|
12 |
25 |
0.11574074074074074 |
|
13 |
21 |
0.09722222222222222 |
|
14 |
15 |
0.06944444444444445 |
|
15 |
10 |
0.046296296296296294 |
|
16 |
6 |
0.027777777777777776 |
|
17 |
3 |
0.013888888888888888 |
|
18 |
1 |
0.004629629629629629 |
SQL для 4-х кубиков
-- заводим значения сторон кубика WITH RECURSIVE step_01_insert (dice) AS ( SELECT 1 AS dice UNION ALL SELECT dice + 1 AS dice FROM step_01_insert WHERE dice < 6 -- сколько граней у кубика ) -- генерируем все возможные ситуации для 4-х кубиков , step_02_spawn AS ( SELECT T0.dice AS dice_0 , T1.dice AS dice_1 , T2.dice AS dice_2 , T3.dice AS dice_3 , T0.dice + T1.dice + T2.dice + T3.dice AS dice_sum -- Значения (сумма выпавших костей) FROM step_01_insert AS T0 , step_01_insert AS T1 , step_01_insert AS T2 , step_01_insert AS T3 ) -- считаем в лоб, сколько раз встречается значение , step_03_dividend (dice_sum, dividend) AS ( SELECT dice_sum -- Значения (сумма выпавших костей) , COUNT(1) AS dividend -- Сколько раз встречается значение FROM step_02_spawn GROUP BY dice_sum ) , step_04_divisor(divisor) AS ( SELECT SUM(dividend) AS divisor FROM step_03_dividend ) SELECT T1.dice_sum -- Значения (сумма выпавших костей) , T1.dividend -- Сколько раз встречается значение , CAST(T1.dividend AS REAL) / CAST(T2.divisor AS REAL) AS probability -- Вероятность FROM step_03_dividend AS T1 , step_04_divisor AS T2 ORDER BY T1.dice_sum;|
dice_sum |
dividend |
probability |
|
4 |
1 |
0.0007716049382716049 |
|
5 |
4 |
0.0030864197530864196 |
|
6 |
10 |
0.007716049382716049 |
|
7 |
20 |
0.015432098765432098 |
|
8 |
35 |
0.02700617283950617 |
|
9 |
56 |
0.043209876543209874 |
|
10 |
80 |
0.06172839506172839 |
|
11 |
104 |
0.08024691358024691 |
|
12 |
125 |
0.09645061728395062 |
|
13 |
140 |
0.10802469135802469 |
|
14 |
146 |
0.11265432098765432 |
|
15 |
140 |
0.10802469135802469 |
|
16 |
125 |
0.09645061728395062 |
|
17 |
104 |
0.08024691358024691 |
|
18 |
80 |
0.06172839506172839 |
|
19 |
56 |
0.043209876543209874 |
|
20 |
35 |
0.02700617283950617 |
|
21 |
20 |
0.015432098765432098 |
|
22 |
10 |
0.007716049382716049 |
|
23 |
4 |
0.0030864197530864196 |
|
24 |
1 |
0.0007716049382716049 |
SQL для 5-х кубиков
-- заводим значения сторон кубика WITH RECURSIVE step_01_insert (dice) AS ( SELECT 1 AS dice UNION ALL SELECT dice + 1 AS dice FROM step_01_insert WHERE dice < 6 -- сколько граней у кубика ) -- генерируем все возможные ситуации для 5-х кубиков , step_02_spawn AS ( SELECT T0.dice AS dice_0 , T1.dice AS dice_1 , T2.dice AS dice_2 , T3.dice AS dice_3 , T4.dice AS dice_4 , T0.dice + T1.dice + T2.dice + T3.dice + T4.dice AS dice_sum -- Значения (сумма выпавших костей) FROM step_01_insert AS T0 , step_01_insert AS T1 , step_01_insert AS T2 , step_01_insert AS T3 , step_01_insert AS T4 ) -- считаем в лоб, сколько раз встречается значение , step_03_dividend (dice_sum, dividend) AS ( SELECT dice_sum -- Значения (сумма выпавших костей) , COUNT(1) AS dividend -- Сколько раз встречается значение FROM step_02_spawn GROUP BY dice_sum ) , step_04_divisor(divisor) AS ( SELECT SUM(dividend) AS divisor FROM step_03_dividend ) SELECT T1.dice_sum -- Значения (сумма выпавших костей) , T1.dividend -- Сколько раз встречается значение , CAST(T1.dividend AS REAL) / CAST(T2.divisor AS REAL) AS probability -- Вероятность FROM step_03_dividend AS T1 , step_04_divisor AS T2 ORDER BY T1.dice_sum;|
dice_sum |
dividend |
probability |
|
5 |
1 |
0.0001286008230452675 |
|
6 |
5 |
0.0006430041152263374 |
|
7 |
15 |
0.0019290123456790122 |
|
8 |
35 |
0.0045010288065843625 |
|
9 |
70 |
0.009002057613168725 |
|
10 |
126 |
0.016203703703703703 |
|
11 |
205 |
0.026363168724279837 |
|
12 |
305 |
0.03922325102880658 |
|
13 |
420 |
0.05401234567901234 |
|
14 |
540 |
0.06944444444444445 |
|
15 |
651 |
0.08371913580246913 |
|
16 |
735 |
0.09452160493827161 |
|
17 |
780 |
0.10030864197530864 |
|
18 |
780 |
0.10030864197530864 |
|
19 |
735 |
0.09452160493827161 |
|
20 |
651 |
0.08371913580246913 |
|
21 |
540 |
0.06944444444444445 |
|
22 |
420 |
0.05401234567901234 |
|
23 |
305 |
0.03922325102880658 |
|
24 |
205 |
0.026363168724279837 |
|
25 |
126 |
0.016203703703703703 |
|
26 |
70 |
0.009002057613168725 |
|
27 |
35 |
0.0045010288065843625 |
|
28 |
15 |
0.0019290123456790122 |
|
29 |
5 |
0.0006430041152263374 |
|
30 |
1 |
0.0001286008230452675 |
SQL для 6-х кубиков
-- заводим значения сторон кубика WITH RECURSIVE step_01_insert (dice) AS ( SELECT 1 AS dice UNION ALL SELECT dice + 1 AS dice FROM step_01_insert WHERE dice < 6 -- сколько граней у кубика ) -- генерируем все возможные ситуации для 6-х кубиков , step_02_spawn AS ( SELECT T0.dice AS dice_0 , T1.dice AS dice_1 , T2.dice AS dice_2 , T3.dice AS dice_3 , T4.dice AS dice_4 , T5.dice AS dice_5 , T0.dice + T1.dice + T2.dice + T3.dice + T4.dice + T5.dice AS dice_sum -- Значения (сумма выпавших костей) FROM step_01_insert AS T0 , step_01_insert AS T1 , step_01_insert AS T2 , step_01_insert AS T3 , step_01_insert AS T4 , step_01_insert AS T5 ) -- считаем в лоб, сколько раз встречается значение , step_03_dividend (dice_sum, dividend) AS ( SELECT dice_sum -- Значения (сумма выпавших костей) , COUNT(1) AS dividend -- Сколько раз встречается значение FROM step_02_spawn GROUP BY dice_sum ) , step_04_divisor(divisor) AS ( SELECT SUM(dividend) AS divisor FROM step_03_dividend ) SELECT T1.dice_sum -- Значения (сумма выпавших костей) , T1.dividend -- Сколько раз встречается значение , CAST(T1.dividend AS REAL) / CAST(T2.divisor AS REAL) AS probability -- Вероятность FROM step_03_dividend AS T1 , step_04_divisor AS T2 ORDER BY T1.dice_sum;|
dice_sum |
dividend |
probability |
|
6 |
1 |
2.143347050754458e-05 |
|
7 |
6 |
0.0001286008230452675 |
|
8 |
21 |
0.0004501028806584362 |
|
9 |
56 |
0.0012002743484224967 |
|
10 |
126 |
0.002700617283950617 |
|
11 |
252 |
0.005401234567901234 |
|
12 |
456 |
0.00977366255144033 |
|
13 |
756 |
0.016203703703703703 |
|
14 |
1161 |
0.02488425925925926 |
|
15 |
1666 |
0.03570816186556927 |
|
16 |
2247 |
0.048161008230452676 |
|
17 |
2856 |
0.061213991769547324 |
|
18 |
3431 |
0.07353823731138547 |
|
19 |
3906 |
0.08371913580246913 |
|
20 |
4221 |
0.09047067901234568 |
|
21 |
4332 |
0.09284979423868313 |
|
22 |
4221 |
0.09047067901234568 |
|
23 |
3906 |
0.08371913580246913 |
|
24 |
3431 |
0.07353823731138547 |
|
25 |
2856 |
0.061213991769547324 |
|
26 |
2247 |
0.048161008230452676 |
|
27 |
1666 |
0.03570816186556927 |
|
28 |
1161 |
0.02488425925925926 |
|
29 |
756 |
0.016203703703703703 |
|
30 |
456 |
0.00977366255144033 |
|
31 |
252 |
0.005401234567901234 |
|
32 |
126 |
0.002700617283950617 |
|
33 |
56 |
0.0012002743484224967 |
|
34 |
21 |
0.0004501028806584362 |
|
35 |
6 |
0.0001286008230452675 |
|
36 |
1 |
2.143347050754458e-05 |
Выводы
В данной статье мы познакомились:
— с операцией свёртка последовательностей
— как при помощи свёртки последовательностей считать вероятности выпадения кубиков
— как посчитать вероятности выпадения найти вероятность выпадения числа k, а именно суммы всех значений, выпавших для 1000 кубиков.
ссылка на оригинал статьи https://habr.com/ru/post/685552/