2008年一月月 发布的文章

查表法求解'自然数对'问题

‘自然数对’是这样的一对自然数,他们的和与差的结果都是平方数,比如:自然数对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的帮助下找到所有自然数对。

三角形输出问题考量

相信很多人在初学某门计算机语言的时候都会做过类似的题目:在控制台上输出用特定字符'拼'出来的某种图形,比如下面的这种三角形:
    *
   ***
  *****
 *******
*********
这样的问题应该算是入门级的了,大多人都是看之,做之,忘之,而今天我就拿这种入门级的题目说事,小问题里也许内含有大道理。

昨晚无意中在编程爱好者论坛看到这样一道三角形输出C语言例题,内容大致如下:
用*号组合成一个三角形!行数由键盘输入(范围为:1~20,输入超过范围,则提示出错)。如:
输入一个数4,则输出以下图形:
     *
    ***
   *****
  *******
共四行;如输入的是6,则输出以下图形:
       *
      ***
     *****
    *******
   *********
  ***********
共六行,依次类推。

对于这类题目,大多数人见到后都会马上敲键盘,也许十分钟或更少时间就能拿出了一个解决方案,比如论坛上发表的一段代码:
int main()
{
        int i, j, n;
        printf("Please enter the number of col(1~20):\n");
        while(1) {
                scanf("%d",&n);
                if(1<=n && n<=20) {
                        break;
                } else {
                        printf("out of range(1~20),please retype:\n");
                }
        }       

        for(i=0; i<n; i++) {
                for(j=i; j<n-1; j++)
                        printf(" ");
                for(j=0; j<2*i+1; j++)
                        printf("*");
                printf("\n");
        }

        return 0;
}
这段代码的实现初步看起来应该是没有问题的,而且很多人的答案与之都大同小异,但是从另外一个角度来看似乎这里存在些小问题。从什么角度呢?从设计角度。我们来看,上面的代码只是从功能的角度去考虑了,导致代码很'死',输出逻辑与图形生成逻辑交叠在一起了,或者说根本谈不上有什么设计的思维在里面。

这时有人会问:这么小的问题还需要设计吗?如果你是在参加ACM竞赛,这么实现一点问题没有,又快又正确。但是如果从一个工程的角度来看,无论问题大小与否,都需要有设计。

类似这种输出三角形或者输出实心(或空心)菱形的问题实际上都可以看成是将一个含有特殊字符的二维数组(或矩阵)输出的一个过程。我们完全可以将输出和形成图形这两种逻辑正交分开。我们的大致思路就是:校验输入 -> 根据输入的参数,确认画布(二维数组)的尺寸 -> 在画布上描点 -> 将画布整体输出到控制台上,这样的逻辑有些类似于Windows GUI图形的输出。

typedef struct {
    int row;
    int col;
    int *p;
} canvas; //画布结构

int prepare_canvas(canvas *p_cns, /* in/out */
                    int row,  /* in */
                    int col); /* in */
void get_option(int *row, /* out */
                int *col); /* out */
void draw(canvas *p_cns); /*in/out */
void show(const canvas *p_cns);
void release_canvas(canvas *p_cns);  /*in/out*/

/* 提供一个宏,方便访问画布上的像素点 */
#define CANVAS_PIXEL(p_cns, i, j) \
     *((p_cns)->p + (i) * (p_cns)->col + (j))

int main(int argc,  char *argv[]) {
    int     rv, row, col;
    canvas   cns;
    
    get_option(&row, &col);
    
    rv = prepare_canvas(&cns, row, col);
    if (rv != 0) {
        printf("fail to prepare_canvas!\n");
        return;
    }
    
    draw(&cns); //描点逻辑
    show(&cns); //输出逻辑

    release_canvas(&cns);
    return 0;
}

void get_option(int *row, int *col) {
    int n;
    do {
        printf("enter the number of lines:\n");
        scanf("%d", &n);
        if (n 20) {
            printf("out of range(3~20), please re-enter.\n");
        } else {
            *row = n;
            *col = 2 * n -1; //确定画布大小
            break;
        }
     } while (1);
}

