事先声明这个题我没做出来,不能本地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 <iostream> 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<<result<<endl; }另附一个能打印数组d的代码,更直观地查看打渔情况
#include <iostream> 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<<d1[i]<<' '; cout<<'\n'; } } 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<<result<<endl; }
顺便把第一题也附上吧,就是计算等额本金和等额本息还款,用的二分法,虽然有公式可以直接计算~~但公式好像没那么好推。
#include <iostream> 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<m;i++){//计算等额本金还款每月还款d2[m]和总计sum 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<m;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<m;i++){ temp+=temp*r; temp-=d1; } } for(i=0;i<m;i++){ printf("%0.2f ",d1); } printf("%0.2f \n",d1*m); for(i=0;i<m;i++){ printf("%0.2f ",d2[i]); } printf("%0.2f \n",sum); }
全部评论
(2) 回帖