黑马程序员技术交流社区

标题: 面试逻辑问题 [打印本页]

作者: 火之意志 时间: 2013-5-23 14:04
标题: 面试逻辑问题
本帖最后由火之意志于 2013-5-23 14:05 编辑

1、一栋房子需要一个工匠七天建成，这个工匠的工钱是一份金条，假如现在你需要盖一栋房子，而你只有一根完整的金条，怎么能把金条分三份的情况下每天都付给工匠工资，最后一天刚好付完？
2、有8个小球,他们颜色,大小一致.但是其中一个的质量比其他几个重.给你一个天平,你用几次可以把这个重的小球找出来.

作者: slatop@qq.com 时间: 2013-5-23 14:23
第一题　是１　２　４
一天１　二天２拿回１，三天１和２，四天４拿回１和２，五天４和１，六天４和２拿回１，七天正好。

第二题　最多３次就可以找出重球。
１次，拿四个球２Ｖ２放天秤上，如果相等代表重球在另外四个。如果不相等重球就在这四个中。然后再２分法拿重的四个中的两个去一对一去秤，如果相等就在另外两个，如果不相等直接２次就出结果了。所以最多三次

作者: 张世威 时间: 2013-5-23 15:12
1这应该是个数学问题，用计算机循环遍历，很快就可以得到结果
①假设a+b+c=7,先用代码把切割的方式遍历出来。

int a=0,b=0,c=0;
//分三段，只能切2刀
int[]num={1,2,3,4,5,6,7};
for(int i=1;i<7;i++){
for(int j=i+1;j<7;j++){
a=i;
b=j-i;
c=7-j;
if(a<=b&&b<=c){
System.out.println(a+""+b+""+c);
}
}
}

复制代码

②遍历后的结果，在这四个结果中，人工一个个试一试了，暂时还想不出来怎么写这个筛选结果。
a+b+c=7 ，abc三个数随意的加减，能得到结果1-7
115
124
133
223

2、8个求，分成3组：1 2 3 、4 5 6 、7 8
①首先123和456比较，根据><=就可以确定重球在哪一组了
②a假设123重,就将1和2比较，根据><=，就可以确定重球是123哪一个了。
b假设456重，过程同②
c 假设78重，7和8一比较就出来了。

作者: lpflpy 时间: 2013-5-23 15:16
第一题：七分之一，七分之二，七分之四
第二题：最多2次就可以找到
第一种情况：
第一次：天平的两边各放3个小球，如果相等，那么其余的2个中有一个是重球
第二次：比较剩下的2个，找出重球
第二种情况：
第一次：天平的两边各放3个小球，如果不相等，那么把重球那一边的3个球拿出2个比较
第二次：如果这两个球相等，那么剩下的那个是重球；如果不等，就直接找到重球了

作者: 无妄无涯 时间: 2013-5-23 15:46
第一个问题，转化为数学需求就是三个值a、b、c，a+b+c=7，三个值可以任意组合出1~7的每个数值。由于数字比较小，应该没必要去探究怎么数学建模来解决，直接列出仅有的4种搭配很容易得出答案，即分成1/7、2/7、4/7。
第二个问题，只需要两次就可以了。第一种情况（重球在第一次称量中出现）：天平两边各放三个小球，天平不平衡，将存在重球那边的三个小球进行第二次称量。比较其中两球，直接称量出重球或者剩下的那个球是重球。
第二种情况（重球未在第一次称量中出现）：天平两边各放三个小球，天平平衡，则剩下两个小球中必有一个是重球，称量这两个小球直接找出重球。

作者: 王靖远 时间: 2013-5-23 16:09
有人答我就不答了，这些题大多都要去往二进制上门靠。

作者: 悟佛修道 时间: 2013-5-23 22:26
又是这种题，想起了小学时的奥数。考的都不是什么学习的知识，都是考你脑子。

作者: 袁梦希 时间: 2013-5-24 00:02
非常好继续努力

作者: 袁梦希 时间: 2013-5-24 00:02

