Solution of a differential problem
Stray dog 2005.3
This is the intelligence problem that most people have played. There are two bottles of bottles that have a capacity of 8 pounds filled with wine, and another three pounds of empty bottles, using these three non-scales to give these cits to Four people drink, each person is divided into 4 pounds. Maybe we have already got a correct answer very early! However, what I want to say is that this is a very interesting question, especially today I want to use a computer to achieve this issue. It may, people who have been in contact with the game will not be unfamiliar with this problem, because this is like this, for example, chess or Wuzi chess for the best way to work, can say, you can say that you are familiar with this solution. Method, then you have to write a simple game search engine. At the same time, this problem will also see his shadow in the interview or a civil servant exam, which is why I put forward this problem!
Now let's get the problem first, first, first, we abstract him into 7 three types of bottles, which can be very intuitive. For each state, there may be several kinds of pouring methods. We choose one from it, then continue to construct the tank method until you find the way you can't finish the wine. If you can't find it anymore In the case of wine, the problem is backtrained, and the next method will continue to solve! The lower side is the core function of the inverter algorithm:
// Pouring the core function, producing a correct pouring sequence int generateresult (int Box [7], List & List_r) {if (! Isend (box)) {list list_temp; int i; i = GenAllCurrentMove (Box, list_temp); // Generate all the ways of walking method IF (i == 0) // if there is no way to return to the previous layer; {return 0;} // find all the current situation Whether it can produce the correct pouring sequence list :: item t = list_temp.begin (); for (ore; izer! = List_temp.end (); it ) {list_r.push_back (* ip); makemove Box, * ip; res = generateresult (Box, List_R); // In the current situation, all of the fooling methods are not successful, then continue the next to seek IF (res == 0) {UNMAKEMOVE (Box , * iter); // Remove the walking of the haircut ();} // If you find the solution Else Return 1;} // If the current layer is not solved, return to the upper RETURN 0;} // If you end Else Return 1;}
For all the solutions of all walking methods, you can list all possible ways:
// Generate all of the current situation, save in List_temp Int genallcurrentmove (int box [7], list & list_temp) {int count = 0; // The number of tap methods int max [7] = {8, 8, 3, 4, 4, 4, 4}; // Each bottle or human maximum capacity for (int K = 0; k <3; k ) {// current wine bottle air, continue A wine bottle IF (Box [K] == 0) Continue; // Cycle to find out the method for pouring wine from left to left, INT DET = 0; DET <7; DET ) {// If the target bottle and the original The bottle is the same, continue the next IF (DET == K) Continue; // Bottle between IF (DET <3) {// Due to 0 bottles and 1 bottle is the same properties, when a bottle is empty, Can't put the wine in another bottle to // target is dissatisfied with IF ((k == 2 || DET == 2)? 1: Box [d]> 0) && box [d] max [DET]) {PMOVE.VALUE = Max [DET] -box [DET];} / / Otherwise, else pmove.value = box [k]; pmove.from = k; pmove.to = DET; if (isvalid) {list_temp.push_back (pmove); Count ;}}}} // If you drink directly if you drink if (DET> = 3) {// If this person has not completed 4 pounds of wine IF (Box [Det] Box [K] <= 4) { Move Pmove; PMOVE.FROM = K; Pmove.to = Det; Pmove.Value = Box [K];
List_temp.push_back (pmove); count ; // From left to right, it is touched that it is still not separated from the wine, this pouring end IF (Box [Det] == 0) Break } // if} // if}} RETURN COUNT; Method: // Judging whether the current walking will generate a dead cycle or will generate a repeated backfront Int isvalid (Move & Move) {move lastmove; // The last pouring method INT TEMP [7] = {8, 8, 0, 0, 0, 0}; // Pushing Makemove (Boxes, Move) by pouring method; List :: iterator it = list_rslt.begin (); // Judgment Whether the secondary pork will result in a previous repetition, thus rear-twigs the secondary method tweak over // ); iter ) {makemove (Temp, * iter); // If generate the previously generated situation IF ((Temp [0] == Boxes [0] && temp [1] == Boxes [1] && temp [2] = = BoxES [2]) || (Temp [1] == BoxES [0] && Temp [0] == BoxES [1] && temp [2] == Boxes [2])) {UNMAKEMOVE (Boxes, Move); Return 0;} lastmove = * t;}
// Restore pour unmakemove (Boxes, Move);
// If you are back and forth, it is (lastmove.from == move.to && lastmove.to == move.from && lastmove.value == move.value) Return 0; Return 1;}
/ / Judgment whether INT isend (int box [7]) {// If the three wine bottles are empty, it means that the end of the pour is ended (Box [0] == 0 && Box [1] == 0 && Box [2] == 0) Return 1; Else Return 0;}
// Pork according to current pouring method Void Makemove (int box [move.from] - = move.value; box [move.to] = move.value;
// Cancel the last pouring Void unmakemove (int box [7], move) {box [move.from] = move.value; box [move.to] - = move.Value;
// Print output void print () {int Temp [7] = {8, 8, 0, 0, 0, 0, 0}; List :: item.begin (); cout << " / * There are two bottles of wine bottles that have a capacity of 8 pounds, and another three pounds of empty wine bottles. Four people drink, each person is divided into 4 pounds. * // n "; cout <<" Solving result / n "; cout <<" 8 8 0 0 0 0 "<< endl; // control output condition /// Count1 is the wine in all wine bottles, count2 is the original int count1, count2; count1 = 16; count2 = 0; for (iter; ore! = list_rslt.end (); ore ) {makemove Temp, * iter); count2 = Temp [0] TEMP [1] Temp [2]; if (count1! = count2) {cout << Temp [0] << "" << Temp [1] << "<< Temp [2] <<" << Temp [3] << "" << Temp [4] << "" << Temp [5] << "<< Temp [6] << Else Cout << Temp [0] << "<< Temp [1] <<" "<< Temp [2] << endl; count1 = count2;}} is the main function body:
#include
Struct Move {int from; // From there Int to; // poured into int value; // pockets}; // generated steps list, global variable List list_rslt; // Wine Wine bottle Box [0..1] represents a bottle of 8 pounds of wine, Box [2] represents wine bottle //box[3..7] represents four people Int Boxes for drinking ] = {8, 8, 0, 0, 0, 0, 0};
// Function declares ISEND (int Box [7]); Int isvalid (Int Box [7], List & list_temp); Void Makemove (int Box [7], Move & Move) void unmnkemove (int Box [7], Move & Move; Int Generateresult (int Box [7], List & List_R); void print (); void main () {
IF (generateresult (boxes, list_rslt)) {print ();} else cout << "no results!";
The results are shown in the figure:
