几个面试题帮看下
1.有3个容器，各是20升，13升，7升， 形状不同也不透明。一开始20升的容器里面装了20升水，反正倒来倒去最后要让20升和13升容器各装了10升水
2. 2个外形不同的瓶子，各装800毫升水，另外还有1个300毫升的杯子
现在有4个人，不限制喝的次数，想办法让每个人都正好喝到400毫升水
第一第二道题目，口头说明解法就行了
第三个题，就是从第一第二题里面随便选择一个，使用编程来求解
[解决办法]
A(20L) B(13L) C(7L)
20 0 0
13 0 7 //A==> C
13 7 0 //C==> B
7 13 0 //A==> B
7 6 7 //B==> C
14 6 0 //C==> A
14 0 6 //B==> C
1 13 6 //A==> B
1 12 7 //B==> C
8 12 0 //C==> A
8 5 7 //B==> C
15 5 0 //C==> A
15 0 5 //B ==> C
2 13 5 //A ==> B
2 11 7 //B ==> C
9 11 0 //C ==> A
9 4 7 //B ==> C
16 4 0 //C ==> A
16 0 4 //B ==> C
3 13 4 //A ==> B
3 10 7 //B ==> C
10 10 0 //C ==> A
[解决办法]
1.设A为20升容器，B为13升容器，C为13升容器，倒水的顺序如下
A(20) A(7) A(7) A(14) A(14) A(1) A(1) A(8) A(8) A(15)
B(0) -> B(13) -> B(6) -> B(6) -> B(0) -> B(13) -> B(12) -> B(12) -> B(5) -> B(5)
C(0) C(0) C(7) C(0) C(6) C(6) C(7) C(0) C(7) C(0)
A(15) A(2) A(2) A(9) A(9) A(16) A(16) A(3) A(3) A(10)
B(0) -> B(13) -> B(11) -> B(11) -> B(4) -> B(4) -> B(0) -> B(13) -> B(10) -> B(10)
C(5) C(5) C(7) C(0) C(7) C(0) C(4) C(4) C(7) C(0)
具体的倒法，一看就明白了，我不好写上去，见谅！
算法我是逆向解出的，然后正向导出，很容易描述了，自己搞吧
2. 貌似没有解，没有时间思考了，明天上班，睡觉先。看看其他人的高论。
[解决办法]
20 0 0
13 0 7
13 7 0
6 7 7
6 13 1
19 0 1
19 1 0
12 1 7
12 8 0
5 8 7
5 13 2
18 0 2
18 2 0
11 2 7
11 9 0
4 9 7
4 13 3
17 0 3
17 3 0
10 3 7
10 10 0
[解决办法]
这种题,解题技巧就是
看到这种题不要慌,相信自己一定可以解决
慢慢来,不要慌 自然就可以解出来.
[解决办法]
第1 题先将13 装 10
0 0 7
7 0 0
7 0 7
14 0 7
20 0 1
20 1 6
0 1 6
做 3 次
0 3 7
剩下 20 7 只要让 20 里有 3水就行
说下思路 3*7%20 = 1 放入 20桶 这时 20容量变为 19
3*7%19 = 2 放入 20桶 这时容量变为 18
3*7%18 = 3 再加上 7桶 = 10
[解决办法]
to：wdclyf()
A有700
B有0
C有300
C倒入A
B倒满C
C倒入A
这里好像有问题吧？？
既然B=0了，怎么还用B倒满C？？？
之前我做出来的与wdclyf()相同，但时候后面还没想好。
[解决办法]
第一题的程序，回溯法。该程序只输出一组解，且非最优解（步数最少），如想得到左右解可尝试用广度搜索。
#include <stdio.h>
struct Bottle
{
int capability;
int water;
};
struct Container
{
Bottle bts[3];
};
struct Stack
{
int t[1000][5];
int index;
};
Container con;
bool bl[21][14][8];
Stack st;
void Inital()
{
for(int i = 0; i < 21;++i)
{
for(int j = 0;j < 14;++j)
{
for(int k = 0;k < 8;++k)
{
bl[i][j][k] = false;
}
}
}
bl[20][0][0] = true;
con.bts[0].capability = 20;
con.bts[0].water = 20;
con.bts[1].capability = 13;
con.bts[1].water = 0;
con.bts[2].capability = 7;
con.bts[2].water = 0;
st.index = 0;
}
bool FindOneSolution(struct Container tcon)
{
int k;
if( tcon.bts[0].water == 10 && tcon.bts[1].water == 10 && tcon.bts[2].water == 0 )
{
return true;
}
for(int i = 0;i < 3;++i)
{
for(int j = 0;j < 2;++j)
{
k = (i + j + 1) % 3;
if( tcon.bts[i].water > 0 && tcon.bts[k].capability - tcon.bts[k].water > 0)
{
int tmp;
tmp = (tcon.bts[k].capability - tcon.bts[k].water > = tcon.bts[i].water)? (tcon.bts[i].water):(tcon.bts[k].capability - tcon.bts[k].water);
tcon.bts[i].water -= tmp;
tcon.bts[k].water += tmp;
if( bl[tcon.bts[0].water][tcon.bts[1].water][tcon.bts[2].water] == false )
{
bl[tcon.bts[0].water][tcon.bts[1].water][tcon.bts[2].water] = true;
if( FindOneSolution(tcon) )
{
st.t[st.index][0] = i;
st.t[st.index][1] = k;
st.t[st.index][2] = tcon.bts[0].water;
st.t[st.index][3] = tcon.bts[1].water;
st.t[st.index][4] = tcon.bts[2].water;
st.index++;
return true;
}
}
tcon.bts[i].water += tmp;
tcon.bts[k].water -= tmp;
}
else
{
continue;
}
}
}
return false;
}
void Print()
{
char cha[3] = { 'A ', 'B ', 'C '};
for(int i = st.index - 1 ;i > = 0;--i)
{
printf( "%d %d %d ",st.t[i][2],st.t[i][3],st.t[i][4]);
printf( "%c ",cha[st.t[i][0]]);
printf( "-> ");
printf( "%c\n ",cha[st.t[i][1]]);
}
}
int main()
{
Inital();
FindOneSolution( con );
Print();
return 0;
}
