主题：[讨论]猴子分桃问题 (要求用队列方法) 急用！
sucaigui
[专家分：0] 发布于 2008-03-17 15:59:00
[color=FF00FF][size=4]«问题描述：(要求用队列方法)
动物园里的n 只猴子编号为1，2，…，n，依次排成一队等待饲养员按规则分桃。动物
园的分桃规则是每只猴子可分得m 个桃子，但必须排队领取。饲养员循环地每次取出1 个，
2 个，…，k 个桃放入筐中，由排在队首的猴子领取。取到筐中的桃子数为k 后，又重新从
1 开始。当筐中桃子数加上队首猴子已取得的桃子数不超过m 时，队首的猴子可以全部取出
筐中桃子。取得桃子总数不足m 个的猴子，继续到队尾排队等候。当筐中桃子数加上队首猴
子已取得的桃子数超过m 时，队首的猴子只能取满m个，然后离开队列，筐中剩余的桃子由
下一只猴子取用。上述分桃过程一直进行到每只猴子都分到m 个桃子。
«实验任务：
对于给定的n，k和m，模拟上述猴子分桃过程。
«数据输入：
由文件input.txt 给出输入数据。第1 行中有3 个正整数n，k 和m，分别表示有n 只猴
子，每次最多取k个桃到筐中，每只猴子最终都分到m个桃子。
«结果输出:
将分桃过程中每只猴子离开队列的次序依次输出到文件output.txt。
输入文件示例 输出文件示例
input.txt output.txt
5 3 4 1 3 5 2
最后更新于：2008-03-18 12:19:00
回复列表 （共5个回复）
沙发
neulinux [专家分：420] 发布于 2008-03-17 18:25:00
我们首先假设num（tag），每经过15轮所有的num就会相等，并且此时tag回到初始序列！
0(1) 0(2) 0(3) 0(4) 0(5)
0(2) 0(3) 0(4) 0(5) 1(1)
0(3) 0(4) 0(5) 1(1) 2(2)
0(4) 0(5) 1(1) 2(2) 3(3)
0(5) 1(1) 2(2) 3(3) 1(4)
1(1) 2(2) 3(3) 1(4) 2(5)
2(2) 3(3) 1(4) 2(5) 4(1)
3(3) 1(4) 2(5) 4(1) 3(2)
1(4) 2(5) 4(1) 3(2) 5(3)
2(5) 4(1) 3(2) 5(3) 4(4)
4(1) 3(2) 5(3) 4(4) 3(5)
3(2) 5(3) 4(4) 3(5) 6(1)
5(3) 4(4) 3(5) 6(1) 6(2)
4(4) 3(5) 6(1) 6(2) 6(3)
3(5) 6(1) 6(2) 6(3) 6(4)
6(1) 6(2) 6(3) 6(4) 6(5)
所以，如果以上的过程符合题意那么到num=36时，见再次出现相等的情况：
36(1) 36(2) 36(3) 36(4) 36(5) +1 r=0
36(2) 36(3) 36(4) 36(5) 37(1) +2 r=0
36(3) 36(4) 36(5) 37(1) 38(2) +3 r=0
36(4) 36(5) 37(1) 38(2) 39(3) +1 r=0
36(5) 37(1) 38(2) 39(3) 37(4) +2 r=0
37(1) 38(2) 39(3) 37(4) 38(5) +3 r=0
1 38(2) 39(3) 37(4) 38(5) +1 r=0
39(3) 37(4) 38(5) 39(2) +2 r=0
3 37(4) 38(5) 39(2) +3 r=1
4 38(5) 39(2) +1 r=1
5 39(2) +2 r=0
2
[quote]
input.txt output.txt
5 3 40 1 3 5 2
[/quote]
所以我认为output.txt不正确
板凳
天之痕99 [专家分：40] 发布于 2008-03-18 11:21:00
struct Monkey
{
int peachesInHand;
int MonkeyNo;
Monkey(int p, int n) : peachesInHand(p), MonkeyNo(n) {}
void increasePeach(int inc) { peachesInHand += inc; }
};
class Peach
{
public:
Peach(int n, int k, int m) : nMonkey(n), round(k), sum(m) { assert(nMonkey != 0 && round != 0 && sum != 0); }
queue<int> dividePeach();
private:
int n, k, m;
};
Peach::dividePeach()
{
int basket = 0;
queue<int> result;
queue<Monkey> Monkeys;
for (int index = 1; index <= n; ++index)
Monkeys.push(Monkey(0, index);
while (!Monkeys.empty())
{
for (int i = 1; i <= round; ++i)
{
Monkey& front = Monkeys.front();
front.inceasePeach(i + basket);
basket = 0;
if (front.peachesInHand >= sum) //monkey leaves queue
{
basket = front.peachesInHand - sum;
Monkeys.pop();
result.push(front);
if (Monkeys.empty())
break;
}
else //go back to the end of queue
{
Monkeys.pop();
Monkeys.push(front);
}
}
}
return result;
}
3 楼
sucaigui [专家分：0] 发布于 2008-03-18 12:23:00
呵呵，output确实错了，40应该为4，还有没有更好的C语言队列 的方法可以解这题啊
4 楼
didorong [专家分：30] 发布于 2008-03-23 19:24:00
#include"stdio.h"
#include"malloc.h"
void main()
{
int n,k,m;
int i,j;
int sub=0,p=0,flag=0;
int *queue;
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
scanf("%d %d %d",&n,&k,&m);
queue=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
queue[i]=0;
/*sub是用来存放多余的桃子。flag是用来控制循环用的。*/
while(flag<n)
{
for(j=0;j<n;j++)
{
if(queue[j]>=m) /*这只猴子已经领满m个桃子。*/
continue;
else if((queue[j]+p%k+1<m)&&(sub==0))
/*这只猴子还要继续领取他的桃子。*/
{
queue[j]=queue[j]+p%k+1;
p++;
}
else if((sub==0)&&(queue[j]+p%k+1>=m))
/*这只猴子刚领满m个桃子。*/
{
sub=queue[j]+(p%k)+1-m;
queue[j]=m;
p++;
flag++;
printf("%d ",j+1);
}
else if((sub+queue[j]<m)&&(sub!=0))
/*这只猴子还要继续领取他的桃子。*/
{
queue[j]=queue[j]+sub;
sub=0;
}
else if((queue[j]+sub>=m)&&(sub!=0))
/*这只猴子刚领满m个桃子。*/
{
sub=sub+queue[j]-m;
queue[j]=m;
flag++;
printf("%d ",j+1);
}
}
}
}
5 楼
didorong [专家分：30] 发布于 2008-03-23 19:25:00
不会是一个系的人吧
这是作业啊~~~~~~~~~~~~
我来回复
您所在位置：