各位,来道面试题!

pure

浏览: 354389 次

最近访客更多访客>>

Franciswmf

mengxiang.com

zhezhiren

蕃薯耀

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

面试算法 J#数据结构编程

有a,b,c,d四个人,现在有三个酒杯X,Y,Z三个不规则酒杯, X,Y容量为8两,现在已装满酒,Z容量为3两,为空杯.现在要求四个人每人都能平均喝到4两酒,请说出该怎么喝?写出算法,并打印出每步X,Y,Z杯内的酒多少和四个人每人所喝的酒?

分享到：

体验了一下 playframework | StAX(Streaming API for XML) 在netbeans r ...

2008-04-28 22:04
浏览 2059
评论(21)
论坛回复 / 浏览 (21 / 14586)
分类:非技术
查看更多

21 楼 Ronald9 2009-02-18

这种还要想?

2个杯子,分别是满的,全是8两,

4个人,2人一杯,每人半杯,不就解决了?

那个3两的没用,忽悠人吗!

20 楼 jltest 2009-02-16

谁能把下面代码中的
state |= cup[i];和 state <<= 4;
转换为普通的算式么，位移不会啊

  static int makeState(int[] cup) {  
         int state = 0;  
         for (int i = 6; i >= 0; i--) {  
            state |= cup[i];  
             if (i > 0)  
                 state <<= 4;  
         }  
         return state;  
     }

19 楼 jltest 2009-02-16

牛逼。。。自己试试

18 楼 Gorden_Lam 2009-01-21

大虾们程序贴上来瞧瞧！

17 楼 pinnacle 2009-01-16

pure 写道

现在要求四个人每人都能平均喝到4两酒......

平均？？一个人全喝了，平均下来也是4两

现在要求四个人每人都喝4两酒!

16 楼 yimu 2008-08-02

zhunahao 写道

非常冒昧的问一下

2 6 3 3 2 0 0
2 8 1 3 2 0 0

这个地方，容器上面是有刻度的吗？怎么能知道从Z中是倒了2两呢？

Y满了就是8了 Z就是1了

15 楼 iceim 2008-07-19

我听过这个问题，同学问的，我想了半个小时排出来的

14 楼 zhunahao 2008-07-19

非常冒昧的问一下

2 6 3 3 2 0 0
2 8 1 3 2 0 0

这个地方，容器上面是有刻度的吗？怎么能知道从Z中是倒了2两呢？

13 楼 weolar 2008-07-18

// Mianshi.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#define Maxstate 1024
int SumMyprint=0;
int state[Maxstate]={0};
void Myprint(int *Arr,int N,char *Str);
bool CheckState(int *Arr,int Sum);
void StateAdd(int *state,int add);
void MyCopy(int *A,int*B,int N);

#define CheckSucc(STR) Sum=Arr[0]*1000000+Arr[1]*100000+Arr[2]*10000+Arr[3]*1000+  Arr[4]*100+Arr[5]*10+Arr[6];\
if(!CheckState(state, Sum))\
{\
	StateAdd(state,Sum);\
	/*Myprint(Arr,7,STR);*/\
	if (Iterative( Arr ))\
{return true;}\
}\
if (Arr[0]==4&&Arr[1]==4&&Arr[2]==4&&Arr[3]==4)\
{\
		Myprint(Arr,7,"True");\
		return true;\
}\


bool Iterative(int *realArr)
{
	int i=0,j=0,k=0,Sum=0;char SS[10];int tmpArr[7]={0};int Arr[7]={0};
	//***检测是否重复的状态,不是的话就添加进状态数组***
	
	
	/*
    if (CheckState(state, Sum))
    {
		printf(" CheckState Fail!\n");
		return false;
    }
	if (Arr[4]==4&&Arr[5]==4&&Arr[6]==4)
	{  
		Myprint(Arr,7,"True");
		return true;
	}
    StateAdd(state,Sum);
	CheckSucc();*/
	//--------------------------------------------
	for (j=4;j<=6;j++)
	{
	  for (i=0;i<=3;i++)
	  {
		if (realArr[i]+realArr[j]<=4&&realArr[j])
		{
			
            MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");
			Arr[i]+=Arr[j];Arr[j]=0;
			if (Arr[0]==4&&Arr[1]==4&&Arr[2]==4&&Arr[3]==4)
			{  
				Myprint(Arr,7,"True");
				return true;
			}
		    //sprintf(SS,"%d=>%d",j,i);
			//Myprint(Arr,7,SS);
			if (Iterative( Arr ))
			{
				Myprint(Arr,7,"True");
				return true; 
			}

		}
	  }
	}
//----------------------------------------
	if (realArr[5]<8&&realArr[4])//4=>5 1
	{
		if (realArr[4]+realArr[5]>8)
		{
			MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");
			Arr[4]=Arr[4]-8+Arr[5];Arr[5]=8;
			CheckSucc("4=>5");

		}
		else
		{
			MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");
			Arr[5]+=Arr[4];Arr[4]=0;
			CheckSucc("4=>5");

		}

	}
	if (realArr[6]<8&&realArr[4])//4=>6 2
	{
		if (realArr[4]+realArr[6]>3)
		{
			MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");
			Arr[4]=Arr[4]-3+Arr[6];Arr[6]=3;
			CheckSucc("4=>6");

		}
		else
		{
			MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");
		    Arr[6]+=Arr[4];Arr[4]=0;
			CheckSucc("4=>6");

		}
	}

	if (realArr[4]<8&&realArr[5])//4<=5 3
	{
		if (realArr[4]+realArr[5]>8)
		{
			MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");
			Arr[5]=Arr[5]-8+Arr[4];Arr[4]=8;
			CheckSucc("5=>4");

		}
		else
		{
			MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");
			Arr[4]+=Arr[5];Arr[5]=0;
			CheckSucc("5=>4");
		}
	}
	if (realArr[4]<8&&realArr[6])//4<=6 4
	{
		if (realArr[4]+realArr[6]>8)
		{
			MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");
			Arr[6]=Arr[6]-8+Arr[4];Arr[4]=8;
			CheckSucc("6=>4");
		}
		else
		{
			MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");
			Arr[4]+=Arr[6];Arr[6]=0;
			CheckSucc("6=>4");
		
		}
	}
	if (realArr[6]<3&&realArr[5])//5=>6 5
	{
		if (realArr[5]+realArr[6]>3)
		{
			MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");
			Arr[5]=Arr[5]-3+Arr[6];Arr[6]=3;
			CheckSucc("5=>6");

		}
		else
		{
			MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");
			Arr[6]+=Arr[5];Arr[5]=0;
			CheckSucc("5=>6");
		}
	}
	if (realArr[5]<8&&realArr[6])//5<=6 6
	{
		if (realArr[5]+realArr[6]>8)
		{
			MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");
			Arr[6]=Arr[6]-8+Arr[5];Arr[5]=8;
			CheckSucc("6=>5");
		}
		else
		{
			MyCopy(Arr,realArr,7);//Myprint(Arr,7,"Org!");
			Arr[5]+=Arr[6];Arr[6]=0;
			CheckSucc("6=>5");
		}
	}
	return false;
}
void MyCopy(int *A,int*B,int N)
{
	for(int i=0;i<N;i++)
	{
		A[i]=B[i];
	}
}
void StateAdd(int *state,int add)
{

	for (int j=0;j<Maxstate;j++)
	{
        if (!state[j])
        {
			state[j]=add;
			if (state[4]==53)
			{
				int asdfasdf=12;	
			}
			return;
        }
	}
}
bool CheckState(int *state,int Sum)//Sum在Arr中则返回true
{
	int SumTemp=(Sum/1000)*1000;SumTemp=Sum-SumTemp;//SumTemp=323...
	int Sum_th=SumTemp/100,Sum_te=(SumTemp/10)%10,Sum_ge=SumTemp%10,Sum_P=(Sum/1000)*1000;//Sum_P=3233000
   	for (int j=0;j<Maxstate;j++)
	{
		//int state_th=state[j]/100,state_te=(state[j]/10)%10,state_ge=state[j]%10;
		int staTemp=(state[j]/1000)*1000;staTemp=state[j]-staTemp;//staTemp=323...
	    int state_th=staTemp/100,state_te=(staTemp/10)%10,state_ge=staTemp%10,state_P=(state[j]/1000)*1000;//state_P=3233000
		if (state[j]==Sum &&state_P==Sum_P)
		{
			return true;
		}
		if (state_ge==Sum_te&&state_th==Sum_th&&state_te==Sum_ge &&state_P==Sum_P)
		{
            return true;
		}
	}
	return false;
}
void Myprint(int *Arr,int N,char *Str)
{
	printf("       a b c d 4 5 6\n");
	printf("Arr is ");
	for (int j=0;j<N;j++)
	{
		printf("%d ",Arr[j]);
	}
	if (SumMyprint==6)
	{
		int asas=1;
	}
	printf("%s S:%d\n\n",Str,SumMyprint++);
// 	if (Arr[0]==4 &&Arr[1]==2 &&Arr[2]==1 &&Arr[3]==1 &&Arr[4]==0 &&Arr[5]==8 &&Arr[6]==0 )
// 	{
// 		 	for (int j=0;j<N;j++)
// 			{
// 		 		printf("%d ",Arr[j]);
// 			}
// 			printf("\n");
// 	}
}


