2007年百度程序设计大赛其中一题之我解！

题目是2007年百度程序设计大赛的第二题。

***********************************************************************

2.大话西游与数字游戏

“叉烧鸡翅膀，我呀最爱吃！……”

 

百度spider组的“黑龙潭之行”在烤着鸡翅，唱着星爷的经典时达到高潮。大家在篝火旁围成一圈，开始玩“数7”加强版游戏，规则如下：

规则1：遇7的倍数或含7的数时pass。

规则2：遇有包含相同数字的数时pass。注意相同数字不必相邻。例如121。

 

数错的惩罚很残酷——吞食烤全羊。为避免惩罚，百度工程师们需要你——史上最强程序员的帮助。百度工程师想知道：

req1 x：符合规则1的第x个数是什么？

req2 y：符合规则2的第y个数是什么？

req12 z：同时符合规则1、2的第z个数是什么？

query n：数n是规则1中的第几个数，是规则2中的第几个数？

 

输入格式

输入的每一行为一个查询，由一个查询词和一个无符号整型数组成。共有四种查询，查询词分别为req1、req2、req12、query（区分大小写）。

 

输出格式

前三种查询输出一个无符号整型的解。对于“query n”的查询，若n是规则中的数则输出相应的解，否则输出-1。

 

输入样例 例

req1 10

req2 10

req12 10

query 14

 

 

输出样例 例

11

10

12

-1 13

 

 

评分规则

 

 

程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试用例上运行不能超过1秒，否则该用例不得分；

 

要求程序能按照输入样例的格式读取标准输入数据，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；

 

该题目共有10个测试数据集，其中数据1~5主要考查正确性，满足x,y,z,n<=1000；输入6~10主要考查时间效率，满足x<=10,000,000，y<=1,000,000，z<=240,000，n<=20,000,000。数据1和6只包含req1，数据2和7只包含req2，数据3和8只包含req12，数据4和7只包含query，数据5和10包含全部四种查询。每组数据都恰好包含100个查询。

 

该题目20分。

 

*********************************************************************

由于闲麻烦没有写IO读取文件的过程。

以下是我写的程序，编写的时第三问，即同时满足以上两个条件。经过数量为100000的用例测试，用时5秒。

java 代码

public class FindNumber {
    private int sum;
    private int lastNumber;
    /*
     *    构造注入
     */
    public FindNumber() {
        this.sum = 0;
        this.lastNumber = 0;
    }

    /******************************************************************
     *    findWithoutSeven(int number)
     *    这个函数接受一个int 类型的参数 number 的传入，这个参数就是将要得出
     *    的数的序列号；
     *    从0开始一直到 sum == number; 查找符合条件得数；当sum == number时
     *    保存最后一个数到lastNumber;
     ******************************************************************
     */

    public int findWithoutSeven(int number) {
        int i = 0;
        while (true) {
            //将 i 转换为相应的 String ；
            String str = Integer.toString(i);
            //每个 i 都是将要判断的一个数，每次while 循环 i = i+1；
            i++;
            //由于代码重构要求将功能分解，但考虑用方法完成该功能会频繁进栈，出栈，故放弃该项子功能。
            //倘若 i 能被7整除
            if (i % 7 == 0) {
            } else //不能被7整除，但是数中存在至少一对相同的数字，或各位数中存在一个或多个7-
            if (findSame(i, str.length())) {
            } else {
                //满足以上条件的话，把这个数算到sum中，保存它到 lastNumber 中
                sum = sum + 1;
                lastNumber = i;
            }
            if (sum == number) {
                //倘若找到了满足条件的数的个数，跳出循环；
                break;
            }
        }
        return this.lastNumber;
    }

