A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

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

例如:用户输入:5
程序输出:
9-3-1
用户输入:
19
程序输出:
27-9+1
输入:
41
输出:
81-27-9-3-1
而且还要求程序输出的组合总是大数在前小数在后。
数据结构与算法没学好,惭愧啊...

评分

参与人数 1技术分 +1 收起 理由
刘芮铭 + 1 赞一个!

查看全部评分

10 个回复

倒序浏览
等答案。。
回复 使用道具 举报
加油学,等你好消息.
回复 使用道具 举报
同学你是不是搞错了,
19
程序输出:
27-9-3-1
回复 使用道具 举报
刘明月 发表于 2012-9-27 19:38
同学你是不是搞错了,
19
程序输出:

呵呵,27-9+1不就等于19吗
同学,看清楚了
回复 使用道具 举报
坐等答案
回复 使用道具 举报
+1           
回复 使用道具 举报
首先我觉得做题讲究的是思路,我先给你思路,看看能不能开窍{:soso_e113:}
//首先如果明白天平原理,两个盘中放的物体如果相同则平衡,那边沉,偏向那边
                //那如果我想测量其中一个重量为x的砝码,而此刻知道的砝码只有1,3,9,27,81
                //如果是我,我会先拿x分别与1,3,9,27,81进行比较
                //而1,3,9,27,81是按顺序排列的而且是多个,而且是固定的,所以想到用数组存储,并且可以通过下标对其进行访问
                int[]nums={1,3,9,27,81};
                int x=19;//定义需要查找重量的砝码
                //思路:然后对数组进行遍历,如果x在数组中的两个元素之间,得到两元素的中间值y,
                //如果是x则返回,
                //如果不是再继续用两元素的中间值与x进行比较
                //此时想到了什么,对二分查找!!!!

评分

参与人数 1技术分 +1 收起 理由
唐志兵 + 1 赞一个!

查看全部评分

回复 使用道具 举报
一定要用递归么?貌似有点难度,递归算法如果使用for循环,也是可以完成任务的,只是貌似不能扩展使用,

貌似是以前的编程竞赛题,楼上的思路强悍,二分法思考的不错,但怎么落实,我也求答案了。

以下是for循环的:

import java.util.Scanner;  

public class Balance1
{  
    public static void main(String[] args)   
   {          
    look();
  }
    public static void look(){
             Scanner sc=new Scanner(System.in);  
             System.out.println("请输入0-121之间的数字:");
             int n=sc.nextInt();
             if(n>=0&&n<=121){  
                    int[] a={0,-1,+1};  
                    int[] b={0,-3,+3};  
                    int[] c={0,-9,+9};  
                    int[] d={0,-27,+27};  
                    int[] e={0,-81,+81};  
                    for(int h=0;h<a.length;h++){  
                        for(int i=0;i<b.length;i++){  
                            for(int j=0;j<c.length;j++){  
                                for(int k=0;k<d.length;k++){  
                                    for(int l=0;l<e.length;l++){  
                                        if(a[h]+b+c[j]+d[k]+e[l]==n){  
                                            if(e[l]!=0){          
                                                    System.out.print(e[l]);               
                                            }  
                                            if(d[k]!=0){
                                                    if(d[k]>0){
                                                            System.out.print("+"+d[k]);  
                                                    }
                                                    else{
                                                            System.out.print(d[k]);  
                                                    }
                                                                                            
                                            }  
                                            if(c[j]!=0){
                                                    if(c[j]>0){
                                                            System.out.print("+"+c[j]);   
                                                    }
                                                    else{
                                                            System.out.print(c[j]);
                                                    }
                                                 
                                            }  
                                            if(b!=0){  
                                                    if(b>0){
                                                            System.out.print("+"+b);
                                                    }
                                                    else{
                                                            System.out.print(b);
                                                    }
                                                  
                                            }  
                                            if(a[h]!=0){  
                                                    if(a[h]>0){
                                                            System.out.print("+"+a[h]);
                                                    }
                                                    else{
                                                            System.out.print(a[h]);
                                                    }      
                                            }  
                                        }  
                                    }  
                                }  
                            }  
                        }  
                    }  
                    System.out.println();
                    look();
                }else{  
                    System.out.println("输入有误,请检查!");  
                    look();
                }  
    }
}  