int main(int argc, char* argv[])
{

	int Arr[7]={0,0,0,0,8,8,0};

    Iterative(Arr);	

	printf("Hello World!\n");
	return 0;
}
// 有a,b,c,d四个人,现在有三个酒杯X,Y,Z三个不规则酒杯, X,Y容量为8两,现在已装满酒,Z容量为3两,
// 为空杯.现在要求四个人每人都能平均喝到4两酒,请说出该怎么喝?写出算法,并打印出每步X,Y,Z杯内的
// 酒多少和四个人每人所喝的酒? 
// 
// X Y Z a b c d 
// 8 8 0 0 0 0 0 
// 8 5 3 0 0 0 0 
// 8 5 0 3 0 0 0 
// 8 2 3 3 0 0 0 
// 8 0 3 3 2 0 0 
// 8 3 0 3 2 0 0 
// 5 3 3 3 2 0 0 
// 5 6 0 3 2 0 0 
// 2 6 3 3 2 0 0 
// 2 8 1 3 2 0 0 
// 2 8 0 4 2 0 0 
// 2 5 3 4 2 0 0 
// 0 7 3 4 2 0 0 !
// 3 7 0 4 2 0 0 !
// 3 4 3 4 2 0 0 !
// 6 4 0 4 2 0 0 !
// 6 1 3 4 2 0 0 !
// 6 0 3 4 2 1 0 !
// 8 0 1 4 2 1 0 !
// 8 0 0 4 2 1 1 !
// 5 0 3 4 2 1 1 
// 5 0 0 4 2 4 1 
// 2 0 3 4 2 4 1 
// 2 0 0 4 2 4 4 
// 0 0 0 4 4 4 4

12 楼 javaeyexp 2008-06-24

880 853 850 553 550 523 520 223 220 202 112 102 002 110 100 000

11 楼 jlite 2008-06-22

刚才写了个小程序算了一下，呵呵

import java.util.HashSet;
import java.util.Stack;

public class Drink {
    //  state 为32位整数，每4bit表示一个cup
    //  cup 0-2 : cup x,y,z
    //  cup 3-6 : people a,b,c,d
    //  state := [D][C][B][A][Z][Y][X]

    int[] maxVol = {8, 8, 3, 4, 4, 4, 4};   // 最大容量
    int stopState = makeState(new int[]{0, 0, 0, 4, 4, 4, 4});  // 最终状态

    Stack<Integer> stateStack = new Stack<Integer>();
    HashSet<Integer> stateStackCache = new HashSet<Integer>();
    HashSet<Integer> failStates = new HashSet<Integer>();

    public static void main(String[] args) {
        new Drink().start();
    }

    static int getCup(int state, int i) {
        return (state & (0xF << (i * 4))) >> (i * 4);
    }

    static int makeState(int curState, int cupIdx, int value) {
        return value << (4 * cupIdx) | (curState & (~(0xF << (4 * cupIdx))));
    }

