Java本科蓝桥杯比赛试题,算法练习

    黄金分割数是个无理数，也就是无法表示为两个整数的比值。0.618只是它的近似值，其真值可以通过对5开方减去1再除以2来获得，我们取它的一个较精确的近似值：0.618034

    有趣的是，一些简单的数列中也会包含这个无理数，这很令数学家震惊！

    1 3 4 7 11 18 29 47 .... 称为“鲁卡斯队列”。它后面的每一个项都是前边两项的和。

    如果观察前后两项的比值，即：1/3,3/4,4/7,7/11,11/18 ... 会发现它越来越接近于黄金分割数！

    你的任务就是计算出从哪一项开始，这个比值四舍五入后已经达到了与0.618034一致的精度。

请写出该比值。格式是：分子/分母。比如：29/47

2.有一群海盗（不多于20人），在船上比拼酒量。过程如下：打开一瓶酒，所有在场的人平分喝下，有几个人倒下了。再打开一瓶酒平分，又有倒下的，再次重复...... 直到开了第4瓶酒，坐着的已经所剩无几，海盗船长也在其中。当第4瓶酒平分喝下后，大家都倒下了。

    等船长醒来，发现海盗船搁浅了。他在航海日志中写到：“......昨天，我正好喝了一瓶.......奉劝大家，开船不喝酒，喝酒别开船......”

    请你根据这些信息，推断开始有多少人，每一轮喝下来还剩多少人。

    如果有多个可能的答案，请列出所有答案，每个答案占一行。

    格式是：人数,人数,...

    例如,有一种可能是：20,5,4,2,0

public class Test_2 {

    public static void main(String[] args) {

        for(int i=1; i<=16; i++)

            for(int j=1; j<=15; j++)

                for(int k=1; k<=14; k++)

                    for(int l=1; l<=13; l++){

                        int sum = i + j + k + l;

                        if(sum <= 20 && 1.0/sum + 1.0/(sum-i) + 1.0/(sum-i-j) + 1.0/(sum-i-j-k) == 1.0)

                            System.out.println(sum++(sum-i)++(sum-i-j)++l);

                    }

    }

}

3.汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。

    大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上(可以借助第三根柱子做缓冲)。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

    如图【】是现代“山寨”版的该玩具。个圆盘太多了，所以减为7个，金刚石和黄金都以木头代替了......但道理是相同的。

    据说完成大梵天的命令需要太多的移动次数，以至被认为完成之时就是世界末日！

    你的任务是精确计算出到底需要移动多少次。

    很明显，如果只有2个圆盘，需要移动3次。

    圆盘数为3，则需要移动7次。

那么个呢？

4. 某电视台举办了低碳生活大奖赛。题目的计分规则相当奇怪：

    每位选手需要回答10个问题（其编号为1到10），越后面越有难度。答对的，当前分数翻倍；答错了则扣掉与题号相同的分数（选手必须回答问题，不回答按错误处理）。

    每位选手都有一个起步的分数为10分。

    某获胜选手最终得分刚好是100分，如果不让你看比赛过程，你能推断出他（她）哪个题目答对了，哪个题目答错了吗？

    如果把答对的记为1，答错的记为0，则10个题目的回答情况可以用仅含有1和0的串来表示。例如：0010110011 就是可能的情况。

    你的任务是算出所有可能情况。每个答案占一行。

5.以下的静态方法实现了：把串s中第一个出现的数字的值返回。

如果找不到数字，返回-1

例如：

s = "abc24us43"  则返回2

s = "82445adb5"  则返回8

s = "ab"   则返回-1   

public static int getFirstNum(String s)

{

    if(s==null || s.length()==0) return -1;

    char c = s.charAt(0);

if(c>='0' && c<='9') return _____________; //填空

    return ___________________;  //填空

}

请分析代码逻辑，并推测划线处的代码。

6.南北朝时，我国数学家祖冲之首先把圆周率值计算到小数点后六位，比欧洲早了1100年！他采用的是称为“割圆法”的算法，实际上已经蕴含着现代微积分的思想。

    如图【】所示，圆的内接正六边形周长与圆的周长近似。多边形的边越多，接近的越好！我们从正六边形开始割圆吧。

    如图【】所示，从圆心做弦的垂线，可把6边形分割为12边形。该12边形的边长a'的计算方法很容易利用勾股定理给出。之后，再分割为正24边形，....如此循环会越来越接近圆周。

    之所以从正六边开始，是因为此时边长与半径相等，便于计算。取半径值为1，开始割圆吧！

    以下代码描述了割圆过程。

    程序先输出了标准圆周率值，紧接着输出了不断分割过程中多边形边数和所对应的圆周率逼近值。

public class B21

{

    public static void main(String[] args)

    {

        System.out.println("标准 " + Math.PI);

        double a = 1; 

        int n = 6;

     for(int i=0; i<10; i++)

        {

            double b = Math.sqrt(1-(a/2)*(a/2));

            a = Math.sqrt((1-b)*(1-b) + (a/2)*(a/2));

            n = ______________; //填空

            System.out.println(n + "  " + _______________);  // 填空

        }

    }

}

