C程序设计例解

    在程序设计过程中，类似于解决其它复杂的智力问题，我们使用推测、直觉、技巧、灵感和经验在内的各种技巧和技术，最经常使用的工具是抽象技术。一般地，在开始阶段，因还未了解问题的全部细节和求解的方法，主要问题集中于对问题的求解方案的全局作出决策，设计出大概的求解步聚，这是非常抽象的算法。其中有许多细节还不明确，只是用结构化的控制结构将若干抽象的计算步聚有机地联系起来。在抽象的计算步聚中，只是确定了计算的目标，而所指的操作对象和数据结构通常还是未确定的。以计算目标为线索，对抽象计算步聚作进一步的深入考虑，可能会引入数据结构和操作对象，并给也更详细的计算过程的描述。其中也许依旧包含有某些抽象计算步聚，但与原来的计算步聚相比，在规模及难度上已有所降低。对新产生的抽象计算步聚作进一步的深入考虑和分解，如此循序渐近，计算步聚、操作对象和数据结构会越来越明确，抽象的东西会越来越少，直至有关细节都已确定后设计过程才算结束，随后的工作是程序编码。
由此看来，程序设计的开始阶段最重要的就是确定算法和使用何种数据结构，只要这个过程完成得很好，随后的程序代码编写工作也就会很轻松了。所以学习时要从例子中得到启发，了解如何设计算法、设计数据结构、最终编出程序或函数的设计过程。

------------------------------------------------------------------------------------------

01. 试按以下给出的基数排序算法思想为整数链表编写一个排序 函数
解：
基数排序是按表元键值的各位值进行排序。
设有一个整数链表，其中表元的键值为不超过三位数的整数，不妨设键值形式ABC。其中A表示键值的百位数，B为十位数，C为个位数。首先按键值中的个位值C对链表作分拆和链接，先把链表分拆成多至10个队列链表，然后以C的值从0至9的顺序把分拆后的十个队列链表重新收集成一个链表。接着依次对键值中的B和A进行同样的分拆和链接操作，则最后收集起来的链表是按键值从小到大排序链接的。如有一个链表按它们的键值其表元的链接顺序依次为：
153 678 56 288 457 653 721 876 433 254
按它们的键值的个位分拆，得到十个队列链表，列出它们的键值顺序有：
0： 空链表
1： 721
2： 空链表
3： 153 653 433
4： 254
5： 空链表
6： 56 876
7： 457
8： 678 288
9： 空链表
顺序将它们收集一起后，链表的键值顺序有：
721 153 653 433 254 56 876 457 678 288
再按它们键值的十位分拆，得到十个队列链表，列出它们的键值顺序有：
0： 空链表
1： 空链表
2： 721
3： 433
4： 空链表
5： 153 653 254 56 457
6： 空链表
7： 876 678
8： 288
9： 空链表
顺序将它们收集在一起后，链表的键值顺序有：
721 433 153 653 254 56 457 876 678 288
再按它们键值的百位分拆，得到十个队列链表，列出它们的键值顺序有：
0： 56
1： 153
2： 254 288
3： 空链表
4： 433 457
5： 军分区边表
6： 653 678
7： 721
8： 876
9： 空链表
顺序将它们收集一起后，链表的键值顺序有：
56 153 254 288 433 457 653 678 721 876
这是一个按键值从小到大链接的链表。
基数排序主要包含以下控制过程，主循环控制对键值顺序从低位高位的重复操作，在主循环内包含两个计算步聚：按键值的当前位置分拆链表为十个队列链表，将对应0至9的十个队列链表收集成一个链表。用算法形式描述其计算过程如下：
算法--基数排序
{
依次对键值的个位到高位逐位循环
{
按键值的当前位将链表分拆成十个队列链表；
按对应0至9的顺序将十个链表收集成一个链表；
}
}
由于分拆时，当前表元接在对应值的队列链表的末尾，为了便于为每 个队列链表接入新表元，除每个队列链表有首指针外，还应为每个队列链表引入末表元指针。又为了能方便处理十个队列，十个队旬的头和尾指针又分别构成两个指针数组。按对应值0至9 的顺序将十个链表收集成一个链表的工作只要将空链表除外，顺序将这些链表的首尾链接即可。另外，编写函数需要知道链表的首指针，但排序后链表中各表元的链接顺序会改变，原来的首表元可能不再是首表元，即链表的首指针也会改变，所以函数的参数应为链表首指针的指针。
程序代码如下：
#include<stdio.h>
#include<stdlib.h>
#define KEYN 3
struct ele{
int key;
struct ele *link;
};
void basesort(struct ele **h)
{
int i,j,factor;
struct ele *head[10],*tail[10],*p,*u;
/*依次对键值的个位到高位逐位循环*/
for(i=0,factor=1,p=*h;i<KEYN;factor*=10,i++)
{
/*按键值的当前值将链表分拆成十个队列链表*/
for(j=0;j<10;j++) /*预置十个空链表*/
head[j]=NULL;
while(p)
{ /*将*p接到某队列链表*/
u=p->link; /*保护下一个表元的指针*/
j=(p->key/factor)%10; /*求表元键值的当前位*/
if(head[j]==NULL) /*按当前位值将*p接在对应队列的末尾*/
head[j]=p;
else
tail[j]->link=p;
tail[j]=p;
p->link=NULL;
p=u; /*准备访问下一表元*/
}
/*将十个队列链表链接成一个链表*/
p=NULL;
for(j=0;j<10;j++)
{
if(head[j]==NULL)continue; /*跳过空链表*/
if(p==NULL)p=head[j];
else u->link=head[j]; /*各链表首尾顺序链接*/
u=tail[j];
}
}
*h=p;
}
int a[]={35,298,832,932,38,635,22,15,48};
#define N sizeof a/sizeof a[0]
void main()
{
struct ele *h,*u;
int i;
h=NULL; /*先形成一个空链表*/
for(i=0;i<N;i++)
{ /*任意形成一个链表*/
u=(struct ele *)malloc(sizeof(struct ele));
u->key=a[i];
u->link=h;
h=u;
}
basesort(&h); /*排序*/
for(u=h;u;u=u->link) /*顺序输出链表各表元的链值*/
printf("%4d",u->key);
printf("/n");
}

