昨日在“三思小百科” http://www.oursci.org/ency/math/002.htm看到一篇好文章。该文较详细的介绍了灌水（倒酒）问题的一般解法。根据文章提示的算法，我写了一个程序。问题和算法简介：倒水问题的经典形式是这样的：“假设有一个池塘，里面有无穷多的水。现有2个空水壶，容积分别为5升和6升。问题是如何只用这2个水壶从池塘里取得3升的水。”　　当然题外是有一些合理的限制的，比如从池塘里灌水的时候，不管壶里是不是已经有水了，壶一定要灌满，不能和另一个壶里的水位比照一下“毛估估”（我们可以假设壶是不透明的，而且形状也不同）；同样的，如果要把水从壶里倒进池塘里，一定要都倒光；如果要把水从一个壶里倒进另一个壶里，也要都倒光，除非在倒的过程中另一个壶已经满了；倒水的时候水没有损失（蒸发溢出什么的）等等等等。 算法介绍：“灌水定理”：“如果有n个壶容积分别为A1，A2，……，An（Ai均为大于0的整数）设w为另一大于0的整数。则用此n个壶可倒出w升水的充要条件为：　1)　w小于等于A1+A2+......+An；　2)　w可被(A1,A2,......,An)（这n个数的最大公约数）整除。”　这两个条件都显然是必要条件，如果1)不被满足的话，你连放这么多水的地方都没有。2)的道理和上面两个壶的情况完全一样，因为在任何步骤中，任何壶中永远只有(A1,A2,......,An)的倍数的水。如果A1，A2，……，An是n个整数，(A1,A2,......,An)=s，那么存在整数U1，U2，……，Un，使得　　　　　　　U1A1 + U2A2 + ...... + UnAn = s. 　　　(*)在代数学上称此结果为“整数环是主理想环”。回头看“灌水定理”。w是(A1,A2,......,An)的倍数，根据上节的公式(*)，两边乘以这个倍数，我们就有整数V1，V2，……，Vn使得 V1A1 + V2A2 + ...... + VnAn = w.注意到Vi是有正有负的。这就说明，只要分别把A1，A2，……，An壶，灌上V1，V2，……，Vn次（如果Vi是负的话，“灌上Vi次”要理解成“倒空-Vi次”），就可以得到w升水了。具体操作： 先求出各Vi。然后遍历所有的壶，往Vi是正数的壶里灌水，灌1次就把Vi减1。再把这些水到进Vi是负数的壶里，等某个壶灌满了，就把它倒空，然后给这个负的Vi加1，壶之间倒来倒去不变更各Vi的值。要注意的是要从池塘里灌水，一定要用空壶灌，要倒进池塘里的水，一定要是整壶的。这样一直到所有Vi都是0为止。注意：为了得到较优解，应先把Vi是负数的壶全部处理好，等到所有的壶都不能往池中倒水了，再把Vi是正数的壶里的水倒入Vi等于0的壶中。 我的程序：#include <stdio.h> #include <stdlib.h> #include <math.h>#define MAX 10 //所需壶的最大数量 int Result(int cubage[], int times[], int n);void GetElements(int cubage[], int times[], int n, int w);void GetBest(int cubage[], int times[], int temp[], int n, int w, int top, int *min);int IsStepEnd(int times[], int n);void Process(int cubage[], int times[], int n);int Sum(int cup[], int n);int CommonDivisor(int m, int n);int ComDiv(int cubage[], int n);int main(void) {     int cubage[MAX] = {0};//用来存储各壶的容积    int times[MAX] = {0};//用来存储从池中加水（或倒水）次数，正数表示加水，负数表示倒水     int n; //壶的实际数量     int d;//存储所有壶的容积的最大公约数     int w;//存储最终需要的水的数量     int i;        while (1)//可以处理多次     {        puts("请输入壶的数量(输入0结束程序)");        scanf("%d", &n);                if (n == 0)//如果输入0，结束程序             break;                puts("请输入各个壶的容积");        for (i=0; i<n; i++)            scanf("%d", &cubage[i]);                    puts("请输入最终需要的水的数量");        scanf("%d", &w);                d = ComDiv(cubage, n);//获取所有壶的容积的最大公约数                 if (Sum(cubage, n) < w || w % d != 0)//如果不满足条件，则无解         {            puts("NO");            continue;        }                //获取各个壶从池中加水（或倒水）次数，times[i]>0表示从池中加水；times[i]<0表示往池中倒水         GetElements(cubage, times, n, w);        for (i=0; i<n; i++)            printf("%d: %d\n", cubage[i], times[i]);                    Process(cubage, times, n);//输出详细操作过程     }              system("pause");      return 0; }void GetElements(int cubage[], int times[], int n, int w){    int temp[MAX] = {0};//用来存储中间结果    int min = 200; //存储最少的操作次数，初始化为200（假设操作次数不超过200）         GetBest(cubage, times, temp, n, w, 0, &min); }//计算U1A1 + U2A2 + ...... + UnAn int Result(int cubage[], int times[], int n){    int sum = 0;    int i;        for (i=0; i<n; i++)        sum += times[i] * cubage[i];            return sum;}//求满足 ∑times[i] * cubage[i] = w的最佳times[]void GetBest(int cubage[], int times[], int temp[], int n, int w, int top, int *min){        int i, sum;        if (top == n)    {        if (Result(cubage, temp, n) == w)//如果满足条件         {            sum = Sum(temp, n);//计算加（倒）水次数之和             if (sum < *min)//取加（倒）水次数之和最小的结果作为最佳结果（意味着操作次数最少）             {                for (i=0; i<n; i++)//存储最佳结果                     times[i] = temp[i];                *min = sum;            }        }    }    else//回溯寻找最佳结果     {        for (i=-50; i<51; i++)        {            temp[top] = i;//存储中间过程             GetBest(cubage, times, temp, n, w, top+1, min);        }    }}int IsEnd(int times[], int n)//判断是否已经处理完毕，处理完毕返回1，否则返回0 {    int i;        for (i=0; i<n; i++)//当所有的times[i] == 0时，表示处理完毕     {        if (times[i] != 0)            return 0;    }        return 1;}int IsStepEnd(int times[], int n)//判断是否已经把该倒水的壶处理完毕，处理完毕返回1，否则返回0 {    int i;        for (i=0; i<n; i++)//当所有的times[i] >= 0时，表示所有的壶都不再往池中倒水     {        if (times[i] < 0)            return 0;    }        return 1;}void Process(int cubage[], int times[], int n)//输出详细操作过程 {    int water[MAX] = {0};//存储各个壶当前的储水量     int count = 0;//累计操作次数     int need, fact;//need表示当前壶需要加入的水量，fact表示当前壶实际加入的水量     int i, j, k;        //输出表头     printf("step: ");    for (j=0; j<n; j++)        printf("c[%d] ", j);    for (j=0; j<n; j++)        printf("t[%d] ", j);    printf("\n");    printf("step: ");    for (j=0; j<n; j++)        printf("%3d  ", cubage[j]);    for (j=0; j<n; j++)        printf("%3d  ", times[j]);    printf("\n\n");                        while (!IsStepEnd(times, n))//一直处理，直到已经把该倒水的壶处理完毕     {        for (i=0; i<n; i++)//遍历数组，进行从池中加水和倒水操作         {            if (water[i] == 0 && times[i] > 0)//若当前壶空，且仍可以进行加水操作，则从池中加水             {                water[i] = cubage[i];                --times[i];                //输出操作步骤                 printf("%4d: ", ++count);                for (j=0; j<n; j++)                    printf("%3d  ", water[j]);                for (j=0; j<n; j++)                    printf("%3d  ", times[j]);                printf("\n");            }            if (water[i] == cubage[i] && times[i] < 0)//若当前壶满，且仍可以进行倒水操作，则往池中倒水            {                water[i] = 0;                ++times[i];                //输出操作步骤                     printf("%4d: ", ++count);                for (j=0; j<n; j++)                    printf("%3d  ", water[j]);                for (j=0; j<n; j++)                    printf("%3d  ", times[j]);                printf("\n");            }        }        //遍历数组，壶之间倒来倒去，以调整各壶的储水量         for (i=0; !IsStepEnd(times, n) && i<n; i++)        {              if (times[i] < 0)//如果当前壶仍可以进行倒水操作，则从别的壶倒水给它，等它满后就可往池中倒水了             {                for (j=0; j<n; j++)//遍历所有的壶，寻找可以倒水给cup[i]的壶，注意：可倒多次                 {                    need = cubage[i] - water[i];//计算cup[i]需要加入的水量                     if (need == 0)//如果不需要加水，退出循环                         break;                                        if (times[j] >= 0)//cup[j]不能往池中倒水了，可以把它的水倒给cup[i]                     {                        fact = water[j] < need ? water[j] : need;//计算cup[i]实际加入的水量                        water[i] += fact;                        water[j] -= fact;                                                if (fact > 0)//如果真的进行了倒水操作，则输出该过程                         {                            printf("%4d: ", ++count);                            for (k=0; k<n; k++)                                printf("%3d  ", water[k]);                            for (k=0; k<n; k++)                                printf("%3d  ", times[k]);                            printf("\n");                        }                    }                }            }         }    }        while (!IsEnd(times, n))//一直操作直至结束     {        for (i=0; i<n; i++)//遍历数组，进行从池中加水操作         {            if (water[i] == 0 && times[i] > 0)//若当前壶空，且仍可以进行加水操作，则从池中加水             {                water[i] = cubage[i];                --times[i];                //输出操作步骤                 printf("%4d: ", ++count);                for (j=0; j<n; j++)                    printf("%3d  ", water[j]);                for (j=0; j<n; j++)                    printf("%3d  ", times[j]);                printf("\n");            }        }        //遍历数组，壶之间倒来倒去，以调整各壶的储水量         for (i=0; !IsEnd(times, n) && i<n; i++)        {              if (times[i] == 0)//cup[i]不能从池中取水和倒水了，可以把其他壶中的水倒给它            {                for (j=0; j<n; j++)//遍历所有的壶，寻找可以倒水给cup[i]的壶，注意：可倒多次                 {                    need = cubage[i] - water[i];//计算cup[i]需要加入的水量                     if (need == 0)//如果不需要加水，退出循环                         break;                                        if (times[j] > 0)//若cup[j]可以从池中取水，则把它的水倒给cup[i]                     {                        fact = water[j] < need ? water[j] : need;//计算cup[i]实际加入的水量                        water[i] += fact;                        water[j] -= fact;                                                if (fact > 0)//如果真的进行了倒水操作，则输出该过程                         {                            printf("%4d: ", ++count);                            for (k=0; k<n; k++)                                printf("%3d  ", water[k]);                            for (k=0; k<n; k++)                                printf("%3d  ", times[k]);                            printf("\n");                        }                    }                }            }         }    }}//对所有壶的容积或加（倒）水次数求和int Sum(int cup[], int n){    int sum = 0;    int i;        for (i=0; i<n; i++)        sum += abs(cup[i]);//注意因为times[]的元素值有正有负，故累计次数时应取绝对值         return sum;}//返回m,n的最大公约数 int CommonDivisor(int m, int n){    int temp;        while (n > 0)    {        temp = m % n;        m = n;        n = temp;    }    return m;}//返回所有壶的容积的最大公约数int ComDiv(int cubage[], int n){    int d = cubage[0];    int i;        for (i=1; i<n; i++)        d = CommonDivisor(d, cubage[i]);        return d;}

评论