首页 > ACM题库 > HDU-杭电 > hdu 2156 分数矩阵[解题报告]C++
2013
12-30

hdu 2156 分数矩阵[解题报告]C++

分数矩阵

问题描述 :

我们定义如下矩阵:
1/1 1/2 1/3
1/2 1/1 1/2
1/3 1/2 1/1
矩阵对角线上的元素始终是1/1,对角线两边分数的分母逐个递增。
请求出这个矩阵的总和。

输入:

每行给定整数N (N<50000),表示矩阵为 N*N.当N为0时,输入结束。

输出:

每行给定整数N (N<50000),表示矩阵为 N*N.当N为0时,输入结束。

样例输入:

1
2
3
4
0

样例输出:

1.00
3.00
5.67
8.83

 

#include<stdio.h>
#include<math.h>
#include<string.h>
#define max 50001
double x[max]={0,1};
int main(){
    int n,i;
	double sum=1;
	for(i=2;i<max;i++){
		sum+=2*(1.0/i);
		x[i]=x[i-1]+sum;
	}
	while(scanf("%d",&n)&& n){ 
		printf("%.2lf\n",x[n]);
	}
	return 0;
}

解题转自:http://blog.csdn.net/qq775445624/article/details/6709966


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