一道面试的笔试题，路过的看看吧 O(∩_∩)O~

zhangheng198913 2012-08-28 12:08:03
一头母牛从出生后，每两年可以生下一头母牛，即在第二年和第四年分别可产下一头母牛，出生后第五年将会死去。假设农场现有一头母牛，N年后农场的母牛数目是多少，编写程序实现
...全文
5849 167 打赏 收藏 转发到动态 举报
写回复
用AI写文章
167 条回复
切换为时间正序
请发表友善的回复…
发表回复
lvjing_CSDN 2012-09-04
  • 打赏
  • 举报
 回复 


#include <stdio.h>

#include <stdlib.h>

void  totalCow(unsigned n)

{

   unsigned years[5]={0,1},i = 1,new_born;/*years分别表示0-4岁的牛的总头数*/

   printf("%uth: year\t%u\n",i,years[0] + years[1] +years[2] + years[3] + years[4]);

   for(i = 2 ; i <= n; ++i)

   {

    new_born = years[1] + years[3];

    years[4] = years[3];

    years[3] = years[2];

    years[2] = years[1];

    years[1] = years[0];

    years[0] = new_born;

    printf("%uth: year\t%u\n",i,years[0] + years[1] +years[2] + years[3] + years[4]);

   }

}

int main()

{

  totalCow(80);

  return 0;

}
smsgreenlife 2012-09-04
  • 打赏
  • 举报
 回复
计算n年后的牛的数量，只需要计算矩阵的n次幂，计算n次幂可以有logn的算法。
[Quote=引用 154 楼 的回复:]
引用 152 楼 的回复:
相信“路遥知马力”大家都听说过吧

你让飞机和摩托车比百米赛跑，那肯定是摩托车赢，因为飞机还没起飞呢，摩托车就冲过终点了。


引用 130 楼 的回复:
正好有更精确的定时方法：

测试条件：Inter i7-2600,16G内存，64位Windows系统
Release版本：

10年
我的算法结果: 16
我的算法用时: 0.13975……
[/Quote]
lpp380 2012-09-03
  • 打赏
  • 举报
 回复
如何引用自己定义的头文件，新手请教。
[root@localhost text]# make
gcc -I./inc -c main.c -o main.o
gcc -c ./src/fun.c -o fun.o
./src/fun.c:1:17: error: head.h: No such file or directory
./src/fun.c: In function ‘fun’:
./src/fun.c:5: warning: incompatible implicit declaration of built-in function ‘printf’
make: *** [fun.o] Error 1

*******************************************
main.c

1 #include"head.h"
2
3 int main(void)
4 {
5 fun();
6 return 0;
7 }

**********************************************

fun.c

1 #include"head.h"
2
3 int fun(void)
4 {
5 printf("I am fun!");
6 return 0;
7 }
**************************************************

head.h


2 #include<stdio.h>
3
4 int fun(void);

*************************************************

makefile

1 all: main.o fun.o
2 gcc *.o -o main
3 main.o: main.c
4 gcc -I./inc -c main.c -o main.o
5 fun.o: ./src/fun.c
6 gcc -c ./src/fun.c -o fun.o
7 clean:
8 rm *.o -fr


*****************************************************
以上是原代码，请高手指教，谢谢！
新手急用
MYNAMELIULI 2012-09-03
  • 打赏
  • 举报
 回复
真是学习不少了
tjwsy 2012-09-03
  • 打赏
  • 举报
 回复
c#
public double GetCowCountNew(int year)
{
double[] arrayModel = new double[5] { 1, 0, 0, 0, 0 };
double[] tempModel = new double[5];
for (int i = 0; i < year; i++)
{
for (int j = 0; j < 5; j++)
{
tempModel[j] = arrayModel[j];
}
arrayModel[0] = tempModel[1] + tempModel[3];
arrayModel[1] = tempModel[0];
arrayModel[2] = tempModel[1];
arrayModel[3] = tempModel[2];
arrayModel[4] = tempModel[3];
}
return arrayModel[0] + arrayModel[1] + arrayModel[2] + arrayModel[3] + arrayModel[4];
}
CPPCODING 2012-09-02
  • 打赏
  • 举报
 回复
记得算法课上有这么一句话：

要想成为一个比较厉害的程序员，需要坚持两年每天编程。
要想成为一个世界级程序员，需要10年如一日的坚持编程，或者两年如一日的编程加一门算法课。
CPPCODING 2012-09-02
  • 打赏
  • 举报
 回复
[Quote=引用 152 楼 的回复:]
相信“路遥知马力”大家都听说过吧

你让飞机和摩托车比百米赛跑，那肯定是摩托车赢，因为飞机还没起飞呢，摩托车就冲过终点了。


引用 130 楼 的回复:
正好有更精确的定时方法：

测试条件：Inter i7-2600,16G内存，64位Windows系统
Release版本：

10年
我的算法结果: 16
我的算法用时: 0.139759毫秒
csdn的33楼的算……
[/Quote]

