例53 螞蟻移動
問題描述
某三角形中各邊長為1的小三角形按下圖所示的方式用連續整數編號，
一只螞蟻需要從編號為M的三角形移動到編號為N的三角形，螞蟻只能通過一個三角形的邊移動到另一個三角形，不能通過頂點從一個三角形移動到另一個三角形，螞蟻通過的邊數作為螞蟻移動路線的長度，
撰寫程式計算從編號為M的三角形移動到編號為N的三角形的最短移動路線的長度，
輸入
輸入包含兩個整數M和N，范圍從1到100000000，用空格分隔，
輸出
輸出應包含最短路徑的長度，
輸入樣例
6 12
輸出樣例
3
（1）編程思路，
觀察三角形中的編號可知，每行最后一個小三角形的編號是行號的平方值，每行第1個小三角形的編號就是上一行行號的平方值加1，例如，第3行第1小三角形的編號為(3-1)*(3-1)+1=5，最后一個小三角形編號為3*3=9，利用這個規律，可以采用二分法計算出編號為X的小三角形位于圖中的第幾行第幾列，
對于題目給出的兩個小三角形M和N，要算出它們之間的行走距離，需要從一個地方按行走、按左下方向走和按右下方向走，把這三個距離都加起來就得到了行走距離，
以樣例為例進行說明，編號為M=6的三角形位于第3行，記為mr=3，距離其左端mb=6-5=1，距離其右端me=9-6=3；編號為N=12的三角形位于第4行，記為nr=4，距離其左端nb=12-10=2，距離其右端ne=16-12=4，將|nr-mr|、|nb/2-mb/2|和|nb/2-mb/2|三個絕對值加起來就是最短的行走距離，
|nr-mr|+|nb/2-mb/2|+|nb/2-mb/2|=|4-3|+|2/2-1/2|+|4/2-3/2|=1+1+1=3，
（2）源程式，
#include <stdio.h>
int abs(int x)
{
return x>0?x:-x;
}
int find(int x)
{
int left=0,right=32000,mid;
int row,col;
while (left<=right)
{
mid=(left+right)/2;
if (mid*mid<x)
{
row=mid;
left=mid+1;
}
else
{
right=mid-1;
}
}
return row+1;
}
int main()
{
int m, n, ans;
while(scanf("%d%d", &m, &n)==2)
{
int mline = find(m);
int nline = find(n);
int mbegin=(mline-1)*(mline-1)+1;
int nbegin=(nline-1)*(nline-1)+1;
int mend=mline*mline;
int nend=nline*nline;
ans = abs(nline - mline) +abs((n-nbegin)/2-(m-mbegin)/2)+
abs((nend-n)/2-(mend-m)/2);
printf("%d\n", ans);
}
return 0;
}
習題53
53-1 巢房的坐標
問題描述
蜜蜂生活在一個蜂巢里，一個蜂巢由許多六角形的小巢房組成，為描述這些巢房的位置，可以采用兩種方式，一種采用二維坐標系統，每個蜂房用2個整數表示，最中部的用（0,0）表示；另一種采用從蜂房中部的以數字1開始順時針方向編號來表示，如下圖所示，
坐標表示法 編號表示法
撰寫程式，實作從編號表示法到坐標表示法的轉換，
輸入
輸入包含一個或多個表示蜂房編號的整數，每個整數單獨排成一行，
輸出
輸出每個編號表示的蜂房的坐標表示，
輸入樣例
1
2
3
4
5
輸出樣例
0 0
0 1
-1 1
-1 0
0 -1
（1）編程思路，
首先，設由1到2的方向記為2，1到3的方向記為3……1到7的方向記為7，它們分別是：(0,1)，(-1,1)，(-1,0)，(0,-1)，(1,-1)，(1,0)；這些規律不僅對于1的周圍六個方向有效，對于所有的點都是有效的，
然后記1所在為圈0，2~7為圈1，8~19為圈2，…，以此類推，可以得到第n圈有蜂窩6n個(n>0)，
對于這個等引數列求和，Sum[1~n]=3n^2+3n，包括第0圈的1，則Sum[0..n]=3n^2+3n+1，
讀入數字x，解方程3n^2+3n+1=x， 解出來n=[sqrt(12x-3)-3]/6，
如果n為整數，則圈數p=n，否則p=(int)(n)+1，
又可以通過公式 t=x-3*sqr(p)+3*p-1 求出t（x是第n圈的第t個蜂巢），
可以發現，從上一圈的最后一點，即(p-1，0)走到目的點，首先應在2方向上走1步，再沿(-1，1)走p-1步，其余的5個方向都走p步，此外每走一次，t就要減去相應的值，當t=0時，就可以退出回圈，這樣就可以得到答案，
（2）源程式，
#include<stdio.h>
#include<math.h>
int main()
{
double x;
int n,t,p,x0,y0,i;
while (scanf("%d",&n)!=EOF)
{
x=(sqrt(12.0*n-3)-3)/6;
p=(int)x;
if (3*p*p+3*p+1!=n)
{
t=n-(3*p*p+3*p+1);
p++;
x0=p-1;
y0=0;
while(t)
{
t--;
y0++; // 先向方向2走一步
for(i=1;i<=p-1 && t;i++,t--) x0--,y0++; // 再向方向3走p-1步
for(i=1;i<=p && t;i++,t--) x0--; // 其他剩余的五個方向各走p步
for(i=1;i<=p && t;i++,t--) y0--;
for(i=1;i<=p && t;i++,t--) x0++,y0--;
for(i=1;i<=p && t;i++,t--) x0++;
for(i=1;i<=p && t;i++,t--) y0++;
}
printf("%d %d\n",x0,y0);
}
else
printf("%d 0\n",p);
}
return 0;
}
53-2 巢房之間的距離
問題描述
蜜蜂生活在一個蜂巢里，一個蜂巢由許多六角形的小巢房組成，我們將任意一個小巢房標記為數字1，然后以順時針方向標記剩余小巢房來標記這些巢房，如下圖所示，
例如，15號和19號巢房相隔4個巢房，連接兩個巢房的最短路徑之一是通過15-5-6-7-19，因此，一只蜜蜂要在這兩個巢房間移動，必須移動4次到相鄰巢房才能從15到19，
撰寫一個程式來計算任意一對巢房之間的距離，定義為最短路徑中的巢房數，
輸入
輸入由幾行組成，每行包含兩個整數a和b（a，b<=10000），表示巢房編號，除最后一行a=b=0外，整數始終為正，最后一行終止輸入，不應進行處理，
輸出
對于輸入的每對數字（a、b），輸出編號為a和b的巢房之間的距離，該距離是從a到b的最小移動次數，
輸入樣例
19 30
0 0
輸出樣例
The distance between cells 19 and 30 is 5.
（1）編程思路，
要求蜜蜂在蜂巢中從一個巢房走到另一個巢房最少的移動次數，先按上面習題53-1中的方法，將代表位置的編號數字轉換為坐標，然后求得兩個坐標之差x，y，如果x，y同號，則相加，否則取x和y絕對值最大的即可，
（2）源程式，
#include<stdio.h>
#include<math.h>
struct Point
{
int x,y;
};
Point change(int n)
{
double x;
Point pos;
int t,p,x0,y0,i;
x=(sqrt(12.0*n-3)-3)/6;
p=(int)x;
if (3*p*p+3*p+1!=n)
{
t=n-(3*p*p+3*p+1);
p++;
x0=p-1;
y0=0;
while(t)
{
t--;
y0++; // 先向方向2走一步
for(i=1;i<=p-1 && t;i++,t--) x0--,y0++; // 再向方向3走p-1步
for(i=1;i<=p && t;i++,t--) x0--; // 向其他剩余的五個方向各走p步
for(i=1;i<=p && t;i++,t--) y0--;
for(i=1;i<=p && t;i++,t--) x0++,y0--;
for(i=1;i<=p && t;i++,t--) x0++;
for(i=1;i<=p && t;i++,t--) y0++;
}
pos.x=x0;
pos.y=y0;
}
else
{
pos.x=p;
pos.y=0;
}
return pos;
}
int main()
{
int n,m,x,y,ans;
Point p1,p2;
while (scanf("%d%d",&n,&m) && n!=0 && m!=0)
{
p1=change(n);
p2=change(m);
x=p1.x-p2.x;
y=p1.y-p2.y;
if ((x<0 && y<0)||(x>0 && y>0))
ans=abs(x+y);
else
ans=abs(x)>abs(y)?abs(x):abs(y);
printf("The distance between cells %d and %d is %d.\n",n,m,ans);
}
return 0;
}
53-3 士兵排隊
問題描述
有N個士兵隨機分布在操場上，每個士兵的位置由一對（x，y）整數坐標給出，現在要求N個士兵站在同一個水平線，即所有士兵的y坐標相同并且x坐標相鄰，移動結束后，整數x和y以及士兵沿水平線的最終順序可以是任意的，但兩名或兩名以上士兵最終不得同時占據同一位置，
每個士兵在每次移動程序中，可以向上、向下、向左或向右移動一個單位（即每次移動可以將其x或y坐標加1或減1），求出所有士兵總的最少移動步數，
輸入
輸入的第一行包含整數N（1<=N<=10000），表示士兵人數，
以下N行輸入為士兵的初始位置，每行包含一對整數x[i]和y[i]（-10000<=x[i]，y[i]<=10000），由單個空白字符分隔，表示第i個士兵的坐標，
輸出
輸出為最小的移動總數，
輸入樣例
5
1 2
2 2
1 3
3 -2
3 3
輸出樣例
8
（1）編程思路，
士兵移動既涉及X分析的移動，也涉及到Y方向的移動，將它們分開討論，
1）Y方向移動，
要使所有士兵最后位于同一水平線，則最終所有士兵的y坐標相同，
將所有坐標的y值從小到大排序，將y值的中位數midY（midY=y[n/2]）作為最終的Y坐標，可使Y方向的移動步數最少，
Y方向的最小移動步數 stepsY=|y[0]-midY|+|y[1]-midY|+…+|y[n-1]-midY|，
2）X方向移動，
先對所有坐標的x值從小到大排序，由于要移動步數最少，所以最終的x坐標相對位置與排序后的x坐標相對位置相同，
設最終的x坐標起始位置為a，則
x[0] 移動到 a
x[1] 移動到 a+1， 也可以看成將 x[1]-1 移動到 a
……
x[n-1] 移動到 a+n-1 ，也可以看成將 x[n-1]-(n-1) 移動到 a
即將所有x[i]-i移動到相同位置a，由此問題轉換為和y方向上相同，重新計算x[i]=x[i]-i，再進行從小到大排序，將新的x[i]值的中位數midX（midX=X[n/2]）作為最終的a坐標，可使X方向的移動步數最少，
X方向的最小移動步數 stepsX=|x[0]-midX|+|x[1]-midX|+…+|x[n-1]-midX|，
總的最小移動步數 steps=stepsX+stepsY，
（2）源程式，
#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
int x[10001], y[10001];
int n;
scanf("%d", &n);
int i;
for (i=0;i<n;i++)
scanf("%d%d", &x[i],&y[i]);
sort(x,x+n);
sort(y,y+n);
for (i=0; i<n; i++)
x[i] -= i;
sort(x,x+n);
int midX=x[n/2];
int midY=y[n/2];
int ans=0;
for (i=0; i<n; i++)
ans += abs(x[i]-midX) + abs(y[i]-midY);
printf("%d\n", ans);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/415203.html
標籤：C