一个新的切 Cake 问题 - 编程论坛

#2

yuyunliuhen2007-04-22 19:18

我想了一下哈,不知道行不:
"切蛋糕前不知道到底是有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

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

#3

leeco2007-05-15 20:47

#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

kisscjy2007-05-16 15:34

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

#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";
}
}

#5

leeco2007-05-16 15:46

回复：（kisscjy）代码:(思路是由斑竹提供)其实只要知...

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

#6

kisscjy2007-05-16 16:53

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

#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";
}
}

#7

kisscjy2007-05-16 17:03

以下是引用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次

#8

幸福等待2011-05-17 19:34

#include<stdio.h>

int gongbeishu(int n,int m)
{
    int c=m%n;
    while(c!=0)
    {
        m=n;
        n=c;
        c=m%n;
    }
    return n;
}
int daxiao(int a,int b)
{
    return a<b?a:b;
}
int main()
{
    int n,m;
    int min;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n>m)
        {
            min=daxiao(n-m,gongbeishu(m,n));
            printf("%d\n",n-gongbeishu(m,n)+min*m/gongbeishu(m,n));
        }
        else
        {
            min=daxiao(m-n,gongbeishu(n,m));
            printf("%d\n",m-gongbeishu(n,m)+min*n/gongbeishu(n,m));
        }
    }
    return 0;
}

这个代码哪里有问题啊真是麻烦啊