空瓶子换水问题

时间:2022-04-19 03:53:47

近期看到有个有趣的问题,我简称为“空瓶子换水”问题,这里分两种情况,一种是有空瓶子,直接换水问题;另一种是知道怎么用空瓶子换水,如果满足一定数量的人喝水,需要至少买多少瓶问题。

这里假设3个空瓶子可以换1瓶水,那么针对上面的两个问题,有如下解释。

1. 有空瓶子,直接换水

对于计算方法,我这里提供两种,

第一种是比较笨拙的方法,假设有100个空瓶子,那个第一次换的为50,然后喝完再换,知道不能继续换为止。那么结果为:33+11+4+1=49;

第二种是,有M个空瓶子,N个瓶子可以换一瓶水(不是一瓶问题,要转换为一瓶问题),那么他可以换的瓶数为小于M/(N-1)的最大整数。针对第一种的情况,小于(100/(3-1))的为49.

 

2. 满足M人很水,需要买多少瓶

这里也有两种方法,和第一种情况有点类似,只是需要先买M瓶,再来换。这里假设满足100人喝水,需要至少买多少瓶。

第一种方法,穷举的方法,从估计的某个数开始尝试,直到找到符合的结果,代码如下:

#include<stdio.h>

int LeastNum(int base, int peopleNum, int begin)
{
	int res=0,temp;
	int temp_res,exchange;
	for(int i=begin; i<peopleNum; i++)
	{
		temp = i;
		temp_res = i;
		while(temp >= base)
		{
			exchange = temp / base;
			temp_res = temp_res + exchange;
			temp = exchange + temp % base;
		}
		if(temp_res >= peopleNum)
		{
			res = i;
			break;
		}
	}
	return res;
}
void main()
{


	// 商店做活动,3个空瓶可以换一瓶水,100个人同时去买水,请问至少需要买多少瓶水才能保证每个人都有一瓶水喝
	int base, peopNum;
	scanf_s("%d %d",&base, &peopNum);
	printf("The minimum purchaing count is %d \n",LeastNum(base,peopNum,60)); //我这里从60开始,也可以从1开始
}

 

第二种方法,和第一种情况第二种方法有些类似,可采用公式(X+(X/(N-1)))=M,这里X为需要购买的瓶数,最后求出的为大于X的最小正整数。正对满足100人问题,求出结果为66.7,那么最少需要买67瓶。