随笔-72  评论-126  文章-0  trackbacks-0
以前就见过不少求期望的题,题意很直白,但是却一直少不到思路做题
今天lcy老师推荐我看了zjut一位大牛的文章
http://bbs.zjut.com/viewthread.php?tid=1170233&extra=page%3D1
终于略知一二了,找几道概率题做做


http://acm.hdu.edu.cn/search.php?field=problem&key=2262
E(now) = (E(NEXT1) + E(NEXT2) +...+E(NEXTn))/n + 1
每个相邻点建方程,注意起点可以走到得边才能建方程,不然会导致无解
先floodfill找到起点可以走到得点,然后建方程,最后仍个高斯消元模板解把答案解出来

http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1423
同上一道一摸一样的题

http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1317
这个需要构造,相隔位子数的转换
想在相邻n,都向内飞的话n-2,都想外飞n+2,一个向左一个向右的话就保持n不变,所以有下列方程
E[n] = E[n+2]/4 + E[n-2]/4 + E[n]/2 + 1

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2619
此题极度郁闷,转移方程已经推出来了,却因为精度问题过不了
第四个sample我试了三个模板,出来的答案都不一样。。。。。
用java可过
http://acm.hdu.edu.cn/showproblem.php?pid=3058
上体升级版,变成了多串匹配,建Tire图的基础上进行转移
一样存在精度问题,用java可过

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2837
因为电梯有上有下,我索性就把楼的高度加倍  n = n * 2 - 2
那sample来说,0~10是向上的,10~20是向下的,20就是0,向上的话又变成1开始
在第7和第13层会碰到鬼(我从0层开始,所以每个量都要-1)
这样就可以得到转移方程
E[i] = E[(i+j)%n]/6 + 1
        for(i =0; i < n ; i ++) {
            
if(i == m ||  i == n-m) {
                mat[i][i] 
= 1;
            } 
else {
                mat[i][i] 
= 6;
                mat[i][n] 
= 6;
                
for(j = 1; j <= 6; j ++) {
                    mat[i][(i
+j)%n] --;
                }
            }
        }
http://acm.hdu.edu.cn/showproblem.php?pid=1204
这题很早就开始想了,现在才会做,公式如下:
a = p * (1 - q);
b = q * (1 - p);
E[n] = E[n-1] * a + E[n+1] * b + E[n] * (1 - a - b);
E[0] = 0;
E[N+M] = 1;


这两道AC的代码都超短,应该是公式题。。没上边几道那么有意思。。。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2949
http://acm.pku.edu.cn/JudgeOnline/problem?id=3682


献上第一次写的高斯消元模板
若返回时false则无解
/**************************************************
 *    mat里建好方程,增广矩阵    n*(n+1)
 *    传入方程个数
 *    答案保存在mat[i][i]中
*************************************************
*/
#include 
"stdio.h"
#include 
"string"
#define ab(a) (((a)>0)?(a):(-a))
#define maxn 100
#define eps 1e-10
double mat[maxn][maxn];
void swap(double &a,double &b) {double t = a;a = b;b = t;}
bool Gauss(int n) {
    
int i,j,row,idx;
    
double maxx,buf;
    
for(row = 0; row < n ; row ++) {
        
for(maxx = 0,i =row ; i < n ; i ++)
            
if(ab(mat[i][row]) > maxx)
                maxx 
= ab(mat[i][row]),idx = i;
        
if(maxx < eps)return false;
        
if(idx != row)    
            
for(j =0 ; j <= n ; j ++)
                swap(mat[row][j],mat[idx][j]);
        
for(i = row + 1; i < n ; i ++)
            
for(buf=mat[i][row]/mat[row][row],j = row; j <= n ; j ++)
                mat[i][j] 
-= buf * mat[row][j];
    }
    
for(i = n-1;i >= 0; i --) {
        
for(j = i +1; j < n ; j ++)
            mat[i][n] 
-= mat[i][j]*mat[j][j];
        mat[i][i] 
= mat[i][n]/mat[i][i];
    }
    
return true;
}

posted on 2009-05-19 13:48 shǎ崽 阅读(3878) 评论(10)  编辑 收藏 引用

评论:
# re: 概率题总汇 2009-08-20 14:52 | lxghost
你怎么能上zjut的啊  回复  更多评论
  
# re: 概率题总汇 2009-08-29 16:21 | ACM
E[n] = E[n-1] * a + E[n+1] * b + E[n] * (1 - a - b);
==> (a + b)E[n] - aE[n-1] - bE[n + 1] = 0;
==>为什么在建增广矩阵时是mat[i][i - 1] = -b, mat[i][i + 1] = -a,mat[i][i] = a + b; 而不是mat[i][i - 1] = -a, mat[i][i + 1] = -b, mat[i][i] = a + b;  回复  更多评论
  
