算法训练

浏览数：18 / 时间：2015年06月08日

一、捕鱼和分鱼

A、B、C、D、E五个人在某天夜里合伙去捕鱼，到第二天凌晨时都疲惫不堪，于是各自找地方睡觉。日上三杆，A第一个醒来，他将鱼分为五份，把多余的一条鱼扔掉，拿走自己的一份。B第二个醒来，也将鱼分为五份，把多余的一条鱼扔掉，保持走自己的一份。C、D、E依次醒来，也按同样的方法拿走鱼。问他们合伙至少捕了多少条鱼？

 1 /**
 2  * 
 3  * 捕鱼和分鱼
 4  * 
 5  * A、B、C、D、E五个人在某天夜里合伙去捕鱼，到第二天凌晨时都疲惫不堪，于是各自找地方睡觉。
 6  * 
 7  * 日上三杆，A第一个醒来，他将鱼分为五份，把多余的一条鱼扔掉，拿走自己的一份。
 8  * 
 9  * B第二个醒来，也将鱼分为五份，把多余的一条鱼扔掉，保持走自己的一份。
10  * 
11  * C、D、E依次醒来，也按同样的方法拿走鱼。问他们合伙至少捕了多少条鱼？
12  * 
13  * @author Administrator
14  * 
15  */
16 public class 捕鱼和分鱼 {
17 
18     public static void main(String[] args) {
19         int num = 5;
20         for (;;) {
21             int count = num;
22             if ((count - 1) % 5 == 0) {
23                 count = (count - 1) / 5 * 4;
24                 if ((count - 1) % 5 == 0) {
25                     count = (count - 1) / 5 * 4;
26                     if ((count - 1) % 5 == 0) {
27                         count = (count - 1) / 5 * 4;
28                         if ((count - 1) % 5 == 0) {
29                             count = (count - 1) / 5 * 4;
30                             if ((count - 1) % 5 == 0) {
31                                 count = (count - 1) / 5 * 4;
32                                 System.out.println("原有的条数：" + num + "\n剩余的条数："
33                                         + count);
34                                 break;
35                             }
36                         }
37                     }
38                 }
39             }
40             num++;
41         }
42     }
43 
44 }

二、出售金鱼

【此题关键在于找到每次卖出的鱼有多少，还有比较重要的一点就是要先减去11条。但是个人感觉这种做法貌似不是很正确啊！！！】

买卖提将养的一缸金鱼分五次出售系统上一次卖出全部的一半加二分之一条；第二次卖出余下的三分之一加三分之一条；第三次卖出余下的四分之一加四分之一条；第四次卖出余下的五分之一加五分之一条；最后卖出余下的11条。问原来的鱼缸中共有几条金鱼？

 1 /**
 2  * 出售金鱼 
 3  * 
 4  * 买卖提将养的一缸金鱼分五次出售
 5  * 
 6  * 系统上一次卖出全部的一半加二分之一条；【卖了1/2+1/2*1/2条】
 7  * 
 8  * 第二次卖出余下的三分之一加三分之一条；【卖了1/3+(1/3)*(2/3条)】
 9  * 
10  * 第三次卖出余下的四分之一加四分之一条；【卖了1/4+(1/4)*(3/4)条】
11  * 
12  * 第四次卖出余下的五分之一加五分之一条；【卖了1/5+(1/5)*(4/5)条】
13  * 
14  * 最后卖出余下的11条。问原来的鱼缸中共有几条金鱼？
15  * 
16  * @author Administrator
17  *
18  */
19 public class 出售金鱼 {
20     public static void main(String[] args) {
21         for (int i = 12;; i++) {
22             int count = i - 11;
23             if (count % 4 == 0) {
24                 count = count - count * 3 / 4;
25                 if (count % 9 == 0) {
26                     count = count - count * 5 / 9;
27                     if (count % 16 == 0) {
28                         count = count - count * 7 / 16;
29                         if (count % 25 == 0) {
30                             count = count - count * 9 / 25;
31                             System.out.println("鱼缸原有的金鱼的数量：" + i);
32                             break;
33                         }
34                     }
35                 }
36             }
37         }
38     }
39 }

三、逻辑判断

A、B、C、D、E、F、G、H、I、J 共10名学生有可能参加本次计算机竞赛，也可能不参加。因为某种原因，他们是否参赛受到下列条件的约束：

1. 如果A参加，B也参加；
2. 如果C不参加，D也不参加；
3. A和C中只能有一个人参加；
4. B和D中有且仅有一个人参加；
5. D、E、F、G、H 中至少有2人参加；
6. C和G或者都参加，或者都不参加；
7. C、E、G、I中至多只能2人参加
8. 如果E参加，那么F和G也都参加。
9. 如果F参加，G、H就不能参加
10. 如果I、J都不参加，H必须参加

