| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 6246 人关注过本帖
标题:广泛版的倒水问题如何实现
只看楼主 加入收藏
ASCIIhaohe
Rank: 1
等 级:新手上路
帖 子:11
专家分:7
注 册:2016-5-3
结帖率:0
收藏
已结贴  问题点数:20 回复次数:3 
广泛版的倒水问题如何实现
倒水问题:
有几个容量不全相等的杯子,一部分杯子里有一定量的水,要求通过有限次倒水使各杯子里的水达到一定量。
倒水规则:
每次倒水都要把本杯子的水倒完或者把被倒杯子倒满。
要求:
输入 杯子个数,容量,初始水量和末水量。//例如杯子数4,容量21 11 8 5,出事水量21 0 0 0,末水量7 7 7 0
输出 倒水步骤或者无解。

这个问题困扰我好几天了,一直没有想到解决方法,在百度贴吧还有各种c++交流群里都问了,新手不会,大神不理
搜索更多相关主题的帖子: 百度贴吧 如何 
2016-05-03 15:41
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:20 
粗暴的遍历,代码写得不好,仅供参考
程序代码:
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编辑过]

2016-05-04 13:22
ASCIIhaohe
Rank: 1
等 级:新手上路
帖 子:11
专家分:7
注 册:2016-5-3
收藏
得分:0 
回复 2楼 rjsp
我复制下来粘贴到我的code block里,编译报错了。。。
||=== Build file: "no target" in "no project" (compiler: unknown) ===|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|1|error: variable or field 'pour' declared void|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|1|error: 'size_t' was not declared in this scope|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|1|error: expected primary-expression before 'const'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|1|error: expected primary-expression before 'const'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|1|error: expected primary-expression before 'const'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp||In function 'int main()':|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|9|error: 'pour' was not declared in this scope|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp||In function 'void pour(size_t, const unsigned int*, const unsigned int*, const unsigned int*)':|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|27|error: template argument for 'template<class> class std::allocator' uses local type 'pour(size_t, const unsigned int*, const unsigned int*, const unsigned int*)::foo'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|27|error:   trying to instantiate 'template<class> class std::allocator'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|27|error: template argument 2 is invalid|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|27|error: invalid type in declaration before '(' token|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|28|error: invalid types 'int[int]' for array subscript|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|29|error: invalid types 'int[int]' for array subscript|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|30|error: invalid types 'int[int]' for array subscript|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|31|error: invalid types 'int[int]' for array subscript|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|35|error: request for member 'size' in 'a', which is of non-class type 'int'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|37|error: invalid types 'int[size_t {aka unsigned int}]' for array subscript|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|39|error: template argument for 'template<class> class std::allocator' uses local type 'pour(size_t, const unsigned int*, const unsigned int*, const unsigned int*)::foo*'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|39|error:   trying to instantiate 'template<class> class std::allocator'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|39|error: template argument 2 is invalid|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|39|error: invalid type in declaration before ';' token|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|40|error: invalid types 'int[size_t {aka unsigned int}]' for array subscript|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|41|error: request for member 'push_back' in 'ret', which is of non-class type 'int'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|41|error: invalid types 'int[size_t {aka unsigned int}]' for array subscript|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|53|error: template argument for 'template<class> class std::allocator' uses local type 'pour(size_t, const unsigned int*, const unsigned int*, const unsigned int*)::foo*'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|53|error:   trying to instantiate 'template<class> class std::allocator'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|53|error: template argument 2 is invalid|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|53|error: invalid type in declaration before 'itor'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|53|error: expected ';' before 'itor'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|53|error: 'itor' was not declared in this scope|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|53|error: request for member 'rbegin' in 'ret', which is of non-class type 'int'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|53|error: request for member 'rend' in 'ret', which is of non-class type 'int'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|53|error: expected ')' before ';' token|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|53|error: 'itor' was not declared in this scope|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|64|error: invalid types 'int[size_t {aka unsigned int}]' for array subscript|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|66|error: invalid types 'int[size_t {aka unsigned int}]' for array subscript|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|68|error: invalid types 'int[size_t {aka unsigned int}]' for array subscript|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|68|error: invalid types 'int[size_t {aka unsigned int}]' for array subscript|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|70|error: invalid types 'int[size_t {aka unsigned int}]' for array subscript|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|84|error: request for member 'size' in 'a', which is of non-class type 'int'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|85|error: invalid types 'int[size_t {aka unsigned int}]' for array subscript|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|89|error: request for member 'push_back' in 'a', which is of non-class type 'int'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|90|error: request for member 'back' in 'a', which is of non-class type 'int'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|91|error: request for member 'back' in 'a', which is of non-class type 'int'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|92|error: request for member 'back' in 'a', which is of non-class type 'int'|
C:\Users\guokelu\Documents\code blocks\texe\daoshui.cpp|93|error: request for member 'back' in 'a', which is of non-class type 'int'|
||=== Build failed: 45 error(s), 0 warning(s) (0 minute(s), 1 second(s)) ===|
2016-05-05 12:41
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9025
专家分:54030
注 册:2011-1-18
收藏
得分:0 
#include <stddef.h>
2016-05-05 12:46
快速回复:广泛版的倒水问题如何实现
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.074823 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved