[ACM] sdut 2878 Circle (高斯消元） - c++编程基础

Circle

Time Limit: 2000ms Memory limit: 65536K 有疑问？点这里^_^

题目描述

You have been given a circle from 0 to n?-?1. If you are currently at x, you will move to (x?-?1) mod n or (x?+?1) mod n with equal probability. Now we want to know the expected number of steps you need to reach x from 0.

输入

The first line contains one integer T ― the number of test cases. Each of the next T lines contains two integers n,?x (0??≤?x? 输出 For each test case. Print a single float number ― the expected number of steps you need to reach x from 0. The figure is accurate to 4 decimal places.

示例输入

示例输出

2.0000
4.0000
25.0000

提示

来源

2014年山东省第五届ACM大学生程序设计竞赛

解题思路：

题意为n个节点编号0到n-1，成一个环形，给定一个数x，求从0号节点走到x节点的期望步数是多少。节点向两边走的概率相同，每一步走一个节点。

高斯消元,n个方程，n个未知量, 设E[ p ] 为从p节点走到x节点还需要走的步数的期望数。那么E [ x ] =0;

对于每个节点都有 E[p]=0.5*E[p-1]+0.5*E[p+1]+1, 即 -0.5*E[p-1]+E[p]-0.5*E[p+1]=1。

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; ///浮点型高斯消元模板 const double eps=1e-12; const int maxm=1000;///m个方程，n个变量 const int maxn=1000; int m,n; double a[maxm][maxn+1];///增广矩阵 bool free_x[maxn];///判断是否是不确定的变元 double x[maxn];///解集 int sign(double x) { return (x>eps)-(x<-eps); } /**返回值： -1 无解 0 有且仅有一个解 >=1 有多个解，根据free_x判断哪些是不确定的解 */ int Gauss() { int i,j; int row,col,max_r; m=n;///n个方程，n个变量的那种情况 for(row=0,col=0;row
         
          0) max_r=i; } if(max_r!=row) { for(j=row;j
          
           =0;i--) { int free_num=0;///自由变元的个数 int free_index;///自由变元的序号 for(j=0;j
           
            1) continue;///该行中的不确定的变元的个数超过1个,无法求解,它们仍然为不确定的变元 ///只有一个不确定的变元free_index,可以求解出该变元,且该变元是确定的 double tmp=a[i][n]; for(j=0;j
            
             =0;i--) { double tmp=a[i][n]; for(j=i+1;j
             
              >t; while(t--) { cin>>n>>xx; memset(a,0,sizeof(a)); for(int i=0;i