# re: 概率题总汇 2009-08-29 16:25 | ACMer
2262我照你的思路建了高斯消元,不知为什么一直错了?能帮我看看吗?
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN = 20;
struct point_T {
int x, y;
};
point_T st, ed[MAXN * MAXN];
char map[MAXN][MAXN];
int board[MAXN][MAXN];
int row, col, cnt;
double mat[MAXN * MAXN][MAXN * MAXN];
int dir[4][2] = { {1, 0}, {-1, 0}, {0, -1}, {0, 1} };
bool ok(int x, int y) {
return x >= 0 && x < row && y >= 0 && y < col && (map[x][y] == '@' || map[x][y] == '.' || map[x][y] == '$');
}
void floodfill(int x, int y) {
board[x][y] = ++ cnt;
for(int i = 0; i < 4; i ++) {
int tx = x + dir[i][0];
int ty = y + dir[i][1];
if(ok(tx, ty) && board[tx][ty] == -1) {
floodfill(tx, ty);
}
}
}
bool gauss(int n) {
int i, j, row, idx;
double buf, maxx;
for(row = 0; row < n; row ++) {
for(maxx = 0, i = row; i < n; i ++) {
if(maxx < fabs(mat[i][row])) {
maxx = fabs(mat[i][row]);
idx = i;
}
}
if(maxx == 0) return false;
if(idx != row) {
for(i = row; i <= n; i ++)
swap(mat[row][i], mat[idx][i]);
}
for(i = row + 1; i < n; i ++) {
buf = mat[i][row] / mat[row][row];
for(j = row; j <= n; j ++)
mat[i][j] -= buf * mat[row][j];
}
}
for(i = n - 1; i >= 0; i --) {
for(j = i + 1; j < n; j ++)
mat[i][n] -= mat[i][j] * mat[j][j];
mat[i][i] = mat[i][n] / mat[i][i];
}
return true;
}
int main() {
int i, j, k, l, cn;
while(scanf("%d%d", &row, &col) != EOF) {
cn = 0;
for(i = 0; i < row; i ++) {
scanf("%s", map[i]);
for(j = 0; j < col; j ++) {
if(map[i][j] == '@') {
st.x = i;
st.y = j;
}else if(map[i][j] == '$') {
ed[cn].x = i;
ed[cn].y = j;
cn ++;
}
}
}
memset(board, -1, sizeof(board));
cnt = -1;
floodfill(st.x, st.y);
for(i = 0; i < cn; i ++) {
if(board[ed[i].x][ed[i].y] != -1)
break;
}
if(i == cn) {
printf("-1\n");
continue;
}
memset(mat, 0, sizeof(mat));
int now, tx, ty, num;
for(i = 0; i < row; i ++) {
for(j = 0; j < col; j ++) {
if(board[i][j] != -1) {
now = board[i][j];
num = 0;
for(k = 0; k < 4; k ++) {
tx = i + dir[k][0];
ty = j + dir[k][1];
if(ok(tx, ty)) {
num ++;
mat[now][board[tx][ty]] = -1;
}
mat[now][now] = num;
mat[now][cnt + 1] = num;
}
}
}
}
for(i = 0; i < cn; i ++) {
l = board[ed[i].x][ed[i].y];
memset(mat[l], 0, sizeof(mat[l]));
mat[l][l] = 1;
}
if(gauss(cnt + 1))
printf("%.6lf\n", mat[board[st.x][st.y]][board[st.x][st.y]]);
else
printf("-1\n");
}
return(0);
}


  回复  更多评论
  
# re: 概率题总汇 2009-11-29 12:26 | torzmai
能不能解释一下hdu 1204的那个公式??  回复  更多评论
  
# re: 概率题总汇 2010-05-16 10:35 | ilj
您给的那位“zjut一位大牛的文章”的链接好像要zjut内网才能链接上的,麻烦您能发那篇文章给我看看吗,谢谢。邮箱349335192@qq.com  回复  更多评论
  
# re: 概率题总汇 2010-11-08 23:39 | JENSENMercedes34
I opine that to get the <a href="http://bestfinance-blog.com/topics/credit-loans">credit loans</a> from creditors you should have a firm motivation. Nevertheless, once I have received a student loan, just because I was willing to buy a building.   回复  更多评论
  
# re: 概率题总汇 2012-08-02 16:36 | 求 zjut一位大牛的文章
matrix,yms@gmail.com 谢谢啦  回复  更多评论
  
# re: 概率题总汇 2012-08-07 10:56 | song
傻仔大哥,我也想看浙大牛人文章,可不可以给我也发一份
462039091@qq.com  回复  更多评论
  
# re: 概率题总汇 2013-04-18 10:45 | meander
我也想看浙大牛人文章,可不可以给我也发一份776593191@qq.com。跪谢  回复  更多评论
  
# re: 概率题总汇 2013-10-25 11:49 | Plumrain
概率题感觉还没入门T T,求看zjut大牛的文章,感谢楼主。lmh463896910@gmail.com  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理