请编程根据这些条件判断这10名同学中参赛者名单。如果有多种可能，则输出所有的可能情况。每种情况占一行。参赛同学按字母升序排列，用空格分隔。

 1 public class LuoJiPanDuan {
 2     public static void show(int[] x) {
 3         for (int i = 0; i < x.length; i++) {
 4             if (x[i] > 0) {
 5                 System.out.print((char) (i + ‘A‘) + " ");
 6             }
 7         }
 8         System.out.println();
 9     }
10 
11     public static boolean judge(int[] x) {
12         boolean t1 = x[0] == 0 || x[1] == 1;
13         boolean t2 = x[2] == 1 || x[3] == 0;
14         boolean t3 = x[0] + x[2] <= 1;
15         boolean t4 = x[1] + x[3] == 1;
16         boolean t5 = x[3] + x[4] + x[5] + x[6] + x[7] >= 2;
17         boolean t6 = (x[2] + x[6] == 0) || (x[2] + x[6] == 2);
18         boolean t7 = x[2] + x[4] + x[6] + x[8] <= 2;
19         boolean t8 = x[4] == 0 || (x[5] + x[6]) == 2;
20         boolean t9 = x[5] == 0 || (x[6] + x[7] == 0);
21         boolean t10 = (x[8] + x[9] > 0) || x[7] == 1;
22         return t1 && t2 && t3 && t4 && t5 && t6 && t7 && t8 && t9 && t10;
23     }
24 
25     public static void f(int[] x, int n) {
26         if (n == x.length) {
27             if (judge(x))
28                 show(x);
29             return;
30         }
31         x[n] = 0;
32         f(x, n + 1);
33         x[n] = 1;
34         f(x, n + 1);
35     }
36 
37     public static void main(String[] args) {
38         // A B C D E F G H I J
39         int[] x = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
40         f(x, 0);
41     }
42 
43 }

四、夺冠概率

足球比赛具有一定程度的偶然性，弱队也有战胜强队的可能。

假设有甲、乙、丙、丁四个球队。根据他们过去比赛的成绩，得出每个队与另一个队对阵时取胜的概率表:

甲乙　　丙　　丁

甲 - 　　0.1 　0.3　　0.5

乙 0.9 　　- 　0.7　　0.4

丙 0.7 　　0.3 　 - 　　0.2

丁 0.5 　　0.6 0.8　　-

数据含义：甲对乙的取胜概率为0.1，丙对乙的胜率为0.3，...

现在要举行一次锦标赛。双方抽签，分两个组比，获胜的两个队再争夺冠军。（参见【1.jpg】）

请你进行10万次模拟，计算出甲队夺冠的概率。

注意：请仔细调试！您的程序只有能运行出正确结果的时候才有机会得分！

 1 /*
 2  * 夺冠概率 足球比赛具有一定程度的偶然性，弱队也有战胜强队的可能。
 3  * 
 4  * 假设有甲、乙、丙、丁四个球队。
 5  * 
 6  * 根据他们过去比赛的成绩，得出每个队与另一个队对阵时取胜的概率表: 
 7  * 
 8  *    甲     乙         丙         丁
 9  *     
10  * 甲 -         0.1     0.3     0.5
11  *  
12  * 乙 0.9     -         0.7     0.4
13  *  
14  * 丙 0.7     0.3     -         0.2
15  *  
16  * 丁 0.5     0.6     0.8     - 
17  * 
18  * 数据含义：甲对乙的取胜概率为0.1，丙对乙的胜率为0.3，...
19  * 
20  * 现在要举行一次锦标赛。双方抽签，分两个组比，获胜的两个队再争夺冠军。（参见【1.jpg】） 
21  * 
22  * 请你进行10万次模拟，计算出甲队夺冠的概率。
23  * 
24  * 注意： 请仔细调试！您的程序只有能运行出正确结果的时候才有机会得分！
25  * 
26  * @author Administrator
27  * 
28  */
29 import java.util.Random;
30 import java.text.DecimalFormat;
31 public class 夺冠概率 {
32     public static void main(String[] args){
33         // (a vs b)a  表示  (a队与b队)对战,a队 胜的概率
34         // (a vs b)a*(c vs d)c*(a vs c)a + (a vs b)1*(c vs d)d*(a vs d)a
35         // 把1看作a
36         double ab_cd = 0.1*0.2*0.3+0.1*0.8*0.5;    // ab_cd 代表  (a与b 对战  c与d 对战)a(c|d) a的概率
37         double ac_bd = 0.3*0.4*0.1+0.3*0.6*0.5;    // ac_bd 代表  (a与c 对战  b与d 对战)a(b|d) a的概率
38         double ad_bc = 0.5*0.7*0.1+0.5*0.3*0.3;    // ad_bc 代表  (a与d 对战  b与c 对战)a(b|c) a的概率
39         double sum = 0;    // 总计
40         Random r = new Random(3);    // 随机对象 r
41         int n = 100000;    // 循环次数
42         for(int i=0;i<n;i++){    // 10万次模拟
43             switch(r.nextInt(3)){
44                 case 0: sum += ab_cd; break;
45                 case 1: sum += ac_bd; break;
46                 case 2: sum += ad_bc; break;
47             }
48         }
49         System.out.println(new DecimalFormat("#.###").format(sum/n));
50     }
51 }

五、 30人的班级，出现生日重复的概率有多大？

 1 /**
 2  * 30人的班级，出现生日重复的概率有多大？
 3  * 
 4  * 生日相同的概率【生日碰撞】
 5  * 
 6  * @author Administrator
 7  *
 8  */
 9 public class Birth {
10     public static void main(String[] args) {
11         final int N = 1000 * 100;
12         int n = 0;
13         for (int i = 0; i < N; i++) {
14             int[] x = new int[365];
15             for (int j = 0; j < 30; j++) {
16                 int p = (int) (Math.random() * 365);
17                 if (x[p] == 1) {
18                     n++;
19                     break;
20                 } else {
21                     x[p] = 1;
22                 }
23             }
24         }
25         double r = (double) n / N;
26         System.out.println(r);
27     }
28 }