测试代码运行时间 java


public class Test {
    public static void main(String[] args)
    {
    //  long startTime = System.nanoTime();             // nano sec.
        long startTime = System.currentTimeMillis();    // micro sec.
 
    //  Ur code
         
    //  long estimatedTime = System.nanoTime() - startTime;
        long estimatedTime=System.currentTimeMillis() - startTime;
        System.out.println(estimatedTime);
    }
}

列出购物方法


题:
公司发了某商店的购物券1000元,限定只能购买店中的m种商品。每种商品的价格分别为m1,m2,…,要求程序列出所有的正好能消费完该购物券的不同购物方法。
程序输入:
第一行是一个整数m,代表可购买的商品的种类数。
接下来是m个整数,每个1行,分别代表这m种商品的单价。
程序输出:
第一行是一个整数,表示共有多少种方案
第二行开始,每种方案占1行,表示对每种商品购买的数量,中间用空格分隔。
例如:
输入:
2
200
300
则应输出:
2
2 2
5 0
输入:
2
500
800
则应输出:
1
2 0

源码ShoppingGame.java


import java.util.Scanner;

public class ShoppingGame {
    
    private static String go(int[] a) {
        int[] b = new int[a.length];
        return go(a, b, 0);
    }
    private static String go(int[] a, int[] b, int x) {
        if (x==a.length) {
            int r = 0;
            for (int i=0; i<a.length; i++) {
                r += a[i]*b[i];
            }
            String s = "";
            if (r==1000) {
                for (int i:b) {
                    s += i+" ";
                }
                s += "\n";
            }
            return s;
        }
        String t = "";
        int[] c = b.clone();// Critical
        for (int i=0; a[x]*i<=1000; i++) {
            String tm = go(a, c, x+1);
            if (tm!="") t += tm;
            c[x] += 1;
        }
        return t;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();
        String s = go(a);
        System.out.println(s.length()/(2*n+1));
        System.out.println(s);
    }
}

加密算法


题:
在对银行账户等重要权限设置密码的时候,我们常常遇到这样的烦恼:如果为了好记用生日吧,容易被破解,不安全;如果设置不好记的密码,又担心自己也会忘记;如果写在纸上,担心纸张被别人发现或弄丢了...
这个程序的任务就是把一串拼音字母转换为6位数字(密码)。我们可以使用任何好记的拼音串(比如名字,王喜明,就写:wangximing)作为输入,程序输出6位数字。
变换的过程如下:
第一步. 把字符串6个一组折叠起来,比如wangximing则变为:
wangxi
ming
第二步. 把所有垂直在同一个位置的字符的ASCII码值相加,得出6个数字,如上面的例子,则得出:
228 202 220 206 120 105
第三步. 再把每个数字“缩位”处理:就是把每个位的数字相加,得出的数字如果不是一位数字,就再缩位,直到变成一位数字为止。例如: 228 => 2+2+8=12 => 1+2=3
上面的数字缩位后变为:344836, 这就是程序最终的输出结果!
要求程序从标准输入接收数据,在标准输出上输出结果。
输入格式为:第一行是一个整数n(<100),表示下边有多少输入行,接下来是n行字符串,就是等待变换的字符串。
输出格式为:n行变换后的6位密码。
例如,输入:
5
zhangfeng
wangximing
jiujingfazi
woaibeijingtiananmen
haohaoxuexi

则输出:
772243
344836
297332
716652
875843

源码NameGame.java


import java.util.Scanner;

public class NameGame {

    private static int go(int x) {
        String s;
        while (x>9) {
            s = ""+x;
            x=0;
            for (int i=0; i<s.length(); i++) {
                x += s.charAt(i)-'0';
            }
        }
        return x;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        String s;
        while ((n--)>0) {
            int[] a = new int[6];
            s = sc.nextLine();
            for (int i=0; i<s.length(); i++) {
                a[i%6] += (int) (s.charAt(i));
            }
            for (int i=0; i<6; i++) {
                System.out.print(go(a[i]));
            }
            System.out.println();
        }
        sc.close();
    }
}

井字棋研究 取卡问题


