当前位置：首页 > news >正文

【蓝桥杯-筑基篇】基础数学思维与技巧(1)

news 来源：原创 2024/4/29 2:03:01

🍓系列专栏:蓝桥杯

🍉个人主页:个人主页

1.一百以内的A+B

2.小学生算术求进位次数

3.最大公约数

4.最小公倍数

5.十进制转换其他进制

6.其他进制转十进制

7.天空数

8.求集合的所有子集

9.判断一个数是否为2的次方数

10.二进制中1的个数

1.一百以内的A+B

小明今年3岁了, 现在他已经能够认识100以内的非负整数, 并且能够进行100以内的非负整数的加法计算.
对于大于等于100的整数, 小明仅保留该数的最后两位进行计算, 如果计算结果大于等于100, 那么小明也仅保留计算结果的最后两位.

例如, 对于小明来说:2.小学生算术求进位次数
1) 1234和34是相等的
2) 35+80=15

a%100 让第一个数变成100以内的数字
b%100 让第二个数变成100以内的数字

因为两个100以内的数相加可能>100
因为小明只知道100以内的数字,故此还需让2数之和对100取余

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
        System.out.println((a%100+b%100)%100);

    }

2.小学生算术求进位次数

题意：计算两个整数相加时需要多少次进位。程序可以一直计算两个整数相加，当输入2个0时,结束循环（输入的整数都不超过9个数字）
输入：123 456 输出：0

输入：555 555 输出：3

输入：123 594 输出：1

分析：输入的数字不超过9个数字，可以用int表示。每次把a和b分别模10得到个位数。

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);


        while (true)
        {
            int a = scan.nextInt();


            int b = scan.nextInt();
            //输入2个0 退出循环
            if (a==0&&b==0){

                break;
            }

            int count=0;
            int c=0;
            while (a>0||b>0){
                c=a%10+b%10+c/10%10;
                if (c>=10){
                    count++;
                }
                a=a/10;
                b=b/10;
            }
            System.out.println(count);
        }

    }

3.最大公约数

公约数，亦称“公因数”。它是一个能同时整除几个整数的数。如果一个整数同时是几个整数的约数，称这个整数为它们的“公约数”。

公约数中最大的称为最大公约数。对任意的若干个正整数，1总是它们的公因数。公约数与公倍数相反，就是既是A的约数同时也是B的约数的数，12和15的公约数有1，3，最大公约数就是3。再举个例子，30和40，它们的公约数有1，2，5，10，最大公约数是10

辗转相除法求最大公约数:

public class Test {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        System.out.println(gcb(a, b));

    }

    private static int gcb(int a, int b) {

        int temp=0;
        while (b>0){
            temp=a%b;
            a=b;
            b=temp;

        }
        return a;
    }


}

4.最小公倍数

以知a和b两个数，最小公倍数 = （a*b）/ 最大公约数

如：4和6的最大公约数是2，那最小公倍数就是（4*6） / 2 = 12。

public class Test {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        System.out.println((a*b)/gcb(a, b));

    }

    private static int gcb(int a, int b) {

        int temp=0;
        while (b>0){
            temp=a%b;
            a=b;
            b=temp;

        }
        return a;
    }


}

5.十进制转换其他进制

1.使用Integer.toxxxString()方法

        // 10进制转2，8，16进制，返回类型String
        String tb = Integer.toBinaryString(9);    // 10进制转2进制
        String to = Integer.toOctalString(10);    // 10进制转8进制
        String th = Integer.toHexString(1194684);    // 10进制转16进制

2.使用Integer.toString() 方法

    public static void main(String[] args) {
        // 10进制转2，8，16进制，返回类型String
        // 使用Integer.toString()方法；
        String tb = Integer.toString(9, 2); // 10进制转2进制
        System.out.println(tb);
        String to = Integer.toString(10, 8);    // 10进制转8进制
        System.out.println(to);
        String th = Integer.toString(1194684, 16);// 10进制转16进制
        System.out.println(th);

    }

6.其他进制转十进制

1.使用Integer.parseInt()方法

// 2，8，16进制转换成10进制
// 使用Integer.parseInt()方法；转换成负数只需要在字符串前面加上负号-；大于Integer.MAX_VALUE或小于Integer.MIN_VALUE的转换将会抛出错误。
int b = Integer.parseInt("1001", 2);    // 2进制转10进制
int o = Integer.parseInt("12", 8);    // 8进制转10进制
int h = Integer.parseInt("123ABC", 16);    // 16进制转10进制

2.使用Integer.valueOf()方法

