apollonin Jun 13 2014 at 13:07

Разделить число на заданное количество кубиков

1 min

6.2K

Algorithms*

-35

Comments 39

Nomad1 Jun 13 2014 at 13:30

Как и множество примитивных задач, эту стоит решать «в лоб», а остальное время потратить на что-то полезное и уж точно не на такую «статью» на хабре.
К примеру, такой же подходящий вариант, как и все остальные: для каждого кубика мы считаем границу max = n / count и min = n / (d * count), где d — максимальный размер дайса, n — число, count — оставшиеся кубики. Затем выбрасываем рандомное число от min до max, но не больше d, сохраняем его, уменьшаем n на выпавшее значение и считаем следующий кубик. Когда дошли до самого конца у нас может получиться некая ошибка, которую распределяем по имеющимся значениям любым разумным методом, хоть в рандомном порядке.

P.S. Судя по вашему коду там принцип схожий, только цикл считается не до конца и остаток пишется в последний слот. Это не верно, потому что в случае с 18 может рандом выдать 1,1,1,15.

apollonin Jun 13 2014 at 13:34

Первый вариант, коотрый мне в голову пришёл как раз и заключался в том, чтобы делать так, как вы говорите и потом погрешность «раскидывать» по существующим кубикам. Но из-за этого разбрасывания алгоритм становится менее эффективным, т.к. повышается его сложность.

p.s. у меня ситуации 1,1,1,15 не будет, потому что есть условие

if ($diff > 0)
    $dices[$j] = rand($diff, 6);

Соответственно на втором кубике рэндом будет не от 1 до 6, а от 5 до 6, чтобы в итоге в конце выйти в 0 без погрешности.

Nomad1 Jun 13 2014 at 13:40

Проблема в том, что за время, потраченное мней и вами на этот посте, можно было набросать два десятка разных алгоритмов. Они все будут примерно одинаково эффективными и все будут считаться меньше 0.01мс на современной технике. Более сложные варианты есть смысл городить только если у нас огромные числа или надо добиться чего-то иного, например, использовать не больше 3х единиц и пр.

apollonin Jun 13 2014 at 13:56

ну так всегда можно пройти мимо, если не считаете данную тему достойной

general Jun 13 2014 at 13:38

Вариантов уйма.
Вариант 1
Получить жадным алгоритмом самый примитивный набор, затем случайным образом «поперекидывать» значения между кубиками. Т.е. сначала пробуем в лоб сгененировать набор 6,6,6,...,1,1,1. Для 19 и 4 у нас будет 6,6,6,1. Для 18 и 4 — 6,6,5,1
Затем случайно можно выбрать два значения и перекинуть 1 с одного на 2. И так N раз

Вариант 2
Построить динамическим программированием все возможные варианты и случайнм образом выбирать один из них.

Вариант 3
Рекурсивно разбить задачу на две подзадачи — случайным образом выбирать сколько кубиков будет в каждой подзадаче и какое число ими надо набрать. Что-то типа такого:

function splitDices($number, $dicesCount)
{
 $x = rand(1, $number);
 $x = rand(1, $dicesCount);
return  splitDices($x, $y)  +  splitDices($number-$x, $dicesCount-$y);
}

anton1234 Jun 13 2014 at 13:43

