刷题---算法

1. [编程题] 汽水瓶

时间限制：1秒

空间限制：32768K

有这样一道智力题：“某商店规定：三个空汽水瓶可以换一瓶汽水。小张手上有十个空汽水瓶，她最多可以换多少瓶汽水喝？”答案是5瓶，方法如下：先用9个空瓶子换3瓶汽水，喝掉3瓶满的，喝完以后4个空瓶子，用3个再换一瓶，喝掉这瓶满的，这时候剩2个空瓶子。然后你让老板先借给你一瓶汽水，喝掉这瓶满的，喝完以后用3个空瓶子换一瓶满的还给老板。如果小张手上有n个空汽水瓶，最多可以换多少瓶汽水喝？

输入描述:

输入文件最多包含10组测试数据，每个数据占一行，仅包含一个正整数n（1<=n<=100），表示小张手上的空汽水瓶数。n=0表示输入结束，你的程序不应当处理这一行。

输出描述:

对于每组测试数据，输出一行，表示最多可以喝的汽水瓶数。如果一瓶也喝不到，输出0。

输入例子1:

输出例子1:

1
5
40

/**
* 思路：
* 初始有n个瓶子，
* n<2 能喝到0瓶水
* n==2 先向老板借一瓶水，然后还给老板三个瓶子
* n>2 可以兑换n/3瓶水，这些水喝完后还剩n%3+n/3个空瓶子
* 接下来用递归的思想来求剩下的n%3+n/3个空瓶子一共可以兑换到多少瓶水
* @author chen
*
*/


import java.util.BitSet;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        
        while(n!=0){
            int sum=total(n);
            System.out.println(sum);
            n=sc.nextInt();
        }
    }//end main
    
    public static int total(int n){
        if(n<2)
            return 0;
        if(n==2)
            return 1;
        
        return n/3+total(n%3+n/3);
    }

}

2. [编程题] 进制转换

时间限制：1秒

空间限制：32768K

写出一个程序，接受一个十六进制的数值字符串，输出该数值的十进制字符串。（多组同时输入）

输入描述:

输入一个十六进制的数值字符串。

输出描述:

输出该数值的十进制字符串。

输入例子1:

0xA

输出例子1:

/**
 * 编程思路：
 *     十进制=十六进制的末尾+倒数第二位*16+倒数第三位*16^2+...
 *  
 * 易错点：
 *     key1,所有输入皆是以0x开头，你首先要去掉前缀“0x”
 *  key2,要注意到十六进制中的字母ABCDEF分别对应于10、11/12/13/14、15
 *  key3,char ch='1'; 
 *       int i=ch; //则i=49而不是1哦，
 *       int num=ch-'0';//num=1
 *  key4,index=length-1时，0次方
 *       注意index和指数的对应关系
 *       不是Math.pow(16,index),而是Math.pow(16,length-1-index)
 */
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            String hex=sc.next().toUpperCase();
            int[] hexArr=new int[hex.length()-2];
            for(int i=hex.length()-1;i>1;i--){
                switch(hex.charAt(i)){
                    case 'F':
                        hexArr[i-2]=15;
                        break;
                    case 'E':
                        hexArr[i-2]=14;
                        break;
                    case 'D':
                        hexArr[i-2]=13;
                        break;
                    case 'C':
                        hexArr[i-2]=12;
                        break;
                    case 'B':
                        hexArr[i-2]=11;
                        break;
                    case 'A':
                        hexArr[i-2]=10;
                        break;
                    default:
                        hexArr[i-2]=hex.charAt(i)-'0';
                        
                }
            }
            int oct=0;
            for(int i=hexArr.length-1;i>=0;i--){
                oct+=hexArr[i]*Math.pow(16, hexArr.length-i-1);
            }
            System.out.println(oct);
        }
    }//end main

}