以下是所谓的递归算法,这里关键是弄清楚fact()方法的原理。

import java.util.Scanner;

public class Balance2 {

        static int data[]={1,3,9,27,81};
       
        public static void main(String[] args) {
                Scanner scanner=new Scanner(System.in);
                deep(scanner.nextInt(),"");
                }
       
        //以下调用递归
        private static void deep(int s,String str){
                //当S变成零则输出结果
                if(s==0){
                        System.out.println(str.substring(1));
                        }
                //当s>0时,还应该添加砝码
                else if(s>0){
                        int temp=s-fact(s);//调用fact()方法
                        deep(temp,str+"+"+fact(s));//调用方法自己,加号添加砝码
                        }
                //当s<0时,应该减去砝码
                else if(s<0){
                        int temp=s+fact(s);
                        deep(temp,str+"-"+fact(s));//调用方法自己
                }
        }
       
        //以下是递归的算法:当物体的质量大于比它质量小的砝码的所有砝码质量和的时候选择大砝码。
        private static int fact(int i) {
                i=Math.abs(i);//返回 i 值的绝对值
                int flag=0;//标记
                int sum=0;//小砝码质量和


                for(int j=1;j<5;j++){
                        //这个条件找到物体的质量的范围
                        if(i>data[j-1] && i<data[j] || i>=data[j]){
  •                                 for(int m=0;m<j;m++){
                                        sum+=data[m];
                                        }
                                if(i>sum){
                                        flag=j;
                                        }else{
                                                flag=j-1;
                                                }
                                }
                        }
                return data[flag];
        }
}


回复 使用道具 举报
  1. import java.util.Scanner;

  2. public class FaMa {
  3.         public static void main(String[] args) {
  4.                 int[] faMa = { 1, 3, 9, 27, 81 };
  5.                 int[] faMa2 = new int[5];
  6.                 int sum;
  7.                 while (true) {
  8.                         Scanner scanner = new Scanner(System.in);
  9.                         sum = scanner.nextInt();
  10.                         if (sum > 121 || sum < 1) {
  11.                                 System.out.println("请输入1到121之间的数字");
  12.                                 continue;
  13.                         }
  14.                         getResult(faMa, faMa2, 0, sum);
  15.                 }
  16.         }

  17.         public static void getResult(int[] faMa1, int[] faMa2, int index, int sum) {
  18.                 if (5 == index) {
  19.                         int cont = 0;
  20.                         for (int i = 0; i < index; i++) {
  21.                                 cont += faMa2[i];
  22.                         }
  23.                         if (cont == sum) {
  24.                                 int i;
  25.                                 for (i = index - 1; faMa2[i] == 0; i--) {
  26.                                 }
  27.                                 System.out.print(faMa2[i--]);
  28.                                 for (; i >= 0; i--) {
  29.                                         if (0 < faMa2[i]) {
  30.                                                 System.out.print("+" + faMa2[i]);
  31.                                         } else if (0 > faMa2[i]) {
  32.                                                 System.out.print(faMa2[i]);
  33.                                         }
  34.                                 }
  35.                                 System.out.println();
  36.                         }
  37.                         return;
  38.                 }
  39.                 faMa2[index] = faMa1[index];
  40.                 getResult(faMa1, faMa2, index + 1, sum);
  41.                 faMa2[index] = -faMa1[index];
  42.                 getResult(faMa1, faMa2, index + 1, sum);
  43.                 faMa2[index] = 0;
  44.                 getResult(faMa1, faMa2, index + 1, sum);
  45.         }
  46. }
复制代码
这是第二届“蓝桥杯”全国软件大赛的C语言专科组四川初赛题的最后一题,我参加的是第三届,这题早就做过了,所以这次写起来是一气呵成,呵呵……你同学是不是要在为参加第四届做准备哦,
回复 使用道具 举报
占个位置。。。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马