сделать рандом(6) заданное число раз
сравнить сумму значений кубиков с заданным числом, повторять до получения заданного числа.
ЗЫ. Думал тут будет интересная задачка, НО НЕТ(

apollonin Jun 13 2014 at 13:44

думал будет интереснее решение, НО НЕТ(

anton1234 Jun 13 2014 at 14:09

Мое решение соответствует условиям задачи. Коротко и лаконично я считаю.
Зачем вы кстати используете кубики? В этом есть какой-то сакральный смысл? Количество граней никак в задаче не фигурирует.

mayorovp Jun 13 2014 at 14:35

Ваше решение может работать слишком долго, особенно в граничных случаях.
Так, чтобы «разложить» 6 на 6 кубиков, понадобится в среднем 6⁶ попыток.

anton1234 Jun 13 2014 at 14:40

В этом и смысл моего решения. Условия задачи не определяют критериев по которым можно оценить качество решения.
Когда я был маленьким, я сильно расстраивался из-за того, что мои программы выполняются мгновенно. Я хотел видеть как компьютер думает, как бежит прогресс бар…
Зато тут можно вести любопытную статистику, считать с какого раза компьютеру удалось подобрать комбинацию!

mayorovp Jun 13 2014 at 14:41

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

anton1234 Jun 13 2014 at 14:50

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

sustenuto Jun 13 2014 at 13:47

Смысл писать просто «случайным образом»? Задача будет иметь смысл если задать распределение. Например, равномерное. А в вашем алгоритме оно не равномерное отнюдь.

Пример: число 4, кубиков: 3.
вероятность варианта 2 1 1 равна сумме вероятностей вариантов 1 2 1 и 1 1 2

Кроме того, ваш алгоритм падает при кол-ве кубиков <= 1.

apollonin Jun 13 2014 at 13:49

нет, не падает, а кидает исключение

sustenuto Jun 13 2014 at 13:52

Я не знаю, на каком языке у вас алгоритм (у вас ни в одном месте этого не сказано), так что считаю, что это псевдокод. В случае $dicesCount <= 1 у вас возможно обращение по отрицательному индексу массива, предполагаю, что это скорее падение.

Arturka Jun 13 2014 at 13:56

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

Kottenator Jun 13 2014 at 14:03

А я вот взял и решил данную задачу школьного уровня :)

function PermutationMaster(sum, dices) {
  this.sum = sum;
  this.dices = dices;
  this.permutations = [];
  this.run();
}

PermutationMaster.prototype = {
  run: function(permutation, dice) {
    permutation = permutation || [];
    dice = dice || 1;
    
    for (var j = 6; j; j--) {
      permutation[dice - 1] = j;
      
      if (dice < this.dices)
         this.run(permutation, dice + 1);
      else if (permutation.reduce(function(a, b) { return a + b; }) == this.sum)
        this.permutations.push([].slice.apply(permutation));
    }
  },
  
  random: function() {
    return this.permutations[~~(Math.random() * this.permutations.length)];
  }
}

var master = new PermutationMaster(18, 4);

console.log(master.random());
console.log(master.random());
console.log(master.random());

apollonin Jun 13 2014 at 14:33

Хабр зануда.

Lissov Jun 13 2014 at 14:52

Ради разминки мозгов почему бы не подумать над такой задачей :)
Если нужно равномерное распределение, не вижу иного варианта кроме как посчитать все варианты и выбрать один случайно. При этом динамическое программирование кажется наилучшим вариантом.
Если любое распределение, то немного анализа вначале — если «кидать» кубики по очереди, то надо чтобы после каждого «броска» остаток можно было разбить на кубики — то есть должно оставаться число от (С-1) до (С-1)*6, где С — количество оставшихся бросков. Отсюда рассчитывается возможный промежуток значений для текущего «броска», из него можно выбирать значение случайно. ИМХО так будет наилучшая производительность.
Написал рекурсией, циклом будет лучше по производительности но менее читаемо :)

Итоговый алгиритм (без очевидных проверок)

public static List<int> SplitDices(int number, int dicesCount)
{
    if (dicesCount == 1)
        return new List<int> { number };

    var otherDices = dicesCount - 1;
    var min = Math.Max(1, number - 6*otherDices);
    var max = Math.Min(6, number - 1*otherDices);

    var dice = random.Next(max - min) + min;
    var other = SplitDices(number - dice, dicesCount - 1);
    other.Add(dice);

    return other;
}

vittore Jun 13 2014 at 15:45

Мне больше интересно откуда такая задача появилась? Если вы например для игры генерируете случайное число одно а потом хотите сэмитировать его на кубиках, надо от этой идеи отказаться и генерировать кубики и из них получать сумму.

youlose Jun 13 2014 at 17:21

Задача несложная, мой вариант:
0. Бросить исключение, если кубиков нехватит или слишком много
1. создасть случайные значения
2. Получить разницу суммы значений кубиков и нужного числа
3. Проходить по всем значениям кубиков по очереди и если число из п.2 положительное, то увеличивать каждое встречное на 1, иначе уменьшать на 1, если сначение больше 1го
4. Как значение из п.2 равно нулю — мы имеем ответ

могу на Ruby написать решение, если интересно

mayorovp Jun 13 2014 at 17:25

Слишком сложно, решение автора проще.

youlose Jun 13 2014 at 17:54

MAX_DICE_VAL = 6

