当前位置:   article > 正文

乐鑫笔试c语言编程题,8-2乐鑫笔试编程题第二题-打渔(递归法)

乐鑫 编程题

事先声明这个题我没做出来,不能本地IDE我真的不知道我的输出结果是啥啊。。。。错了都不知道从哪改,难受~~

考完在本地调了下很快就改出来了(其实就写错了一行),更加难受。。。

由于我没做出来,可能我的理解有误,要是理解错了大家看看就好。。。

原题:

有个渔民 每天可以选择打鱼或者休息,打鱼一天可以够吃两天,但是第k天必须休息,最后一天(即第2n天,也就是说总共天数必须是偶数)鱼必须吃完。

要求输入n,k,输出共有多少种不同打渔情况。

个人理解:

假定建立一个数组 bool d[2*n]; d[i]表示第i+1天打渔情况,1表示打渔,0表示休息。

1.第一天必须打鱼,不然没鱼吃 d[0]=1;

2.第k天必须休息 d[k-1]=0;

3.个人理解的隐藏条件:鱼的保质期就能放到下一天,也就是说第i天打的鱼第i+2天就不能吃了,也就是说要想第i天休息,只能在第i-1天打鱼。转换到数组d上就是不可能存在d[i-1]=d[i]=0

4.最后一天吃完鱼,即倒数第二天打渔,最后一天休息,d[2*n-2]=1;

d[2*n-1]=0;

题解:

目前就想到了最直接的递归算法,也不知道会不会递归太多导致超时,先放出来大家看一下好了

#include 

using namespace std;

int n,k;//k天必须休息,2n天必须吃完

long result;//最终结果

void xuanze(int t,bool p){//t为当前组,两天一组,共n组,p为上一组最后一天是打渔(1)还是休息(0)

if (t==n) result++;//每次得到一个解result++;

else{

if(2*t-1==k) xuanze(t+1,1);//2*(t-1)==k-1 第t组第一个数就是k-1(第k天)

else if(2*t==k) xuanze(t+1,0);//2*(t-1)+1==k-1 第t组第二个数是k-1

else if(2*t+1==k){//2*(t-1)+2==k-1 第t+1组第一个数是k-1

if(p) {

xuanze(t+1,1);//第t组两天打渔情况为01

xuanze(t+1,1);//11

}

else{

xuanze(t+1,1);//11

}

}

else {

if(p) {

xuanze(t+1,0);//10

xuanze(t+1,1);//11

xuanze(t+1,1);//01

}

else{

xuanze(t+1,0);//10

xuanze(t+1,1);//11

}

}

}

}

int main() {

cin >>n>>k;

xuanze(1,0);

cout<

} 另附一个能打印数组d的代码,更直观地查看打渔情况

#include 

using namespace std;

int n,k;//k天必须休息,2n天必须吃完

long result;

void xuanze(int t,bool* d){

int i;

bool d1[2*n];

for(i=0;i<2*n;i++){

d1[i]=d[i];

}

if (t==n) {

d1[2*(t-1)]=1;d1[2*(t-1)+1]=0;

if (d1[k-1]==0) {

result++;

for(i=0;i<2*n;i++) cout<

cout<

}

}

else {

if(d[2*(t-1)-1]) {

d1[2*(t-1)]=0;d1[2*(t-1)+1]=1;xuanze(t+1,d1);

d1[2*(t-1)]=1;d1[2*(t-1)+1]=1;xuanze(t+1,d1);

d1[2*(t-1)]=1;d1[2*(t-1)+1]=0;xuanze(t+1,d1);

}

else{

d1[2*(t-1)]=1;d1[2*(t-1)+1]=0;xuanze(t+1,d1);

d1[2*(t-1)]=1;d1[2*(t-1)+1]=1;xuanze(t+1,d1);

}

}

}

int main() {

int i;

cin >>n>>k;

bool d[2*n];

for(i=0;i<2*n;i++){

d[i]=0;

}

d[0]=1;

if (k==2){

d[1]=0;

xuanze(2,d);

}

else if(k==3){

d[1]=1;

xuanze(2,d);

}

else{

d[1]=0;

xuanze(2,d);

d[1]=1;

xuanze(2,d);

}

cout<

}

顺便把第一题也附上吧,就是计算等额本金和等额本息还款,用的二分法,虽然有公式可以直接计算~~但公式好像没那么好推。

#include 

using namespace std;

int main(){

float t,r;

int m,i;

cin>>t>>r>>m;//t金额 r利率 m期数

float temp=t,sum=0,templ,tempr;

r/=1200.0;//月利率

float d1,d2[m];

for(i=0;i

d2[i]=t/m+temp*r;

temp-=t/m;

sum+=d2[i];

}

d1=(d2[m-1]+d2[0])/2;//d1为等额本息,必定介于等额本金d2[m]的最大金额和最小金额之间

temp=t;

templ=d2[m-1];

tempr=d2[0];

for(i=0;i

temp+=temp*r;

temp-=d1;

}

while(temp>=0.01||temp<=-0.01){//二分法求d1

if(temp>0){//钱没还完,d1小了

templ=d1;

d1=(templ+tempr)/2;

}

else{//钱还多了,d1大了

tempr=d1;

d1=(templ+tempr)/2;

}

temp=t;

for(i=0;i

temp+=temp*r;

temp-=d1;

}

}

for(i=0;i

printf("%0.2f ",d1);

}

printf("%0.2f \n",d1*m);

for(i=0;i

printf("%0.2f ",d2[i]);

}

printf("%0.2f \n",sum);

}

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/1018393
推荐阅读
相关标签
  

闽ICP备14008679号