其实你的算法是挺牛的，开始没有仔细看，我按照121楼的方法，测了500000000年后的，33楼的用了3秒多，你的算法用了0.25ms，不在一个等级。

但是也有问题存在，根据规律，每过1000年，牛的头数的位数增加100位，到100万年后，数字的位数已经到了10万位了。

问题就是，33楼的算法，用的是加法，一个没有少算，
而你用的是矩阵运算，10万位的乘法你当成10位运算，恐怕少运算了很多吧。
试想，两个10万位数相乘和两个10位数相乘耗时会差多少呢？你的算法里面会用到多少次这样的乘法呢？


不考虑大数相乘的时间影响，你的算法是o（logn），公式法也是o(logn),你的确实略胜一筹。

但是也不能否认模版元加查表的方法（模版元定义宏或者枚举，用到的时候根据偏移查表），模版元是在编译期间运算好的，不过就是编译的时间长了点，但是也不失为一种一劳永逸的方法，只需要运算一次。


我的算法是最耗时，效率最低的一个，但是全部用的是面向对象的思维逻辑，这在框架设计时是必不可少的。

总之，各有各的用途，讨论一下，长了见识。你能把一维运算转到二维空间里，算法你是真牛（别管公牛母牛了）！能将一下你的原理吗？说不定其他地方能够用到呢。

kongpinggudaodeai 2012-09-02
  • 打赏
  • 举报
 回复
大家说的其实都有些道理，但也要倾听别人的意见，在讨论中学习，在学习中学会与人交往。我看了几十楼的评论，大家真的是好好考虑了，给我不少药学习的知识，谢谢大家了
flkejgoiejgiejgkejgh 2012-09-02
  • 打赏
  • 举报
 回复 
long myfun(int year){

	assert(year>=5);



	long ini_1;

	long ini_2;

	long tmp;



	if( year%2==0 ){

		ini_1=2;

		ini_2=4;

	}

	else if( year%2==1 ){

		ini_1=1;

		ini_2=2;



	}



	//递推求 裴波那契 序列

	//奇数从 fun(5)=fun(1)+fun(3) 开始

	//偶数从 fun(6)=fun(2)+fun(4) 开始

	for(int i=5+((year+1)%2);i<=year;i+=2){

		tmp=ini_1+ini_2;

		ini_1=ini_2;

		ini_2=tmp;

	}

	printf("%d years later total = %ld\n",year,ini_2);

	return ini_2;

}
adream307 2012-09-02
  • 打赏
  • 举报
 回复
using System;
class Test
{
static void Main()
{
int[] x=new int[5];
int[] bak=new int[5];
x[0]=1;
int n=int.Parse(Console.ReadLine());
while(n>0)
{
bak[0]=x[1]+x[3];
bak[1]=x[0];
bak[2]=x[1];
bak[3]=x[2];
bak[4]=x[3];
x[0]=bak[0];
x[1]=bak[1];
x[2]=bak[2];
x[3]=bak[3];
x[4]=bak[4];
n=n-1;
}
Console.WriteLine(x[0]+x[1]+x[2]+x[3]+x[4]);
}
}
与你相约 2012-09-02
  • 打赏
  • 举报
 回复
自己想一点思路都没有，明天再好好研究一下~~
光与影的平衡 2012-09-02
  • 打赏
  • 举报
 回复
#include<iostream>
using namespace std;


int main()
{
int year;
cin>>year;

//牛的寿命为5年，所以死去的牛为5年前的新牛的数量。

//当前牛的数量(第4年)
int cownum=4;

//2年生小牛，因此 2年也会死老牛。偶数年生牛，奇数年死牛；
//所以 2年为周期;
//i=1,从第一个周期开始，即2年开始;

//保存3个周期的牛数目
int cowold[3]={1,2,4}; //1,2,4为前3周期的牛的数目 即，0,2,4年，以下忽略前5年 直接从3个周期之后开始（第6年）。

//计算至最后一次生牛年；
for(int i=6;i<=year;i+=2)
{
//首先 除去去年死掉的牛。
//生牛和死牛不是同一年，即死去的牛是前3个周期的新牛,每个生牛年，新牛要占总牛数的一半
if(cowold[0]>1)
{
cownum=cownum-cowold[0]/2;
}
else
{
//只有1只就不是死一半了。。
cownum=cownum-1;
}
//新的总牛数；
cownum=cownum*2;
//更新数组
cowold[0]=cowold[1];
cowold[1]=cowold[2];
cowold[2]=cownum;
}
//判断输入年份是否为 死牛年（好悲剧的年份 - -!）
if(year % 2 == 1)
{
//是 ，则死掉一批牛 - -！
cownum=cownum-cowold[0];
}

cout<<"第"<<year<<"年: 有"<<cownum<<"头牛"<<endl;
}



╮(╯▽╰)╭。。。看到人家0（logn）的算法只能膜拜啊。。 咱只能写写这种了。。
CPPCODING 2012-09-02
  • 打赏
  • 举报
 回复

