首页 > Java开发 > 数字覆盖问题的一种解法

数字覆盖问题的一种解法

数字覆盖问题,没什么解题思想,如果说有的话,就是数学观察,代码如下

[java][/java] view plaincopy

  1. package com.wly.algorithmproblem;
  2. /**
  3.  * 数字覆盖问题
  4.  *
  5.     题目详情
  6.     给定整数区间[a,b]和整数区间[x,y],你可以使用任意多次a,b之间的整数做加法,可以凑出多少个[x,y]区间内的整数?
  7.     输入 a,b,x,y,其中1<= a < b <= 1000000000,  1 <= x < y <= 1000000000。
  8.     输出: 用[a,b]内的整数做任意多次加法,可以得到多少个[x,y]内的整数。
  9.     例如a = 8, b = 10, x = 3 , y = 20
  10.     我们可以得到 [3..20]之间的整数 8, 9, 10, 16 ( 8 + 8), 17(8 + 9), 18(9 + 9), 19(9 + 10), 20(10 + 10),因此输出8。
  11.     问:2+3=5 1+4=5 这算1个还是2个?
  12.     答:算1次 问你能覆盖多少个不同的数字 [x,y]全覆盖住得话 就是y - x + 1。
  13.  * @author wly
  14.  *
  15.  */
  16. public class howmany {
  17.     public static void main(String[] args) {
  18.         long time1;
  19. //      int max = 10000;
  20.         int max = 1000000000;
  21.         time1 = System.currentTimeMillis();
  22.         System.out.println("m1:" + howmany(3,4,10,max)); //999999440,5242
  23.         System.out.println(System.currentTimeMillis() - time1);
  24.         time1 = System.currentTimeMillis();
  25. //      System.out.println("m2:" + howmany2(400000000,400000050,1,1000000000)); //33993551
  26.         System.out.println("m2:" + howmany2(3,4,10,max)); //33993551
  27.         System.out.println(System.currentTimeMillis() - time1);
  28.     }
  29.     public static int howmany(int a,int b,int x,int y) {
  30.         int num = 0;
  31.         long times = 0;
  32.         if(x < a) {
  33.             x = a;
  34.         }
  35.         for(int i=x;i<=y;i++) {
  36.             times = i /a;
  37.             if(times*b >= i) {
  38.                 num ++;
  39. //              System.out.print(i + " ");
  40.             } else {
  41.                 continue ;
  42.             }
  43.         }
  44.         return num;
  45.     }
  46.     /**
  47.      * 结题思想:
  48.      * 本解法基本没有使用算法思想,主要是从数学推理解得的,根据题目要求若x可用[m,n]表示,则x属于[c language="*m,c*(m+n)"][/c],其中c是>=1的正整数
  49.      * 或者说[c language="*m,c*(m+n)"][/c]中的元素总是可以用[m,n]中的元素来表示
  50.      * 公式推理过程:设一个[c language="*m,c*(m+n)"][/c]中的数c*m + an + b,则c*m + an + b = a(m+n) + (c-a)m * b,其中1<=b<=n
  51.      * @param a
  52.      * @param b
  53.      * @param x
  54.      * @param y
  55.      * @return
  56.      */
  57.     public static int howmany2(int a,int b,int x,int y) {
  58.         int num = 0;
  59.         long times = 0;
  60.         if(a >= b || x >= y) {
  61.             return 0;
  62.         }
  63.         if(x < a) {
  64.             x = a;
  65.         }
  66.         //优化解法
  67.         int i = x; //-------就因为这里出错了,哎,,,
  68.         while(i <= y) { //使用while来实现i的改变
  69.             times = i /a;
  70.             if(times*b > i) {
  71.                 int delta;
  72.                 if(times*b >= y) {
  73.                     delta = (int) (y - i+1);
  74.                 } else {
  75.                     delta = (int) (times*b - i+1);
  76.                 }
  77.                 num = (int)(num + delta);
  78.                 i = delta + i;
  79. //              System.out.print(i + " ");
  80.             } else if(times*b == i) {
  81.                 i ++;
  82.                 num ++;
  83.             } else { //无解情况
  84.                 i ++;
  85.             }
  86.         }
  87.         return num;
  88.     }
  89. }

运行结果:

[java][/java] view plaincopy

  1. m1:999999991
  2. 3430
  3. m2:999999991
  4. 0

O啦~~~


本文固定链接: http://www.devba.com/index.php/archives/3926.html | 开发吧

报歉!评论已关闭.