李白打酒

喜欢ヅ旅行 2022-08-02 06:53 139阅读 0赞

话说大诗人李白，一生好饮。幸好他从不开车。一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：

无事街上走，提壶去打酒。

逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。

请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。

参考代码：

回溯方法：

#include<stdio.h>
    
    int wine,shop,flower,s[15],count;
    void backtrack(int t)
    {
    	int i;
    	if(t==15){
    		if(shop==5&&flower==10&&!wine&&!s[14]){
    			count++;
    			for(i=0;i<15;i++){
    				if(s[i]){
    					putchar('a');
    					putchar(' ');
    				}else{
    					putchar('b');
    					putchar(' ');
    				}
    			}
    			putchar('\n');
    		}
    	}else{
    		//遇到店
    		wine*=2;
    		shop+=1;
    		s[t]=1;
    		backtrack(t+1);
    		wine/=2;
    		shop-=1;
    		s[t]=-1;
    
    		//遇到花
    		wine--;
    		flower++;
    		s[t]=0;
    		backtrack(t+1);
    		wine++;
    		flower--;
    		s[t]=-1;
    
    
    	}
    	
    }
    
    int main()
    {
    	int i;
    	shop=0;
    	flower=0;
    	wine=2;
    	count=0;
    	for(i=0;i<15;i++)
    		s[i]=-1;
    	backtrack(0);
    	printf("The number of result is:%d.\n",count);
    
    	return 0;
    }

暴力求解：

#include<stdio.h>
    #include<math.h>
    
    int main()
    {
    	int wine=2,num=pow(2,15),shop=0,flower=0;
    	int i,j,temp,count=0,mark=0;
    	
    	for(i=0;i<num;i++)
    	{
    		wine=2,shop=0,flower=0;
    		temp=i;j=15;
    		while(j>0){
    			if(temp%2){
    				wine*=2;
    				shop++;
    				mark=0;
    			}else{
    				wine--;
    				flower++;
    				mark=1;
    			}
    			temp/=2;
    			j--;
    		}
    		if(flower==10&&shop==5&&wine==0&&mark){
    			temp=i;
    			count++;
    			j=15;
    			while(j>0){
    			if(temp%2){
    				putchar('a');
    			}else{
    				putchar('b');
    			}
    			temp/=2;
    			j--;
    			}
    			putchar('\n');
    		}
    	}
    
    	printf("The number of result is:%d.\n",count);
    
    	return 0;
    }