惭愧的是，在下算法没有学好。
感觉像是，时域频域，傅里叶变换之类的东西，但从来没有在实际中应用过。
smsgreenlife 2012-09-01
  • 打赏
  • 举报
 回复
相信“路遥知马力”大家都听说过吧

你让飞机和摩托车比百米赛跑，那肯定是摩托车赢，因为飞机还没起飞呢，摩托车就冲过终点了。

[Quote=引用 130 楼 的回复:]
正好有更精确的定时方法：

测试条件：Inter i7-2600,16G内存，64位Windows系统
Release版本：

10年
我的算法结果: 16
我的算法用时: 0.139759毫秒
csdn的33楼的算法结果: 16
csdn的33楼的算法用时: 0.072143毫秒
请按任意键继续. . .


50年
我的算法结果: 242786
我的算法用时: 0……
[/Quote]
bladeblue 2012-09-01
  • 打赏
  • 举报
 回复
两个N年后,还是一头,因为没公牛.
lp310018931 2012-09-01
  • 打赏
  • 举报
 回复
[Quote=引用 12 楼 的回复:]
11L的代码改了一下。笔误，不好意思。

C/C++ code

int CowCntAftNyears(int n)
{
int i,sum;
int a[5]={1,0,1,0,2}; /* increment */
if(n<0)return -1;
switch(n)
{
case 0:
cas……
[/Quote]这样做不对，那每5年死去没有考虑到吧？
蜡笔小新啦 2012-09-01
  • 打赏
  • 举报
 回复
其实完全可以 i+=2诶。
蜡笔小新啦 2012-09-01
  • 打赏
  • 举报
 回复
我的时间复杂度是O(n),
空间复杂度O(5)，
你们不要说多少毫秒行不？
蜡笔小新啦 2012-09-01
  • 打赏
  • 举报
 回复
就用一个5位数组来表示不同年龄的牛，每到一个偶数增加的时候就增加a[0]中牛数量。！
就这么简单啊。
int N=75;
int a[6]={0};
a[0]=1;
int total=1;int new1=0;
for(int i=0;i<N;i++)
{
new1=0;
total -= a[5];a[5]=0;
a[5] += a[4];a[4]=0;
a[4] += a[3];new1+=a[3];a[3]=0;
a[3] += a[2];a[2]=0;
a[2] += a[1];new1+=a[1];a[1]=0;
a[1] += a[0];a[0]=0;a[0]=new1;
total += new1;
}

cout << total << endl;
smsgreenlife 2012-09-01
  • 打赏
  • 举报
 回复
分析你的数据得出：从第五年开始每隔一年牛的数量翻一倍，太可怕了！！！！！！！！！！！！！！！
[Quote=引用 148 楼 的回复:]
欢迎给点意见：

Java code
public class T2 {
public static void count(int N){
// 各个岁数的牛的个数，age[0]保留不用
//age[1]的值表示1岁的牛的个数、age[2]的值表示2岁的牛的个数，以此类推
int age[] = { 0, 0, 0, 0, 0 ……
[/Quote]
加载更多回复（141）
java面试笔试题整理(学习java基础理论最好的资料)_2020Java笔试/面试题（持续收集整理更新）...
若是地址不相同，再看两个字符串内容是否相同，是的话也返回true。 String能够用字面量方式建立。String 是一个类，与其余类不一样的是，String可使用字面量的形式建立或赋值。 String str = "123"; /* 1 先到常量池...
2022Java笔试题选择题整理（附答案解析）走过路过不要错过了喂！
2022Java笔试题选择题
2011神州数码Java笔试面试题
2011神州数码Java笔试面试题 时间：2011-2-12 11:20:11 作者：Gjrencai.com 来源：【Gjava人才】 查看：7 评论：0 内容摘要：神州数码笔试面试题分享 1、把字符串转化成整形，不能用系统函数。 package jishi;...
漫谈Java IO之基础篇，java初级面试笔试题
我总结出了很多互联网公司的面试题及答案，并整理成了文档，以及各种学习的进阶学习资料，免费分享给大家。 扫描二维码或搜索下图红色VX号，加VX好友，拉你进【程序员面试学习交流群】免费领取。也欢迎各位一起在群...
智乐软件笔试题(Gameloft) C++
“是日也，天朗气清，惠风和畅。仰观宇宙之大，俯察品类之盛，... 为此再写XX公司笔试题之二（ C++）以寄托……===声明：本人在技术上向来支持直接明了问题根本，阐述问题，解答问题,力求让每个过客知道所以然，(Know
C语言

69,373

社区成员

243,080

社区内容

发帖
与我相关
我的任务
社区描述
C语言相关问题讨论
社区管理员
  • C语言
  • 花神庙码农
  • 架构师李肯
加入社区
  • 近7日
  • 近30日
  • 至今

加载中

查看更多榜单
社区公告
暂无公告

试试用AI创作助手写篇文章吧

+ 用AI写文章