Tony Bai

<< 三角形输出问题考量 | 首页 | '灾难'到来之前,我们该做点啥 >> 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