研究研究算法--递归算法(poj1191)

一、题目

地址:http://poj.org/problem?id=1191

二、分析

方格只能横着切、竖着切,并且指定切割的次数。所以,递归的方式列出所有的切割可能性,每递归一次切割次数减1,直到切割次数为0,就停下来。

三、实现

C代码:

#include "stdio.h"
#include "math.h"
#include "string.h"
#include "limits.h"
#include "stdlib.h"

#define col 8
#define row 8
#define MIN(a,b) ((a)<(b)?(a):(b))

typedef struct{
  int left,top,right,bottom;
}Rect;

double avg(int a[],int num);
double delta(int a[],int num);
void cut(Rect full,int cutTime,Rect * cutRects,int cutSize,double * out,Rect * outRect);

int main(int argc, char const *argv[]) {
  Rect full = {0,0,col,row};
  Rect hasCut[0];
  double out = LONG_MAX;
  int cutTime = 99;
  printf("%s\n", "现需切割8*8方格,保证各个小块的面积方差最小。请输入切割次数(1-->14):");
  while (1) {
    scanf("%d", &cutTime);
    if(cutTime<1 || cutTime>14){
      printf("%s\n", "输入错误,请重新输入:");
    }else{
      break;
    }
  }

  Rect * outRect = (Rect *)malloc(sizeof(Rect)*(cutTime+1));
  cut(full,cutTime,hasCut,0,&out,outRect);
  printf("\n最小的方差为: %lf\n",out);
  printf("%s\n", "其中一种最佳的切割方案为:");
  for(int i = 0;i<cutTime+1;i++){
    printf("方块%d :坐标区间为 left %d, top %d,right %d,bottom %d,方块面积为 %d\n",i+1, outRect[i].left,outRect[i].top,outRect[i].right,outRect[i].bottom,
    (outRect[i].right-outRect[i].left)*(outRect[i].bottom-outRect[i].top));
  }
  return 0;
}

// 切方块
// cutTime : 切割次数
// cutRects : 已经被切割的方块
// cutSize : 已经被切割的方块个数
// out : 存储最小的方差
void cut(Rect full,int cutTime,Rect * cutRects,int cutSize,double * out,Rect * outRect){
  if(cutTime == 0){
    // printf("%s %d\n", "== 0",cutSize);
    Rect hasCutsInH[cutSize+1];
    memcpy(hasCutsInH,cutRects,sizeof(Rect)*cutSize);
    hasCutsInH[cutSize] = full;

    int tempAreaSize[cutSize+1];
    for(int i = 0;i<cutSize+1;i++){
      // printf("left %d, top %d,right %d,bottom %d,areaSize %d\n", hasCutsInH[i].left,hasCutsInH[i].top,hasCutsInH[i].right,hasCutsInH[i].bottom,
      // (hasCutsInH[i].right-hasCutsInH[i].left)*(hasCutsInH[i].bottom-hasCutsInH[i].top));
      tempAreaSize[i] = (hasCutsInH[i].right-hasCutsInH[i].left)*(hasCutsInH[i].bottom-hasCutsInH[i].top);
    }
    double tempDelta = delta(tempAreaSize,cutSize+1);
    // printf("has cut nums %d,tempDelta %lf\n", cutSize,tempDelta);
    if(tempDelta<*out){
      *out = tempDelta;
      memcpy(outRect,hasCutsInH,sizeof(Rect)*(cutSize+1));
    }
    // *out = MIN(*out,tempDelta);
    return;
  }
  // 当前被切割的方块
  Rect cutRect;
  cutRect.left = full.left;
  cutRect.top = full.top;

  // 竖着切
  for(int y=full.top+1;y<full.bottom;y++){
    cutRect.bottom = y;
    cutRect.right = full.right;

    Rect restRect = {full.left,cutRect.bottom,full.right,full.bottom};
    Rect hasCutsInH[cutSize+1];
    memcpy(hasCutsInH,cutRects,sizeof(Rect)*cutSize);
    hasCutsInH[cutSize] = cutRect;
    cut(restRect,cutTime-1,hasCutsInH,cutSize+1,out,outRect);
  }
  // 横着切
  for(int x=full.left+1;x<full.right;x++){
    cutRect.bottom = full.bottom;
    cutRect.right = x;

    Rect restRect = {cutRect.right,full.top,full.right,full.bottom};
    Rect hasCutsInH[cutSize+1];
    memcpy(hasCutsInH,cutRects,sizeof(Rect)*cutSize);
    hasCutsInH[cutSize] = cutRect;
    cut(restRect,cutTime-1,hasCutsInH,cutSize+1,out,outRect);
  }
}

// 计算平均数
// a:数组  num:数组长度
double avg(int a[],int num){
  double sum = 0.0;
  for(int i=0;i<num;i++){
    sum +=a[i];
  }
  return sum/num;
}
// 计算方差
// a:数组  num:数组长度
double delta(int a[],int num){
  double avgNum = avg(a,num);
  double sum = 0;
  for(int i=0;i<num;i++){
    sum +=pow(a[i]-avgNum,2);
  }
  return sqrt(sum/num);
}

上面代码最重要的就是cut函数中的两个for循环,递归寻找所有可能。

四、测试

第一次测试

现需切割8*8方格,保证各个小块的面积方差最小。请输入切割次数(1-->14):
2

最小的方差为: 1.885618
其中一种最佳的切割方案为:
方块1 :坐标区间为 left 0, top 0,right 8,bottom 3,方块面积为 24
方块2 :坐标区间为 left 0, top 3,right 4,bottom 8,方块面积为 20
方块3 :坐标区间为 left 4, top 3,right 8,bottom 8,方块面积为 20

第二次测试

现需切割8*8方格,保证各个小块的面积方差最小。请输入切割次数(1-->14):
3

最小的方差为: 0.000000
其中一种最佳的切割方案为:
方块1 :坐标区间为 left 0, top 0,right 8,bottom 2,方块面积为 16
方块2 :坐标区间为 left 0, top 2,right 8,bottom 4,方块面积为 16
方块3 :坐标区间为 left 0, top 4,right 8,bottom 6,方块面积为 16
方块4 :坐标区间为 left 0, top 6,right 8,bottom 8,方块面积为 16

五、总结

做了很久,还是搞定了。期间学到的最重要的是memecpy拷贝对象。



打赏作者

发表评论

电子邮件地址不会被公开。 必填项已用*标注