砝码称重问题

晨曦之光 发布于 2012/03/09 14:15
阅读 312
收藏 0

本博客(http://blog.csdn.net/livelylittlefish)贴出作者(三二一、小鱼)相关研究、学习内容所做的笔记,欢迎广大朋友指正!

 

砝码称重问题

 

问题:4个砝码,每个重量都是整数克,总重量为40克,放在天平上可以称出1~40克的物体。求这4个砝码各多少克。

 

1. 问题分析

设4个砝码的重量分别为w1、w2、w3、w4,则w1+w2+w3+w4=40,且w1,w2,w3,w4均为正整数。
假设不相等(假设w1<w2<w3<w4),故砝码中最大为34克。

称重的天平有物体盘和砝码盘,称重时,若砝码只放在砝码盘,则
物体质量=砝码盘砝码质量
但若砝码盘和物体盘中都放置了砝码,则
物体质量=砝码盘砝码质量-物体盘砝码质量

 

从1~40,任意一个数,都应该能找到相应的砝码放置方法。砝码只有4个,且每次称重时,这4个砝码只能出现0次或者1次,且砝码要么在物体盘,要么在砝码盘,要解该问题,应该转换思路。
假设砝码在物体盘,认定其出现-1次
假设砝码在砝码盘,认定其出现1次
若该次称重,不需要该砝码,认定其出现0次

 

设4个砝码在每次称重中出现的次数分别为x1,x2,x3,x4,则只有-1、0、1这三种取值

如上分析,找到的砝码组合个数应该为40个(即1~40中的任意一个数都有对应的砝码组合)

 

2. C++版

/************************************************************************
 * 4个砝码,每个重量都是整数克,总重量为40克,放在天平上可以称出1~40克的
 * 物体。求这4个砝码各多少克。
 * C++版
 ************************************************************************/
#include <stdio.h>

class CWeight
{
	int w1,w2,w3,w4;	//砝码的重量

	//砝码总重量
	static const int TOTALWEIGHT=40;

	//4个砝码,w1+w2+w3+w4=40,且w1,w2,w3,w4均为整数,假设不相等(假设w1<w2<w3<w4)故最大为34
	static const int MAXWEIGHT=34;
public:
	CWeight(){w1=w2=w3=w4=0;}
	~CWeight(){}

	void Calculate();
	bool weight(int w1,int w2,int w3,int w4);
	void output(int w1,int w2,int w3,int w4);
};

void CWeight::Calculate()
{
	int w1,w2,w3,w4;
	for (w1=1;w1<=MAXWEIGHT;w1++)
	{
		for (w2=w1+1;w2<=MAXWEIGHT;w2++)
		{
			for (w3=w2+1;w3<=MAXWEIGHT;w3++)
			{
				for (w4=w3+1;w4<=MAXWEIGHT;w4++)
				{
					if (w1+w2+w3+w4==TOTALWEIGHT)
					{
						if (weight(w1,w2,w3,w4))
						{
							printf("w1=%d w2=%d w3=%d w4=%d/n",w1,w2,w3,w4);
							output(w1,w2,w3,w4);
						}						
					}
				}
			}
		}
	}
}

//从1~40,不管哪个重量都要找到相应的砝码放置方法
//w1,w2,w3,w4分别为4个砝码的重量
bool CWeight::weight(int w1,int w2,int w3,int w4)
{
	int w;	//物体重量
	
	//砝码只有4个,且每次称重时,这4个砝码只能出现0次或者1次
	//出现时,砝码要么在物体盘,要么在砝码盘,要解该问题,转换思路
	//假设砝码在物体盘,认定其出现-1次
	//假设砝码在砝码盘,认定其出现1次
	//若该次称重,不需要该砝码,认定其出现0次
	//4个砝码在每次称重中出现的次数
	int x1,x2,x3,x4;	//只有-1,0,1这三种取值

	int count=0;		//找到的砝码组合个数

	//对1~40中的每个重量,都要找到相应的砝码组合
	//若有一个w(1<=w<=TOTALWEIGHT)没有找到相应的砝码组合,则表明该组砝码值不是所求
	for (w=1;w<=TOTALWEIGHT;w++)	
	{
		for (x1=-1;x1<=1;x1++)
		{
			for (x2=-1;x2<=1;x2++)
			{
				for (x3=-1;x3<=1;x3++)
				{
					for (x4=-1;x4<=1;x4++)
					{
						if (w1*x1+w2*x2+w3*x3+w4*x4==w)
						{
							count++;

							//找到该重量对应的砝码组合后,继续下一个重量
							x1=x2=x3=x4=2;
						}
					}
				}
			}
		}
	}

	//如果找到所有的1~TOTALWEIGHT的砝码组合,则该组砝码值即为所求
	if (count==TOTALWEIGHT)
		return true;
	else
		return false;
}

//输出1~40中每个重量对应的砝码组合(负数表示该砝码放在物体盘)
void CWeight::output(int w1,int w2,int w3,int w4)
{
	int w;	//物体重量
	int x1,x2,x3,x4;	//只有-1,0,1这三种取值

	//对1~TOTALWEIGHT中的每个重量,都要找到相应的砝码组合
	for (w=1;w<=TOTALWEIGHT;w++)	
	{
		for (x1=-1;x1<=1;x1++)
		{
			for (x2=-1;x2<=1;x2++)
			{
				for (x3=-1;x3<=1;x3++)
				{
					for (x4=-1;x4<=1;x4++)
					{
						if (w1*x1+w2*x2+w3*x3+w4*x4==w)
						{
							printf("w=%2d: ",w);
							if (x1!=0)
								printf("%d ",w1*x1);
							if (x2!=0)
								printf("%d ",w2*x2);
							if (x3!=0)
								printf("%d ",w3*x3);
							if (x4!=0)
								printf("%d ",w4*x4);
							printf("/n");

							//继续下一个重量
							x1=x2=x3=x4=2;
						}
					}
				}
			}
		}
	}
}

int main()
{
	CWeight wei;
	wei.Calculate();

	return 0;
}
    

 

3. C#版

/************************************************************************
 * 4个砝码,每个重量都是整数克,总重量为40克,放在天平上可以称出1~40克的
 * 物体。求这4个砝码各多少克。
 * C#版
 ************************************************************************/
using System;
using System.Collections.Generic;
using System.Text;

namespace Weight
{
    class Program
    {
        //砝码总重量
        const int TOTALWEIGHT = 40;

        //4个砝码,w1+w2+w3+w4=40,且w1,w2,w3,w4均为整数,假设不相等(假设w1<w2<w3<w4)故最大为34
        const int MAXWEIGHT = 34;

        static void Main(string[] args)
        {
            int w1, w2, w3, w4;
            for (w1 = 1; w1 <= MAXWEIGHT; w1++)
            {
                for (w2 = w1 + 1; w2 <= MAXWEIGHT; w2++)
                {
                    for (w3 = w2 + 1; w3 <= MAXWEIGHT; w3++)
                    {
                        for (w4 = w3 + 1; w4 <= MAXWEIGHT; w4++)
                        {
                            if (w1 + w2 + w3 + w4 == TOTALWEIGHT)
                            {
                                if (weight(w1, w2, w3, w4))
                                {
                                    System.Console.WriteLine("w1={0} w2={1} w3={2} w4={3} ", w1, w2, w3, w4);
                                    output(w1, w2, w3, w4);
                                }
                            }
                        }
                    }
                }
            }
        }

        //从1~40,不管哪个重量都要找到相应的砝码放置方法
        //w1,w2,w3,w4分别为4个砝码的重量
        static bool weight(int w1, int w2, int w3, int w4)
        {
            int w;	//物体重量

            //砝码只有4个,且每次称重时,这4个砝码只能出现0次或者1次
            //出现时,砝码要么在物体盘,要么在砝码盘,要解该问题,转换思路
            //假设砝码在物体盘,认定其出现-1次
            //假设砝码在砝码盘,认定其出现1次
            //若该次称重,不需要该砝码,认定其出现0次
            //4个砝码在每次称重中出现的次数
            int x1, x2, x3, x4;	//只有-1,0,1这三种取值

            int count = 0;		//找到的砝码组合个数

            //对1~40中的每个重量,都要找到相应的砝码组合
            //若有一个w(1<=w<=TOTALWEIGHT)没有找到相应的砝码组合,则表明该组砝码值不是所求
            for (w = 1; w <= TOTALWEIGHT; w++)
            {
                for (x1 = -1; x1 <= 1; x1++)
                {
                    for (x2 = -1; x2 <= 1; x2++)
                    {
                        for (x3 = -1; x3 <= 1; x3++)
                        {
                            for (x4 = -1; x4 <= 1; x4++)
                            {
                                if (w1 * x1 + w2 * x2 + w3 * x3 + w4 * x4 == w)
                                {
                                    count++;

                                    //找到该重量对应的砝码组合后,继续下一个重量
                                    x1 = x2 = x3 = x4 = 2;
                                }
                            }
                        }
                    }
                }
            }

            //如果找到所有的1~TOTALWEIGHT的砝码组合,则该组砝码值即为所求
            if (count == TOTALWEIGHT)
                return true;
            else
                return false;
        }

        //输出1~40中每个重量对应的砝码组合(负数表示该砝码放在物体盘)
        static void output(int w1, int w2, int w3, int w4)
        {
            int w;	//物体重量
            int x1, x2, x3, x4;	//只有-1,0,1这三种取值

            //对1~TOTALWEIGHT中的每个重量,都要找到相应的砝码组合
            for (w = 1; w <= TOTALWEIGHT; w++)
            {
                for (x1 = -1; x1 <= 1; x1++)
                {
                    for (x2 = -1; x2 <= 1; x2++)
                    {
                        for (x3 = -1; x3 <= 1; x3++)
                        {
                            for (x4 = -1; x4 <= 1; x4++)
                            {
                                if (w1 * x1 + w2 * x2 + w3 * x3 + w4 * x4 == w)
                                {
                                    System.Console.Write("w={0}: ", w);
                                    if (x1 != 0)
                                        System.Console.Write("{0} ", w1 * x1);
                                    if (x2 != 0)
                                        System.Console.Write("{0} ", w2 * x2);
                                    if (x3 != 0)
                                        System.Console.Write("{0} ", w3 * x3);
                                    if (x4 != 0)
                                        System.Console.Write("{0} ", w4 * x4);
                                    System.Console.WriteLine();

                                    //继续下一个重量
                                    x1 = x2 = x3 = x4 = 2;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

 

4. 运行结果

 

说明:第一行表示4个砝码的质量分别为1,3,9,27

         其他行,负数表示该砝码放在物体盘,正数表示该砝码放在砝码盘

 

w1=1 w2=3 w3=9 w4=27
w= 1: 1
w= 2: -1 3
w= 3: 3
w= 4: 1 3
w= 5: -1 -3 9
w= 6: -3 9
w= 7: 1 -3 9
w= 8: -1 9
w= 9: 9
w=10: 1 9
w=11: -1 3 9
w=12: 3 9
w=13: 1 3 9
w=14: -1 -3 -9 27
w=15: -3 -9 27
w=16: 1 -3 -9 27
w=17: -1 -9 27
w=18: -9 27
w=19: 1 -9 27
w=20: -1 3 -9 27
w=21: 3 -9 27
w=22: 1 3 -9 27
w=23: -1 -3 27
w=24: -3 27
w=25: 1 -3 27
w=26: -1 27
w=27: 27
w=28: 1 27
w=29: -1 3 27
w=30: 3 27
w=31: 1 3 27
w=32: -1 -3 9 27
w=33: -3 9 27
w=34: 1 -3 9 27
w=35: -1 9 27
w=36: 9 27
w=37: 1 9 27
w=38: -1 3 9 27
w=39: 3 9 27
w=40: 1 3 9 27


原文链接:http://blog.csdn.net/livelylittlefish/article/details/3854702
加载中
返回顶部
顶部