小景哥哥

1060. 爱丁顿数(25)–PAT乙级真题java实现

英国天文学家爱丁顿很喜欢骑车。据说他为了炫耀自己的骑车功力，还定义了一个“爱丁顿数”E，即满足有E天骑车超过E英里的最大整数E。据说爱丁顿自己的E等于87。

现给定某人N天的骑车距离，请你算出对应的爱丁顿数E（<=N）。

输入格式：

输入第一行给出一个正整数N（<=105），即连续骑车的天数；第二行给出N个非负整数，代表每天的骑车距离。

输出格式：

在一行中给出N天的爱丁顿数。

输入样例：

10

6 7 6 9 3 10 8 2 7 8

输出样例：

6

1020. 月饼 (25)
月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。
注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有3种月饼，其库存量分别为18、15、10万吨，总售价分别为75、72、45亿元。如果市场的最大需求量只有20万吨，那么我们最大收益策略应该是卖出全部15万吨第2种月饼、以及5万吨第3种月饼，获得 72 + 45/2 = 94.5（亿元）。
输入格式：
每个输入包含1个测试用例。每个测试用例先给出一个不超过1000的正整数N表示月饼的种类数、以及不超过500（以万吨为单位）的正整数D表示市场最大需求量。随后一行给出N个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出N个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。
输出格式：
对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后2位。
输入样例：
3 20
18 15 10
75 72 45
输出样例：
94.50

1030. 完美数列(25) 
给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。 
现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。 
输入格式： 
输入第一行给出两个正整数N和p，其中N（<= 10^5）是输入的正整数的个数，p（<= 10^9）是给定的参数。第二行给出N个正整数，每个数不超过10^9。 
输出格式： 
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。 
输入样例： 
10 8 
2 3 20 4 5 1 6 7 8 9 
输出样例： 
8

9.变态跳台阶

题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解题思路：

关于本题，前提是n个台阶会有一次n阶的跳法。分析如下:

        f(1) = 1

        f(2) = f(2-1) + f(2-2)         //f(2-2) 表示2阶一次跳2阶的次数。

        f(3) = f(3-1) + f(3-2) + f(3-3) 

        ...

        f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n) 

        说明： 

        1）这里的f(n) 代表的是n个台阶有一次1,2,...n阶的 跳法数。

        2）n = 1时，只有1种跳法，f(1) = 1

        3) n = 2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1） ，f(2) = f(2-1) + f(2-2) 

        4) n = 3时，会有三种跳得方式，1阶、2阶、3阶，

            那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3)

            因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)

        5) n = n时，会有n中跳的方式，1阶、2阶...n阶，得出结论：

            f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)  

        6) 由以上已经是一种结论，但是为了简单，我们可以继续简化：

            f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)

            f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)

            可以得出：

            f(n) = 2*f(n-1)

        7) 得出最终结论,在n阶台阶，一次有1、2、...n阶的跳的方式时，总得跳法为：

                   | 1       ,(n=0 ) 

        f(n) =  | 1       ,(n=1 )

                   | 2*f(n-1),(n>=2)

//java代码实现
  public class Solution {

  public int JumpFloorII(int target) {
        if (target <= 0) {
            return -1;
        } else if (target == 1) {
            return 1;
        } else {
            return 2 * JumpFloorII(target - 1);
        }
    }

    //Another solution
    public int JumpFloorII2(int target){
        int a=1; 
        return a<<(target-1);
    }
}

1046. 划拳(15) 
划拳是古老中国酒文化的一个有趣的组成部分。酒桌上两人划拳的方法为：每人口中喊出一个数字，同时用手比划出一个数字。如果谁比划出的数字正好等于两人喊出的数字之和，谁就赢了，输家罚一杯酒。两人同赢或两人同输则继续下一轮，直到唯一的赢家出现。 
下面给出甲、乙两人的划拳记录，请你统计他们最后分别喝了多少杯酒。 
输入格式： 
输入第一行先给出一个正整数N（<=100），随后N行，每行给出一轮划拳的记录，格式为： 
甲喊 甲划 乙喊 乙划 
其中“喊”是喊出的数字，“划”是划出的数字，均为不超过100的正整数（两只手一起划）。 
输出格式： 
在一行中先后输出甲、乙两人喝酒的杯数，其间以一个空格分隔。 
输入样例： 
5 
8 10 9 12 
5 10 5 10 
3 8 5 12 
12 18 1 13 
4 16 12 15 
输出样例： 
1 2

1009. 说反话 (20)
给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。
输入格式：测试输入包含一个测试用例，在一行内给出总长度不超过80的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用1个空格分开，输入保证句子末尾没有多余的空格。
输出格式：每个测试用例的输出占一行，输出倒序后的句子。
输入样例：
Hello World Here I Come
输出样例：输入样例：
Come I Here World Hello 

1022. D进制的A+B (20) 
输入两个非负10进制整数A和B(<=2^30-1)，输出A+B的D (1 < D <= 10)进制数。 
输入格式： 
输入在一行中依次给出3个整数A、B和D。 
输出格式： 
输出A+B的D进制数。 
输入样例： 
123 456 8 
输出样例： 
1103