程序运行结果为：
15 22 35 38 48 298 635 832 932

从上面的s[]表查得：
50=1*1+7*7=5*5+5*5
65=1*1+8*8=4*4+7*7
所以50是两对自然 平方和的最小者。要寻找的产生候选者的规则就是要寻找一个方法，使枚举产生的候选者(自然数对)的平方和构成以下数列：
2 5 8 10 13 ... 45 50 50
仔细考查表中s[i][j]与i和j，不难发现有以下性质：
1) s[i][j]>s[i][k],对于所有的i，当j>k
2) s[i][j]>s[k][j],对于所有的j，当i>k
3)s[i][j]=s[j][i]
因问题将自然数对(i,j)和(j,i)视为同一个自然数对，所以只需考虑i>=j的情况，性质1)说明对于表中的每一行，应从左到右逐个考查，且没有必要保存一整行的候选者供选择，一行只要保存一个已足够。当某行的当前候选者已被确认不是解时，则可生成该行的下一个候选者，等候被考虑。
由以上分析，可用下面的两个一维数组表示当前正在考虑的状态：
int s[?],j[?];
其中？意指数组的大小还未确定。数组j[]的成份j[k]表示s表中的第k行当前待考虑的列号。所以，s[]和j[]有关系：
s[k]=k*k*k+j[k]*j[k]*j[k]
将以上分析结果反映到找解方法中，原先的找解算法可改写成如下形式：
{
for(k=1;k<?;k++)
{ /*每行都从第一列一始考查*/
j[k]=1;
s[k]=k*k*k+1;
}
i=1; /*最初候选者在第一行*/
do
{
min=s[i];i0=i;j0=j[i];
为i行设定下一个候选者存入s[i];
在s[]中找最小的候选者为正式候选者，并将找到的位置存于i中；
}while(s[i]!=min);
printf("%d=%d^3+%d^3=%d^3+%d^3/n",min,i0,j0,i,j[i]);
}
按上述算法编写程序还有两处不足，需进一步确定或调整：一是为个数不确定的数组s[]和j[]送初值；另一个是个数不确定的候选者中选正式候选者。由性持，由性质2)，引入当前考虑的行的范围，最大行ih和最小行il，其中ih是指有j[k]为1的最小下标k，因为当前还不可能在ih行之后选到最小的s[i]，所以置初值和选最小元可局限于k<=ih的s[k]中进行。另外,当j[i]=i时，因对s表的考查只限于它的左下角，所以对该行的进一步考查应放弃。利用这个事实，程序可引入il表示s表的当前行范围的下界。于是置初值、寻找局限于s表的il 行到 ih行之间。每当j[i]=i时，il增1；每当j[i]=1时,ih增1,并同时设定s[ih]和j[ih]的初值。
再次把上述思想反映到算法中，找解算法又可改写成如下形式：
算法--找一个最小的自然数x，使它等于不同的两对自然 的三次幂之和
{
il=1;ih=1; /*首先只局限于第一行*/
j[1]=1;s[1]=2;i=1;
do
{
min=s[i];i0=i;j0=j[i];
if(j[i]==1)
{ /*调整ih,并为j[ih]与s[ih]设定初值*/
ih++;
j[ih]=1;
s[ih]=ih*ih*ih+1;
}
if(j[i]==i)il++; /*调整il*/
else
{ /*为i行设定下一个待候选者*/
j[i]++;
s[i]=i*i*i+j[i]*j[i]*j[i];
}
/*以下确定新的i，使得s[i]=min(s[il],...s[ih])*/
i=il;
for(k=il+1;k<=ih;k++)
if(s[k]<s[i])i=k;
}while(s[i]!=min(;
printf("%d=%d^3+%d^3=%d^3+%d^3/n",min,i0,j0,i,j[i]);
}
以上算法可作为最后的算法，下面的程序作了必要的优化，避免反复计算一个整数的三次幂。引入数组p[]，其中p[i]存储i*i*i。

程序代码如下：
#include<stdio.h>
#define N 50
void main()
{
int i,il,ih,i0,j0,min,k;
int j[N],s{n],p[N];
il=1;ih=1;j[1]=1;
p[1]=1;s[1]=2;i=1;
do
{
min=s[i];i0=i;j0=j[i];
if(j[i]==1)
{
ih++;p[ih]=ih*ih*ih;
j[ih]=1;s[ih]=p[ih]+1;
}
if(j[i]==i) il++;
else{
j[i]++;
s[i]=p[i]+p[j[i>;
}
i=il;
for(k=il+1;k<=ih;k++)
if(s[k]<s[i]) i=k;
}while(s[i]!=min&&ih!=N);
if(s[i]==min)
printf("%d=%d^3+%d^3=%d^3+%d^3/n",min,i0,j0,i,j[i]);
else printf("The %d is too small./n",N);
}

程序运行结果如下：

1729=10^3+9^3=12^3+1^3

03. 找一个最小的自然数，使它等于不同的两组三个自然数的三次幂之和，即找最小的x，使得：
x=a*a*a+b*b*b+c*c*c+d*d*d+e*e*e+f*f*f
其中，a,b,c,d,e,f都是自然数,a<=b<=c<=d<=e<=f; [a,b,c]!=[d,e,f]
解：
利用上一问题的求解思想，上一问题在正方形平面下三角区内找解，本题在正立方体的下三角棱内找解。记i为三角棱体的平面，j为某平面的行，k为某行上的列。当前考察的下三角棱体的范围由最上平面至最下平面控制；对应每个平面的下三角区域，在每个下三角区域内当前待考查的行可由行的下界和上界控制，每个有效行上的候选列由其当前列来表示。因此有如下解法：
算法---找一个最小的自然数x，使它等于不同的两组三个自然数的三次幂之和
{
以三角棱体的顶点为最初候选者；
为最初寻找平面设定行的变化范围和列的初值；
do
{
保存上一个候选者；
if(当前候选者在最下平面)
{
寻找平面范围的最下平面向下进一层；
为新平面设定行的变化范围；
}
if(在最上平面最下角点找到候选者)
寻找平面范围的最上平面向下进一层；
else
{
if(在第一列找到候选者)
{
当前平面的行的变化上增1；
置当前平面的最高行的列为1；
}
if(在对角线上找到候选者)
当前平在的行的变化下界增1；
else
调整当前平面当前行的列号值；
}
在当前最上平面至当前最下平面范围内寻找最小值的候选者；
}while(两候选者对应的值不相等);
输出解；
}
因每个平面有行变化的下界和上界，程序分别用两个一维数组来存贮；每个平面的每行都有一个当前列，程序用一个二维数组来存贮；为避免反复计算一个整数的三次幂，另引入一个一维数组，对应第i下标位置存贮i*i*i。令当前找到的候选者为i1,j1,k表示在i1平面的第j1行的k1列找到的候选者。因候选者限制在三角棱内，i1,j1,k1满足条件：
i1>=j1>=k1
当候选者在最下平面时，则最下平面向下进一层，并为新平面设定行的变化范围和对应列号；当前最上平面的最下角点找到候选者时，最上平面向下进一层；当在第一列找到候选者时，当前平面的行的上界增，并为新的行设定初始列号；当在某行的对角线上找到候选者时，该行不应该再被考虑，当前平面的行的下界增1；其它情况，当前行的下一列将会被考虑，为该行调整当前列。在调整当前平面的行的下界和上界时，应不能超过当前平面号。为在三角棱体的当前有效平面内找最小值的候选者，先假定最上平面的最小行的当前列为下一个候选者，然后自最上平面至最下平面，每个平面自最小行至最大行，寻找最小值所在平面号、行号和列号。

程序代码如下：
#include<stdio.h>
#define N 100
void main()
{
int i,j,il,ih,i0,j0,k0,i1,j1,k1;
int jl[N],jh[N]; /*第i层平面的行的变化范围，自jl[i]至jh[i]*/
int k[N][N]; /*第i层平面中，对应行j，当前的列号值为k[i][j]*/
int p[N], min; /*p[i]=i*i*i*/
i1=1;j1=1;k1=1; /*首先只局限下三角棱体的顶点*/
il=1;ih=1; /*预置i的变化范围初值il<=i<=ih*/
jl[1]=1;jh[1]=1; /*对应i层平面的行的变化范围*/
k[il][jl[il>=1; /*第i层平面中，对应行的列的初值*/
p[1]=1;
do
{
min=p[i1]+p[j1]+p[k1];
i0=i1;j0=j1;k0=k1;
if(i1==ih) /*当前候选者在ih平面，则ih增1*/
{
ih++;
p[ih]=ih*ih*ih;
/*为ih平面设定j的变化范围和对应k值*/
jl[ih]=1;jh[ih]=1;k[ih][1]=1;
}
if(i1==il&&j1==il&&k1==il)
il++; /*在il平面最下角点找到候选者，il增1*/
else
{
if(k1==1&&jh[i1]<i1)
{ /*在第一列找到候选者，i1平面的行的上界增1*/
jh[i1]++;
k[i1][jh[i1>=1;
}
if(k1==j1&&jl[i1]<i1)
jl[i1]++; /*在对角线上找到候选者，il平面的行的下界增1*/
else
k[i1][j1]++; /*调整i1平面当前行的列号*/
}
i1=il; /*预定最上平面的最小行的当前列为下一个候选者*/
j1=jl[i1];
k1=k[i1][j1];
for(i=il;i<=ih;i++) /*寻找最小值所在平面号、行号和列号*/
{
for(j=jl[i];j<=jh[i];j++)
if(p[i]+p[j]+p[k[i][j><p[i1]+p[j1]+p[k1])
{
i1=i;j1=j;k1=k[i][j];
}
}
}while(p[i1]+p[j1]+p[k1]!=min&&ih!=N);
if(p[i1]+p[j1]+p[k1]==min)
printf("%4d=%2d^3+%d^3+%d^3=%2d^3+%d^3+%d^3/n",min,i0,j0,k0,i1,j1,k1);
else printf("The %d is too small./n",N);
}

程序运行结果如下：
251 = 5^3 + 5^3 + 1^3 = 6^3 + 3^3 + 2^3

04. 试从含有n个int型数的数组中删去若干个成分，使剩下的全部成分构成一个不减的子序列。设计算法和编写程序求出数组的不减子序列的长。
解：
从数组的第一个元素开始，顺序考察数组的每个元素，当数组的全部元素都被考察后才能求出数组的最长不减子序列的长。设数组为b[]，已考察了b[0]至b[i-1]的全部元素，求得当前最长的不减子序列长为k。当前正要考察b[i]是否会引起k值增大，依赖于b[i]是否会大于或等于b[0]至b[i-1]中某个最长不减子序列的终元素.b[0]至b[i-1]中可能有多个长为k的不减子序列。很显然，在同样长度的不减子序列中，只要保留那个子序列终元素最小的一个就足够了。如有一变量保存有在b[0]至b[i-1]中长度为k的不减子序列最小的终元素，这样在b[0]至b[i-1]中，是否有长度为k+1的不减子序列，依赖于b[i]是否大于等于那个长度为k的不减子序列的终元素值。
但当b[i]小于那个长度为k的不减子序列最小的终元素的值时，如果在b[0]至b[i-1]中有长度为k-1的不减子序列，且该子序列的值不大于b[i]，这时因长度为k-1的不减子序列的终元素值小于等于b[i]，就得到一个终元素更小的长度为k的不减子序列。为能发现上述可能，就得保留长度为k-1的不减子序列的终元素。依此类推，为保留长为k-2,k-3等的不减子序列，相应地也要为它们保留终元素的值。为此要引入一个数组变量，设为数组a[]，其第j个元素a[j]存放长为j的不减子序列的终元素的值。显然，数组a[]中的元素也是不减的序列。利用这个性质，在考察b[i]时，就能知道a[]中哪个元素需要改变。从最长子序列至最短子序列顺序寻找终元素小于等于b[i]的长为j的子序列，因b[i]大于等于长为j的不减子序列的终元素，找到了一个终元素更小的长为j+1的不减子序列，用b[i]作长为j+1的子序列的终止元素。当j的值为k 时，已为长为k+1的子序列设定了终元素，这时最长不减子序列长k应增1。通过以上分析，得到求最长不减子序列长的算法如下：
算法---求数组b[]的最长不减子序列长
{
置最长不减子序列长k为1；
用b[0]设置长为1的子序列的终止元素；
for(i=1;i<n;i++) /*顺序至b[1]考察至b[n-1]*/
{
以子序列长为k至1的顺序寻找其终元素小于等于b[i]的长为j的子序列；
用b[i]作为长为j+1的子序列的终元素；
if(j==k)k++; /*最长不减子序列长k增1*/
}
}
程序代码如下：
#include<stdio.h>
#define N 100
int b[]={9,8,5,4,3,2,7,6,8,7,5,3,4,5,9,1};
int a[N];
#define n sizeof b/sizeof b[0]
void main()
{
int k,i,j;
a[1]=b[0];
k=1;
for(i=1;i<n;i++)
{
for(j=k;j>=1&&a[j]>b[i];j--);
a[j+1]=b[i]; /*长为j+1的子序列的终元素存贮在a[j+1]*/
if(j==k) k++; /*最长不减子序列长k增1*/
}
printf("K = %d/n",k);
}

程序运行结果如下：
k = 5
------------------
若把本问题改为求从数组中删去部分元素后的最长不减子序列，就要在求最长不减子序列长的过程中，不仅要保留各种长度不减子序列的终元素，同时要保留不减子序列的全部元素。为此，上述程序中的数组a[]应改为两维数组a[][]，其中a[][]的j行存储长为不减子序列的元素，该子序列的终元素为a[j][j-1]。在找到一个终元素更小的长为j+1的不减子序列时，除用b[i]作为j+1的子序旬的终止元素外，应同时将长为j的子序列元素全部复制到长为j+1的子序列中。直接写出程序如下：
#include<stdio.h>
#define N 100
int b[] = {9,8,5,4,3,2,7,6,8,7,5,3,4,5,9,1};
int a[N][N];
#define n sizeof b/sizeof b[0]
void main()
{
int k,i,j,m;
a[1][0]=b[0];
k=1;
for(i=1;i<n;i++)
{
for(j=k;j>=1&&a[j][j-1]>b[i];j--);
for(m=0;m<j;m++) /*长为j的子序列复制到长为j+1的子序列*/
a[j+1][m]=a[j][m];
a[j+1][j]=b[i]; /*长为j+1的终元素存贮在a[j+1][j]*/
if(j==k) k++; /*最长不减子序列长k增1*/
}
printf("K = %d/n",k);
for(j=0;j<k;j++)
printf("%4d",a[k][j]);
printf("/n");
}
程序运行结果如下：
k=5
2 3 4 5 9

05. 从n个不同价值、不同重量的物品中选取一部分，在不超过限定的总重量的前提下，使该部分的价值最大。这里假定的总重量不超过n个物品的总重量总和，且没有一样物品的重量超过限定的总重量。
解：
这个问题是求最佳解的典型例子。为找最佳解，需生成所有可能的解。在生成这些解的同时，保留一个指定意义下的当前最佳解，当发现一个更好的解时，就把这个解改为当前最佳解，并保留之。
现给出一组n个物品中找出满足约束条件的最佳解的通例。为便于构造算法，采用递归方法。构成可接受解的所有选择是通过依次考察组中的各个物品的结果，对每个物品的考察均有两种可能：或所考察的物品被包括在当前选择中，或所考察的物品不被包括在当前选择中。递归函数是描述指定物品被包括或不被包括在当前选择中的计算过程，只要指定物品被包括后重量满足约束条件，该物品被包括是应该被考虑的；仅当一个物品如不被包括也可能达到比当前最佳解所达到的总价值大时，为满足重量的限制，不把该物品包含在当前选择中也是应该被考虑的。为此，递归函数设有三个参数：指定的物品、当前选择已达到的总重量和可能达到的总价值。下面的递归算法就是考察某个物品在当前选择中是否被包括的计算过程描述。
算法---物品i在当前选择中被包括与否的递归算法
try(物品i，当前选择已达到的总重量tw，可能达到的总价值tv)
{
/*考察当前选择包含物品i的合理性*/
if(包含物品i是可接受的)
{
将物品i包括在当前解中；
if(i<n-1(try(i+1,tw+物品i的重量，tv);
else
调整当前最佳解；
将物品i从当前解中消去；
}
/*考察当前选择不包含物品i的合理性*/
if(i<n-1)try(i+1,tw,tv-物品i的价值)；
else
调整当前最佳解；
}
对当前选择而言，“包含物品i是可接受的”准则是它被包括后，有可能达到的总价值也不小于当前最佳解所达到的价值，因为如果小于的话，继续考察下去也不会产生更好的解。

程序代码如下：
#include<stdio.h>
#define N 100
double limw, /*物品的约束重量*/
totv, /*全部物品的总价值*/
maxv; /*解的总价值*/
int opts[N], /*当前最佳选择*/
cs[N]; /*当前选择*/
int n, /*物品数*/
k; /*工作变量*/
struct{
double weight; /*物品的重量*/
double value; /*物品价值*/
}a[N]; /*一组物品*/
void tryy(int i,double tw,double tv)
{
/*考察当前选择物品i的合理性*/
if(tw+a[i].weight<=limw) /*包含物品i是可接受的*/
{
cs[i]=1; /*将物品i包括在当前解中*/
if(i<n-1)tryy(i+1,tw+a[i].weight,tv);
else
if(tv>maxv)
{ /*调整当前最佳解*/
for(k=0;k<=i;k++)
opts[k]=cs[k];
maxv=tv;
}
cs[i]=0; /*将物品i从当前解中消去*/
}
/*考察当前选择不包含物品i的合理性*/
if(tv-a[i].value>maxv) /*不包含物品i是可接受的*/
if(i<n-1)
tryy(i+1,tw,tv-a[i].value);
else
{ /*调整当前最佳解*/
for(k=0;k<=i;k++)
opts[k]=cs[k];
maxv=tv-a[i].value;
}
}
void main()
{
printf("Enter number of mails./n");
scanf("%d",&n);
printf("Enter limit of weight./n");
scanf("%lf",&limw);
printf("Enter weight and value of mails./n");
for(k=0;k<n;k++)
scanf("%lf%lf",&a[k].weight,&a[k].value);
for(totv=0.0,k=0;k<n;k++)
totv+=a[k].value;
maxv=0;
for(k=0;k<n;k++)
opts[k]=cs[k]=0;
tryy(0,0,totv);
for(k=0;k<n;k++)
if(opts[k])
printf("%4d",k+1);
printf("/nTotal value = %lf/n",maxv);
}

程序运行结果如下：

    06.设有大小不等的X，Y，Z三个无刻度的油桶，分别能够盛满油X，Y，Z(例如，X=80，Y=50，Z=30)，并约定X>Y>Z。初始时，仅X油桶盛满油，Y和Z油桶为空。要求程序寻找一种最少的分油步聚，在某个油桶中分出T升油(例如T=40)。
解：
令三个油桶的盛油情况为倒油过程的状态，则倒油过程就是状态变化的过程。为了记录倒油过程，程序引入倒油状态队列，将倒油过程中产生的状态存储在队列中。队列的每个元素记录每次分油后各个油桶的分油后各个油桶的盛油量和倒油轨迹等有关信息。程序反复从队列中取出第一个还未检查过的状态，对该状态下的每个油桶判断其是否可以倒出油，及是否可以倒进油。由于油桶没有刻度，分油时只能将某个油桶倒满或倒空。程序分别按倒空或倒满两种可能的倒油动作执行不同的处理，产生新的倒油状态，为避免某个倒油状态在队列中重复出现，程序只将未曾出现过的新状态及其倒油轨迹信息存入队列中，假定程序检查了相当多的状态后，或能找到解，或能确定问题无解。

倒油程序算法如下：
算法---无刻度油桶分油
{
输入各桶容量和目标容量；
将初始状态存入倒油状态队列；
设置其它初始值；
do
{
对状态队列中第一个还未检查的元素
在还未检查完每个倒出的桶且还未找到解且还未确定无解情况下循环
if(倒出桶有油)
在还未检查完每个桶且还未找到解且还未确定无解情况下循环
if(当前桶不是倒出桶且桶还有空)
{
确定本次倒油量；
在队列中检查倒油后的结果状态是否在队列中出现；
if(结果状态不在队列中出现)
{
将结果状态和轨迹信息存入队列；
if(有桶中的油达到目标容量)
设置找到解标志；
}
}
if(还未找到解)
{
修正队列第一个还未检查过的元素指针；
if(队列中的元素都已检查过)
设置无解标志；
}
}while(还未找到解且还未确定无解)；
if(找到解)
{
根据倒油步聚的轨迹信息，形成倒油步聚序列；
输出倒油步聚序列；
}
}
倒油队列中的元素应包含下列信息：各桶的盛油量，该状态是从哪一个桶(源桶)倒向哪一个桶(目标桶)而形成的，形成该状态的元素在队列中的位置。根据以上算法编写如下程序。

程序代码如下：
#include<stdio.h>
#define N 100
#define BUCKETS 3
struct ele{
int state[BUCKETS]; /*各桶盛油量*/
int sbucket; /*源桶*/
int obucket; /*目标桶*/
int last; /*轨迹元素在队列中的下标*/
}q[N]; /*队列*/
int full[BUCKETS];
int i,j,k,found,unable,wi,wj,v,targ;
int head,tail;
void main()
{
/*输入各桶容量和目标容量*/
printf("Enter volume of buckets./n");
for(i=0;i<BUCKETS;i++)
scanf("%d",&full[i]);
/*如要检查full[0]>full[1]>full[2],相应代码在此*/
printf("Enter volume of targ./n");
scanf("%d",&targ); /*检查targ<=full[0]的代码在此*/
/*设置将初始状态存入倒油状态队列等初值*/
q[0].state[0]=full[0];
for(i=1;i<BUCKETS;i++)
q[0].state[i]=0;
q[0].sbucket=0;
q[0].obucket=0;
q[0].last=0;
found=unable=0;
head=tail=0;
do
{
/*对状态队列中第一个还未检查过的元素在还未检查完每个倒出的桶
且还未找到解且还未确定无解情况下循环*/
for(i=0;i<BUCKETS&&!found&&!unable;i++)
if(q[head].state[i]>0) /*倒出桶有油*/
/*在还未检查完每个油桶且还未找到解且还未确定无解情况下循环*/
for(j=0;j<BUCKETS&&!found&&!unable;j++)
if(j!=i&&q[head].state[j]<full[j])
{ /*当前桶不是倒出桶且桶还有空*/
/*确定本次倒油量*/
if(q[head].state[i]>full[j]-q[head].state[j])
v=full[j]-q[head].state[j];
else v=q[head].state[i];
wi=q[head].state[i]-v;
wj=q[head].state[j]+v;
/*在队列中检查倒油后的结果状态是否在队列中出现*/
for(k=0;k<=tail;k++)
if(q[k].state[i]==wi&&q[k].state[j]==wj) break;
if(k>tail) /*结果状态不在队列中出现*/
{
/*将结果状态和轨迹信息存入队列*/
tail++;
q[tail].state[i]=wi;
q[tail].state[j]=wj;
q[tail].state[3-i-j]=q[head].state[3-i-j];
q[tail].sbucket=i+1;
q[tail].obucket=j+1;
q[tail].last=head;
/*如有桶达到目标盛油量，则设置找到解标志*/
if(wi==targ||wj==targ)found=1;
}
}
if(!found) /*还未找到解*/
{
head++; /*修正队列第一个还未检查过元素指针*/
if(head>tail) /*队列中的元素都已检查过*/
unable=1; /*设置无解标志*/
}
}while(!found&&!unable); /*还未找到解且还未确定无解*/
if(found) /*找到解*/
{
/*根据倒油步聚的轨迹信息，形成倒油步聚序列*/
i=tail;
j=-1;
do /*原倒油步聚逆向链接，现改为正向链接*/
{
k=q[i].last;
q[i].last=j;
j=i;
i=k;
}while(j);
/*输出倒油步聚序列*/
for(k=q[k].last;k>=0;k=q[k].last)
{
printf("%5d to %2d:",q[k].sbucket,q[k].obucket);
for(i=0;i<BUCKETS;i++)
printf("%4d",q[k].state[i]);
printf("/n");
}
}
else printf("Unable!/n");
}

程序运行结果如下：

07. 有2*n个盒子排成一行，其中有两个相邻的空盒，有n-1个盒子有符号'A'，有n-1个盒子有符号'B'。例如，n=5，并有初始配置如下：

试编制程序，将输入的盒子排列状态按以下交换规则将全部‘A'放到全部‘B'的左边，不管相邻两空盒的位置。交换规则是任意两个非空相邻盒子的内容可移入两个空盒中，但移动时不得变更两符号的前后次序。编写程序输入初始配置后，找出达到目标要求的最少交换次数的方案。
解：
从一种盒子排列出发，将其中两个非空相邻盒子中的内容移入空盒的每一种移动，会使盒子产生新的排列状态，采用试探法穷举所有可能的移动找问题的解。首先将盒子初始排列存入移动步聚表，然后是试探和回溯循环。循环工作内容有：检查当前排列，若当前排列是要求的最终状态，则将达到该状态的移动步聚保存，并回溯去找更少移动步数的解。在试探超 过限定的深度或当前状态的所有可能移动都已试探穷尽情况下回溯；否则对当前状态取其当前移动方法产生新的后继状态存入移动步聚表，并继续向前试探。为能从某种排列出发，通过移动产生更接近目标要求的排列，对移动方法的选取作如下规定：
。掠过无意义的来回移动；
。不把两个相邻的同为符号‘A'的盒子向后移；
。不把两个相邻的同为符号‘B'的盒子向前移；
。不把两个盒子移入到这样的位置，移入后其首尾没有一个与相邻的盒子相同。
试探回溯找解算法如下：
算法---试探回溯找解
{
输入初始排列；
初始状态存入移动步聚表；
设置其它初值；
d=0; /*当前试探深，或当前状态位置*/
do
{
if(当前状态为盒子排列的终态)
{
保存解；
记录当前解的试探深度；
回溯；
if(取尽所有可能的解)break;
}
if(试探深度超过设定值，或取尽当前状态的所有选择)
{
回溯；
if(取尽所有可能的选择)break;
}
else
{
求新状态的空盒位置；
取当前状态的移动方法和当前状态；
设定当前状态的下一个移动方法；
掠过各种不希望的方法；
生成新状态；
试探深度增1；
}
}while(1);
if(找到解)
输出解；
}

程序代码如下：
#include<stdio.h>
#include<string.h>
#define N 30
#define DEPTH 15
char b[2*N+1];
struct node
{
int empty; /*两空盒的开始位置*/
char s[2*N+1]; /*盒子排列*/
int no; /*下一个移动开始的位，或称移动方法*/
}q[DEPTH]; /*移动步聚表*/
char result[DEPTH][2*N+1]; /*存放解*/
char *s;
int best,empty,i,j,n,an,bn,sn,c,d;
void main()
{
printf("/nEnter N: ");
scanf("%d",&n);
printf("Enter initial state./n"); /*输入初始状态*/
for(an=bn=sn=i=0;i<2*n;)
{
c=getchar();
if(c==' ')
{
if(sn)continue; /*强制两空白符连续出现*/
sn=1;
empty=i;
b[i++]='_';
b[i++]='_';
}
if(c=='A'||c=='a')
{
if(an==n-1)continue; /*限制A的个数*/
an++;b[i++]='A';
}
if(c=='B'||c=='b')
{
if(bn==n-1)continue; /*限制B的个数*/
bn++;b[i++]='B';
}
}
b[2*n]='/0';
strcpy(q[0].s,b); /*初始状态存入移动步聚表*/
q[0].empty=empty;
q[0].no=0;
best=DEPTH-1; /*设定试探深度*/
d=0;
do
{
for(s=q[d].s; *s!='B';s++);
for(;*s&&*s!='A';s++);
if(*s=='/0') /*当前状态为盒子排列的终态*/
{
for(j=0;j<=d;j++) /*保存解*/
strcpy(result[j],q[j].s);
best=d; /*记录当前解的试探深度*/
d--; /*回溯*/
while(d>=0&&q[d].no==2*n-1)d--;
if(d<0)break; /*取尽所有可能的选择*/
}
if(d>=best||q[d].no==2*n-1)
{
d--; /*回溯*/
while(d>=0&&q[d].no==2*n-1)d--;
if(d<0)break; /*取尽所有可能的选择*/
}
else
{
empty=q[d].empty; /*新状态的空盒位置*/
j=q[d].no++; /*取当前状态的移动方法和设定新移动方法*/
if(d>=1&&q[d-1].empty==j)continue; /*掠过来回移动*/
s=q[d].s; /*取当前状态*/
/*掠过各种不希望的移动*/
if(s[j]=='_'||s[j+1]=='_')continue;
if(j<empty&&s[j]=='A'&&s[j+1]=='A')continue;
if(j>empty&&s[j]=='B'&&s[j+1]=='B')continue;
if(empty!=0&&s[empty-1]!=s[j]&&
(empty!=2*n-2&&s[empty+2]!=s[j+1]))continue;
if(empty==0&&s[j]=='B')continue;
if(empty==2*n-2&&s[j+1]=='A')continue;
/*生成新状态*/
strcpy(q[d+1].s,q[d].s); /*形成移动后的状态*/
q[d+1].s[empty]=q[d+1].s[j];
q[d+1].s[empty+1]=q[d+1].s[j+1];
q[d+1].s[j]=q[d+1].s[j+1]='_';
q[d+1].empty=j;
for(j=0;strcmp(q[j].s,q[d+1].s);j++);
if(j<=d)continue;
q[d+1].no=0;
d++; /*试探深度增1*/
}
}while(1);
if(best!=DEPTH-1)
{
printf("/n/n");
for(j=0;j<=best;j++)
printf("%s/n",result[j]);
}
}

程序运行结果如下：