第2章数字之魅——找符合条件的整数

找符合条件的整数

问题描述

　　任意给定一个正整数N，求一个最小的正整数M(M>1)，使得N*M的十进制表示形式里只含有1和0。

　　解决这个问题首先考虑对于任意的N，是否这样的M一定存在。可以证明，M是一定存在的，而且不唯一。
简单证明：因为

这是一个无穷数列，但是数列中的每一项取值范围都在[0, N-1]之间。所以这个无穷数列中间必定存在循环节。即假设有s,t均是正整数，且s<t，有。于是循环节长度为t-s。于是10^s = 10^t。因此有：
，所以

例如，取N＝3，因为10的任何非负次方模3都为1，所以循环节周期为1.有：

分析与解法

【解法一】

　　给定N，令M从2开始，枚举M的值直到遇到一个M使得N*M的十进制表示中只有1和0。

代码如下：

 1 package chapter2shuzizhimei.findminint;
 2 /**
 3  * 找符合条件的整数
 4  * 【解法一】
 5  * @author DELL
 6  *
 7  */
 8 public class FindMinInt1 {
 9     //判断整数的十进制表示中是否只有0和1
10     public static boolean hasOnlyOneAndZero(long x){
11         while(x!=0){
12             if(x%10>=2)
13                 return false;
14             x /= 10;
15         }
16         return true;
17     }
18     //找符合条件的最小的正整数
19     public static long findMin(long n){
20         for(int i=2;;i++){
21             if(hasOnlyOneAndZero(i*n))
22                 return i;
23         }
24     }
25     
26     public static void main(String[] args) {
27         long n = 3;
28         System.out.println("使得与"+n+"的乘积的十进制表示形式里只有1和0的最小正整数为："+findMin(n));
29 
30     }
31 
32 }

程序运行结果如下：

使得与3的乘积的十进制表示形式里只有1和0的最小正整数为：37

【解法二】

　　求出10的次方序列模N的余数序列并找出循环节。然后搜索这个余数序列，搜索的目的就是要在这个余数序列中找到一些数出来让它们的和是N的倍数。例如N=13，这个序列就是1,10,9,12,3,4然后不断循环。很明显有1+12=13，而1是10的0次方，12是10的3次方，所以这个数就是1000+1=1001，M就是1001/13=77。

【解法三】

　　因为N*M的取值就是1,10,11,100,101,110,111,......所以直接在这个空间搜索，这是对方法一的改进。搜索这个序列直到找到一个能被N整除的数，它就是N*M，然后可计算出M。例如N=3时，搜索树如下：

上图中括号内表示模3的余数。括号外表示被搜索的数。左子树表示0，右子树表示1.上图中搜索到第二层（根是第0层）时遇到111，它模3余数为0.所以N*M=111, M=111/3=37。

具体实现代码如下：

 1 package chapter2shuzizhimei.findminint;
 2 
 3 import java.util.LinkedList;
 4 import java.util.Queue;
 5 
 6 /**
 7  * 找符合条件的整数
 8  * 【解法三】
 9  * @author DELL
10  *
11  */
12 public class FindMinInt3 {
13     
14     //找符合条件的最小的正整数
15     public static long findMin(long n){
16         Queue<Long> queue = new LinkedList<Long>();
17         queue.add((long) 1);
18         long temp;  //存放取出的队首元素
19         while(true){
20             temp = queue.poll();
21             if(temp%n==0)
22                 return temp/n;
23             queue.add(temp*10);
24             queue.add(temp*10+1);
25         }
26     }
27     
28     public static void main(String[] args) {
29         long n = 3;
30         System.out.println("使得与"+n+"的乘积的十进制表示形式里只有1和0的最小正整数为："+findMin(n));
31 
32     }
33 
34 }

程序运行结果如下：

使得与3的乘积的十进制表示形式里只有1和0的最小正整数为：37

【解法四】

　　对方法三的改进。将方法三的搜索空间按模N余数分类，使得搜索时间和空间都由原来的指数级降到了O(N)。改进的原理：假设当前正在搜索由0，1组成的K位十进制数，这样的K位十进制数共有2^k个。假设其中有两个数X、Y，它们模N同余，那么在搜索由0、1组成的K+1位十进制数时，X和Y会被扩展出四个数：10X, 10X+1, 10Y, 10Y+1。因为X和Y同余（同余完全可以看作相等），所以10X与10Y同余，10X+1与10Y+1同余。也就是说由Y扩展出来的子树和由X扩展产生出来的子树产生完全相同的余数，如果X比Y小，那么Y肯定不是满足要求的最小的数，所以Y这棵子树可以被剪掉。这样，2^k个数按照模N余数分类，每类中只保留最小的那个数以供扩展。原来在这一层需要搜索2^k个数，现在只需要搜索O(N)个数。例如，当N=9时，第0层是1(1)，

　　如上图所示，第2层的110，第三层的1010、1110都因为同一层有和它同余且更小的数而被剪掉。如果按照方法三搜索，第三层本来应该有8个结点，但现在只有4个结点。

只需要将10^k%N的结果与余数信息数组里非空的元素相加，再去模N，看看会不会出现新的余数。

具体代码如下：

 1 package chapter2shuzizhimei.findminint;
 2 
 3 import java.util.LinkedList;
 4 import java.util.Queue;
 5 
 6 /**
 7  * 找符合条件的整数
 8  * 【解法四】
 9  * @author DELL
10  *
11  */
12 public class FindMinInt4 {
13     
14     //找符合条件的最小的正整数
15     public static long findMin(long n){
16         long[] a = new long[(int) n]; //a[i]记录模n余i之后的数值
17         for(int i=0;i<n;i++){ //初始化数组
18             a[i]=-1;
19         }
20         int factor = 1;
21         a[1] = 1;
22         int i;
23         for(i=0; ;i++){
24             factor *= 10;
25             int current = (int) (factor % n);
26             if(current == 0){
27                 a[current] = factor; //保存余数为0的数
28                 return factor/n;
29             }
30             if(a[current]==-1){
31                 a[current] = factor;
32             }
33             //将当前的余数跟余数数组里面的余数相加mod n
34             int k; //存放前面的余数
35             //将当前的余数与前面的余数都相加再模上n，若产生新的余数的数值保存下来，另外若得到与以前相同的数值，不更新，因为要保存最小的
36             for(k=1;k<n;k++){
37                 if(a[k]==-1)
38                     continue;
39                 int newyu = (int) ((current+k)%n);
40                  //新产生的余数不存在，将factor与k相加，得到新的数，只与小于factor的数进行想加，不要与后面的相加,与factor相加的数一定要小于factor
41                 if(a[newyu]==-1&&a[k]<factor){
42                     a[newyu] = factor + a[k];
43                     if(newyu==0)
44                         return a[newyu]/n;
45                 }
46             }
47         }
48     }
49     
50     public static void main(String[] args) {
51         long n = 3;
52         System.out.println("使得与"+n+"的乘积的十进制表示形式里只有1和0的最小正整数为："+findMin(n));
53 
54     }
55 
56 }

程序运行结果如下：

使得与3的乘积的十进制表示形式里只有1和0的最小正整数为：37