事先声明这个题我没做出来，不能本地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) 回帖