//从0到n有n+1个格子//对于格子i，，掷一次骰子的数为x，那么可以从位置i到位置i+x//格子之间有连线，如果格子a和b有连线，那么从a到b不用掷骰子//求从0到n的骰子掷的次数的期望//dp[i] = 1/6*segma(dp[k]) + 1 (i<=k<=i+6)#include<cstdio>#include<iostream>#include<cstring>using namespace std ;const int maxn = 100000 ;double dp[maxn] ;int line[maxn] ;int main(){ int n , m ; while(scanf("%d%d" , &n ,&m) && n+m) { memset(line , -1 , sizeof(line)) ; memset(dp , 0 ,sizeof(dp)) ; int a , b ; for(int i = 1;i <= m ;i++) { scanf("%d%d" ,&a , &b) ; line[a] = b ; } for(int i = n-1 ;i >= 0 ;i–) { if(line[i] != -1){dp[i] = dp[line[i]] ;continue;} for(int k = i + 1;k <= i+6 ;k++) dp[i] += ((double)1/(double)6)*dp[k]; dp[i] += 1 ; } printf("%.4lf\n" , dp[0]) ; } return 0 ;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
追寻爱情，然后发现，爱，从来就是一件千回百转的事。
