一个新的切 Cake 问题

※随风飘荡※

一次生日会，可能会有p或q个人参加，现准备了一个大蛋糕，只有1个，问最少切成多少块（不用每块大小一样），能使无论q或p个人参加，都能平均吃掉蛋糕
(切蛋糕前不知道到底是有q或p个人参加，只知道是这2种情况的人)

比如，如果有2个人或3个人参加
可以把蛋糕切分成4块
大小为3分之1，3分之1，6分之1，6分之1；

有高手能用C,or C++写吗
给个算法也可以

Yaci

我想了一下哈,不知道行不:
"切蛋糕前不知道到底是有q或p个人参加，只知道是这2种情况的人",首先排除p=q的情况.
若有p或q个人参加.
1:比较p,q的大小,比如说p>q;
2:将蛋糕分成p份,那么每分都为1/p;
3:保持q个1/p不动,(p-q)个1/p每个都分成q份,也就是每份大小1/pq.

不知道说的够不够明白哈,举几个例子.
p=4,q=3;将蛋糕分成4份,那么有3个1/4,3个1/12.
p=5,q=3;1/5,1/5,1/5, 1/15,1/15,1/15,1/15,1/15,1/15
p=8,q=3;3个1/8,15个1/24
p=8,q=5;5个1/8,9个1/24

可能考虑的不够全面,大家继续讨论吧

为爱种菜！

程序代码：

#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a,int b)
{
int r;
while(r=a%b){
a=b;
b=r;
}
return b;
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
int main()
{
int a,b,p,q,l;
while(scanf("%d %d",&p,&q)!=EOF){
if(p>q){
swap(p,q);
}
l=lcm(p,q);
a=l/p;
b=l/q;
printf("把蛋糕切分成%d块\n",(a-b+1)*p);
if(q==l){
printf("大小分别为%d个%d分之1\n",(a-b+1)*p,l);
}
else {
printf("大小分别为%d个%d分之1 和 %d个%d分之1\n",p,q,(a-b)*p,l);
}
}
}

为爱种菜！

代码:(思路是由斑竹提供)
其实只要知道规律就挺简单:

#include<iostream>
using namespace std;
void main()
{
int p,q;
cout<<"输入有可能来的人个数:\n";
cin>>p>>q;
int r;
if(p>q)
{
r=p%q;
cout<<"一共需要切"<<(p-r)<<"个 1/"<<p<<" 块蛋糕,\n";

cout<<"还需要切"<<(r*q)<<"个 1/"<<(p*q)<<" 块蛋糕!\n";

}
else
{
r=q%p;
cout<<"一共需要切"<<(q-r)<<"个 1/"<<q<<" 块蛋糕,\n";

cout<<"还需要切"<<(r*p)<<"个 1/"<<(p*q)<<" 块蛋糕!\n";
}
}

冰封シ绝恋

对于4 6的输入，你需要切12块，我只要切8块。

冰rose冰

是我没注意到切多的问题~~~
改进了一下:

#include<iostream>
using namespace std;
void main()
{
int p,q;
cout<<"输入有可能来的人个数:\n";
cin>>p>>q;
int r;
int number;
int value;
if(p>q)
{
r=p%q;
cout<<"一共需要切"<<(p-r)<<"个 1/"<<p<<" 块蛋糕,\n";

number=r*q;
value=p*q;
if(number%q==0)
{
number=number/2;
value=value/2;
}
cout<<"还需要切"<<number<<"个 1/"<<value<<" 块蛋糕!\n";

}
else
{
r=q%p;
cout<<"一共需要切"<<(q-r)<<"个 1/"<<q<<" 块蛋糕,\n";
number=r*p;
value=p*q;
if(number%p==0)
{
number=number/2;
value=value/2;
}

cout<<"还需要切"<<number<<"个 1/"<<value<<" 块蛋糕!\n";
}
}

尐妖

以下是引用leeco在2007-5-15 20:47:49的发言：

程序代码：

#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a,int b)
{
int r;
while(r=a%b){
a=b;
b=r;
}
return b;
}
int lcm(int a,int b)
{
return a/gcd(a,b)*b;
}
int main()
{
int a,b,p,q,l;
while(scanf("%d %d",&p,&q)!=EOF){
if(p>q){
swap(p,q);
}
l=lcm(p,q);
a=l/p;
b=l/q;
printf("把蛋糕切分成%d块\n",(a-b+1)*p);
if(q==l){
printf("大小分别为%d个%d分之1\n",(a-b+1)*p,l);
}
else {
printf("大小分别为%d个%d分之1 和 %d个%d分之1\n",p,q,(a-b)*p,l);
}
}
}

刚刚研究了一下,发现你和我的代码都有点问题~~~
比如4,7,
你要切4个1/7和12个1/28,一共16次
但其实可以切成
4个1/7,4个1/14,4个1/28,这样只要切12次