    /***********************
     * 递归函数：找到没有相同数字，不能被7整除，数中没有相同的数字，并且不含有7的数字的数！
     * 这个函数是这样一个递归函数，取得sInt.substring(position-1,position);
     */
    public boolean findSame(int find, int position) {
        // flag：标志；
        boolean flag = true;
        // rPosition ：
        int rPosition;
        if (position > 1) {
            rPosition = position - 1;
            //将int 类型的 find 转换位String 类型的 sInt
            String sInt = Integer.toString(find);
            //取得sInt 的 position个数为第一个数，它将和后面的数做比较；
            String first = sInt.substring(position - 1, position);
            //for循环从rPosition 位向前比较。
            for (; rPosition > 0; rPosition--) {
                if (first.equals(sInt.substring(rPosition -1,rPosition)) ||
                    sInt.substring(sInt.length()-1 ,sInt.length()).equals("7") ||
                    sInt.substring(rPosition -1,rPosition).equals("7")
                        ) {
                    //倘若有，那么标志位置 true
                    flag = true; ;
                    return true;
                }
            }
            //倘若标志位flag 是 true ，那么换下一位数开始比较；
            if (flag) {
                return findSame(find, position - 1);
            }
        } else {
            //倘若标志位是false ，那么这个数符合要求，返回,换下个数；
            return false;
        }
        //倘若位数为一位，那么直接返回
        return false;
    }

    public static void main(String[] args) {
        //构造对象；
        FindNumber findnumber = new FindNumber();
        //测试用例第100000个数，使用 C2.4G cpu 用时约 5秒；
        System.out.println(findnumber.findWithoutSeven(100000));
     }
}

   

呵呵，其实挺容易的，计算机专业的一般都写的出。就是用时难把握，由于本例是用java语言编写，故用时较多，改写为C/C plus plus 的话，应该能够满足1秒的条件。

分享到：

学习，真的是需要毅力的！

• 2007-08-30 16:55
• 浏览 1786
• 评论(2)
• 论坛回复 / 浏览 (2 / 2621)
• 分类:编程语言
• 查看更多

评论

2 楼 ido158 2007-08-30  

这个思路我确实做确实没有想到过（大学没选学概率统计,想不到有这么多好处）。我曾经尝试过多次用例测试，发现200000 与  100000的运行时间相差很多，这应该是当数字变大时进行比较时递归太耗时了。我想你这个方法应该能够解决我的这个问题（除非天文数字），如果数字太大后面的递归也比较耗时，但足够满足需求了。

1 楼 yujiang 2007-08-30  

<p><font>楼主的解法好像比较暴力,其实规则2的那个题可以用排列组合+逼近来解决.</font></p>
<p><font>这个问题在数字的位数大于10时就没有意义了,</font></p>
<p><font>记 P(n) 为 [power(10, n-1), power(10, n)) 之间 符合规则2的数的个数</font></p>
<p><font>1. [0, 10)之间是没有这样的数的. 也就是P(1) = 0<br/>
2. [10,100) 之间 有 C(9,1)*C(1,1), 就是十位随意给一个数字,个位要一个一样的.<br/>
   可以有 P(2) = 9<br/>
3. [100, 1000) 之间的先不说. <br/>
4. [1000, 10000) 之间的数可表示为abcd. <br/>
   如果bcd中有至少2个相同的数字.<br/>
     当bcd为3位数时 有 P(3)个可能.<br/>
     当bcd为2位数时 有P(2) + C(9,1)个可能(011, 010这样的都可以) .</font><font><br/>
     当bcd为1位数时 那就只有 000-009 C(10,1)个可能了.<br/>
     这个地方有一点要注意就是在归纳的n超过4的时候可能有a00de a000e这样形式的数出现.<br/>
   如果bcd中的数相互不等,这个时候要想符合规则2那就要求a同bcd中的某一个相同了<br/>
      这样的bcd可能有C(3,1)*C(9,1)*C(8,1) (bcd互不相同可以保证不出现重复).<br/>
   这样 P(4) = C(9,1) * (P(3) + P(2) + C(9,1) + C(10,1) + C(3,1)*C(9,1)*C(8,1))<br/>
5. 之后的分析其实都差不多了.<br/>
6. 在[A0...0, A9...9]之间符合规则2的个数为 P(K)/9<br/>
7. 慢慢尝试 到了一定的时候 再使用暴力精确逼近.<br/>
8. 这样的算法几乎是常数时间的.</font></p>
<p><font>9. 在解决[req12 z：同时符合规则1、2的第z个数是什么？]这样的问题时<br/>
   上面的解法可以算出一个比较大的起点,但是估计作用不是很大.....</font></p>
<p> </p>
<p>附注: 把abcd 切成 abc  d分析起来应该更方便</p>
<p><font><br/>
   </font></p>