[ACM] sdut 2878 Circle (高斯消元）

[ACM] sdut 2878 Circle (高斯消元）

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.

示例輸入

3
3 2
5 4
10 5

示例輸出

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;row0)
                max_r=i;
        }
        if(max_r!=row)
        {
            for(j=row;j=0;i--)
        {
            int free_num=0;///自由變元的個數
            int free_index;///自由變元的序號
            for(j=0;j1)
                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