题:
闲暇时,福尔摩斯和华生玩一个游戏:
在N张卡片上写有N个整数。两人轮流拿走一张卡片。要求下一个人拿的数字一定是前一个人拿的数字的约数或倍数。例如,某次福尔摩斯拿走的卡片上写着数字“6”,则接下来华生可以拿的数字包括:
1,2,3, 6,12,18,24 ....
当轮到某一方拿卡片时,没有满足要求的卡片可选,则该方为输方。
请你利用计算机的优势计算一下,在已知所有卡片上的数字和可选哪些数字的条件下,怎样选择才能保证必胜!
当选多个数字都可以必胜时,输出其中最小的数字。如果无论如何都会输,则输出-1。
输入数据为2行。第一行是若干空格分开的整数(每个整数介于1~50间),表示当前剩余的所有卡片。
第二行也是若干空格分开的整数,表示可以选的数字。当然,第二行的数字必须完全包含在第一行的数字中。
程序则输出必胜的招法!!
例如:
用户输入:
2 3 6
3 6
则程序应该输出:
3
再如:
用户输入:
1 2 2 3 3 4 5
3 4 5
则程序应该输出:
4

源码CardGame.java


import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class CardGame {
    
    @SuppressWarnings({ "rawtypes" })
    private static boolean go(ArrayList t1, ArrayList t2, boolean x) {
        if (t2.isEmpty()) return !x;
        boolean[] t = new boolean[t2.size()];
        for (int i=0; i<t2.size();i++) {
            int s = (int) t2.get(i);
            ArrayList tm = (ArrayList) t1.clone();
            tm.remove(tm.indexOf(s));
            ArrayList<Integer> t3 = new ArrayList<Integer>();
            t3.clear();
            for (int k=0; k<tm.size(); k++) {
                if (s%(int) tm.get(k)==0 || (int) tm.get(k)%s==0) {
                    t3.add((int) tm.get(k));                    
                }
            }
            t[i] = go(tm, t3, !x);
        }
        for (int i=0; i<t.length; i++) {
            if (t[i]==x) return x;
        }
        return !x;
    }

    public static void main(String[] args) {
        
        ArrayList<Integer> s1 = new ArrayList<Integer>();
        ArrayList<Integer> s2 = new ArrayList<Integer>();
        Scanner sc = new Scanner(System.in);
        String a = sc.nextLine();
        String b = sc.nextLine();
        sc.close();
        
        sc = new Scanner(a);
        while (sc.hasNextInt()) {
            s1.add(sc.nextInt());
        }
        sc.close();
        
        sc = new Scanner(b);
        while (sc.hasNextInt()) {
            s2.add(sc.nextInt());
        }
        sc.close();
        Collections.sort(s1);
        Collections.sort(s2);

        ArrayList<Integer> s3 = new ArrayList<Integer>();
        int k = 0;
        for (int i=0; i<s2.size(); i++) {
            s3.clear();
            s3.add(s2.get(i));
            if (go(s1, s3, true)) {
                k = s2.get(i);
                break;
            }
        }
        System.out.println((k==0)? -1: k);
    }
}

博弈树 火柴棒游戏的实现


题:
这是一个纵横火柴棒游戏。如图,在3x4的格子中,游戏的双方轮流放置火柴棒。其规则是:
1. 不能放置在已经放置火柴棒的地方(即只能在空格中放置)。
2. 火柴棒的方向只能是竖直或水平放置。
3. 火柴棒不能与其它格子中的火柴“连通”。所谓连通是指两根火柴棒可以连成一条直线,且中间没有其它不同方向的火柴“阻拦”。
例如:图所示的局面下,可以在C2位置竖直放置(为了方便描述格子位置,图中左、下都添加了标记),但不能水平放置,因为会与A2连通。同样道理,B2,B3,D2此时两种方向都不可以放置。但如果C2竖直放置后,D2就可以水平放置了,因为不再会与A2连通(受到了C2的阻挡)。
4. 游戏双方轮流放置火柴,不可以弃权,也不可以放多根。直到某一方无法继续放置,则该方为负(输的一方)。
游戏开始时可能已经放置了多根火柴。
你的任务是:编写程序,读入初始状态,计算出对自己最有利的放置方法并输出。
如图的局面表示为:
00-1
-000
0100

即用“0”表示空闲位置,用“1”表示竖直放置,用“-”表示水平放置。
【输入、输出格式要求】
用户先输入整数 n(n<100), 表示接下来将输入 n 种初始局面,每种局面占3行(多个局面间没有空白行)。
程序则输出:每种初始局面情况下计算得出的最佳放置法(行号+列号+放置方式)。
例如:用户输入:
2
0111
-000
-000
1111
----
0010

则程序可以输出:

00-
211

不难猜出,输出结果的含义为:
对第一个局面,在第0行第0列水平放置
对第二个局面,在第2行第1列垂直放置
注意:
行号、列号都是从0开始计数的。
对每种局面可能有多个最佳放置方法(解不唯一),只输出一种即可。
例如,对第一个局面,001 也是正解;对第二个局面,201也是正解。

源码MatchGame.java
示例图片

match game pic
match game pic


import java.util.Scanner;

public class MatchGame {

    private static boolean ck(char[][] c, int i, int k) {
        if (c[i][k]=='-') {
            for (int k2=k+1; k2<4; k2++) {
                if (c[i][k2]=='-') {
                    return false;
                }
                else if (c[i][k2]=='1') {
                    return true;
                }
            }
            for (int k2=k-1; k2>=0; k2--) {
                if (c[i][k2]=='-') {
                    return false;
                }
                else if (c[i][k2]=='1') {
                    return true;
                }
            }
        }
        else if (c[i][k]=='1') {
            for (int i2=i+1; i2<3; i2++) {
                if (c[i2][k]=='1') {
                    return false;
                }
                else if (c[i2][k]=='-') {
                    return true;
                }
            }
            for (int i2=i-1; i2>=0; i2--) {
                if (c[i2][k]=='1') {
                    return false;
                }
                else if (c[i2][k]=='-') {
                    return true;
                }
            }
        }
        return true;
    }
    
    private static String xt(char[][] c) {
        String s = "";
        for (int i=0; i<3; i++) {
            for (int k=0; k<4; k++) {
                if (c[i][k]=='0') {
                    c[i][k] = '-';
                    if (ck(c, i, k)) {
                        if (xt(c, false)) s = ""+i+k+"-";
                    }
                    c[i][k] = '1';
                    if (ck(c, i, k)) {
                        if (xt(c, false)) s = ""+i+k+"1";
                    }
                    c[i][k] = '0';// Critical
                }
            }
        }
        return (s=="")? "Bless..": s;
    }
    
    private static boolean xt(char[][] c, boolean x) {
        boolean r = false;
        String s = "";
        for (int i=0; i<3; i++) {
            for (int k=0; k<4; k++) {
                if (c[i][k]=='0') {
                    c[i][k] = '-';
                    if (ck(c, i, k)) {
                        r = true;
                        s += (xt(c, !x))? 1: 0;
                    }
                    c[i][k] = '1';
                    if (ck(c, i, k)) {
                        r = true;
                        s += (xt(c, !x))? 1: 0;
                    }
                    c[i][k] = '0';
                }
            }
        }
        if (!r) return !x;
        if (x) {
            if (s.indexOf("1")!=-1) 
                return true;
            else
                return false;
        }
        else {
            if (s.indexOf("0")!=-1)
                return false;
            else
                return true;
        }
    }
    
    public static void main(String[] args) {
    /*  
        try {
            FileInputStream fis= new FileInputStream("/Users/Tro/Desktop/Trial.txt");
            System.setIn(fis);
        }
        catch(IOException e) {
            e.printStackTrace();
        }
    */  
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        char[][] c = new char[3][4];
        String s;
        while((n--)>0) {
            for (int i=0; i<3; i++) {
                s = sc.nextLine();
                for (int k=0; k<4; k++) {
                    c[i][k] = s.charAt(k);
                }
            }
            System.out.println(xt(c));
        }
        sc.close();
    }
}

概率模拟法 股票问题


题:
股票交易上的投机行为往往十分危险。假设某股票行为十分怪异,每天不是涨停(上涨10%)就是跌停(下跌10%)。假设上涨和下跌的概率均等(都是50%)。再假设交易过程没有任何手续费。某人在开始的时候持有总价值为x的该股股票,那么100个交易日后,他盈利的可能性是多少呢?

源码Missing3.java


public class Missing3 {
    public static void main(String[] args) {
        int N = 1000000;
        int n = 0;
        for(int i=0; i<N; i++)
        {
            double value = 1000.0;  
            for(int k=0; k<100; k++)
            {
                if(Math.random()>0.5)
                    value = value * 1.1;
                else
                    value = value * 0.9;
            }
            if(value>1000.0) n++;
        }
        System.out.println(1.0*n/N);
    }
}

表达式求值 缺少代码填写


题:
正常的表达式称为中缀表达式,运算符在中间,主要是给人阅读的,机器求解并不方便。
例如:3 + 5 * (2 + 6) - 1
而且,常常需要用括号来改变运算次序。
相反,如果使用逆波兰表达式(前缀表达式)表示,上面的算式则表示为:
- + 3 * 5 + 2 6 1
不再需要括号,机器可以用递归的方法很方便地求解。
为了简便,我们假设:
1. 只有 + - * 三种运算符
2. 每个运算数都是一个小于10的非负整数
下面的程序对一个逆波兰表示串进行求值。
其返回值为一个数组:其中第一元素表示求值结果,第二个元素表示它已解析的字符数。

源码Missing2.java


public class Missing2 {
    
    static int[] evaluate(String x) {
        if(x.length()==0) return new int[] {0,0};
        char c = x.charAt(0);
        if(c>='0' && c<='9') return new int[] {c-'0',1};
        int[] v1 = evaluate(x.substring(1));
        int[] v2 = evaluate(x.substring(v1[1]+1)); //填空位置
        int v = Integer.MAX_VALUE;
        if(c=='+') v = v1[0] + v2[0];
        if(c=='*') v = v1[0] * v2[0];
        if(c=='-') v = v1[0] - v2[0];
        return new int[] {v,1+v1[1]+v2[1]};
    }
    
    public static void main(String[] args) {
        String x = "-+3*5+261";
        int[] t = evaluate(x);
        for (int i=0; i<t.length; i++) {
            System.out.println(t[i]);
        }
    }
}

编程解决问题 BMP图片连通


题:
BMP是常见的图像存储格式。
如果用来存黑白图像(颜色深度=1),则其信息比较容易读取。

与之相关的数据:

(以下偏移均是从文件头开始)
偏移:10字节, 长度4字节: 图像数据真正开始的位置。
偏移:18字节, 长度4字节: 位图的宽度,单位是像素。
偏移:22字节, 长度4字节: 位图的高度,单位是像素。

从图像数据开始处,每个像素用1个二进制位表示。
从图片的底行开始,一行一行向上存储。

Windows规定图像文件中一个扫描行所占的字节数必须是4字节的倍数,
不足的位均以 0 填充。例如,图片宽度为45像素,实际上每行会占用
8个字节。

可以通过Windows自带的画图工具生成和编辑二进制图像。
需要在“属性”中选择“黑白”,指定为二值图像。
可能需要通过查看 | 缩放 | 自定义... 把图像变大比例一些,
更易于操作。

图像的左下角为图像数据的开始位置。白色对应1,黑色对应0

我们可以定义:两个点距离如果小于2个像素,则认为这两个点连通。
也就是说:以一个点为中心的九宫格中,围绕它的8个点与它都是连通的。
如:t1.bmp 所示,左下角的点组成一个连通的群体;
而右上角的点都是孤立的。

程序的目标是:根据给定的黑白位图,分析出所有独立连通的群体,输出每个连通群体的面积。所谓面积,就是它含有的像素的个数。

输入数据固定存在in.bmp中。

如示例的in.bmp,
程序应该输出:
12
81
52
133

该输出表示:共有4个连通群体。
输出的连通体面积间的顺序可以随意。

请编程解决上述问题。

我们测试程序的时候,会使用不同的in.bmp文件。

源码BMPGame.java
BMP文件

bmp game
bmp game


import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;

import javax.imageio.ImageIO;


public class BMPGame {
    
    private static int t(int i, int k, int w, int h, boolean[][][] x) {
        if (i<0 || i>=w || k<0 || k>=h) {
            return 0;
        }
        if (x[i][k][1]) {
            return 0;
        }
        x[i][k][1] = true;
        if (x[i][k][0]) {
            return t(i-1, k-1, w, h, x) + t(i+1, k-1, w, h, x) +
                    t(i-1, k+1, w, h, x) + t(i+1, k+1, w, h, x) + 
                    t(i, k-1, w, h, x) + t(i, k+1, w, h, x) + 
                    t(i-1, k, w, h, x) + t(i+1, k, w, h, x) + 1;
        }
        else {
            return 0;
        }
    }
    
    public static void main(String args[]) throws IOException {
        
        long st=System.currentTimeMillis();
        
        String path = "/Users/Tro/Desktop/t.bmp";
        File f = new File(path);
        BufferedImage b = ImageIO.read(f);
        int w = b.getWidth();
        int h = b.getHeight();
        boolean[][][] x = new boolean[w][h][2];
    
        
        for (int i=0; i<w; i++) {
            for (int k=0; k<h; k++) {
                x[i][k][0] = (b.getRGB(i, k)==-1)? false: true;
            }
        }
    
        for (int i=0; i<w; i++) {
            for (int k=0; k<h; k++) {
                int r = t(i, k, w, h, x);
                if (r>1) {
                    System.out.println(r);
                }
            }
        }
        
        long ed=System.currentTimeMillis();
        System.out.println(ed-st);
    }
}

树形结构应用


题:
填写代码缺失部分
下面这段代码根据用户添加的数据,在内存中构建一个逻辑上等价的树形结构。
通过ShowTree() 可以把它显示为控制中的样子。
其中:
a.add('a', 'b');
a.add('b', 'e');
表示:'b' 作为 'a' 的孩子节点;'e' 作为 'b'的孩子节点。
如代码中给出的示例数据,输出结果应该为:

a--b--e
|  |--f--j
|    |--k
|--c
|--d--g--h
  |--i

源码Missing.java


import java.util.*;

class MyTree {
    @SuppressWarnings("rawtypes")
    private Map map = new HashMap();

    @SuppressWarnings({ "unchecked", "rawtypes" })
    public void add(char parent, char child) {
        List t = (List)map.get(parent);
        if(t==null) {
            t = new Vector();
            // 填空1
            map.put(parent, t);
            // 填空1
        }
        t.add(child);
    }
    
    @SuppressWarnings("rawtypes")
    public List getChild(char x) {
        return (List)map.get(x);
    }
}

public class Missing {
    
    @SuppressWarnings({ "rawtypes", "unchecked" })
    public static List showTree(MyTree tree, char x) {
        List t = tree.getChild(x);
        List r = new Vector();
        if(t==null) {
            r.add("" + x);
            return r;
        }
        for(int i=0; i<t.size(); i++) {
            List ri = showTree(tree, (char) t.get(i));
            for(int j=0; j<ri.size(); j++) {
                String pre = "|  ";
                if(j==0) {
                    if(i==0)
                        pre = x + "--";
                    else 
                        pre = "|--";
                }
                else {
                    if(i==ri.size()) // 填空2
                        pre = "   ";
                    else
                        pre = "|  ";
                }
                r.add(pre + ri.get(j));
            }
        }
        return r;
    }

    @SuppressWarnings("rawtypes")
    public static void main(String[] args) {
        MyTree a = new MyTree();
        a.add('a', 'b');
        a.add('b', 'e');
        a.add('b', 'f');
        a.add('a', 'c');
        a.add('a', 'd');
        a.add('d', 'g');
        a.add('d', 'i');
        a.add('g', 'h');
        a.add('f', 'j');
        a.add('f', 'k');

        List lst = showTree(a, 'a');
        for(int i=0; i<lst.size(); i++) {
            System.out.println(lst.get(i));
        }
    }
}

分酒问题 求最大不能组合出的数字


题:
小明开了一家糖果店。他别出心裁:把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候,他就用这两种包装来组合。当然有些糖果数目是无法组合出来的,比如要买 10 颗糖。
你可以用计算机测试一下,在这种包装情况下,最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时,求最大不能组合出的数字。
输入:
两个正整数,表示每种包装中糖的颗数(都不多于1000)

要求输出:
一个正整数,表示最大不能买到的糖数

例如:
用户输入:
4 7
程序应该输出:
17

再例如:
用户输入:
3 5
程序应该输出:
7

源码SweetGame.java


import java.util.Scanner;

public class SweetGame {
    public static int xymod(int a, int b) {
        if (a<b) {
            int temp;
            temp = a;
            a = b;
            b = temp;
        }
        if (0==b) {
            return a;
        }
        return xymod(a-b, b);
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Pls input 2 nums");
        int a = sc.nextInt();
        int b = sc.nextInt();
        sc.close();
        if (xymod(a, b)!=1 || a<2 || b<2) {
            System.out.println("No solution !");
        }
        else {
            System.out.println("Max num is "+(a*b-a-b));
        }
    }
}