how can i find all possible combination of a decision tree?

1 次查看(过去 30 天)
hello all ,
for a project that i am doing
a team can score 1 goal or 2 goal per move , if someone told me that the end score between 2 teams was for example was 2:2
i need to find out all possible ways to reach that score
in this case its :
so in this case the answer is 60
but if someone told me that the end score was 3:2 or 8:8 how can i find out the number of possible ways to reach that score?
Thanks joe
  1 个评论
jgg
jgg 2015-12-4
I'm not sure what the answer is here, but it seems like this would be easiest if you augment the scores with a zero score, then add the rule if that last round 0 was scored, then this round zero cannot be scored, and have the teams alternate.
Then, you could just write a program to solve this recursively using a tree transit algorithm with halting criteria that stop if it reaches the desired score or encounters two sequential zero moves.
I'd bet there's a concise analytical answer, though.

请先登录,再进行评论。

回答(1 个)

arich82
arich82 2015-12-5
There's a very good chance I've made several errors here, but this might get you started:
We seek the final score of a:b.
We'll first consider the rounds when Team A scores independently from the rounds when Team B scores. (I'm assuming that only one team can score per round, and one team MUST score; the scoring team can earn one or two points [never zero].)
If Team A earned only one point in each of its scoring rounds, it would need a rounds to achieve a points. In general, it needs at most a scoring rounds, and at least ceil(a/2) scoring rounds.
Let n1 be the number of scoring rounds where Team A scores one point, and n2 the number of two-point rounds; clearly a = 1*n1 + 2*n2, with 0 <= n1 <= a, 0 <= n2 <= floor(a/2), and the total nrounds = n1 + n2.
For a given pair of n1 and n2, the number of possible ways for Team A to achieve a points is (n1 + n2)!/(n1!*n2!) (I think; please correct me if I'm wrong...). [To compute this, I thought about how to assign the values 1:nrounds to two groups: one with n1 spots, and one with n2 spots.]
To compute the above, consider the function:
function out = nways(score)
% out(:, 1) = nrounds to achieve score
% out(:, 2) = number of possible ways to achieve score in nrounds
N2 = 0:floor(score/2);
out = NaN(numel(N2), 2);
for k = 1:numel(N2) % for n1 = mod(a, 2):2:a
n2 = N2(k);
n1 = score - 2*n2;
out(k, :) = [n1 + n2, factorial(n1 + n2)/(factorial(n1) * factorial(n2))];
end
end % function nways
I haven't had time to verify the rest, but see if this code dump works. I'll try to check back on Monday.
a = 2;
b = 2;
out_a = nways(a);
out_b = nways(b);
count = 0;
for ka = 1:size(out_a, 1)
nrounds_a = out_a(ka, 1);
nways_a = out_a(ka, 2);
for kb = 1:size(out_b, 1)
nrounds_b = out_b(kb, 1);
nways_b = out_b(kb, 2);
count = count + nways_a*nways_b*factorial(nrounds_a + nrounds_b)/(factorial(nrounds_a) * factorial(nrounds_b));
end
end

类别

Help CenterFile Exchange 中查找有关 Naming Conventions 的更多信息

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by