def dices_for_num num, num_of_dices
	raise 'Too many dices' if num < num_of_dices
	raise 'Not enough dices' if num > num_of_dices * MAX_DICE_VAL

	dices = []
	dices_sum = 0;
	num_of_dices.times do
		dice_val = rand(1..MAX_DICE_VAL)
		dices << dice_val
		dices_sum += dice_val
	end

	delta = num - dices_sum
	while delta != 0 do
		dices.each_with_index do |val, index|
			if delta > 0 and val < MAX_DICE_VAL
				dices[index] += 1
				delta -= 1
			elsif delta < 0 and val > 1
				dices[index] -= 1
				delta += 1
			end
		end
	end

	dices
end

puts dices_for_num(16,4).inspect

Там цикл, 3 условия (одно сложное) и 2 места где случайные значения генеряцца, чем же это проще одного цикла двух логичных условий и вычитаний и прибавлений единиц?

mayorovp Jun 13 2014 at 17:59

Вообще-то у вас три цикла, притом еще и два из них — вложенные. А авторские условия легко упрощаются, если чуть подумать.

youlose Jun 13 2014 at 18:05

ок, генерацию упростим:

  dices = num_of_dices.times.map { rand 1..MAX_DICE_VAL }
  delta = num - dices.inject(:+)

(вместо второго абзаца)

осталось два цикла, оба простые

youlose Jun 13 2014 at 18:38

Правильно заминусовали, 1 цикл заменил на 3 в генерации при помощи «сахара».

mayorovp Jun 13 2014 at 18:17

Ruby я не знаю, но попробую написать на нем решение автора. Для сравнения.

MIN_DICE_VAL = 1
MAX_DICE_VAL = 6

def dices_for_num num, num_of_dices
    raise 'Too many dices' if num < num_of_dices * MIN_DICE_VAL
    raise 'Not enough dices' if num > num_of_dices * MAX_DICE_VAL

    dices = []

    for i in (0...num_of_dices).reverse do
        lower_bound = [MIN_DICE_VAL, num - i * MAX_DICE_VAL].max
        upper_bound = [num - i * MIN_DICE_VAL, MAX_DICE_VAL].min
        dice_val = rand(lower_bound .. upper_bound)
        dices << dice_val
        num -= dice_val
    end

    dices
end

youlose Jun 13 2014 at 18:26

у вас лучше чем у автора получилось и лаконичнее.

mayorovp Jun 13 2014 at 18:26

Не буду спорить. Но алгоритм у нас один и тот же.

valemak Jun 13 2014 at 18:18

Вот взяли и заминусовали человека.

А между тем пост выслал вполне конструктивное обсуждение, люди варианты предлагают )))

mayorovp Jun 13 2014 at 18:21

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

Lockal Jun 13 2014 at 20:42

Тёплый ламповый сви-пролог:

use_module(library(clpfd)).

