【用计算机求解经典问题】难忘的五猴分桃
2008-03-08 12:28:42 来源:WEB开发网核心提示:/*问题描述*//**五只猴子一起摘了一堆桃子,因为太累,【用计算机求解经典问题】难忘的五猴分桃,决定先睡一觉再分,*过了不知多久,(2)这是一种比较直接的算法,有许多地方值得改进,来了一只猴子,它见别的猴子没来
/*问题描述*/
/*
*五只猴子一起摘了一堆桃子,因为太累,决定先睡一觉再分。
*过了不知多久,来了一只猴子,它见别的猴子没来,便将一堆桃子平均分成 5 份,结果*多了一个,就将多的这个吃了,拿走其中的一堆。
*又过了不知多久,第二只猴子来了,它不知道有一个同伴已经来过,还以为自己是第一*个,便将地上的桃子平均分成 5 份,发现也多了一个,同样吃了这一个,拿走其中的一*堆。第3只,第4只,第5 只猴子都是这样......
*问这5只猴子至少摘了多少个桃子?
*/ /* 程序说明: (1)修改宏 MAXNUM 的大小,重新编译后即可搜索出所有0~MAXNUM 之间满足条件的数字。 (2)这是一种比较直接的算法,有许多地方值得改进。欢迎大家一起探讨 (3)本程序用vc++6.0在win2000环境中编译通过。 */ /*zhaitao.c*/ #include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "string.h" #define bool int
#define true 1
#define false 0 #define MAXNUM 5000 /*target number strUCt*/
typedef struct tagTARGETNUM
{
int totalN;
int remains;
} _TargetNum, *p_TargetNum; typedef struct tagTAGTEST
{
_TargetNum targetNum[MAXNUM];
int count; /*num satisfied our condition*/
}_tagTest, p_tagTest; bool monkey(int iOriginal, int * PRemains);
bool SepPeach(int iTotal, int *remains);
void FindSmallest(_tagTest* tgtst); void main(void)
{
int i = 0;
int tempRmn = 0;
bool ret = false;
_tagTest tgtst;
memset(&tgtst,0,sizeof(_tagTest));
printf("test-- from:%d , to:%d press any key to continue ",i,MAXNUM);
getchar();
printf("starting find... "); for(; i < MAXNUM; i++)
{
if( (ret = SepPeach(i,&tempRmn)) != true)
else
{
tgtst.targetNum[tgtst.count].totalN = i;
tgtst.targetNum[tgtst.count++].remains = tempRmn;
}
} FindSmallest(&tgtst);
getchar();
} /************************************************************************/
/* if the original number satified our condition,
the function will return true, else return false. */
/************************************************************************/
bool monkey(int iOriginal, int * pRemains)
{
// int remains = 0;
iOriginal -= 1; //remain 1
if (iOriginal % 5 != 0)
{
return false;
}
*pRemains = iOriginal - iOriginal/5;
return true;
} bool SepPeach(int iTotal, int* remains)
{
int flag = false;
int tempNum = 0; //temporary number of remained peaches
int i = 0;
tempNum = iTotal;
for(i = 0; i < 5; i++)
{
if((flag = monkey(tempNum, &tempNum)) == false)
{
printf("total num of peaches %d does not satisfy our condition! ",iTotal);
return false;
}
}
*remains = tempNum;
printf("total num of peaches: %d, remains: %d ", iTotal, *remains);
return true;
} void FindSmallest(_tagTest* tgtst)
{
int i;
//int temp = -1;
_TargetNum tempTn;
tempTn.totalN = 1000000;
printf("we found %d nums which satisfied our condition ",tgtst->count);
if (tgtst->count == 0)
else
{
printf("----these nums are: ");
}
for(i = 0; i < tgtst->count; i++)
{
printf("total:%d remains:%d ",tgtst->targetNum[i].totalN,tgtst->targetNum[i].remains);
if(tempTn.totalN >= tgtst->targetNum[i].totalN)
{
tempTn.totalN = tgtst->targetNum[i].totalN;
tempTn.remains = tgtst->targetNum[i].remains;
} }
printf(" ---------------------------------------- ");
printf("the smallest total num of peaches is: %d, the remains is: %d ",tempTn.totalN,tempTn.remains);
return;
}
*过了不知多久,来了一只猴子,它见别的猴子没来,便将一堆桃子平均分成 5 份,结果*多了一个,就将多的这个吃了,拿走其中的一堆。
*又过了不知多久,第二只猴子来了,它不知道有一个同伴已经来过,还以为自己是第一*个,便将地上的桃子平均分成 5 份,发现也多了一个,同样吃了这一个,拿走其中的一*堆。第3只,第4只,第5 只猴子都是这样......
*问这5只猴子至少摘了多少个桃子?
*/ /* 程序说明: (1)修改宏 MAXNUM 的大小,重新编译后即可搜索出所有0~MAXNUM 之间满足条件的数字。 (2)这是一种比较直接的算法,有许多地方值得改进。欢迎大家一起探讨 (3)本程序用vc++6.0在win2000环境中编译通过。 */ /*zhaitao.c*/ #include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "string.h" #define bool int
#define true 1
#define false 0 #define MAXNUM 5000 /*target number strUCt*/
typedef struct tagTARGETNUM
{
int totalN;
int remains;
} _TargetNum, *p_TargetNum; typedef struct tagTAGTEST
{
_TargetNum targetNum[MAXNUM];
int count; /*num satisfied our condition*/
}_tagTest, p_tagTest; bool monkey(int iOriginal, int * PRemains);
bool SepPeach(int iTotal, int *remains);
void FindSmallest(_tagTest* tgtst); void main(void)
{
int i = 0;
int tempRmn = 0;
bool ret = false;
_tagTest tgtst;
memset(&tgtst,0,sizeof(_tagTest));
printf("test-- from:%d , to:%d press any key to continue ",i,MAXNUM);
getchar();
printf("starting find... "); for(; i < MAXNUM; i++)
{
if( (ret = SepPeach(i,&tempRmn)) != true)
else
{
tgtst.targetNum[tgtst.count].totalN = i;
tgtst.targetNum[tgtst.count++].remains = tempRmn;
}
} FindSmallest(&tgtst);
getchar();
} /************************************************************************/
/* if the original number satified our condition,
the function will return true, else return false. */
/************************************************************************/
bool monkey(int iOriginal, int * pRemains)
{
// int remains = 0;
iOriginal -= 1; //remain 1
if (iOriginal % 5 != 0)
{
return false;
}
*pRemains = iOriginal - iOriginal/5;
return true;
} bool SepPeach(int iTotal, int* remains)
{
int flag = false;
int tempNum = 0; //temporary number of remained peaches
int i = 0;
tempNum = iTotal;
for(i = 0; i < 5; i++)
{
if((flag = monkey(tempNum, &tempNum)) == false)
{
printf("total num of peaches %d does not satisfy our condition! ",iTotal);
return false;
}
}
*remains = tempNum;
printf("total num of peaches: %d, remains: %d ", iTotal, *remains);
return true;
} void FindSmallest(_tagTest* tgtst)
{
int i;
//int temp = -1;
_TargetNum tempTn;
tempTn.totalN = 1000000;
printf("we found %d nums which satisfied our condition ",tgtst->count);
if (tgtst->count == 0)
else
{
printf("----these nums are: ");
}
for(i = 0; i < tgtst->count; i++)
{
printf("total:%d remains:%d ",tgtst->targetNum[i].totalN,tgtst->targetNum[i].remains);
if(tempTn.totalN >= tgtst->targetNum[i].totalN)
{
tempTn.totalN = tgtst->targetNum[i].totalN;
tempTn.remains = tgtst->targetNum[i].remains;
} }
printf(" ---------------------------------------- ");
printf("the smallest total num of peaches is: %d, the remains is: %d ",tempTn.totalN,tempTn.remains);
return;
}
[]
更多精彩
赞助商链接