/ 2，8，16进制转换成10进制
// 使用Integer.valueOf()方法；转换成负数只需要在字符串前加上负号-；大于Integer.MAX_VALUE或小于Integer.MIN_VALUE的转换将会抛出错误。
Integer b = Integer.valueOf("1001", 2); // 2进制转10进制
Integer o = Integer.valueOf("12", 8);    // 8进制转10进制
Integer h = Integer.valueOf("123ABC", 16);    // 16进制转10进制

7.天空数

四位数2992，这个数，它的十进制数，其四位数字之和为2+9+9+2=22，它的十六进制数BB0，其四位数字之和也为22，同时它的十二进制数表示1894，其四位数字之和也为22，把这样的一个四位数命名为天空数，任给一个四位数判断它是否为天空数

public class Test {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int number = scanner.nextInt();
        if (getSum(number,10)==getSum(number,16)&&getSum(number,10)==getSum(number,12)){
            System.out.println("true");
        }else System.out.println("false");
    }

    private static int getSum(int number, int i) {
        int sum=0;
        while (number>0){
            sum=sum+number%i;
            number=number/i;
        }
        return sum;
    }


}

8.求集合的所有子集

如果一个集合的元素个数为n,则每个元素都有存在或不存在两种情况，n个元素一共2^n种情况，因此元素个数为n的集合一共有2的n次方个子集。

利用二进制的思想:

0表示该数组位置不选，1表示选中。加入数组为[1,2,3,4] 0110就表示[2,3] 1001表示[1,4]

    public static void main(String[] args) {
        int arr[]={1,2,3,4};
        int number = (int)Math.pow(2, arr.length)-1;
        for (int i = 0; i <= number; i++) {
            int index=arr.length-1;
            int n=i;
            System.out.print("{");
            while (n>0){

                if (n%2==1){
                    System.out.print(arr[index]);
                }
                index--;
                n=n/2;

            }
            System.out.println("}");

        }


    }

9.判断一个数是否为2的次方数

如果采用循环去遍历2的次方数，来判断时，当这个数特别大，时间复杂度为O（n）；

所以采用别的方法，2的次方数其二进制表示最高位肯定为1，其余为0。
例如：8 二进制位 1000，64 二进制位 1000000。将这个二进制-1，然后和其原来的数&运算，如果是2的次方数，其结果应该为0，否则不是2的次方数。

    public static void main(String[] args) {
        int number=0;
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            number=scanner.nextInt();
            if ((number&(number-1))==0){
                System.out.println("yes");

            }else System.out.println("no");


        }




    }

10.二进制中1的个数

方法一 : 调用API

先将整数转为二进制.然后统计1的个数.

    public static void main(String[] args) {
        int number=0;
        
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int count=0;
            number=scanner.nextInt();
            String s = Integer.toBinaryString(number);
            char[] array = s.toCharArray();
            for (int i = 0; i < array.length; i++) {
                if (array[i]=='1'){
                    count++;
                }
            }

            System.out.println(count);
        }




    }

方法二 : 对2取余

假如 10 这个数，它的二进制数是 00000000000000000000000000001010

10 % 2 = 0 —— 相当于把 10 的二进制的最低位也就是最右边的 0 拿到了

10 / 2 = 5 —— 5 的二进制是 00000000000000000000000000000101 相当于去掉了 10 的二进制最低位也就是最右边 0

5 % 2 = 1 —— 相当于把 5 的二进制的最低位也就是最右边的 1 拿到了

5 / 2 = 2 —— 2 的二进制是 00000000000000000000000000000010 相当于去掉了 5 的二进制最低位也就是最右边 1

2 % 2 = 0 —— 相当于把 2 的二进制的最低位也就是最右边的 0 拿到了

2 / 2 = 1 —— 1 的二进制是 00000000000000000000000000000001 相当于去掉了 2 的二进制最低位也就是最右边 0

后面依次类推，当每次 n%2 = 1 就累计一次，知道 n = 0 为止，下面是代码：

    public static void main(String[] args) {
        int number=0;


        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            int count=0;
            number=scanner.nextInt();
            while (number >0) {
                if (number%2==1){
                    count++;
                }
                number=number/2;

            }

            System.out.println(count);
        }


    }

方法三：位运算

有个表达式是 ====> n = n & ( n-1 ) ，假如输入 n = 13 ，13 的二进制 1101

1101 —— n

1100 —— n-1

1100 —— n & n-1 再赋给 n、

1011 —— n-1

1000 —— n & n-1 再赋给 n

0111 —— n-1

0000 —— n & n-1 再赋给 n

每次去掉一个 1，执行几次就有几个 1 ，每次把二进制数的最右边的 1去掉，直到为零停止，代码如下：

    public static void main(String[] args) {
        int number = 0;

        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int count = 0;
            number = scanner.nextInt();
            while (number!=0) {
                number = (number & (number - 1));
                count++;
            }
            System.out.println(count);

        }
    }