求高手帮忙解决生活中的问题

゛找不到╮回去的路 发布于 2011/08/02 15:43
阅读 1K+
收藏 1

本人刚开始学习java,老师出了个题,让我费尽脑汁想不出来,麻烦各位高手帮我解决一下,题目是这样的:

有20头牛,每头牛每年生出1头小牛,然后每头小牛每4年在生出一头小牛,问20年后总共有多少头牛?

谢谢各位java高手用for循环帮忙解决一下!!

加载中
1
风林火山
风林火山

应该是4年后小牛开始产仔吧。

20,40,60,80,120,180,260,380,560........

F(n)=F(n-1)+F(n-3) n>4

伪代码:

F(int n)

{

    if(n=0)

    {

          print(“输入必须大于 0!”);

          exit(1);

    }

    if(n<4)

    return (20*n+20);

   else

    return F(n-1)+F(n-3);

}

晓寒
晓寒
@张金富 : 证明过程见下面回复
张金富
张金富
还有这么个公式呀!这个更简洁,谁能证明下?
1
晓寒
晓寒
@张金富 和 @风林火山 的分析是正确的。
第 n 年的总牛数公式为:
f(n) = f(n-1) + f(n-3) (n > 4)
推导如下:

f(n)  为第 n 年总牛数
f(n)4 为第 n 年 4岁以上牛总数
f(n)3 为第 n 年 3岁牛总数
f(n)2 为第 n 年 2岁牛总数
f(n)1 为第 n 年 1岁牛总数

以下的结论是显而易见的:
f(n)4 = f(n-1)4 + f(n-1)3
f(n)3 = f(n-1)2
f(n)2 = f(n-1)1
f(n)1 = f(n)4

推导:
f(n) = f(n)4 + f(n)3 + f(n)2 + f(n)1
     = (f(n-1)4 + f(n-1)3 + f(n-1)2 + f(n-1)1) + f(n)1
     = f(n-1) + f(n)1
     = f(n-1) + f(n)4

f(n)4 = f(n-1)4 + f(n-1)3
      = f(n-2)4 + f(n-2)3 + f(n-2)2
      = f(n-3)4 + f(n-3)3 + f(n-3)2 + f(n-3)1
      = f(n-3)

由上: f(n) = f(n-1) + f(n)4 = f(n-1) + f(n-3)
张金富
张金富
牛就一个字!
0
张金富
张金富
生活中是不会出现这种单纯的问题的。时间再长点,地球不得撑爆了?
0
puxc
puxc
同意楼上,现在出这种问题的话肯定玩命质疑需求,敲定细节。哈哈,看到问题第一反应不是算法了,而是需求是否合理,完全了
0
兔bug
兔bug
你们俩都是在扯蛋!
0
鉴客
鉴客

粗粗看了下问题,觉得:

1. 前20头牛和生出来的新牛要分开计算
2. 生出的新牛可使用递归方法计算20年后的情况

0
puxc
puxc
    int parent = 20;
        int total = 20;
        int years = 20;
        int growUp = 4;
        int baby = 0;

        Map<Integer,Integer> map = new HashMap<Integer, Integer>();
        for(int i=1;i<=years;i++){
            map.put(i, parent);
            baby += parent;
            if(i >= growUp){
                for(int j=1;j<i;j++){
                    if(i-j>= growUp){
                        if(map.get(j)!=null){
                            parent = parent + map.get(j);
                            baby -=  map.get(j);
                            map.remove(j);
                        }
                    }
                }
            }
           
            System.out.println("第"+i+"年:全部"+total+";可以生宝宝的牛"+parent+";小母牛"+baby);
           
            total =total +  parent;
           
        }
        System.out.println(total);
゛找不到╮回去的路
゛找不到╮回去的路
麻烦问一下Map。。那一句什么意思?怎么看不懂?有错误!!
0
puxc
puxc
我就扯淡了,咋地吧
0
zhucb2009
zhucb2009

前3年增加的20,20,20 第4年开始 40,60,80....用递归了

package com.client;

public class Test {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(getSum(20));
	}
	
	public static int getSum(int n)
	{
		if(n<4)
		{
			return 20*n;
		}
		else
		{
			return getSum(n-1)+getSum(n-2);
		}
		
	}
}

张金富
张金富
数学功底不错,可惜分析错误了。
0
redraiment
redraiment

不晓得你的问题描述是否正确,是关于“然后每头小牛每4年在生出一头小牛”这句话。

这类递推题以前接触过不少,不过一般都是“小牛在4年后成长为大牛,也能每年生1头小牛”。如果是这种,那就是“斐波那契”序列,只不过 step = 4;

public class Main {
    public static void main(String[] args) {
        int[] cow = new int[21]; // 保存每年牛的总数
        cow[0] = 20;
        for (int year = 1; year <= 20; year++) {
            cow[year] = cow[year - 1] + cow[year > 3? year - 4: 0];
        }
        System.out.printf("After 20 years, you totally have %d cows.\n", cow[20]);
    }
}

运行结果是:After 20 years, you totally have 18140 cows.

但如果按照你题目的原意,那小牛和母牛要分开处理,因为它们各自的生育能力是不同的(母牛每年都能产仔,而小牛4年产1仔),那这个算法就有点类似求素数的筛法了(setp = 4):

public class Main {
    public static final int numberOfCows = 20;

    public static void main(String[] args) {
        int[] calf = new int[21]; // 仅保存每年出生的小牛的总数
        
        calf[0] = 0;
        for (int year = 1; year <= 20; year++) {
            calf[year] = numberOfCows; // 母牛每年产仔
        }
        
        for (int year = 1; year <= 20; year++) {
            for (int future = year + 4; future <= 20; future += 4) {
                calf[future] += calf[year]; // 小牛每4年产仔
            }
        }

        int total = numberOfCows;
        for (int year = 1; year <= 20; year++) {
            total += calf[year];
        }
        System.out.printf("After 20 years, you totally have %d cows.\n", total);
    }
}

运行结果是:After 20 years, you totally have 2500 cows.

返回顶部
顶部