如果只有1个骰子,那么它的点数范围是1到6,如果是2个骰予,那么可能的区间是2到12,如果是3个骰子,那么可能的区间是3到18,如果是n个骰子,那么可能的区间是n到6*n。
有了以上分析,此时假设有n个骰子,总的点数和为sum,那么在前面n-1个骰子的情况,最后一个可以有sum-1、sum-2、sum-3、sum-4、sum-5和sum-6六种情况,而最后的那个骰子有下面的情况:
(n-1,sum-1):第n个骰子扔出了1,等同n-1个骰子扔出了sum-1的情况。
(n-1,sum-2):第n个骰子扔出了2,等同n-1个骰子扔出了sum-2的情况。
(n-1,sum-3):第n个骰子扔出了3,等同n-1个骰子扔出了sum-3的情况。
(n-1,sum-4):第n个骰子扔出了4,等同n-1个骰子扔出了sum-4 l拘情况。
(n-1,sum-5):第n个骰子扔出了5,等同n-1个骰子扔出了sum-5的情况。
(n-1,sum-6):第n个骰予扔出了6,等同n-1个骰子扔出了sum-6的情况。
那么n个骰子扔出了sum的情况等于上面六种情况相加:
n=1时:f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1
n=2时:
f(2,2)=f(1,1)=1
f(2,3)=f(1,2)+f(1,1)=2
...
f(2,6)=f(1,5)+f(1,4)+f(1,3)+f(1,2)+f(1,1)
f(2,7)=f(1,6)+f(1,5)+f(1,4)+f(1,3)+f(1,2)+f(1,1)=6
总数
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
1个
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
2个
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
5
|
4
|
3
|
2
|
1
|
根据上面的解析,可以看出本题就是一个简单的动态规划问题,在代码编写的时候注意一下边界即可。
有了以上思路,实现代码如下所示:
public class Test
{
public static Dictionary<int, double>DicesSum(int n)
{
//初始化一个二维表格
int[,]dp=new int[n+1,n*6+1];
dp[1,1]=1;
dp[1,2]=1;
dp[1,3]=1;
dp[1,4]=1;
dp[1,5]=1;
dp[1,6]=1;
for(int i=2;i<=n;i++)
{
for(int j=i;j<=i*6;j++)
{
int x1=0,x2=0,x3=0,x4=0,x5=0,x6=0;
if(j-1>0)
{
x1=dp[i-1,j-1];
}
if(j-2>0)
{
x2=dp[i-1,j-2];
}
if(j-3>0)
{
x3=dp[i-1,j-3];
}
if(j-4>0)
{
x4=dp[i-1,j-4];
}
if(j-5>0)
{
x5=dp[i-1,j-5];
}
if(j-6>0)
{
x6=dp[i-1,j-6];
}
dp[i,j]=x1+x2+x3+x4+x5+x6;
}
}
var dict=new Dictionary<int, double>();
for(int i=n;i<=6*n;i++)
{
dict.Add(i, dp[n,i]/Math.Pow(6, n));
}
return dict;
}
public static void Main(String[] args)
{
var dict=DicesSum(3);
foreach(var item in dict)
{
Console.WriteLine("["+item.Key+","+item.Value+"],");
}
Console.Read();
}
}
程序运行结果
[1,0.1667],[2,0.1667],[3,0.1667],[4,0.1667],[5,0.1667],[6,0.1667]
算法性能分析:
此题采用了动态规划算法,申请了一个2维数组所以空间复杂度为O(n
2),采用了双重循环所以时间复杂度为O(n
2)。