经典的农夫养牛问题（常考的面试题）

假设牛不死亡的话，10年后有55头牛
package dailyTest;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class Test006 { /**
* @param args
*/
public static void main(String[] args) {
System.out.println("你要查询几年后牛的总数:");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n;
try {
n = Integer.parseInt(br.readLine());
int x = 1, y = 1;
for(int i=0;i<n;i++) {
if(i>=2) {
y = x + y;
x = y - x;
}
}
System.out.println(n + "年后总共有" + y + "头牛");
} catch (NumberFormatException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}

}}

或者直接利用通式求，不过只适合int范围内，超过一定范围该程序失效，计算结果不准，但再计算结果不超过int 或long最大值范围内还是可以求出结果来的
附上代码，只是一种想法而已import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class Test {
public static void main(String[] args) throws NumberFormatException, IOException {
System.out.println("你要查询几年后牛的总数:");
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
final double C = Math.sqrt(5);
double r = (1/C) * (Math.pow((1 + C) / 2, n) - Math.pow((1 - C) / 2, n));
System.out.println((long)r);
}
}

public class Cow {
private int age;
public Cow(){
age = 0;
}
public Cow play(){
age ++;
return age > 2 ? new Cow():null;
}
}public class Test { public static void main(String[] args) {
List<Cow> list = new ArrayList<Cow>();
list.add(new Cow());
for(int i = 0; i < 10;i++){
for(int j =0;j<list.size();j++){
Cow cow = list.get(j).play();
if(cow != null)
list.add(cow);
}
System.out.println("第" + (i+1)+"年，共有：" + list.size());
}
}}第1年，共有：1
第2年，共有：1
第3年，共有：2
第4年，共有：3
第5年，共有：5
第6年，共有：8
第7年，共有：13
第8年，共有：21
第9年，共有：34
第10年，共有：55感觉麻烦了点,但应该容易理解,不知道对不对

public class OxProblem {
public static void main(String[] args) {
for(int i=1;i<=20;i++){
System.out.println("第"+i+"年牛的数量："+getOxs(i));
} }
public static int getOxs(int n){
int answer = 0;
if(n>=3){
answer = 1;
for(int i=1;i<=n-2;i++){
answer += getOxs(i);
}
}else{
answer = 1;
}
return answer;
}
}
第1年牛的数量：1
第2年牛的数量：1
第3年牛的数量：2
第4年牛的数量：3
第5年牛的数量：5
第6年牛的数量：8
第7年牛的数量：13
第8年牛的数量：21
第9年牛的数量：34
第10年牛的数量：55
第11年牛的数量：89
第12年牛的数量：144
第13年牛的数量：233
第14年牛的数量：377
第15年牛的数量：610
第16年牛的数量：987
第17年牛的数量：1597
第18年牛的数量：2584
第19年牛的数量：4181
第20年牛的数量：6765用递归来做的。

好多人貌似没看清楚题，是三年后，不是第三年，放出两种解题思路，一种是递归，一种是面向对象的思维，第二个很经典，面试的时候能写出第二个这样的代码，会添色不少。
1.递归(结果为28，如果要算n年后的结果，只需将10改为n)：
public class Cow {
static int count = 1;
private static void feedCow(int year,int age){
year++;
age++;
if(year<=30){
if(age>=3){
count++;
feedCow(year,0);
}
feedCow(year,age);
}
}

public static void main(String[] args) {
new Cow().feedCow(0, 0);
System.out.println(count);
}
}2.面向对象（很经典的思路，结果当然是28，要求n年后，只需将i<10改为i<n
public class Cow {
public static int count = 0;
public Cow(int year){
count++;
for(int i=3+year;i<=10;i++){
new Cow(i);
}
}

public static void main(String[] args) {
new Cow(0);
System.out.println(count);
}
}

