9911请你编程

卜天明
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
　　本期题目由上海的卜天明提供。

 