无妄无涯发表于 2013-5-23 15:46
第一个问题，转化为数学需求就是三个值a、b、c，a+b+c=7，三个值可以任意组合出1~7的每个数值。由于数字比 ...

非常好加油

作者: 袁梦希 时间: 2013-5-24 00:03

张世威发表于 2013-5-23 15:12
1这应该是个数学问题，用计算机循环遍历，很快就可以得到结果
①假设a+b+c=7,先用代码把切割的方式遍历出来 ...

很全面

作者: kaka小明 时间: 2013-5-24 17:25
1.第一反应就是想起高中的等比例数列1,2,4,8.。。。。，答案分7份：1,2,4，全面的扩展代码实现（这代码是某个周末做的，结果没看答题要求，晚上6点以后上传，LZ给个面子啊！多谢啦。）
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;

public class Main {


   /*
   * 问题分析:分金条问题本质是数据分割问题，针对数M，将其分为N块(M>N,M<=N的情况下肯定是可以解决的),（d(1),d(2),...,d(N)）,满足以下条件:
   * 从1,2,3,。。。M-1,M结束，对其任意数字M(x)都可以从块中通过某一组合的和得到  这让我自然地联想到比例系数为2的等比例数列，我们知道，它的一个特征就是：
   * 给定一个等比例数列a(n)，比例系数为2,那么从从1-n中的任意一个数x，都能从该数列中找到几个元素，来凑足它。下面就是分析的例子，可以从中总结出规律
   * M--N-------最小分块组合
   * ***********************
   * 2--2-------1,1
   * 3--2-------1,2    <------分界，表示如果此数能分割，同段位的数据必然也能分割
   * **************
   * 4--2-------1,3(N=2无效!!段数加1,以下分析类似)
   * 4--3-------1,2,1
   * 5--3-------1,2,2
   * 6--3-------1,2,3
   * 7--3-------1,2,4 <------分界
   * ***************
   * 8--4-------1,2,4,1
   * 9--4-------1,2,4,2
   * ........
   * 14--4------1,2,4,7
   * 15--4------1,2,4,8 <------分界
   ******************
   *........
   *从以上分析中可以看出，关键是对边界的判断，只要确定了边界的最小分段数，那么所有处于同一段位的数据也能按照该分段数分段，
   *而分界数据的分段正是按照标准的等比例数列来确定的。只要确定了M的处在哪个边界之内问题就迎刃而解。如果N小于这个分段数，那么则无法实现分配.
   */
public static void main(String[] args){

System.out.println(add(1.0f, 2.0f));
System.out.println(add(1, 4));
ArrayList<Integer> list=new ArrayList<Integer>();

BufferedReader br=new BufferedReader(new InputStreamReader(System.in));//键盘录入缓冲流
try {
//获得M
System.out.println("请输入M..");
int m=new Integer(br.readLine());
//获得N
System.out.println("请输入N..");
int n=new Integer(br.readLine());
br.close();
System.out.println("分析结果:");
//获得最优分配方案，各个元素存放在list中
list=getBlocks(m);
//打印处理
if(n>=list.size()){
Iterator<Integer> it=list.iterator();
System.out.println("最优数据分块方案:");
while(it.hasNext()){
System.out.print(it.next()+", ");
}
}else{
System.out.println("对不起，无法实现分配!");
}

} catch (NumberFormatException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}

}
public static ArrayList<Integer> getBlocks(int m){
ArrayList<Integer> tmp=new ArrayList<Integer>();
int sum=1;
int a=1;//元素临时变量
int b=0;//末尾余数临时变量
while(sum<=m){
tmp.add(a);
a=a*2;
sum+=a;
}
if(sum>m){//sum超出，求出余数，也就是最后一个元素
b=m-(sum-a);
if(b!=0)//杜绝0元素
tmp.add(b);
}
return tmp;
}

public static float add(float x,float y){
return (float)(x+y);
}
public static int add(int x,int y){
return (int)(x+y);
}
}
2提。2分法思想 4-4 2-2 1-1。 3次

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2