有点乱，重新发下
1.
public class Cow {
static int count = 1;
private static void feedCow(int year,int age){
year++;
age++;
if(year<=30){
if(age>=3){
count++;
feedCow(year,0);
}
feedCow(year,age);
}
}

public static void main(String[] args) {
new Cow().feedCow(0, 0);
System.out.println(count);
}
}2.
public class Cow {
public static int count = 0;
public Cow(int year){
count++;
for(int i=3+year;i<=10;i++){
new Cow(i);
}
}

public static void main(String[] args) {
new Cow(0);
System.out.println(count);
}
}

public class Cow {
    public static int count = 0;
    public Cow(int year){//这里的参数year是干什么的？
        count++;
        for(int i=3+year;i<=10;i++){
            new Cow(i);
        }
    }

    public static void main(String[] args) {
        new Cow(0);
        System.out.println(count);
    }
}

year表示几年后，0年后，1年后,2年后......10年后

public class Cow {
private int age;
public Cow(){
age = 0;
}
public Cow play(){
age ++;
return age > 3 ? new Cow():null;
}

public static void main(String[] args) {
List<Cow> list = new ArrayList<Cow>();
list.add(new Cow());
for(int i = 0; i <= 10;i++){
for(int j =0;j<list.size();j++){
Cow cow = list.get(j).play();
if(cow != null)
list.add(cow);
}
}
System.out.println("10年后，共有：" + list.size());
}
}10年后，共有：28
好像是没有楼上的经典,学习

kltwjt 绝对是个算法高手

I'm very sorry.考虑错了，出丑了。

public class Test2
{
public static void main(String[] args){
int one = 1;
int two = 1;
if(Integer.parseInt(args[0]) == 1 || Integer.parseInt(args[0]) == 2){
System.out.println("老汉养了 "+Integer.parseInt(args[0])+" 只羊");
}else{
for(int i = 3;i <= Integer.parseInt(args[0]);i++){
int number = two;
two = one + two;
one = number;
}
System.out.println("老汉养了 "+two+" 只羊");
}
}
}

刚看到这个题目很喜欢，但小弟我尚未学java，就用控制台写了一下
#include"iostream"
using namespace std;int Cow(int n)
{
if(n<0) return 0;
int Count[3]={1,0,0};
//Count[0]为年龄为1的牛的数量，Count[1]为年龄为2的牛的数量
//Count[2]为年龄大于等于3的牛的数量
for(int i=0;i<n;i++)
{
int temp=Count[2];//temp为第i年生下的小牛数
Count[2]+=Count[1];//年龄加1
Count[1]=Count[0];
Count[0]=temp;
}
return Count[0]+Count[1]+Count[2];
}int main()
{
for(int i=1;i<=15;i++)
cout<<"第"<<i<<"年的牛为"<<Cow(i)<<"头"<<endl;
}运行结果：
第1年的牛为1头
第2年的牛为1头
第3年的牛为2头
第4年的牛为3头
第5年的牛为4头
第6年的牛为6头
第7年的牛为9头
第8年的牛为13头
第9年的牛为19头
第10年的牛为28头
第11年的牛为41头
第12年的牛为60头
第13年的牛为88头
第14年的牛为129头
第15年的牛为189头

算法时间和空间复杂度均为O(n),n为年数，是一个动态规划算法public class CowBreed
{
public static void main(String args[])
{
final int size = 100; //可以根据需要，设置为所需要计算的最大年限
long[] num = new long[size + 1];
num[0] = num[1] = num[2] = 0;
for(int i = 3; i <= size; ++ i)
{
num[i] = num[i - 1] + 1 + num[i - 3];
System.out.println("第" + i + "年，牛的数量为：" + (num[i] + 1));
}
}
}第3年后，牛的数量为：2
第4年后，牛的数量为：3
第5年后，牛的数量为：4
第6年后，牛的数量为：6
第7年后，牛的数量为：9
第8年后，牛的数量为：13
第9年后，牛的数量为：19
第10年后，牛的数量为：28
第11年后，牛的数量为：41
第12年后，牛的数量为：60
第13年后，牛的数量为：88
第14年后，牛的数量为：129
第15年后，牛的数量为：189
...

