Chinaunix首页 | 论坛 | 博客

Archer\'s Life

首页　| 　博文目录　| 　关于我

archer239915

  • 博客访问： 151401
  • 博文数量： 40
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 908
  • 用 户 组： 普通用户
  • 注册时间： 2013-09-03 11:03
个人简介

学习linux

文章分类

全部博文（40）

文章存档

2014年（7）

2013年（33）

我的朋友
最近访客
推荐博文
相关博文
找出最大矩形的算法

分类： C/C++

2014-03-29 20:08:24

刚刚参加了实习生笔试，最后是很有趣的一个算法题，回来没事就把代码写出来了。

题目大概：

一个数组：A[10]每个值代表矩形的高度，求最大的矩形大小。
比如A[10]= { 1, 2 , 4, 6, 0 ,5, 3 ,0 ,2 ,2};
1表示横坐标为1的单元高度为1； 6就表示横坐标为4的单元高度为6；
很明显最大是4和6组成的矩形，面积为8

下面是我写的程序：（不好意思，这个有bug，看最后一个改好的程序）

点击(此处)折叠或打开

  1. #include <stdio.h>

  3. int find_max(int A[],int left,int right);

  5. //only one zero
  6. int main(int argc,char *argv[])
  7. {
  8.     int ret;

  10.     int A[10] = {6,7,9,1,13,12,2,4,20,4};

  12.     ret = find_max(A,0,9);

  14.     printf("%d\n",ret);

  16.     return 0;
  17. }

  19. void change(int A[],int left,int right,int d0)
  20. {
  21.     int i;
  22.     for(i=left;i<=right;i++)
  23.     {
  24.         A[i] = A[i] - d0;
  25.         printf("%d ",A[i]);
  26.     }
  27.     printf("\n\n");
  28. }

  30. int which_max(int a,int b,int c)
  31. {
  32.     int tmp;
  33.     if(a>b)
  34.         tmp = a;
  35.     else
  36.         tmp = b;

  38.     if(c>tmp)
  39.         return c;
  40.     else
  41.         return tmp;
  42. }

  44. void min_height(int A[],int left,int right,int *i0,int *d0)
  45. {
  46.     int i;
  47.     
  48.     *i0 = left;
  49.     *d0= A[left];

  51.     for(i=left+1;i<=right;i++)
  52.     {
  53.         if(A[i]<*d0)
  54.         {
  55.             *i0 = i;
  56.             *d0 = A[i];
  57.         }
  58.     }
  59. }
  60.     

  62. int find_max(int A[],int left,int right)
  63. {
  64.     int i0,d0;
  65.     int base_max;
  66.     int left_max;
  67.     int right_max;
  68.     int max;

  70.     min_height(A,left,right,&i0,&d0);

  72.     base_max = (right - left + 1)*d0;

  74.     printf("find base_max = %d int %d to %d,middle is %d ,height %d\n",
  75.         base_max,left,right,i0,d0);

  77.     change(A,left,right,d0);


  80.     if(left == i0)
  81.         left_max = 0;
  82.     else
  83.     {
  84.         left_max = find_max(A,left,i0-1);
  85.         left_max = left_max + (i0-left)*d0;
  86.     }
  87.     
  88.     if(right == i0)
  89.         right_max = 0;
  90.     else
  91.     {
  92.         right_max = find_max(A,i0+1,right);
  93.         right_max = left_max + (right-i0)*d0;
  94.     }
  95.     
  96.     
  97.     max = which_max(base_max,left_max,right_max);
  98.     printf("base_max %d ,left_max %d ,right_max %d max %d\n\n",
  99.         base_max,left_max,right_max,max);

  101.     return max;
  102. }
下面是运行结果：（错误程序运行结果，看下面正确程序的运行结果）

点击(此处)折叠或打开

  1. root@archer:/work/user-lib/test# ./tencent
  2. find base_max = 10 int 0 to 9,middle is 3 ,height 1
  3. 5 6 8 0 12 11 1 3 19 3

  5. find base_max = 15 int 0 to 2,middle is 0 ,height 5
  6. 0 1 3

  8. find base_max = 2 int 1 to 2,middle is 1 ,height 1
  9. 0 2

  11. find base_max = 2 int 2 to 2,middle is 2 ,height 2
  12. 0

  14. base_max 2 ,left_max 0 ,right_max 0 max 2

  16. base_max 2 ,left_max 0 ,right_max 1 max 2

  18. base_max 15 ,left_max 0 ,right_max 10 max 15

  20. find base_max = 6 int 4 to 9,middle is 6 ,height 1
  21. 11 10 0 2 18 2

  23. find base_max = 20 int 4 to 5,middle is 5 ,height 10
  24. 1 0

  26. find base_max = 1 int 4 to 4,middle is 4 ,height 1
  27. 0

  29. base_max 1 ,left_max 0 ,right_max 0 max 1

  31. base_max 20 ,left_max 11 ,right_max 0 max 20

  33. find base_max = 6 int 7 to 9,middle is 7 ,height 2
  34. 0 16 0

  36. find base_max = 0 int 8 to 9,middle is 9 ,height 0
  37. 16 0

  39. find base_max = 16 int 8 to 8,middle is 8 ,height 16
  40. 0

  42. base_max 16 ,left_max 0 ,right_max 0 max 16

  44. base_max 0 ,left_max 16 ,right_max 0 max 16

  46. base_max 6 ,left_max 0 ,right_max 4 max 6

  48. base_max 6 ,left_max 22 ,right_max 25 max 25

  50. base_max 10 ,left_max 18 ,right_max 24 max 24

  52. 24