    static int makeState(int curState, int cupIdx1, int value1, int cupIdx2, int value2) {
        return makeState(makeState(curState, cupIdx1, value1), cupIdx2, value2);
    }

    // cup.length MUST == 7
    static int makeState(int[] cup) {
        int state = 0;
        for (int i = 6; i >= 0; i--) {
            state |= cup[i];
            if (i > 0)
                state <<= 4;
        }
        return state;
    }


    void start() {
        boolean r = testState(makeState(new int[]{8, 8, 0, 0, 0, 0, 0}));
        System.out.println(r ? "found" : "not found");
    }

    boolean testState(int curState) {
        if (stateStackCache.contains(curState) || failStates.contains(curState))
            return false;

        pushState(curState);
        try {
            if (curState == stopState) {
                printStack();
                return true;
            }

            if (testMoves(curState)) {
                return true;
            } else {
                failStates.add(curState);
                return false;
            }
        } finally {
            popState(curState);
        }
    }

    private boolean testMoves(int curState) {
        for (int from = 0; from < 3; from++) {
            int curCupFrom = getCup(curState, from);
            if (curCupFrom == 0)
                continue;

            for (int to = 6; to >= 0; to--) {
                if (to == from)
                    continue;

                int curCupTo = getCup(curState, to);
                int maxTo = maxVol[to] - curCupTo;
                if (maxTo == 0)
                    continue;

                int moveValue = curCupFrom;
                if (curCupFrom > maxTo) {
                    if (to >= 3)    //people
                        continue;
                    moveValue = maxTo;
                }

                int newCupFrom = curCupFrom - moveValue;
                int newCupTo = curCupTo + moveValue;

                if (from < 2 && to < 2 && newCupTo == curCupFrom) {
                    //两个同样的杯子倒来倒去
                    continue;
                }

                final int newState = makeState(curState, from, newCupFrom, to, newCupTo);

                if (testState(newState))
                    return true;
            }
        }
        return false;
    }

    private void printStack() {
        System.out.println("Success! all steps: " + stateStack.size());
        int step = 0;
        for (Integer state : stateStack) {
            System.out.print("\t" + (++step) + ":\t");
            for (int i = 0; i < 7; i++) {
                System.out.print(getCup(state, i));
                if (i == 2)
                    System.out.print(" | ");
            }
            System.out.println();
        }
    }

    private void popState(int newState) {
        stateStack.pop();
        stateStackCache.remove(newState);
    }

    private void pushState(int newState) {
        stateStack.push(newState);
        stateStackCache.add(newState);
    }
}

10 楼抛出异常的爱 2008-05-08

andyhan 写道

这个和算法有什么关系？

这个是迷宫算法。
用电脑一个一个试出来的。

9 楼 andyhan 2008-05-07

这个和算法有什么关系？

8 楼 pure 2008-04-30

偶非计算专业,没学过数据结构,也没学过算法,也没学过sql!呵!

也从事java算三年了!只是还欠缺的东西还多,得找时间学学!

7 楼 zhangsheng79 2008-04-30

bio1984 写道

感觉这样的题目非常的考验算法的基本功。如果大学数据结构和算法学的不错的话应该做这种题会轻松点。

谁能把算法写出来学习一下

6 楼 bio1984 2008-04-29

感觉这样的题目非常的考验算法的基本功。如果大学数据结构和算法学的不错的话应该做这种题会轻松点。

5 楼 pure 2008-04-29

考的时候没做出来!失败!楼上的是正解了!

4 楼 zhangsheng79 2008-04-29

zhanghaoyang 写道

我试出来的，不过应该是递归实现，还需要再总结一下
880，853，850，553，550，523，703，433，460，163，063，081，080，053，323，600，402。全部喝4两

你算错了，600到402怎么可能？

3 楼 zhanghaoyang 2008-04-29

我试出来的，不过应该是递归实现，还需要再总结一下
880，853，850，553，550，523，703，433，460，163，063，081，080，053，323，600，402。全部喝4两

2 楼阳光晒晒 2008-04-29

ms小猪喝水问题

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论