|
#2
rjsp2016-05-04 13:22
粗暴的遍历，代码写得不好，仅供参考
 程序代码：void pour( size_t size, const unsigned volume[], const unsigned initial[], const unsigned terminate[] ); int main( void ) { // 杯子数4，容量分别为21,11,8,5，初始水量分别为21,0,0,0，末水量7,7,7,0 const unsigned volume[4] = { 21, 11, 8, 5 }; const unsigned initial[4] = { 21, 0, 0, 0 }; const unsigned terminate[4] = { 7, 7, 7, 0 }; pour( 4, volume, initial, terminate ); return 0; } #include <iostream> #include <vector> void pour( size_t size, const unsigned volume[], const unsigned initial[], const unsigned terminate[] ) { struct foo { size_t parent; size_t from; size_t to; std::vector<unsigned> yield; }; std::vector<foo> a( 1 ); a[0].parent = 0; a[0].from = 0; a[0].to = 0; a[0].yield = std::vector<unsigned>( initial+0, initial+size ); const std::vector<unsigned> b( terminate+0, terminate+size ); for( size_t i=0; i!=a.size(); ++i ) { if( a[i].yield == b ) { std::vector<foo*> ret; for( size_t j=i; j!=0; j=a[j].parent ) ret.push_back( &a[j] ); std::cout << "Volu: "; for( size_t j=0; j!=size; ++j ) std::cout << '\t' << volume[j]; std::cout << '\n'; std::cout << "Init: "; for( size_t j=0; j!=size; ++j ) std::cout << '\t' << initial[j]; std::cout << '\n'; for( std::vector<foo*>::const_reverse_iterator itor=ret.rbegin(); itor!=ret.rend(); ++itor ) { const foo& f = **itor; std::cout << char('A'+f.from) << "->" << char('A'+f.to) << ": "; for( size_t k=0; k!=f.yield.size(); ++k ) std::cout << '\t' << f.yield[k]; std::cout << '\n'; } return; } for( size_t j=0; j!=a[i].yield.size(); ++j ) { for( size_t k=0; k!=a[i].yield.size(); ++k ) { if( j!=k && a[i].yield[j]!=0 && a[i].yield[k]!=volume[k] ) { std::vector<unsigned> cur = a[i].yield; if( cur[j]+cur[k] <= volume[k] ) { cur[k] += cur[j]; cur[j] = 0; } else { cur[j] -= volume[k]-cur[k]; cur[k] = volume[k]; } bool bfound = false; for( size_t m=0; !bfound && m!=a.size(); ++m ) if( a[m].yield == cur ) bfound = true; if( !bfound ) { a.push_back( foo() ); a.back().parent = i; a.back().from = j; a.back().to = k; a.back().yield.swap( cur ); } } } } } return; } 输出： Volu: 21 11 8 5 Init: 21 0 0 0 A->B: 10 11 0 0 B->D: 10 6 0 5 B->C: 10 0 6 5 D->A: 15 0 6 0 C->D: 15 0 1 5 D->B: 15 5 1 0 C->D: 15 5 0 1 A->C: 7 5 8 1 C->B: 7 11 2 1 B->D: 7 7 2 5 D->C: 7 7 7 0 [此贴子已经被作者于2016-5-4 14:14编辑过] |
有几个容量不全相等的杯子，一部分杯子里有一定量的水，要求通过有限次倒水使各杯子里的水达到一定量。
倒水规则:
每次倒水都要把本杯子的水倒完或者把被倒杯子倒满。
要求：
输入 杯子个数，容量，初始水量和末水量。//例如杯子数4，容量21 11 8 5，出事水量21 0 0 0，末水量7 7 7 0
输出 倒水步骤或者无解。
这个问题困扰我好几天了，一直没有想到解决方法，在百度贴吧还有各种c++交流群里都问了，新手不会，大神不理