说明最大面积是 24，很显然就是 12和13组成的矩形。


正确的程序：

点击(此处)折叠或打开

  1. #include <stdio.h>

  3. int find_max(int A[],int left,int right);


  6. int main(int argc,char *argv[])
  7. {
  8.     int ret;

  10.     int A[10] = {6,7,0,0,13,12,2,2,20,3};
  11. //    int A[] = {2,18,1};

  13.     ret = find_max(A,0,9);

  15.     printf("%d\n",ret);

  17.     return 0;
  18. }

  20. void change(int A[],int left,int right,int d0)
  21. {
  22.     int i;
  23.     for(i=left;i<=right;i++)
  24.     {    
  25.         A[i] = A[i] - d0;
  26.         printf("%d ",A[i]);
  27.     }
  28.     printf("\n");
  29. }

  31. int which_max(int a,int b,int c)
  32. {
  33.     int tmp;
  34.     if(a>b)
  35.         tmp = a;
  36.     else
  37.         tmp = b;

  39.     if(c>tmp)
  40.         return c;
  41.     else
  42.         return tmp;
  43. }

  45. void min_height(int A[],int left,int right,int *i0,int *d0)
  46. {
  47.     int i;
  48.     
  49.     *i0 = left;
  50.     *d0= A[left];

  52.     for(i=left+1;i<=right;i++)
  53.     {
  54.         if(A[i]<*d0)
  55.         {
  56.             *i0 = i;
  57.             *d0 = A[i];
  58.         }
  59.     }
  60. }
  61.     

  63. int find_max(int A[],int left,int right)
  64. {
  65.     int i0,d0;
  66.     int base_max;
  67.     int left_max;
  68.     int right_max;
  69.     int max;

  71.     if(right == left)
  72.     {
  73.         printf("%d \n",A[left]);
  74.         return A[left];
  75.     }

  77.     min_height(A,left,right,&i0,&d0);

  79.     base_max = (right - left + 1)*d0;

  81.     change(A,left,right,0);
  82.     
  83.     printf("find base_max = %d int %d to %d,middle is %d ,height %d\n",
  84.         base_max,left,right,i0,d0);

  86. //    change(A,left,right,d0);


  89.     if(left == i0)
  90.         left_max = d0;
  91.     else
  92.     {
  93.         left_max = find_max(A,left,i0-1);
  94. //        left_max = left_max + (i0-left)*d0;
  95.     }
  96.     
  97.     if(right == i0)
  98.         right_max = d0;
  99.     else
  100.     {
  101.         right_max = find_max(A,i0+1,right);
  102. //        right_max = right_max + (right-i0)*d0;
  103.     }
  104.     
  105.     
  106.     max = which_max(base_max,left_max,right_max);
  107.     printf("base_max %d ,left_max %d ,right_max %d max %d\n\n",
  108.         base_max,left_max,right_max,max);

  110.     return max;
  111. }

正确的运行结果如下：

root@archer:/work/user-lib/test# ./tencent 
6 7 0 0 13 12 2 2 20 3 
find base_max = 0 int 0 to 9,middle is 2 ,height 0
6 7 
find base_max = 12 int 0 to 1,middle is 0 ,height 6
7 
base_max 12 ,left_max 6 ,right_max 7 max 12


0 13 12 2 2 20 3 
find base_max = 0 int 3 to 9,middle is 3 ,height 0
13 12 2 2 20 3 
find base_max = 12 int 4 to 9,middle is 6 ,height 2
13 12 
find base_max = 24 int 4 to 5,middle is 5 ,height 12
13 
base_max 24 ,left_max 13 ,right_max 12 max 24


2 20 3 
find base_max = 6 int 7 to 9,middle is 7 ,height 2
20 3 
find base_max = 6 int 8 to 9,middle is 9 ,height 3
20 
base_max 6 ,left_max 20 ,right_max 3 max 20


base_max 6 ,left_max 2 ,right_max 20 max 20


base_max 12 ,left_max 24 ,right_max 20 max 24


base_max 0 ,left_max 0 ,right_max 24 max 24


base_max 0 ,left_max 12 ,right_max 24 max 24


24
阅读(2762) | 评论(0) | 转发(0) |
0

上一篇：linux的中断模式

下一篇：字符串移位包含的问题

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6