自我感觉良好的高精度

2008年7月5日琐事杂谈
1

Comments

一道题目，要用高精度。我觉得这次写的高精度是我写得最清晰的一次了，所以贴出来纪念一下。

这道题目是这样的：

找关系(relation)

【问题描述】

任意给定两个数a,b，众所周知，它们之间有两种大小比较关系，如下：

a = b       a < b       b < a

由于“=”的左右两边是对称的，所以a = b与b = a一共只算一种关系，并且a < b与b > a一共也只算一种关系。
那么按照如上规则：给定3个数a,b,c，它们之间大小比较关系就有13种，具体如下：

a = b = c       a = b < c       c < a = b       a < b = c
b = c < a       a = c < b       b < a = c       a < b < c
a < c < b       b < a < c       b < c < a       c < a < b
c < b < a

问题来了：请你设计一个程序算出对于给的N（意为有N个数，N<=300），求出这N个数大小比较关系有多少种。

【输入文件】

有多组数据，数据组数<=10，每行一个N数据最后以-1结尾

【输出文件】

有多少组数据分多少行

按输入的顺序每行输出每个N对应的大小关系种数

【样例输入】 【样例输出】
2
3
-1		 3
13

数据下载：data_relation.rar （11.1 KB)

我的程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

#include <stdio.h>
#include <memory.h>
 
#define BIGBIT 1000000
#define MAX(a, b) ((a)>(b)?(a):(b))
 
struct bignum
{
	int len;
	int num[150];
};
 
int n[301], maxn;
bignum f[2][300];
int fp, fn, ft;
bignum tans[300], ans[20];
 
bignum& add(const bignum &a, const bignum &b, bignum &result)
{
	memset(result.num, 0, sizeof(result.num));
 
	for (int i = 0; i < a.len; ++i)
		result.num[i] = a.num[i];
	for (int i = 0; i < b.len; ++i)
		result.num[i] += b.num[i];
 
	result.len = MAX(a.len, b.len);
	for (int i = 0; i < result.len; ++i)
		if (result.num[i] >= BIGBIT)
			result.num[i + 1] += result.num[i] / BIGBIT,
			result.num[i] %= BIGBIT;
 
	if (result.num[result.len])
		++result.len;
 
	return result;
}
 
void mul(bignum &dest, const int src)
{
	for (int i = 0; i < dest.len; ++i)
		dest.num[i] *= src;
 
	for (int i = 0; i < dest.len; ++i)
		if (dest.num[i] >= BIGBIT)
			dest.num[i + 1] += dest.num[i] / BIGBIT,
			dest.num[i] %= BIGBIT;
 
	if (dest.num[dest.len])
		++dest.len;
}
 
void set(bignum &dest, const int src)
{
	if (src >= BIGBIT)
		dest.num[0] = src % BIGBIT,
		dest.num[1] = src / BIGBIT,
		dest.len = 2;
	else if (src == 0)
		dest.len = 0;
	else
		dest.num[0] = src,
		dest.len = 1;
}
 
void set(bignum &dest, const bignum &src)
{
	dest.len = src.len;
	for (int i = 0; i < src.len; ++i)
		dest.num[i] = src.num[i];
}
 
void print(const bignum &src)
{
	printf("%d", src.num[src.len - 1]);
	for (int i = src.len - 2; i >= 0; --i)
		printf("%06d", src.num[i]);
	printf("\n");
}
 
int main()
{
	freopen("relation.in", "r", stdin);
	freopen("relation.out", "w", stdout);
 
	maxn = 0;
	for (int i = 1; i <= 15; ++i)
	{
		int tn;
		scanf("%d", &tn);
		if (tn == -1)
		{ n[0] = i - 1; break; }
		n[tn] = i;
		if (tn > maxn) maxn = tn;
	}
 
	fp = 0, fn = 1;
	set(f[fp][0], 2); set(f[fp][1], 1);
	for (int i = 3; i <= maxn; ++i)
	{
		for (int j = 0; j < i; ++j)
			mul(add(f[fp][j], f[fp][j - 1], f[fn][j]), i - j);
		if (n[i])
		{
			set(tans[0], f[fn][0]);
			for (int j = 1; j < i; ++j)
				add(tans[j - 1], f[fn][j], tans[j]);
			set(ans[n[i]], tans[i - 1]);
		}
		ft = fp, fp = fn, fn = ft;
	}
 
	for (int i = 1; i <= n[0]; ++i)
		print(ans[i]);
 
	return 0;
}

结果：

1：0.07s
2：0.17s
3：0.12s
4：0.04s
5：0.07s 		6：0.06s
7：0.21s
8：0.07s
9：0.12s
10：0.28s

You can follow any responses to this entry through the RSS 2.0 | You can leave a response or trackback from your own site.

Related Posts Random Posts

One Response to “自我感觉良好的高精度”

  1. MRain Says:
    2008年7月7日 20:28 回复

    自我感觉良好…

Leave a Reply