int prepare_canvas(canvas *p_cns, int row, int col) {

    p_cns->row = row;
    p_cns->col = col;
    p_cns->p = (int*)malloc(row * col * sizeof(int));
    if (p_cns->p == NULL) {
        printf("fail to malloc the canvas!\n");
        return -1;
    }
    
    memset(p_cns->p, ' ', row * col * sizeof(int)); //将画布上的'像素点'都置为空白
    return 0;
}

void draw(canvas *p_cns) { //生成图形逻辑,我们的focus点
        int row, col;
        for (row = 0; row

row; row++) {
                for(col =p_cns->row-1-row ; col row-1+row; col++) {
                         CANVAS_PIXEL(p_cns, row, col) = '*';
                }
        }
}

void show(const canvas *p_cns) { //图形的通用输出逻辑,此后无须关注
    int row, col;
    for (row = 0; row

row; row++) {
                for (col = 0; col

col; col++) {
                        printf("%c", CANVAS_PIXEL(p_cns, row, col));
                }
                printf("\n");
        }
}

void release_canvas(canvas *p_cns) {
    if (p_cns->p != NULL) {
        free(p_cns->p);
    }
}

也许单单从上面的例子来看,你会觉得这样做的代码量会多出几倍。这里我们不妨再考虑另一个道问题:输入一个奇数n,输出对角线长为n的实心菱形。比如:
  *  
 ***
*****
 ***
  *  

使用我们上面的设计,我们只需改造几个地方就可以完成这个问题。main函数是不需要改动的。我们需要关注的只是输入的校验逻辑和draw的逻辑。

void get_option(int *row, int *col) {
    int n;
    do {
        printf("enter the number of lines:\n");
        scanf("%d", &n);
        if (n 20) {
            printf("out of range(1~20), please re-enter.\n");
        } else if (n % 2 == 0) { //增加是否为奇数的判断
            printf("the number is not even, please re-enter.\n");
        } else {
            *row = n;
            *col = n; //画布规模需根据问题的不同而定
            break;
        }
     } while (1);
}

void draw(canvas *p_cns) {
        int row, col;
        
        int temp_row = (p_cns->row+1)/2;
        for (row = 0; row < temp_row; row++) {
                for(col = temp_row -1-row ; col <= temp_row-1+row; col++) {
                         CANVAS_PIXEL(p_cns, row, col) = '*'; //画菱形的上半部分
                         CANVAS_PIXEL(p_cns, p_cns->row-1-row, col) = '*'; //画镜像
                }
        }
}

有了三角形输出设计的基础,我们完成菱形输出已经很easy了,关键是我们可以focus到图形生成逻辑,也就是更关注问题域了。'画布'这种概念为图形生成逻辑提供了一个很好的复用平台,而且也符合我们头脑中的平面思维逻辑。

以上问题如果用面向对象的语言来实现,用面向对象的思维(我们的那个main是否类似template method)和特性(override)就更容易实现我们的这个设计了。

如发现本站页面被黑,比如:挂载广告、挖矿等恶意代码,请朋友们及时联系我。十分感谢! Go语言第一课 Go语言精进之路1 Go语言精进之路2 Go语言编程指南
商务合作请联系bigwhite.cn AT aliyun.com

欢迎使用邮件订阅我的博客

输入邮箱订阅本站,只要有新文章发布,就会第一时间发送邮件通知你哦!

这里是 Tony Bai的个人Blog,欢迎访问、订阅和留言! 订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠 ,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:

如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:

以太币:

如果您喜欢通过微信浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:
本站Powered by Digital Ocean VPS。
选择Digital Ocean VPS主机,即可获得10美元现金充值,可 免费使用两个月哟! 著名主机提供商Linode 10$优惠码:linode10,在 这里注册即可免费获 得。阿里云推荐码: 1WFZ0V立享9折!


View Tony Bai's profile on LinkedIn
DigitalOcean Referral Badge

文章

评论

  • 正在加载...

分类

标签

归档



View My Stats