class TestNiu
{

public static int niu(int n)
{
int num=0;
if(n<3)
{
return n=1;
}
else
{
num=niu(n-1)+niu(n-2);
return num;

}
}
public static void main(String[] args)
{
int num1=TestNiu.niu(10);
System.out.println("十年后有"+num+"头牛");
}
}

class TestNiu
{

public static int niu(int n)
{
int num=0;
if(n<3)
{
return n=1;
}
else
{
num=niu(n-1)+niu(n-2);
return num;

}
}
public static void main(String[] args)
{
int num1=TestNiu.niu(20);
System.out.println("十年后有"+num1+"头牛");
}
}

package com.springinaction.test;import java.util.ArrayList;
import java.util.List;public class CowTest { /**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
           Cow cow=new Cow();
           for(int i=0;i<10;i++)
           {
            cow.birth();
            System.out.println((i+1)+"年后："+(cow.getSize()+1));
           }
}}
class Cow
{
private static int size;//这个是静态的
private int age=0;
private List<Cow> children=new ArrayList<Cow>();
public void birth()
{
for(Cow cow:children)
{
cow.birth();//把每头都执行一遍
}
age++;
if(age<3)
{
return;
}
else
{
children.add(new Cow());
size++;
//System.out.println(size);
}

}
public int getSize()
{
return size;
}

}
自己也写了一个，希望大家指点
思路是：计算n年后第一头牛后代的数量，最后加上1就可以了

用面向对象的方法很简单：
import java.util.HashSet;
import java.util.Set;class Cow
{
    private int age;

    public Cow()
    {
        age = 0;
    }

    public Cow bearCow()//生小牛
    {
        return new Cow();
    }

    public void grow()//每年牛龄加1
    {
        age = age + 1;
    }

    public int getAge()
    {
        return age;
    }
}
public class Main {
    private static Set<Cow> cowSet = new HashSet<Cow>();//牛圈，存放所有的牛    public static int check()//每年检测一边所有的牛，年龄要加一，并且够岁数了要生效牛
    {
        Set<Cow> newCowSet = new HashSet<Cow>();
        for(Cow cow : cowSet)
        {
            cow.grow();//年龄加一
            if(cow.getAge() >= 3)
                newCowSet.add(cow.bearCow());//够岁数的生小牛

        }
        cowSet.addAll(newCowSet);//把所有生出来的小牛放牛圈里
        return cowSet.size();
    }
    public static void main(String args[])
    {
        Cow cow = new Cow();
        cowSet.add(cow);
        for(int i = 0; i < 10; i ++)
        {
            System.out.println(i+1 + " : " + check());
        }
    }}

public static int f(int i) {
if (i < 0)
return 0; // 在第0年之前是没有牛的
if (i == 0)
return 1; // 第0年时有1头牛
return f(i - 1)/* 1年前的牛的数量，这些牛依然活着 */
+ f(i - 3) /* 3年前的牛的数量，这些牛获得了生小牛的能力= = */;
}

public class Cow {
public static int coun=1;
public static void main(String args[]) {
new Cow().cowY(10);

System.out.println(coun);
}

public void cowY(int year){

int age=1;
while(age<=year){
age ++;

if(age<=year&&age>=3){
coun ++;
cowY(year-age);
}
}
}
}

斐波那契数列int n = 10
int x = 1, y = 1;
for (int i = 0; i < n - 2; i++) {
y = x + y;
x = y - x;
}这是最经典的算法

public class CCOW {
  static ArrayList<cow> to = new ArrayList<cow>();  public static void main(String[] args) {
    to.add(new cow());
    for (int i = 0; i < 10; i++) {
      for (int j = to.size() - 1; j >= 0; j--)
        to.get(j).addOneYear();
      System.out.println((i + 1) + ":" + to.size());
    }
  }  static class cow {
    int age = 0;    void addOneYear() {
      age++;
      if (age >= 3)
        to.add(new cow());
    }
  }
}
1:1
2:1
3:2
4:3
5:4
6:6
7:9
8:13
9:19
10:28

