论坛首页 → 综合技术论坛 →

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

浏览 2620 次
锁定老帖子 主题：2007年百度程序设计大赛其中一题之我解！
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
作者 正文
  • ido158
  • 等级: 初级会员
  • 性别:
  • 文章: 11
  • 积分: 30
  • 来自: 长沙
   发表时间：2007-08-30  
OO
题目是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 代码
  1. public class FindNumber {   
  2.     private int sum;   
  3.     private int lastNumber;   
  4.     /*  
  5.      *    构造注入  
  6.      */  
  7.     public FindNumber() {   
  8.         this.sum = 0;   
  9.         this.lastNumber = 0;   
  10.     }   
  11.     
  12.     /******************************************************************  
  13.      *    findWithoutSeven(int number)  
  14.      *    这个函数接受一个int 类型的参数 number 的传入，这个参数就是将要得出  
  15.      *    的数的序列号；  
  16.      *    从0开始一直到 sum == number; 查找符合条件得数；当sum == number时  
  17.      *    保存最后一个数到lastNumber;  
  18.      ******************************************************************  
  19.      */  
  20.     
  21.     public int findWithoutSeven(int number) {   
  22.         int i = 0;   
  23.         while (true) {   
  24.             //将 i 转换为相应的 String ；   
  25.             String str = Integer.toString(i);   
  26.             //每个 i 都是将要判断的一个数，每次while 循环 i = i+1；   
  27.             i++;   
  28.             //由于代码重构要求将功能分解，但考虑用方法完成该功能会频繁进栈，出栈，故放弃该项子功能。   
  29.             //倘若 i 能被7整除   
  30.             if (i % 7 == 0) {   
  31.             } else //不能被7整除，但是数中存在至少一对相同的数字，或各位数中存在一个或多个7-   
  32.             if (findSame(i, str.length())) {   
  33.             } else {   
  34.                 //满足以上条件的话，把这个数算到sum中，保存它到 lastNumber 中   
  35.                 sum = sum + 1;   
  36.                 lastNumber = i;   
  37.             }   
  38.             if (sum == number) {   
  39.                 //倘若找到了满足条件的数的个数，跳出循环；   
  40.                 break;   
  41.             }   
  42.         }   
  43.         return this.lastNumber;   
  44.     }   
  45.     
  46.     /***********************  
  47.      * 递归函数：找到没有相同数字，不能被7整除，数中没有相同的数字，并且不含有7的数字的数！  
  48.      * 这个函数是这样一个递归函数，取得sInt.substring(position-1,position);  
  49.      */  
  50.     public boolean findSame(int find, int position) {   
  51.         // flag：标志；   
  52.         boolean flag = true;   
  53.         // rPosition ：   
  54.         int rPosition;   
  55.         if (position > 1) {   
  56.             rPosition = position - 1;   
  57.             //将int 类型的 find 转换位String 类型的 sInt   
  58.             String sInt = Integer.toString(find);   
  59.             //取得sInt 的 position个数为第一个数，它将和后面的数做比较；   
  60.             String first = sInt.substring(position - 1, position);   
  61.             //for循环从rPosition 位向前比较。   
  62.             for (; rPosition > 0; rPosition--) {   
  63.                 if (first.equals(sInt.substring(rPosition -1,rPosition)) ||   
  64.                     sInt.substring(sInt.length()-1 ,sInt.length()).equals("7") ||   
  65.                     sInt.substring(rPosition -1,rPosition).equals("7")   
  66.                         ) {   
  67.                     //倘若有，那么标志位置 true   
  68.                     flag = true; ;   
  69.                     return true;   
  70.                 }   
  71.             }   
  72.             //倘若标志位flag 是 true ，那么换下一位数开始比较；   
  73.             if (flag) {   
  74.                 return findSame(find, position - 1);   
  75.             }   
  76.         } else {   
  77.             //倘若标志位是false ，那么这个数符合要求，返回,换下个数；   
  78.             return false;   
  79.         }   
  80.         //倘若位数为一位，那么直接返回   
  81.         return false;   
  82.     }   
  83.     
  84.     public static void main(String[] args) {   
  85.         //构造对象；   
  86.         FindNumber findnumber = new FindNumber();   
  87.         //测试用例第100000个数，使用 C2.4G cpu 用时约 5秒；   
  88.         System.out.println(findnumber.findWithoutSeven(100000));   
  89.      }   
  90. }   
   
呵呵，其实挺容易的，计算机专业的一般都写的出。就是用时难把握，由于本例是用java语言编写，故用时较多，改写为C/C plus plus 的话，应该能够满足1秒的条件。
返回顶楼
         
  • yujiang
  • 等级: 初级会员
  • 性别:
  • 文章: 49
  • 积分: 52
  • 来自: 杭州
   发表时间：2007-08-30  

楼主的解法好像比较暴力,其实规则2的那个题可以用排列组合+逼近来解决.

这个问题在数字的位数大于10时就没有意义了,

记 P(n) 为 [power(10, n-1), power(10, n)) 之间 符合规则2的数的个数

1. [0, 10)之间是没有这样的数的. 也就是P(1) = 0
2. [10,100) 之间 有 C(9,1)*C(1,1), 就是十位随意给一个数字,个位要一个一样的.
   可以有 P(2) = 9
3. [100, 1000) 之间的先不说.
4. [1000, 10000) 之间的数可表示为abcd.
   如果bcd中有至少2个相同的数字.
     当bcd为3位数时 有 P(3)个可能.
     当bcd为2位数时 有P(2) + C(9,1)个可能(011, 010这样的都可以) .
     当bcd为1位数时 那就只有 000-009 C(10,1)个可能了.
     这个地方有一点要注意就是在归纳的n超过4的时候可能有a00de a000e这样形式的数出现.
   如果bcd中的数相互不等,这个时候要想符合规则2那就要求a同bcd中的某一个相同了
      这样的bcd可能有C(3,1)*C(9,1)*C(8,1) (bcd互不相同可以保证不出现重复).
   这样 P(4) = C(9,1) * (P(3) + P(2) + C(9,1) + C(10,1) + C(3,1)*C(9,1)*C(8,1))
5. 之后的分析其实都差不多了.
6. 在[A0...0, A9...9]之间符合规则2的个数为 P(K)/9
7. 慢慢尝试 到了一定的时候 再使用暴力精确逼近.
8. 这样的算法几乎是常数时间的.

9. 在解决[req12 z：同时符合规则1、2的第z个数是什么？]这样的问题时
   上面的解法可以算出一个比较大的起点,但是估计作用不是很大.....

 

附注: 把abcd 切成 abc  d分析起来应该更方便


  

返回顶楼
          回帖地址
0 请登录后投票
  • ido158
  • 等级: 初级会员
  • 性别:
  • 文章: 11
  • 积分: 30
  • 来自: 长沙
   发表时间：2007-08-30  
这个思路我确实做确实没有想到过（大学没选学概率统计,想不到有这么多好处）。我曾经尝试过多次用例测试，发现200000 与  100000的运行时间相差很多，这应该是当数字变大时进行比较时递归太耗时了。我想你这个方法应该能够解决我的这个问题（除非天文数字），如果数字太大后面的递归也比较耗时，但足够满足需求了。
返回顶楼
          回帖地址
0 请登录后投票
论坛首页 → 综合技术版

跳转论坛:
Global site tag (gtag.js) - Google Analytics