杭电2050

http://acm.hdu.edu.cn/showproblem.php?pid=2050

1
2
3
4
5
6
7
8
9
10
11
12
13
package oj;
import java.util.Scanner;
public class Main_2050 {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int t = scanner.nextInt();
		while (t-->0) {
			int a=scanner.nextInt();
			System.out.println(""+(2*a*a-a+1));
			
		}
	}
}

如果是直线，会有啥规律？
在平面添加一条直线，会把平面分成两部分，在这个基础上再添加一条直线那就是变成4部分要得到平面分割最大面数，就要让第n条直线，穿过前面n－1条直线。可以得到规律
直线 面数量
1 2
2 4
3 7
4 11

a1=1+1=2
a2=1+1+2=4
a3=1+1+2+3=7
a4=1+1+2+3+4=11
所以规律是
an=(n*(n+1))/2+1;

如果在此基础上提出，每次给定的是两条平行线，就是每次给两条平行的线，求n条线能把平面划分多少个面，很明显n是偶数，它相对于直线添加的规律，假定直线的线面函数叫f(n)现在输入的j设定必定为偶数.很明显可以得到
g(j)=f(j)-j/2;
注意只适用j为偶数那么－j/2是怎么得来的？试想，本来应该香蕉的两条线，结果被搞成平行了，那么，会因为这个最少得减少1个面，因为每次添加都是偶数，那么就是，每次添加两天平行线，那就是在直线f(n)规律上减少一个面

那么g(j) j为偶数，这就是平行线的规律。在g(j)的基础上，如果每组平行线它不是平行线而是从某个点发出的两条射线，就是说，每次添加的两条线，不再是平行线，而是射线，它两个有共同的原点。那么面数量会如何改变？结果就是面的数量得再减少一个
h(j)=g(j)-j/2;j还是偶数，这样才能符合g(j)得规律.所以最终整理出来
h(n)=(n(n+1))/2+1-n; n为偶数
所以这边就是把每条折线当成两个有同一原点的射线，为了适应输入j(j属于自然数) 所以方程里面的n都用2j来代替
得到新的y(j)=2jj -j+1 (j属于自然数)
这就是折线最大面数量规律
只要得到规律函数，这题就解了。
但是，实际上这道题的初衷，是让我们用递归的思想去解决，以上都是纯数学分析，得到规律公式。
递归，就是想要缩减n的规模，一个简单的方法得到递归的表达式就是：
y(j)-y(j-1)
整理得到j和j-1的增量表达式：
4j-3
所以，偷懒的变异代码变成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

package oj;
import java.util.Scanner;
public class Main_2050 {
   public static void main(String[] args) {
  Scanner scanner = new Scanner(System.in);
 int t = scanner.nextInt();
    while (t-->0) {
   int a=scanner.nextInt();
  System.out.println(""+fun(a));
    
  }
 }
   private static int fun(int a) {
   if (a==1) {
   return 2;
 
  }else{
    return fun(a-1)+4*a-3;
    }
 }
}

如果光从递归就想解决，n和n－1之间的增量，还真的想不出来哦