Tony Bai
bigwhite · 2008-02-01
<< 三角形输出问题考量
|
首页
|
'灾难'到来之前,我们该做点啥 >>
2008-01-29
查表法求解'自然数对'问题
- [
语言探索
]
Tag:
语言探索
版权声明
:转载时请以超链接形式标明文章原始出处和作者信息及
本声明
http://bigwhite.blogbus.com/logs/14643594.html
'自然数对'是这样的一对自然数,他们的和与差的结果都是平方数,比如:自然数对32和68,根据定义32+68 = 100 = 10^2,68-32 = 36 = 6^2。现在的题目是:根据输入的两个100以内的自然数,打印出这两个整数之间的所有自然数对。
这道题不难,而且限制了范围,在两个100以内的自然数区间,很多人马上就能给出程序。这道题的有两个点需要思考:一个是关于平方数的判断;另一个就是两个数的组合控制。
关于平方数的判断,多数人采用的方法就是利用现成的sqrt函数来做判断。当然也有人和我想的一样,采用表查询的方法。因为题目明确限制了范围是两个100以内的数,试想一下100以内最大的两个数的和99+98=197,也就是说100以内自然数对的和如果是平方数的话,肯定是下面集合中的一个,这个集合为{1,4,9,16,25,36,49,64,81,100,121,144,169,196}。那么既然我们已经肯定了如此,我们还何必去做sqrt操作呢,直接在这个集合中查找不就行了,这也是一种最简单的查表法,至于表的存储结构和查询算法可自定义(影响性能)。
关于数的组合控制,很多人都会使用两层循环,这没错。除了循环,递归也是一个不错的方法。简单的看了下,这个例子还是比较符合递归的两个条件的:
1、有basis case;
2、规模逐渐缩小;
基于上述两点,这里给出一个简单的实现:
int square_number_tbl[] = {1,4,9,16,25,36,49,64,81,100,121,144,169,196};
int is_natural_number_pair(int a) {
int i;
//简单的顺序查找
for (i = 0; i < sizeof(square_number_tbl)/sizeof(square_number_tbl[0]); i++) {
if (square_number_tbl[i] == a) return 1;
}
return 0;
}
//find natural number pair
void find_nnp(int a, int b) {
int i;
if (b - a <=0) { //basis case
return;
}
i = a;
do {
if (is_natural_number_pair(b+i) && is_natural_number_pair(b-i)) {
printf("%d, %d\n", b, i);
}
i++;
}while (i <= b);
return find_nnp(a, b-1);//recursive invoke
}
int main() {
int a, b; //we suppose that b is greater than a, and both are less than 100
printf("Please Input two integrals (1,100):");
scanf("%d %d",&a,&b);
find_nnp(a, b);
}
完成这个后,突然又想到的一个方法:根据输入的范围[a, b]动态构造一张矩阵,矩阵的x轴方向和y轴方向的都是由a->b的数轴。矩阵中的数值按如下方式初始化M(x, y) = x + y; M(y, x) = y - x; (y > x);初始化完矩阵后,对矩阵进行一次扫描,并在is_natural_number_pair的帮助下找到所有自然数对。
随机文章:
多行宏定义中的注释问题
2008-03-14
三角形输出问题考量
2008-01-27
C++咬文嚼字-'Pointer Trick'
2007-05-22
C++咬文嚼字-'Functions'
2007-03-13
C++咬文嚼字-'Evil cast'
2007-03-12
收藏到:
Del.icio.us
引用地址:
bigwhite
发表于
00:00
|
编辑
|
继续话题
|
转发
|
推荐
评论
怎么刷不出来啊
bigwhite
回复
bbzh
说:
???什么刷不出来?
2008-02-01 11:29:25
bbzh
|
[
回复
]
您有MSN吗,我的是bbzh_2@hotmail.com
加下说吧~~
bbzh
|
[
回复
]
发表评论
原始快照:web.archive.org