|
锁定老帖子 主题：各位,来道面试题!
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (1)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2008-05-08
andyhan 写道 这个和算法有什么关系？ 这个是迷宫算法。 用电脑一个一个试出来的。 |
| 返回顶楼 | |
|
发表时间：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);
}
}
|
| 返回顶楼 | |
|
发表时间：2008-06-24
880 853 850 553 550 523 520 223 220 202 112 102 002 110 100 000
|
| 返回顶楼 | |
|
发表时间：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
|
| 返回顶楼 | |
|
发表时间：2008-07-19
非常冒昧的问一下
2 6 3 3 2 0 0 2 8 1 3 2 0 0 这个地方，容器上面是有刻度的吗？怎么能知道从Z中是倒了2两呢？ |
| 返回顶楼 | |
|
发表时间：2008-07-19
我听过这个问题，同学问的，我想了半个小时排出来的
|
| 返回顶楼 | |
|
发表时间：2008-08-02
zhunahao 写道 非常冒昧的问一下
2 6 3 3 2 0 0 2 8 1 3 2 0 0 这个地方，容器上面是有刻度的吗？怎么能知道从Z中是倒了2两呢？ Y满了 就是8了 Z就是1了 |
| 返回顶楼 | |
|
发表时间：2009-01-16
pure 写道 现在要求四个人每人都能平均喝到4两酒...... 平均？？ 一个人全喝了，平均下来也是4两 现在要求四个人每人都喝4两酒! |
| 返回顶楼 | |
|
发表时间：2009-01-21
大虾们程序贴上来瞧瞧！
|
| 返回顶楼 | |
|
发表时间：2009-02-16
最后修改：2009-02-16
牛逼。。。自己试试
|
| 返回顶楼 | |
