砝码称重

砝码称重

时间： 1ms        内存：128M

描述：

5个砝码

用天平称重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。

如果只有5个砝码，重量分别是1，3，9，27，81。则它们可以组合称出1到121之间任意整数重量（砝码允许放在左右两个盘中）。

本题目要求编程实现：对用户给定的重量，给出砝码组合方案。

输入：

用户输入：

5

输出：

程序输出：

9-3-1

示例输入：

1

示例输出：

1

提示：

参考答案（内存最优[1092]）：

#include <stdio.h>
int main()
{
    int a[5]={0},b[5]={1,3,9,27,81},i,n;
    scanf("%d",&n);
    i=0;
    while(n>0)
    {
        a[i]=n%3;
        n=n/3;
        i++;
    }
    for(i=0;i<4;i++)
        switch(a[i])
        {
            case 2:a[i]=-1;a[i+1]++;break;
            case 3:a[i]=0;a[i+1]++;
        }
    for(i = 4; i>=0; i--)
        if(a[i])
            printf("%d", a[i]*b[i]);
    printf("\n");
    return 0;
}

参考答案（时间最优[0]）：

#include <iostream>
using namespace std;
int n;
int RE[5];
char sy[4];
int main()
{	
	int find(int i,int FM[]);
	int FM[]={1,3,9,27,81};
	while(cin>>n)
	{	
		int i,j;
		for(i=0;i<4;i++)
		{
			RE[i]=0;
			sy[i]=0;
		}
		RE[i]=0;
		for(i=1;i<=5;i++)
		{
			if(find(i,FM))break;
		}
		for(j=i-1;j>0;j--)
		{
			cout<<RE[j]<<sy[j];
		}
		cout<<RE[0];
		cout<<endl;
	}
	return 0;
}
int find(int i,int FM[])
{	
	int ge(int *p[5],int i,int sum=0,char what=0);
	int j;
	int *p[5];
	for(j=0;j<i;j++)
	{
		p[j]=&FM[j];
	}
	if(i==1)
	{
		for(j=0;j<5;j++)
		{	
			if(FM[j]==n)
			{
				RE[0]=FM[j];
				return 1;
			}
		}
		return 0;
	}
	else
	{
		while(p[0]!=&FM[5]-i+1)
		{	
			if(ge(p,i,*p[i-1]))return 1;
			p[i-1]++;
			if(p[i-1]==&FM[5])
			{	
				if(i<=1)break;
				p[i-2]++;
				if(p[i-2]==&FM[4])
				{	
					if(i<=2)break;
					p[i-3]++;
					if(p[i-3]==&FM[3])
					{	
						if(i<=3)break;
						p[i-4]++;
						if(p[i-4]==&FM[2])
						{
							if(i<=4)break;
							p[i-5]++;
							if(p[i-5]==&FM[1])
							break;
							p[i-4]=p[i-5]+1;
						}
						p[i-3]=p[i-4]+1;
					}
					p[i-2]=p[i-3]+1;
				}
				p[i-1]=p[i-2]+1;
			}
		}
	}
	return 0;
}
  //   1  3          4    2    
int ge(int *p[5],int i,int sum=0,char what=0)
{	
	switch(what)
	{
	case'+':sum+=*p[i-1];break;
	case'-':sum-=*p[i-1];break;
	default: break;
	}
	if(sum==n&&i==1) 
	{	
		RE[i-1]=*p[i-1];
		return 1;
	}
	if(i==1)return 0;
	if(ge(p,i-1,sum,'-')>=1){RE[i-1]=*p[i-1];sy[i-1]='-';return 1;}
	if(ge(p,i-1,sum,'+')>=1){RE[i-1]=*p[i-1];sy[i-1]='+';return 1;}
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。