请分析代码逻辑，并推测划线处的代码。

7.[12,127,85,66,27,34,15,344,156,344,29,47,....]  

    这是某设备测量到的工程数据。

    因工程要求，需要找出最大的5个值。

    一般的想法是对它排序，输出前5个。但当数据较多时，这样做很浪费时间。因为对输出数据以外的数据进行排序并非工程要求，即便是要输出的5个数字，也并不要求按大小顺序，只要找到5个就可以。

    以下的代码采用了另外的思路。考虑如果手里已经抓着5个最大数，再来一个数据怎么办呢？让它和手里的数据比，如果比哪个大，就抢占它的座位，让那个被挤出来的再自己找位子,....

import java.util.*;

public class B23

{

public static List max5(List lst)

    {

     if(lst.size()<=5) return lst;    

        int a = _______________________;  // 填空

     List b = max5(lst);

     for(int i=0; i        {

            int t = b.get(i);

         if(a>t)

            {

                __________________;  // 填空

                a = t;  

            }

        }

        return b;

    }

    public static void main(String[] args)

    {

     List lst = new Vector();

        lst.addAll(Arrays.asList(12,127,85,66,27,34,15,344,156,344,29,47));        

        System.out.println(max5(lst));

    }

}

    请分析代码逻辑，并推测划线处的代码。

8.在编写图形界面软件的时候，经常会遇到处理两个矩形的关系。

    如图【】所示，矩形的交集指的是：两个矩形重叠区的矩形，当然也可能不存在（参看【】）。两个矩形的并集指的是：能包含这两个矩形的最小矩形，它一定是存在的。

    本题目的要求就是：由用户输入两个矩形的坐标，程序输出它们的交集和并集矩形。

    矩形坐标的输入格式是输入两个对角点坐标，注意，不保证是哪个对角，也不保证顺序（你可以体会一下，在桌面上拖动鼠标拉矩形，4个方向都可以的）。

    输入数据格式：

x1,y1,x2,y2

x1,y1,x2,y2  

    数据共两行，每行表示一个矩形。每行是两个点的坐标。x坐标在左，y坐标在右。坐标系统是：屏幕左上角为(0,0)，x坐标水平向右增大；y坐标垂直向下增大。

    要求程序输出格式：

x1,y1,长度,高度

x1,y1,长度,高度

    也是两行数据，分别表示交集和并集。如果交集不存在，则输出“不存在”

    前边两项是左上角的坐标。后边是矩形的长度和高度。

    例如，用户输入：

100,220,300,100    

150,150,300,300

    则程序输出：

150,150,150,70

100,100,200,200    

    例如，用户输入：

10,10,20,20

30,30,40,40

    则程序输出：

不存在

10,10,30,30

9.匪警请拨110,即使手机欠费也可拨通！

    为了保障社会秩序，保护人民群众生命财产安全，叔叔需要与罪犯斗智斗勇，因而需要经常性地进行体力训练和智力训练！

    某批叔叔正在进行智力训练：

    1 2 3 4 5 6 7 8 9 = 110;

    请看上边的算式，为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12+34+56+7-8+9 就是一种合格的填法；123+4+5+67- 是另一个可能的答案。

    请你利用计算机的优势，帮助叔叔快速找到所有答案。

    每个答案占一行。形如：

12+34+56+7-8+9

123+4+5+67-

......

    已知的两个答案可以输出，但不计分。   

    各个答案的前后顺序不重要。

10.泊松是法国数学家、物理学家和力学家。他一生致力科学事业，成果颇多。有许多著名的公式定理以他的名字命名，比如概率论中著名的泊松分布。

    有一次闲暇时，他提出过一个有趣的问题，后称为：“泊松分酒”。在我国古代也提出过类似问题，遗憾的是没有进行彻底探索，其中流传较多是：“韩信走马分油”问题。

    有3个容器，容量分别为12升，8升，5升。其中12升中装满油，另外两个空着。要求你只用3个容器操作，最后使得某个容器中正好有6升油。

    下面的列表是可能的操作状态记录：

12,0,0

4,8,0

4,3,5

9,3,0

9,0,3

1,8,3

1,6,5

    每行3个数据，分别表示12，8，6升容器中的油量

    第一行表示初始状态，第二行表示把12升倒入8升容器后的状态，第三行是8升倒入5升，...

    当然，同一个题目可能有多种不同的正确操作步骤。

    本题目的要求是，请你编写程序，由用户输入：各个容器的容量，开始的状态，和要求的目标油量，程序则通过计算输出一种实现的步骤（不需要找到所有可能的方法）。如果没有可能实现，则输出：“不可能”。

    例如，用户输入：

12,8,5,12,0,0,6

    用户输入的前三个数是容器容量（由大到小），接下来三个数是三个容器开始时的油量配置，最后一个数是要求得到的油量（放在哪个容器里得到都可以）

    则程序可以输出（答案不唯一，只验证操作可行性）：

12,0,0

4,8,0

4,3,5

9,3,0

9,0,3

1,8,3

1,6,5

    每一行表示一个操作过程中的油量状态。