| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4762 人关注过本帖
标题:砝码称重问题和分红酒问题
只看楼主 加入收藏
sala0127
Rank: 2
等 级:论坛游民
帖 子:56
专家分:52
注 册:2011-11-8
结帖率:85.71%
收藏
已结贴  问题点数:50 回复次数:20 
砝码称重问题和分红酒问题
砝码称重问题描述如下:
5个砝码

用天平称重时,我们希望用尽可能少的砝码组合称出尽可能多的重量。
如果只有5个砝码,重量分别是1,3,9,27,81。则它们可以组合称出1到121之间任意整数重量(砝码允许放在左右两个盘中)。
本题目要求编程实现:对用户给定的重量,给出砝码组合方案。
例如:
用户输入:
5
程序输出:
9-3-1
用户输入:
19
程序输出:
27-9+1

要求程序输出的组合总是大数在前小数在后。
可以假设用户的输入的数字符合范围1~121。

分红酒问题描述如下:

  有4个红酒瓶子,它们的容量分别是:9升, 7升, 4升, 2升
  
  开始的状态是 [9,0,0,0],也就是说:第一个瓶子满着,其它的都空着。

  允许把酒从一个瓶子倒入另一个瓶子,但只能把一个瓶子倒满或把一个瓶子倒空,不能有中间状态。这样的一次倒酒动作称为1次操作。

  假设瓶子的容量和初始状态不变,对于给定的目标状态,至少需要多少次操作才能实现?

  本题就是要求你编程实现最小操作次数的计算。
 
  输入:最终状态(逗号分隔)
  输出:最小操作次数(如无法实现,则输出-1)

例如:
输入:
9,0,0,0
应该输出:
0

输入:
6,0,0,3
应该输出:
-1

输入:
7,2,0,0
应该输出:
2


砝码称重我只想到穷举每个砝码的三种状态,但是我搜索到论坛里算法大神之一的czz5242199用了一种更快捷的方法,不过我看不懂他的思路。。。请各位大神通俗易懂一点解析一下czz5242199大神的方法
分红酒问题我不懂。。但是我想每个瓶子只有倒空和倒满二种状态。是否可以穷举每个瓶子的状态,如果瓶子不为空再穷举瓶子里酒的倒向而且要排除倒回上一个瓶子的情况,直到找出次数最少又符合状态要求的情况。。这想法看起来好混乱的样子应该不科学。。。求教各位大神们的做法
搜索更多相关主题的帖子: 砝码 用户 
2013-04-01 18:11
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:37 
我是这么想的
转为 3进制:
5(10)  = 12 = 20 - 1 = 100 - 10 - 1
19(10) = 201 = 1000 - 100 + 1


[fly]存在即是合理[/fly]
2013-04-01 18:35
fourleaves
Rank: 2
等 级:论坛游民
帖 子:194
专家分:99
注 册:2010-5-8
收藏
得分:5 
第二题的模型是图,但是可以转化为求树模型的最短路问题。

再复杂的问题也基于最简单的原理。耐心,耐心!丰富自己!等待时机!
2013-04-01 18:45
sala0127
Rank: 2
等 级:论坛游民
帖 子:56
专家分:52
注 册:2011-11-8
收藏
得分:0 
回复 2楼 azzbcc
额转化为3进制后后面的怎么转换的?比如5(10)换为12(3)后为什么还要换成20-1(3)再后面的100-10-1又是怎么转换的。。。
2013-04-01 18:57
sala0127
Rank: 2
等 级:论坛游民
帖 子:56
专家分:52
注 册:2011-11-8
收藏
得分:0 
回复 3楼 fourleaves
具体怎么实现呢
2013-04-01 19:00
helloUJS
Rank: 8Rank: 8
等 级:蝙蝠侠
帖 子:168
专家分:731
注 册:2013-3-27
收藏
得分:8 
回复 楼主 sala0127
#include <stdio.h>
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;
}
称砝码问题程序参考,思路:将n转换成3进制。

[ 本帖最后由 helloUJS 于 2013-4-1 19:22 编辑 ]
2013-04-01 19:06
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
以下是引用sala0127在2013-4-1 18:57:17的发言:

额转化为3进制后后面的怎么转换的?比如5(10)换为12(3)后为什么还要换成20-1(3)再后面的100-10-1又是怎么转换的。。。


是我原来做过的一道题,外星人的三进制,‘1’表示+1, ‘0’表示 0,‘-’表示 减 1,然后 5就用 1-- 表示,10就用 101表示,

所以求出 某个数的三进制表示,这道题的答案也就出来了。


[fly]存在即是合理[/fly]
2013-04-01 19:10
sala0127
Rank: 2
等 级:论坛游民
帖 子:56
专家分:52
注 册:2011-11-8
收藏
得分:0 
嗯自习回来再仔细看下3进制解决砝码问题,那分红酒问题该怎么弄呢
2013-04-01 19:34
czzdcn123
Rank: 7Rank: 7Rank: 7
来 自:江西
等 级:黑侠
威 望:3
帖 子:258
专家分:510
注 册:2013-3-7
收藏
得分:0 
来学习
2013-04-01 20:39
fourleaves
Rank: 2
等 级:论坛游民
帖 子:194
专家分:99
注 册:2010-5-8
收藏
得分:0 
回复 5楼 sala0127
去看我发过的帖子。

再复杂的问题也基于最简单的原理。耐心,耐心!丰富自己!等待时机!
2013-04-01 20:53
快速回复:砝码称重问题和分红酒问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.037182 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved