題意：十二枚硬幣中有一個與其它重量不一樣，用天平只稱三次，請推斷出哪一枚銀幣與其它不一樣，是輕了還是重了？
這是一道to satisty題目，就是去滿足給定的條件。
解這類題目的思路有兩種：
方法一、假設不知道那一枚硬幣有問題，根據條件推測出有問題的硬幣。
方法二、依次假設硬幣有問題，看那種假設滿足題意。
顯然，這類題目用第二種方法更好做，因為可以假設的情況是很少的。只需要把所有出現的硬幣都“懷疑”一遍就可以得到正確結果了。

代碼
1

import java.io.*;
2

import java.util.*;
3

class Main
4

{
5

public static void main(String[] args)
7

{
8

Scanner sc = new Scanner(System.in);
9

int n = sc.nextInt();
10

sc.nextLine();
11

for(int i = 0; i < n; i++)
12

{
13

String strs[] = new String[3];
14

strs[0] = sc.nextLine();
15

strs[1] = sc.nextLine();
16

strs[2] = sc.nextLine();
17

getRS(strs);
19

}
20

}
21

private static void getRS(String[] strs){
22

TreeSet<Character> trset = new TreeSet<Character>();
23

int[] weights = new int[300];
24

for(int i = 0; i < 3; i++)
25

{
26

char[] chArry = strs[i].toCharArray();
27

for(int j = 0; j < chArry.length; j++)
28

{
29

if(Character.isUpperCase(chArry[j]))
30

{
31

trset.add(chArry[j]);
32

}
33

}
34

}
35

for(char ch : trset)// may light
36

{
37

//System.out.println("ch=" + ch);
38

Arrays.fill(weights, 0);
39

weights[ch] = -1;
40

boolean success = true;
41

for(int i = 0; i < 3; i++)
42

{
43

String[] strArry = strs[i].split(" ");
44

int wl = 0;
45

int wr = 0;
46

char[] chArry2 = strArry[0].toCharArray();
47

for(char ch2 : chArry2)
48

{
49

wl += weights[ch2];
50

}
51

char[] chArry3 = strArry[1].toCharArray();
52

for(char ch3 : chArry3)
53

{
54

wr += weights[ch3];
55

}
56

if(!getRSString(wl, wr).equals(strArry[2]))
57

success = false;
58

}
59

if(success)
60

{
61

System.out.println(ch + " is the counterfeit coin and it is light.");
62

return;
63

}
64

}
65

//
66

for(char ch : trset)// may heavy
67

{
68

Arrays.fill(weights, 0);
70

weights[ch] = 1;
71

boolean success = true;
72

for(int i = 0; i < 3; i++)
73

{
74

String[] strArry = strs[i].split(" ");
75

int wl = 0;
76

int wr = 0;
77

char[] chArry2 = strArry[0].toCharArray();
78

for(char ch2 : chArry2)
79

{
80

wl += weights[ch2];
81

}
82

char[] chArry3 = strArry[1].toCharArray();
83

for(char ch3 : chArry3)
84

{
85

wr += weights[ch3];
86

}
87

if(!getRSString(wl, wr).equals(strArry[2]))
88

success = false;
89

}
90

if(success)
91

{
92

System.out.println(ch + " is the counterfeit coin and it is heavy.");
93

return;
94

}
95

}
96

}
97

private static String getRSString(int wl, int wr)
98

{
99

if(wl == wr)
100

return "even";
101

if(wl > wr)
102

return "up";
103

return "down";
104

}
105

106

}
107

posted on 2013-03-22 22:31 小鼠標閱讀(175) 評論(0) 編輯收藏引用所屬分類: Java基礎練習

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 編輯距離閏年判斷正則表達式簡單筆記 Excel格式地址轉換一道模擬題——機器人行走距離計算排列練習2 素數篩法排列組合練習排列組合 poj1068Parencodings

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

2012年4月

日

一

二

三

四

五

六

常用鏈接

隨筆分類(111)

隨筆檔案(127)

friends

最新評論

閱讀排行榜