HDOJ(HDU) 2156 分数矩阵(嗯、求和)

谙忆

发布于 2021-01-21 15:42:15

2640

发布于 2021-01-21 15:42:15

文章被收录于专栏：程序编程之旅程序编程之旅

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

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

Output 输出答案，保留2位小数。

Sample Input 1 2 3 4 0

Sample Output 1.00 3.00 5.67 8.83

简单题不打表会超时。。。。还可以用一个公式做，有规律。

打表：

import java.util.Scanner;

public class Main{
    static double db[] = new double[50002];
    public static void main(String[] args) {
        dabiao();
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n =sc.nextInt();
            if(n==0){
                return;
            }
            System.out.printf("%.2f",db[n]);
            System.out.println();
        }
    }
    private static void dabiao() {
        db[1]=1;
        double m =1;
        for(int i=2;i<db.length;i++){
            m=m+2.0*1.0/i;
            db[i]=db[i-1]+m;
        }
    }
}

找规律：分析：

初始条件：a[5005]={0,1,3}

1/1  a[1]

1/1 1/2
1/2 1/1   a[2]

1/1 1/2 | 1/3
1/2 1/1 | 1/2
--------|
1/3 1/2   1/1   a[3]

 ____________
|1/1  1/2 1/3| 1/4
      ____________
|1/2 |1/1 1/2| 1/3|
|1/3 |1/2 1/1| 1/2|
|____|_______|    |
 1/4 |1/3 1/2  1/1|   a[4]
     |____________|

递推公式：a[i]=2*a[i-1]-a[i-2]+2.0/i; 初始条件：a[5005]={0,1,3}

#include <stdio.h>
double a[50005]={0,1,3};
int main()
{
    int n,i;
    for (i=3;i<=50000;i++)
        a[i]=2*a[i-1]-a[i-2]+2.0/i;
    while (scanf("%d",&n)!=EOF&&n)
        printf("%.2fn",a[n]);
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016/05/05 ，如有侵权请联系 cloudcommunity@tencent.com 删除

input