apollonin13 июн 2014 в 13:07

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

1 мин

6.3K

Алгоритмы *

-36

Комментарии 39

Nomad1 13 июн 2014 в 13:30

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

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

apollonin 13 июн 2014 в 13:34

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

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

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

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

Nomad1 13 июн 2014 в 13:40

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

apollonin 13 июн 2014 в 13:56

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

general 13 июн 2014 в 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 13 июн 2014 в 13:43

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

apollonin 13 июн 2014 в 13:44

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

anton1234 13 июн 2014 в 14:09

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

mayorovp 13 июн 2014 в 14:35

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

anton1234 13 июн 2014 в 14:40

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

mayorovp 13 июн 2014 в 14:41

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

anton1234 13 июн 2014 в 14:50

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

sustenuto 13 июн 2014 в 13:47

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

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

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

apollonin 13 июн 2014 в 13:49

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

sustenuto 13 июн 2014 в 13:52

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

Arturka 13 июн 2014 в 13:56

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

Kottenator 13 июн 2014 в 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 13 июн 2014 в 14:33

Хабр зануда.

Lissov 13 июн 2014 в 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 13 июн 2014 в 15:45

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

youlose 13 июн 2014 в 17:21

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

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

mayorovp 13 июн 2014 в 17:25

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

youlose 13 июн 2014 в 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 13 июн 2014 в 17:59

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

youlose 13 июн 2014 в 18:05

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

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

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

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

youlose 13 июн 2014 в 18:38

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

mayorovp 13 июн 2014 в 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 13 июн 2014 в 18:26

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

mayorovp 13 июн 2014 в 18:26

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

valemak 13 июн 2014 в 18:18

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

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

mayorovp 13 июн 2014 в 18:21

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

Lockal 13 июн 2014 в 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 14 июн 2014 в 07:28

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

AraneusAdoro 14 июн 2014 в 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 14 июн 2014 в 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 14 июн 2014 в 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 14 июн 2014 в 08:25

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

Lockal 14 июн 2014 в 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 14 июн 2014 в 10:49

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

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

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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий