JD 1147：Jugs（一种用最少步骤求解的方法）

本文主要是介绍JD 1147：Jugs（一种用最少步骤求解的方法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

OJ题目：click here~~

题目分析：九度上这道没有要求最少步数，只要得到最后结果即可AC ， bfs ， dfs都行。最少步骤的方法肯定也能AC啦，分析如下。

输入的三个数：a,b,n;
> 由题不定方程ax+by=n必定有解
> 如果b=n，则fill B即可，否则用试探法求出这样的两组解（a1，b1）及（a2，b2），其中a1 >0，b1<0；a1是满足方程的最小正整数；a2<0，b2>0，a2是满足条件的最大负整数；
> (i)  如果|a1|+|b1|<|a2|+|b2|-1,则fill A a1次，每次fill A后,pour到B，如果B满则empty B,再将A中剩下的pour到B，这样empty B |b1|次以后，即可得解；（因为a*a1+b*b1=n）
> (ii)如果|a1|+|b1|>=|a2|+|b2|-1,则fill B b2次，每次fill B后,pour到A，如果A满则empty A,再将B中剩下的pour到A，这样经过empty A |a2|-1次以后，再将A装滿，B中剩下的就是n了；
> 
> Sample Input
> 
> 3 5 4 
> 5 7 3 
> 3x+5y=4的两组解为(2,-1),(-2,2)
> 2+1=1+2;
> 用方法II：（fill B两次，empty A 一次）
> fill B (第一次fill B)
> pour B A 
> empty A (A 滿清空A)（这里只需要清一次A，因为a2=-1）
> pour B A （B中剩下的到A）
> fill B （第二次fill B）
> pour B A （装滿 A，B中剩下的即为n）
> success 
> 
> 5x+7y=3的两组解为（2,-1）(-5,4)
> 2+1<5+4
> 用方法I：(fill A 两次empty B 一次)
> fill A （第一次fill A）
> pour A B 
> fill A （第二次fill A）
> pour A B 
> empty B 
> pour A B 
> success 

int main(){//freopen("in.txt","r",stdin) ;int i , j , n , A , B ;while(cin >> A >> B >> n){int a1 , b1 , a2 , b2 , a , b , t ;int x , y ;for(i = 1; ;i++){y = n - A*i ;if(y%B == 0 && y < 0){a1 = i ;b1 = y/B ;break ;}}for(i = -1; ;i--){y = n - A*i ;if(y%B == 0 && y > 0){a2 = i ;b2 = y/B ;break ;}}a = b = 0 ;if(abs(a1) + abs(b1) < abs(a2) + abs(b2) - 1){t = abs(b1) ;for(i = 0;i < a1;i++){puts("fill A") ;a = A ;puts("pour A B") ;if(!t) break ;if(a + b >= B){puts("empty B") ;puts("pour A B") ;t-- ;a = a + b - B ;b = 0 ;b = a ;a = 0 ;}else{b = a + b ;a = 0 ;}}}else{t = abs(a2) - 1 ;for(i = 0;i < b2;i++){puts("fill B") ;b = B ;puts("pour B A") ;if(!t) break ;if(a + b >= A){puts("empty A") ;puts("pour B A") ;t-- ;b = a + b - A ;a = 0 ;a = b ;b = 0 ;}else{a = a + b ;b = 0 ;}}}puts("success") ;}return 0 ;
}

这篇关于JD 1147：Jugs（一种用最少步骤求解的方法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---