`
pure
  • 浏览: 350897 次
社区版块
存档分类
最新评论

各位,来道面试题!

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

分享到：
| StAX(Streaming API for XML) 在netbeans r ...
评论
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小猪喝水问题
发表评论

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

相关推荐

    170道面试题

    java面试题！包括各种方面，有题，有答案，希望能帮到各位！

    Google的15道面试题与答案

    这是Google的15道面试题与答案，word文档！大家感兴趣的看看吧！呵呵！希望对各位有帮助！

    极具参考价值的Python面试题！从创业公司到一线大厂的所有面经汇总

    各位读者朋友们大家好！我是爬虫领域的职业段子手。这篇文章今天在CSDN首发，后续我会持续维护更新。希望能帮助每一位读者减少掉坑的机率，也祝愿每位读者都能拿到心仪的offer！由于时间原因还有很多实战资源题目及...

    2018iOS面试题汇总

    本文档记录了18年大致的iOS面试题，希望对各位同道有所帮助

    嵌入式C语言面试题汇总(超经典).pdf

    我们在找嵌入式方面的工作时，让我们头疼的恐怕就是面试题了，因为我们摸不到企业的命题规律，也不知道该怎样去准备，今天将各大企业的面试题进行汇总，分享给大家，希望可以帮到各位小伙伴。加油哦！

    C++_Qt面试题整理.txt

    整理了一些Qt和基于Qt的C++常见面试题，适用于初中级程序员面试自检使用，祝各位学习愉快，面试顺利，生活开心！

    java面试题，技术面试与设计模式

    java面试题，希望能帮到各位IT工作者！java面试题，希望能帮到各位IT工作者！

    Java .Net面试题大集合

    包含全部java面试题和.Net面试题及部分sql面试题，全部是大小公司必问问题，很不容易才找到，绝对有用，希望对各位有帮助！ 希望认识更多IT人士，如有疑问或帮助，请登陆本人空间或blog留言！

    银行IT部门各岗位面试题和笔试题

    各个银行IT部门各岗位面试题和笔试题资料汇总，看各位需要。 各个银行IT部门各岗位面试题和笔试题资料汇总，看各位需要。

    java最新面试题很全

    很全的java面试题 基本笔试题都用很全，刚毕业的去面试看下，面试题基本都会

    xml面试题 .net 适用

    xml初中级面试题，希望各位同仁可以顺利通过，题目不多，但是有一定难度！

    android framework面试题集

    android framework面试题集 自己亲自总结的，各位有需要的可以随时下载

    网页设计面试题

    网页设计的面试题及基础，主要涉及一些网页设计的基本知识 仅供各位HR参考

    搜狐java面试题

    本人亲身经历的搜狐面试题，相当经典，欢迎各位同胞下载

    Java中高级工程师面试题

    包含各公司的面试题及部分笔试题，希望能给各位Java求职者带来帮助！

    模拟面试题及答案 Java

    选择了一些经常问到的java面试题，及建议答案，希望对各位面试者有用。 描述final﹑finally和finalize的区别。 编程题：使用JavaScript和HTML编写网页实现如图一所示计算功能： 购买总价=购买价格×购买数量。

    2018最新python面试题

    这是一份2018年最新python编程面试题给各位培训出身或者自学python的一个参考

    2011Java新版面试题

    此面试题为本人最近搜集整理，为目前企业面试最会被考到的问题，包括：java基础、多线程、常见排序算法、23种设计模式、堆栈、tomcat和jboss性能优化、JDK新特性、SSH框架、SQL数据库、面向对象设计原则等一系列综合...

    java常用面试题集锦

    java方面的一些常见面试题，希望对各位有用。

Magicbox
Global site tag (gtag.js) - Google Analytics