本文主要是介绍玩转算法01——寻找满足确定公因式的整数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：

在[1,10000]之间任选一个整数n，再在[1,1000000000]之间任选n个整数。 在这n+1个数中，寻找出由11,111,1111，…1111…组成的数。

例如n+1个数中 某一些数为 22=11+11，——符合范围；122=111+11，——符合范围；111111233=111111111+111+11——符合范围。
思路
保存所有的n+1个待测数据，11,111，…111111之间有个规律

111=11*10+1；
1111=111*10+1；
11111=1111*10+1
...

求解一个九位数的整数N1234546789；
第一步
先判断九位数的111111111 是否大于N;如果大于N，那么退一步选八位数的11111111，如果小于N，则选择和N同位数的1；

第二步
令N等于N%…11… 的余数

重复一二两步

最后一步是判断推出条件
能够退出的条件分别是：最后取余小于11但不等于0——不符合范围
最后取余等于0，——符合条件
能直接整除11,111,11111…的——符合条件

结果

这种思路应该可以寻找出大部分的数了
题目来源2021sf开发笔试题，——师兄分享的哈哈哈哈，然后花了点时间做出来，不过放到面试上就来不及了
不过先涨涨经验。

代码

import java.util.ArrayList;
import java.util.Random;

/**
 * @author #Description findFactor
 * #Date: 2021/9/7 14:52
 */
public class findFactor {
    public static void main(String[] args) {
        //求出第一行
        int n;
        n=out_N();
        System.out.println("第一行的整数n:"+n);

        //求出第二行
        ArrayList random_all=new ArrayList();
        random_all=out_array_all_num(n);
        System.out.println("第二行"+n+"个随机数：");
        for (Object ran_num:random_all) {
            System.out.print(ran_num+"\t");
        }

        //求出在1000000000以内所有的1111....
        ArrayList arr_111=new ArrayList();
        arr_111=sta_111();
        int count=arr_111.size();//统计个数  11在0  111在1   1111在2   11111111在6

        //从最大的一开始排除
        test(random_all,arr_111);
    }

    public static int out_N(){
        Random random=new Random();
        int n = random.nextInt(100 + 1)+1;//100000
        return n;
    }

    public static ArrayList out_array_all_num(int n){
        ArrayList arrayList=new ArrayList();
        Random random=new Random();
        int random_num;
        for (int i = 0; i < n; i++) {
            random_num=random.nextInt(1000000000+1)+1;//
            //System.out.print(rnum+"\t");
            arrayList.add(random_num);
        }
        return arrayList;
    }

    //保存所有111111
    public static ArrayList sta_111(){
        ArrayList arrayList2=new ArrayList();
        int x1=11;
        arrayList2.add(x1);
        int x=0,count=1;
        while (x<1000000000){
            x=x1*10+1;//算倒数第二次  链表里也不要最后一个
            x1=x;
            count++;
            if (x<=1000000000) {
                arrayList2.add(x);
                System.out.println(x+"次数"+count);
            }
        }
        return arrayList2;
    }

    //求几位数
    public static int weinum(int num){
        int count=0;
        while(num!=0)
        {
            num/=10;
            count++;
        }
        return count;
    }

    //算法实现
    //从最大的1111....组合开始取余
    public static void test(ArrayList random_all,ArrayList arr_111){
        System.out.println(random_all.size());
        int wei_N=0;//位数
        int temp_num=0;
        for (int i = 0; i <random_all.size() ; i++) {
            temp_num=(int)random_all.get(i);
            System.out.print(i+"初始："+temp_num);
            while (temp_num>=0){
                wei_N=weinum(temp_num);
                if(temp_num==0){
                    //System.out.println("成立");
                    break;
                }
                if(wei_N==1||temp_num<11){
                    System.out.println("-----不能被11组合");
                    break;
                }
                if(temp_num>=(((int)arr_111.get(wei_N-2))*wei_N)){//如果可以除以相同位数的11111
                    temp_num=(temp_num)%((int)arr_111.get(wei_N-2));
                }else if ((wei_N-2-1>=0)&&temp_num%(int)arr_111.get(wei_N-2-1)!=0){//整除小一位的11111....
                    temp_num=(temp_num)%((int)arr_111.get(wei_N-2-1));
                } else if((wei_N-2-1)<0&&temp_num%11!=0) {
                    temp_num=(temp_num)%11;
                }
                else if(temp_num%11==0){
                    System.out.println("-----成立,能被11组合");
                    break;
                }else if(temp_num%111==0){
                    System.out.println("-----成立,能被11组合");
                    break;
                }else if(temp_num%1111==0){
                    System.out.println("-----成立,能被11组合");
                    break;
                }else if(temp_num%11111==0){
                    System.out.println("-----成立,能被11组合");
                    break;
                }else if(temp_num%111111==0){
                    System.out.println("-----成立,能被11组合");
                    break;
                }else if(temp_num%1111111==0){
                    System.out.println("-----成立,能被11组合");
                    break;
                }else if(temp_num%11111111==0){
                    System.out.println("-----成立,能被11组合");
                    break;
                }else if(temp_num%111111111==0){
                    System.out.println("-----成立,能被11组合");
                    break;
                }

            }
            if(temp_num==0){
                System.out.println("-----成立,能被11组合");
            }
        }
    }
}

这篇关于玩转算法01——寻找满足确定公因式的整数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！