`

面试题：农夫养牛问题

面试J#CC++C#
阅读更多

今天在群中，有人说到这个一个面试题：

一头母牛在3—10岁的时候每年可以生一头小牛，生公牛和母牛的比率是50%，在牛12岁的时候就送入屠宰场买了。现在有一个农夫有1头1岁大的母牛，在母牛3岁的时候就送到附近的农场去配种，请问40年后这个农夫可能会有多少头牛，写出相关的代码或答题思路，最好用面向对象。

polaris将代码（Java实现）写了一下，如有不对的地方欢迎指出。同时也欢迎您给出自己的解法。

package com.polaris.test;

import java.util.*;

/**
 * 问题描述：
 * 
 * 一头母牛在3—10岁的时候每年可以生一头小牛，生公牛和母牛的比率是50%，
 * 在牛12岁的时候就送入屠宰场买了。现在有一个农夫有1头1岁大的母牛，
 * 在母牛3岁的时候就送到附近的农场去配种，请问40年后这个农夫可能会有多少头牛，
 * 写出相关的代码或答题思路，最好用面向对象。
 * @author polaris http://www.beijixing001.com
 * @version 1.0
 */
public class ComputeCattleNum {
	
	// 保存所有母牛
	private static List<Cattle> cows = new ArrayList<Cattle>();
	
	// 保存所有当前农夫拥有的牛
	private static List<Cattle> cattles = new ArrayList<Cattle>();
	
	public static void main(String[] args) {
		// 第一头母牛
		Cattle cow = new Cattle(0,3);
		cows.add(cow);
		
		// 40年
		for(int i=0;i<40;++i) {
			// 大于等于12岁的牛送到屠宰场卖掉；同时每年，所有的牛
			for(int j=0;j<cattles.size();++j) {
				Cattle temp = cattles.get(j);
				if(temp.getDead()) {
					cattles.remove(temp);
				}
				
				// 开始只有一头母猪，年龄不生长
				if(i>0) {
					cattles.get(j).grow();
				}
			}
			
			// 母牛生小牛
			for(int j=0;j<cows.size();++j) {
				Cattle calf = cows.get(j).bear();
				if(calf!=null) {
					if(calf.getSex()==0)
						cows.add(calf);
					cattles.add(calf);
				}
			}
		}
		
		System.out.println("40年后农夫拥有" + cattles.size() + "头牛");
	}
}

class Cattle {
	
	// 牛的雌雄：0代表雌，1代表雄
	private int sex;
	// 牛的年龄
	private int age;
	// 是否卖掉（已死）
	private boolean dead = false;
	
	public Cattle(int sex, int age) {
		this.sex = sex;
		this.age = age;
	}
	
	/**
	 * 生小牛
	 * @return 生出的小牛
	 */
	public Cattle bear() {
		Cattle calf = null;
		if(this.sex==0) {
			if(this.age>=3 && this.age<=10) {
				calf = new Cattle(random(),0);
			} else {
				//System.out.println("抱歉，此牛太小或太老，不能生育。");
			}
		} else {
			//System.out.println("有没有搞错，公牛也想让它生小牛？");
		}
		return calf;
	}
	
	private int random() {
		return (int)Math.round(Math.random());
	}
	
	/**
	 * 长大一岁，如果当前大于等于12岁，则卖掉
	 */
	public void grow() {
		if(this.age>=12) dead = true;
		else this.age++;
	}
	
	public int getSex() {
		return this.sex;
	}
	
	public boolean getDead() {
		return this.dead;
	}
}
 点击此处获得ComputeCattleNum.java类文件

分享到：
| 谷歌笔试题（Google十二岁生日晚）
评论
15 楼 z673182 2010-10-13  
1岁的开的母牛  在加上 3-10岁 每年产一头牛 公母50%  先算 从3岁开始算 一点累积 得出 的
14 楼 注册真难 2010-10-09  
第一次回帖，不怎么会。也来说说我的思路。 
public class CountCow {

	List<Cow> list = new ArrayList<Cow>();
	
	public CountCow() {
		Cow cow = new Cow();
		cow.setAge(1);
		cow.setSex(1);
		list.add(cow);
	}
	
	public void computeCow(int year){
		for(int i=0;i<year;i++){
			
			for(int j=0;j<list.size();j++){
				Cow cow = (Cow)list.get(j);
				cow.setAge(cow.getAge()+1);
				
				if(cow.getAge()>2&&cow.getAge()<11&&cow.getSex()==1){
				   list.add(new Cow());
				}

				if(cow.getAge()==12){
				   list.remove(list.lastIndexOf(cow));
				   j--;
				}
			}
			
		}
	}
	
	
	public static void main(String[] args) {
		CountCow c= new CountCow();
		c.computeCow(40);
		System.out.println(c.list.size());
		
	}

}

class Cow{
	
	int sex;    // 0 公, 1 母
	int age;
	
	Cow(){
		setAge(0);
		setSex(new Random().nextInt(2));
	}

	public int getSex() {
		return sex;
	}

	public void setSex(int sex) {
		this.sex = sex;
	}

	public int getAge() {
		return age;
	}

	public void setAge(int age) {
		this.age = age;
	}
}
13 楼 polaris1119 2010-10-09  
长大做IT 写道
第一头母牛应该是从1岁开始吧？


问过那人，他说是从3岁开始。
12 楼 长大做IT 2010-10-09  
第一头母牛应该是从1岁开始吧？
11 楼 polaris1119 2010-10-08  
shxiao 写道

--楼主代码里什么地方体现的0.5的概率呢？我怎么看不出来呢？O(∩_∩)O哈哈~


private int random() { 
        return (int)Math.round(Math.random()); 
    } 

这个函数要么返回0、要么返回1。根据API说明，Math.random返回的值近似均匀分布的。round(double x)函数则会返回最近x的long值。不知道你明白没有？
10 楼 shxiao 2010-10-08   
(defn cattle
  [sex  live]
  (condp = sex
    1 (cond 
        (> live 12) 0
        :else 1)
    0 (cond
        (< live 3)
        1
        (< live 11)
        (inc (reduce + (map #(+ 
                         (* 0.5 (cattle 0 (- live %))) 
                         (* 0.5 (cattle 1 (- live %))))
                    (range 3 (inc live)))))
        :else (reduce + (map #(+ 
                          (* 0.5 (cattle 0 (- live %))) 
                          (* 0.5 (cattle 1 (- live %))))
                    (range 3 11))))))


我写的，边界值搞不清楚呀！

--楼主代码里什么地方体现的0.5的概率呢？我怎么看不出来呢？O(∩_∩)O哈哈~
9 楼 polaris1119 2010-10-08  
hikaru1012 写道
Lz答得很好。个人觉得有些地方可以优化。

觉得楼主程序中定义的  // 保存所有母牛 
    private static List<Cattle> cows = new ArrayList<Cattle>(); 
可以不用，然后修改一下40年for循环中的第一个for循环
for(int j=0;j<cattles.size();++j)
这样只要在40年的for循环中使用一次for循环即可解决问题。


当时写主要是想实现功能，没有过多考虑优化的问题。呵呵
8 楼 polaris1119 2010-10-08  
yangguo 写道
引用

# public Cattle bear() { 
#         Cattle calf = null; 
#         if(this.sex==0) { 
#             if(this.age>=3 && this.age<=10) { 
#                 calf = new Cattle(random(),0); 
#             } else { 
#                 //System.out.println("抱歉，此牛太小或太老，不能生育。"); 
#             } 
#         } else { 
#             //System.out.println("有没有搞错，公牛也想让它生小牛？"); 
#         } 
#         return calf; 
#     } 




这段应聘外企可加分。


呵呵。谢谢。你最近没写啥啊？想看看你大牛写的东西呢。呵呵
7 楼 yangguo 2010-10-08  
引用

# public Cattle bear() { 
#         Cattle calf = null; 
#         if(this.sex==0) { 
#             if(this.age>=3 && this.age<=10) { 
#                 calf = new Cattle(random(),0); 
#             } else { 
#                 //System.out.println("抱歉，此牛太小或太老，不能生育。"); 
#             } 
#         } else { 
#             //System.out.println("有没有搞错，公牛也想让它生小牛？"); 
#         } 
#         return calf; 
#     } 




这段应聘外企可加分。
6 楼 haycat1314 2010-10-08   
import java.util.ArrayList;
import java.util.List;

public class Farm {	
	public List<Cow> cows = new ArrayList<Cow>();

	public void firstCow() {
		Cow fc = new Cow(0);
		fc.setAge(3);		
		cows.add(fc);
	}

	public int forgrow() {
		firstCow();
		for (int i = 0; i < 40; i++) {
			int k = cows.size();
			for (int j = 0; j < k; j++) {
				Cow cow = cows.get(j);				
				if (cow.sell()) {
					cows.remove(j);
				} else {
					if (cow.getSex() == 0 && cow.getAge() >= 3) {
						int sex = cow.prow();
						cows.add(new Cow(sex));
						cow.grow();
					} else {
						cow.grow();
					}
				}				
			}
		}
		return cows.size();
	}
	
	public static void main(String[] args) {
		System.out.println(new Farm().forgrow());
	}
}

public class Cow {

	private int age = 0;

	public int getAge() {
		return age;
	}

	private int sex = 0;	

	public int getSex() {
		return sex;
	}

	public void setSex(int sex) {
		this.sex = sex;
	}

	public void setAge(int age) {
		this.age = age;
	}

	public void grow() {
		age++;
	}

	public boolean sell() {
		return (age == 12);
	}

	public boolean enough() {
		return age > 3;
	}
	
	public int prow() {
		return (int) (Math.random() * 2);
	}
	
	public Cow(int sex) {
		this.sex = sex;
		this.age = 1;
	}
}


菜鸟发着玩  轻喷

PS: 喷也无所谓， 我脸皮厚
5 楼 bo_83 2010-10-08  
上班第一天，无心工作，我也养牛玩...
好像很简单，不知道对不对哦... 
public class Cow {
	
	private boolean isCow;
	private int age;
	private boolean alive;
        ......


public class CountCow {
	
	private static int year = 40;
	private static List<Cow> cows = new ArrayList<Cow>();

	public static void main(String[] args) {

		Cow cow = new Cow();
		cow.setAge(1);
		cow.setAlive(true);
		cow.setCow(true);
		cows.add(cow);
		
		for(int i = 1; i <= year; i ++){
			
			List<Cow> tmp = new ArrayList<Cow>();
			
			for(Cow c : cows){
				
				if(c.getAge()>=3 && c.getAge() <=10 && c.isCow()){
					
					Cow cc = new Cow();
					cc.setAge(0);
					cc.setAlive(true);
					cc.setCow(isCow());
					tmp.add(cc);
				}
				
				if(c.getAge() < 12){
					
					c.setAge(c.getAge()+1);
					tmp.add(c);
				}
			}
			cows.clear();
			cows.addAll(tmp);
			System.out.println(cows.size());
		}
		System.out.println("="+cows.size());
	}
	
	private static boolean isCow(){
		
		Random random = new Random();
		return random.nextInt(10) % 2 == 0;
	}

}

反复运行好多好多遍。。。
最小值 624
最大值 10687
足足相差17倍！！！

真的是人的命天注定呢！你说，都是养牛的，找谁说理去！！！

哎，终于下班了。。。

又转了几遍，还出现0值了！！！！
每年结果如下：
1
1
2
3
4
5
6
7
8
9
9
8
8
8
8
7
6
5
4
3
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
=0
没天理啊！！！

走了！
4 楼 hikaru1012 2010-10-08  
Lz答得很好。个人觉得有些地方可以优化。

觉得楼主程序中定义的  // 保存所有母牛 
    private static List<Cattle> cows = new ArrayList<Cattle>(); 
可以不用，然后修改一下40年for循环中的第一个for循环
for(int j=0;j<cattles.size();++j)
这样只要在40年的for循环中使用一次for循环即可解决问题。

3 楼 yongdi2 2010-10-08  
没看清题目，还以为要考虑公母配对的问题。我觉得lz答的不错
2 楼 polaris1119 2010-10-02  
cch123 写道
polaris威武，我也要加群，求群号

呵呵。那个群不是专门讨论面试题之类的，只是一个一般的群，有人在里面问到一个题目而已。呵呵
1 楼 cch123 2010-10-02  
polaris威武，我也要加群，求群号
发表评论

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

相关推荐

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