算法帖：砝码

Miu

算法帖
一个40g重的砝码，掉在地上摔成4块，每块都是整数，且这4块砝码可用来称量1~40g的任何物体。
3星期内有效，前2名奖金50元。任何语言。

荣誉勋章

和游戏有关吗?

Miu

嗯，有点关系，请大家支持。

Miu

评委不是我，绝对公平。
我先发，大家写好后跟帖，前2名（程序质量）50元。

justgame

Miu: 算法帖：砝码

算法帖
一个40g重的砝码，掉在地上摔成4块，每块都是整数，且这4块砝码可用来称量1~40g的任何物体。
3星期内有效，前2名奖金50元。任何语言。

需要做碰撞效果吗?我是说相互碰撞或掉在地上然后有弹起.最好四块的形状每次都不一样.

荣誉勋章

这个程序吗？

LoLitter

5楼的似乎理解错了，一看楼主就是在中学或者大学搞竞赛的同志，用Pascal编控制台程序。我觉得这个程序写的效率是比较低的，而且GOTO太多，也非常难看，比较好的办法是应该先数学证明一定有1
如果没有1, 用3个砝码必然不可能和为39，如果是2边相减得到39，那其中一边总重量必然大于40，所以肯定有一个1
剩下的3个用类似动态规划的方法求解

#include<iostream>
typedef unsigned short WORD;

//*****************************
//用数组和引用两种方式保存四个砝码的重量
//好处在后面的代码中可以看出
WORD Weight[4];
WORD &W1=Weight[0];
WORD &W2=Weight[1];
WORD &W3=Weight[2];
WORD &W4=Weight[3];
//*****************************

//是否能称出这个重量的物品
//Can[w]=true代表可以称出,否则无法称出
bool Can[41];

int main()
{
        //W1=1很容易证明,通过可以称出39来反证
        W1=1;
        //W2最大值为37,此时其它三个砝码都是1
        for (W2=1;W2<=37;W2++)
        {
                //W3最大值为38-W2
                for(W3=1;W3<38-W2;W3++)
                {
                        W4=40-W1-W2-W3;
                        //初始化Can数组
                        memset(Can,0,sizeof(Can));
                        Can[0]=true;
                        Can[1]=true;
                        //遍历第2~4个砝码的重量
                        for(WORD w=1;w<=3;w++)
                        {
                                //这个用来保存Can的一个副本
                                bool CanCopy[41];
                                memcpy(CanCopy,Can,sizeof(Can));
                                for(WORD i=0;i<=40;i++)
                                {
                                        //如果i能称出,那么i加上或减去目前砝码的重量也可以称出
                                        if (CanCopy)
                                        {
                                                Can[Weight[w]+i]=true;
                                                Can[abs(Weight[w]-i)]=true;
                                        }
                                }
                        }
                        //检查是否成功
                        bool Success=true;
                        for(WORD i=1;i<=40;i++)
                        {
                                if(!Can)
                                {
                                        Success=false;
                                        break;
                                }
                        }
                        if (Success)
                        {
                                std::cout<<W1<<" "<<W2<<" "<<W3<<" "<<W4<<std::endl;
                        }
                }
        }
        return 0;
}

LoLitter

楼主的程序只能求出4组解，我的能求出全排列的6组，而且我的要快得多

LoLitter

用GetTickCount(似乎精确度不算太高)测速，没有用时间

sandy_zc_1

嗯，终于有研究算法的了。

楼主的题目发的不太清楚和规范，比如求什么就没有明确写出。