N = 18,
sum([A, B, C, D], #=, N),
[A, B, C, D] ins 1..6,
findall([A, B, C, D], label([A, B, C, D]), List),
random_member(RandomResponse, List).

Сильно тапками не бейте, мой скилл пролога равен полутора лабам трёхлетней давности.

mayorovp Jun 14 2014 at 07:28

Как эта магия работает?!

AraneusAdoro Jun 14 2014 at 07:38

Выдаёт четвёрку чисел, удовлетворяющую условиям:
A+B+C+D = N
sum([A, B, C, D], #=, N)
1 ≤ A, B, C, D ≤ 6
[A, B, C, D] ins 1..6

Находит все такие четвёрки:
findall([A, B, C, D], label([A, B, C, D]), List)
И выбирает случайную из них:
random_member(RandomResponse, List)

mayorovp Jun 14 2014 at 07:51

Ну, начнем с того, что в классическом прологе конъюнкты разрешались последовательно. У первого, sum([A, B, C, D], #=, N), — бесконечное множество возможных решений, то есть уже на этой стадии программа зависнет. Точнее, не на этой стадии, а из-за этой стадии. Или, если предикат sum сделан по уму, вернет ошибку.

Вот второй, [A, B, C, D] ins 1..6, чем-то классический Пролог напоминает. Действительно, сложностей в переборе 6⁴ вариантов и присвоении их 4м переменным нет. Если такую строчку поменять с предыдущей, то это даже будет работать — sum сработает как фильтр.

Но вот дальше и происходит полная магия! К моменту вызова findall([A, B, C, D], label([A, B, C, D]), List) все 4 переменные, A, B, C и D — уже имеют свои фиксированные значения. Иными словами, вместо одного вызова findall с неопределенными переменными происходит столько же вызовов findall, сколько нашлось решений. findall как-то умудряется их аккамулировать — и записать в список List. Но главное, получая управление кучу раз, findall вызвращает его всего 1 раз! КАК?!

AraneusAdoro Jun 14 2014 at 08:13

У первого, sum([A, B, C, D], #=, N), — бесконечное множество возможных решений, то есть уже на этой стадии программа зависнет.

?- sum([A,B,C,D], #=, 19).
A+B+C+D#=19.

Пролог просто не знает решения на этой стадии. Может, классический пролог и вис, не знаю.

Но вот дальше и происходит полная магия! К моменту вызова findall([A, B, C, D], label([A, B, C, D]), List) все 4 переменные, A, B, C и D — уже имеют свои фиксированные значения.

?- sum([A,B,C,D], #=, 19),
|    [A,B,C,D] ins 1..6.
A in 1..6,
A+B+C+D#=19,
B in 1..6,
C in 1..6,
D in 1..6.

Нет. На этой стадии у пролога на руках всё ещё только набор фактов.

?- sum([A,B,C,D], #=, 19),
[A,B,C,D] ins 1..6,
|    findall([A, B, C, D], label([A, B, C, D]), List).
List = [[1, 6, 6, 6], [2, 5, 6, 6], [2, 6, 5, 6], [2, 6, 6, 5], [3, 4, 6, 6], [3, 5, 5|...], [3, 5|...], [3|...], [...|...]|...],
A in 1..6,
A+B+C+D#=19,
B in 1..6,
C in 1..6,
D in 1..6.

А вот теперь есть список всех значений, подходящих под предыдущие условия.

?- sum([A,B,C,D], #=, 19), [A,B,C,D] ins 1..6, findall([A,B,C,D], label([A, B, C, D]), List), length(List, Len), random(0, Len, I), nth0(I, List, Elt).
<...>
Elt = [6, 6, 3, 4],
<...>

?- sum([A,B,C,D], #=, 19), [A,B,C,D] ins 1..6, findall([A,B,C,D], label([A, B, C, D]), List), length(List, Len), random(0, Len, I), nth0(I, List, Elt).
<...>
Elt = [5, 6, 2, 6],
<...>

?- sum([A,B,C,D], #=, 19), [A,B,C,D] ins 1..6, findall([A,B,C,D], label([A, B, C, D]), List), length(List, Len), random(0, Len, I), nth0(I, List, Elt).
<...>
Elt = [6, 6, 1, 6],
<...>

mayorovp Jun 14 2014 at 08:25

Ну и ну. Нас-то учили, что алгоритм перебора с возвратом — неотъемлемая часть языка. А тут ее взяли и выкинули… Как же теперь GUI на Прологе писать?)

Lockal Jun 14 2014 at 10:31

Действительно, сложностей в переборе 6^4 вариантов и присвоении их 4м переменным нет.

Пролог не перебирает все варианты. Если вы запустите N = 18, sum([A, B, C, D], #=, N), [A, B, C, D] ins 0..sup., (sup = +бесконечность), то пролог сократит домены решений до 0..18:

A in 0..18,
B in 0..18,
C in 0..18,
D in 0..18.

Если же мы возьмём N = 5 и кубик 1..6, то пролог сократит домены до:

A in 1..2,
B in 1..2,
C in 1..2,
D in 1..2.

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

?- N = 5, sum([A, B, C, D], #=, N), [A, B, C, D] ins 1..6, findall([A, B, C, D], indomain(A), List).
N = 5,
List = [[1, _G419, _G422, _G425], [2, 1, 1, 1]],
A in 1..2,
A+B+C+D#=5,
B in 1..2,
C in 1..2,
D in 1..2,
_G419 in 1..2,
1+_G419+_G422+_G425#=5,
_G422 in 1..2,
_G425 in 1..2.

Таким образом, пролог нашёл одно решение [2, 1, 1, 1] и установил новые ограничения для _G419, _G422, _G425.

mayorovp Jun 14 2014 at 10:49

Пролог не перебирает все варианты.

Тот вариант Пролога, который я знал, именно и делал, что перебирал все варианты. Причем делал это в строго определенной последовательности — на этом строились все реализации, скажем, взаимодействия с пользователем.

Рад за современный Пролог.