随手写了一个。public class OrderTest {

public static void main(String[] args) {
for (int i=1; i<=20; i++) {
Cow father = new Cow(i);
father.compute();
int sum = father.numOfChilds + 1;
System.out.println("第" +i+ "年: "+sum);
}
}
}class Cow {
public int numOfChilds = 0;
private int years;
public Cow(int years) {
this.years = years;
}

public void compute() {
for (int i=3; i<=years; i++) {
Cow child = new Cow(years-i);
child.compute();
numOfChilds += child.numOfChilds + 1;
}
}
}第1年: 1
第2年: 1
第3年: 2
第4年: 3
第5年: 4
第6年: 6
第7年: 9
第8年: 13
第9年: 19
第10年: 28
第11年: 41
第12年: 60
第13年: 88
第14年: 129
第15年: 189
第16年: 277
第17年: 406
第18年: 595
第19年: 872
第20年: 1278

高中数学教材上有个数组就是这个问题,不过是讲的兔子.用递归法:a1=1;a2=1;an=a(n-1)+a(n-2)

a1 = 1
a2 = 1
a3 = 1
a4 = 2Ai = Ai-1 + Ai-4;

#include<stdio.h>
  2
  3
  4 int main()
  5 {
  6     int new=0,middle=0,old=0,total=0;
  7     int year=0,i=0;
  8     char adj=-1;
  9
10 start:
11     printf("请输入你需要查询第几年牛的头数：（年数必须大于0）");
12     scanf("%d",&year);
13
14
15     if(year<1)
16     {
17         printf("输入有误，您是不是在耍我？\n");
18         return -1;
19     }
20     //前三年的牛的头数
21     else if(year<4)
22     {
23         printf("*************************第%d年共1头牛\n",year);
24         printf("需要再次查询么？是请选择y,结束请输入n");
25
26         getchar();
27         adj=getchar();
28         if(adj=='y')
29         {
30             goto start;
31         }
32         else if(adj=='n')
33         {
34             return 0;
35         }
36         else
37         {
38             printf("%c",adj);
39             printf("您又在考验我了\n");
40             return -1;
41         }
42     }
43     //三年后牛的头数
44     else
45     {
46     //第四年牛的头数
47         new=0;
48         middle=0;
49         old=1;
50
51         for(i=3;i<year;++i)
52         {
53             old=middle+old;
54             middle=new;
55             new=old;
56         }
57         total=new+middle+old;
58         printf("*************************第%d年共%d头牛\n",year,total);
59         printf("需要再次查询么？是请选择y,结束请输入n");
60         getchar();
61         adj=getchar();
62         if(adj=='y')
63         {
64             goto start;
65         }
66         else if(adj=='n')
67         {
68             return 0;
69         }
70         else
71         {
72             printf("%c",adj);
73             printf("您又在考验我了\n");
74             return -1;
75         }
76
77
78     }
79
80     return 0;
81 }
  请输入你需要查询第几年牛的头数：（年数必须大于0）10
*************************第10年共34头牛
需要再次查询么？是请选择y,结束请输入ny
请输入你需要查询第几年牛的头数：（年数必须大于0）4
*************************第4年共2头牛
需要再次查询么？是请选择y,结束请输入ny
请输入你需要查询第几年牛的头数：（年数必须大于0）5
*************************第5年共3头牛
需要再次查询么？是请选择y,结束请输入ny
请输入你需要查询第几年牛的头数：（年数必须大于0）6
*************************第6年共5头牛
需要再次查询么？是请选择y,结束请输入ny
请输入你需要查询第几年牛的头数：（年数必须大于0）7
*************************第7年共8头牛
需要再次查询么？是请选择y,结束请输入ny
请输入你需要查询第几年牛的头数：（年数必须大于0）8
*************************第8年共13头牛
需要再次查询么？是请选择y,结束请输入ny
请输入你需要查询第几年牛的头数：（年数必须大于0）9
*************************第9年共21头牛
需要再次查询么？是请选择y,结束请输入n

