9911请你编程

Author: 卜天明 Date: 2000年 第2期

#1    9911请你编程
  读者朋友们新年好!《请你编程》又与你们见面了。《请你编程》得到了广大朋友的关心和支持,我在这里表示衷心的感谢。《请你编程》是一个读者朋友直接参与的栏目,是一个体现自我的园地,希望有编程愿望的朋友,无论是编程高手,还是初学者都能参与进来,我们将会认真对待每一份作品。下面请看本期重庆读者杨先飞的解法。
  9911请你编程解题思路
  将蜂窝形分成12个区域,如^02020401a^1:蜂房1为区域0;直线2-9-22为区域8;直线3-11-25为区域9;直线4-13-28为区域10;直线5-15-31为区域11;直线6-17-34为区域12;直线7-19-37为区域7;区域7与区域8之间为区域1,区域8与区域9之间为区域2,区域9与区域10之间为区域3,区域10与区域11之间为区域4,区域11与区域12之间为区域5,区域12与区域7之间为区域6。
    然后对每个小六边形定义如^02020401b^2:
  最后,求出与number1的边1相邻的六边形,再求出与该六边形的边1相邻的六边形,以此类推,然后求与number2的边1相邻的六边形,再检查此六边形number1是否已求出,如果还没有求出,就继续计算下一个六边形,然后再次判断……。最后在计算出的路径中选择出最短路径。程序使用Turbo C++ 3.00调试通过。
  源程序
  #include <stdio.h>
  #include <iostream.h>
  #include <stdlib.h>
  #include <conio.h>
  int cal_loca(int number)// 计算number所处的层数
  { int loca=2,tmp=2;
   while(number>=tmp) {tmp=tmp+(loca-1)*6;loca++;}
   return --loca;}
  int cal_start(int loca)// 计算loca层的开始数字,参数loca为number所处的层数
  { if(loca<3) return loca;int i=3,start=2;
   for(;i<=loca;i++) start=start+(i-2)*6;return start;}
  int which_seg(int number)//计算number位于哪条边上
  { if(number==1) return 0;
   int start,loca,a[6],i;loca=cal_loca(number);start=cal_start(loca);
   a[0]=start+loca*6-7;a[1]=start+loca-2;
   for(i=2;i<6;i++) a[i]=a[i-1]+loca-1;
   for(i=0;i<6;i++) if(number==a[i]) return i+7;
  for(i=1;i<6;i++) if(number<a[i]) return i;return 6;}
  int cal_round(int number,int which)//计算number的第which边相邻的数字
  { if(number==1) return which+1; //区域0(即number=1)时
   int next_start,pre_start,dis,loca,seg,start;
  loca=cal_loca(number);next_start=cal_start(loca+1); pre_start=cal_start(loca-1);
   start=cal_start(loca);dis=number-start;seg=which_seg(number);
   if(seg<7) //区域1--6时
  { if(seg==which) return next_start+dis+seg;
  if(which==(seg-1>0?seg-1:6)) return next_start+dis+seg-1;
  if((seg==6?1:seg+1)==which) return number+1;
  if((which<seg?which+6-seg:which-seg)==4) return (dis==0?number+loca*6-7:number-1);
  if((which<seg?which+6-seg:which-seg)==2) return pre_start+dis+1-seg;
  return pre_start+(dis<1?loca*6-13:dis-seg);}
  if(seg==7) //区域7时
  switch(which) {
  case 1: return number+1;
  case 4: return number-1;
  case 2: return start;
  case 3: return start-1;
  case 5: return (loca==2?7:next_start+loca*6-2);
  case 6: return next_start+loca*6-1;}
  if((seg-(which==1?7:which))==5) return number+1;
  if((seg-(which<4?which+6:which))==3) return (dis==0?7:number-1);
  if((seg-(which==6?0:which))==8) return next_start+dis+(which==6?0:which);
  if((seg-which)==7||(seg-which)==6) return next_start+dis+which;
  return (loca==2?1:pre_start+dis-(which<3?which+3:which-3));}
  int is_reach(int *tmp_num1,int tmp2,int max_step)// 检查是否找到路径
  { int i;
   for(i=0;i<max_step;i++)
   if(tmp2==tmp_num1[i]) return i;//找到
   return max_step+1; //没找到}
  int cal_step(int*tmp_num1,int*tmp_num2,int max_step)// 寻找两个数字之间的最短路径
  { int path1,path2,i,step=max_step,step1;
   for(path1=1;path1<7;path1++)
   { for(i=1;i<max_step;i++)
   tmp_num1[i]=cal_round(tmp_num1[i-1],path1);
   if((step1=is_reach(tmp_num1,tmp_num2[0],max_step))<step) step=step1;
   for(path2=1;path2<7;path2++)
   { for(i=1;i<max_step;i++)
   { tmp_num2[i]=cal_round(tmp_num2[i-1],path2);
   step1=is_reach(tmp_num1,tmp_num2[i],max_step)+i;
   if(step1<step) step=step1;}}}
   return step;}
  void main(void) // 主程序
  { int loca1,loca2,max_step,i,loop,c,number1,number2,*tmp_num1,*tmp_num2;
   FILE * handle;clrscr();
   if((handle=fopen("network.txt","r"))==NULL)
   { cout<<"\nCan't open file network.txt!"; exit(1);}
   fscanf(handle,"%i",&loop);
   for(i=0;i<loop;i++)
   { fscanf(handle,"%i%c%i",&number1,&c,&number2);
   loca1=cal_loca(number1);loca2=cal_loca(number2);
   max_step=(loca1>loca2?loca1:loca2)*2+1;//两点之间的最大步数不超过 max_step tmp_num1=(int*)malloc(sizeof(int) *max_step);tmp_num2=(int*)malloc(sizeof(int) *max_step);
   tmp_num1[0]=number1;tmp_num2[0]=number2;cout<<number1<<" to "<<number2<<" need ";
   cout<<cal_step(tmp_num1,tmp_num2,max_step)<<" steps.\n";
   free(tmp_num1);free(tmp_num2);}
   fclose(handle);}
  2000.1请你编程题目
  有一家工厂生产一种产品,这种产品呈立方体。它的高度都为h,但底面有1×1,2×2,3×3,4×4,5×5,6×6这六种系列。现在有一种高为h,底面为6×6的箱子来装这些产品。为了节约成本,一个箱子应装尽可能多的产品。请你编程解决至少要用多少箱子来装这些产品。
  输入:输入文件为packets.txt;输入文件有若干行,每一行有6个用空格分隔的整数;这6个整数分别表示底面从1×1到6×6每种系列产品的数量
  输出:输出的每一行对应于输入文件中该行,表示至少要用多少箱子来装这些产品,如:
  输入:
  0 0 4 0 0 1
  7 5 1 0 0 0
  0 0 1 1 0 0
  输出:
  2
  1
  2
  本期题目由上海的卜天明提供。