Private Function Cow() As Integer
    Dim intAge3 As Integer = 0
    Dim intAge2 As Integer = 0
    Dim intAge1 As Integer = 1
    Dim intTemp As Integer
    For i As Integer = 1 To n
      intTemp = intAge3
      intAge3 = intAge3 + intAge2
      intAge2 = intAge1
      intAge1 = intTemp
    Next
    Return intAge3 + intAge2 + intAge1
  End Function

Sorry I Don't Know
Thank You
Study

递归啊
public int getNum(int i) {
if (i < 3) {
return 1;
} else {
return getNum(i - 1) + getNum(i - 2); } }

    public class Cow
    {
        public Cow()
        {
        }
        private int _age = 0; //0岁。
        public int age
        {
            set { this._age = value; }
            get { return this._age; }
        }
    }    class Program
    {
        static void Main(string[] args)
        {
            ArrayList arr = new ArrayList();
            arr.Add(new Cow());//老本牛。            int cnt, years = 10;
            for (int i = 1; i<=years; i++)
            {
                cnt = arr.Count;//避免将新生的牛长大。
                for(int j = 0; j<cnt; j++)
                {
                    if ((((Cow)arr[j]).age != 0) && (((Cow)arr[j]).age + 1)>= 3 )
                    {
                        arr.Add(new Cow());//生牛
                    }                    ((Cow)arr[j]).age++;//长大。
                }
            }
            Console.WriteLine("total = " + arr.Count.ToString());
        }
    }   数组就可以解决啦！

题目一两种理解:一种就是一头牛从第三年开始就能下崽,那就是55头,算法如下:int x1=0;//1岁牛
int x2=0;//2岁牛
int x3=1;//可以生育的牛for(int x=3; x<=10; x++)
{
x3 = x3 + x2;//2岁牛长一岁,达到可生育
x2 = x1; //1岁牛长一岁,变2岁
x1 = x3; //可生育牛下的崽子都是一岁

//"第"+(x)+"年共有",x1+x2+x3, x1,x2,x3,
}
int Total=x1+x2+x3;//总牛数如果第四年才下崽,实际上应该是19头这个算法再加一个x4就可以了^^^

    public partial class _Default : System.Web.UI.Page
    {
        int year = 10;
        int value = 1;
        protected void Page_Load(object sender, EventArgs e)
        {            acc(year);
            Response.Write(value);
        }        private void acc(int y)
        {
            for (int i = 0; i < y; i++)
            {
                if (i > 1)
                {
                    value ++;
                    acc(y - i);
                }
            }
        }
    }C# asp.net环境，10年55头

恭喜正解首先出现在28楼
小试了一下：
public class Test { public static void main(String[] args) {
List cowList = new ArrayList<Cow>();
        Cow firstCow = new Cow(0); // 第一头牛
        cowList.add(firstCow);
        // 循环 10 年
        for(int yearth = 1; yearth <= 10; yearth++) {
         int cowChildSum = 0;
         for(int listIdx = 0; listIdx < cowList.size(); listIdx++) {
         Cow tempCow = (Cow)cowList.get(listIdx);
         //先给每头牛长一岁
         tempCow.addAge();
         cowList.set(listIdx, tempCow);
         //然后判断牛是否可生育，可：生小牛，记录个数
         if(tempCow.newChild()) {
         cowChildSum ++;
         }
         }
         for(int i= 1; i <= cowChildSum; i++) {
                cowList.add(new Cow(0));// 小牛年龄初始为0
         }
         //输出每年牛的总数
         System.out.println("第" + yearth + "年：" + cowList.size());
        }
}
}
class Cow{
    //牛的年龄
private int age;
public Cow (int age) {
this.age = age;
}
    // 判断此牛是否可以生育
public boolean newChild() {
if(age >= 3){
return true;
}else{
return false;
}
}
// 每一年，牛的年龄+1
public void addAge(){
age++;
}

}

调试易

经典的农夫养牛问题（常考的面试题）

解决方案 »