Десять простых арифметических вопросов

Java задняя часть алгоритм WeChat

предисловие

Недавно я просматривал структуры данных и алгоритмы, написанные ранее на C, и обнаружил, что мои алгоритмы и структуры данных очень слабые, теперь переписываю их на Java и пересматриваю.

Можно только сказать, что он накапливается медленно ~ сложность следующих тем проста, старший брат алгоритма может напрямую игнорировать эту статью ~ студенты, которые являются новичками или слабы в алгоритме, могут ссылаться на нее ~

Многие мелкие алгоритмы, связанные с сортировкой (объединение массивов, получение суммы каждого значения числа), я не записал, потому что пока вы умеете сортировать слиянием (объединять массивы), вы будете знать сортировку ведра (получать значение каждый бит числа), это больше не проблема. Если вы не знакомы с восемью основными сортирующими учениками, вы можете прочитать: [Резюме восьми основных рейтингов

Из-за нехватки места давайте напишем по десять глав~

Если есть неправильное место или есть лучшая реализация, более подходящий способ понимания, я надеюсь, что вы оставите сообщение в области комментариев ~ Давайте общаться больше

Десять простых арифметических вопросов

Обзор тем

  1. 1-nсумма факториалов
  2. Получить наименьшее значение в каждом столбце двумерного массива
  3. Найдите значение «1!+4!(2 в квадрате)+9!(3 в квадрате)+...+n
  4. сумма диагональных элементов массива
  5. Распечатайте треугольник Ян Хуэй
  6. обезьяна ест персик проблема
  7. посчитать количество слов
  8. Определить, совпадают ли буквы
  9. Определить, является ли число степенью двойки
  10. Определить, является ли число уродливым числом

1. Сумма 1-n факториалов

Как посчитать сумму 1-n факториалов?

  • Факториал 1 равен1
  • Факториал 2 равен1*2
  • Факториал 3 равен1*2*3
  • Факториал 4 равен1*2*3*4
  • .........

Теперь мы запрашиваем сумму этих факториалов.Идеи:

  • сумма 3 факториаловНа самом деле это2 факториала и +3 факториала
  • сумма 4 факториаловНа самом деле это3 факториала и +4 факториала
  • .......


    /**
     * 1-n的阶乘之和
     */
    public static void Factorial(int n) {

        //总和
        double sum = 0;

        //阶乘值,初始化为1
        double factorial = 1;

        for (int i = 1; i <= n; i++) {

            factorial = factorial * i;


            sum = (int) (sum + factorial);

        }

        System.out.println("公众号:Java3y" + "     " + sum);

    }

2. Получить минимальное значение каждого столбца двумерного массива

Получить наименьшее значение в каждом столбце двумерного массива

Идеи:Итерация по столбцу, затем итерация по строкам в столбце

Обычно мы работаем с массивами из строк в столбцы.На этот раз требуется минимальное значение каждого столбца, поэтому внутренний цикл for должен пройти по строкам.


    /**
     * 求出二维数组每列的最小值
     */
    public static void minArray() {


        //二维数组
        int[][] arrays = {
            {23, 106, 8, 234},
            {25, 9, 73, 19},
            {56, 25, 67, 137}
        };


        //获取列数
        int maxColLength = arrays[0].length;



        //使用一个数组来装载每列最小的值
        int[] minArray = new int[maxColLength];


        //控制列数
        for (int i = 0; i < maxColLength; i++) {

            //假设每列的第一个元素是最小的
            int min = arrays[0][i];

            //控制行数
            for (int j = 1; j < arrays.length; j++) {


                //找到最小值
                if (arrays[j][i] < min) {
                    min = arrays[j][i];
                }
            }

            //赋值给装载每列最小的值的数组
            minArray[i] = min;
        }


        System.out.println("公众号:Java3y" + "     " + minArray);

    }


3. Найдите значение «1!+4!(2 квадрата)+9!(3 квадрата)+...+n

Найдите значение «1!+4!(2 в квадрате)+9!(3 в квадрате)

Идеи:Сначала найдите квадрат, затем факториал и, наконец, сложите.



    /**
     * 求"1!+4!(2的平方)+9!(3的平方)+...+n的值
     */
    public static void calculate() {

        double sum = 0;

        for (int i = 1; i <= 3; i++) {

            //得到平方数
            int square = i * i;

            //阶乘值,从1开始
            double factorial = 1;

            //求阶乘
            for (int j = 1; j <= square; j++) {
                factorial = factorial * j;
            }

            sum = sum + factorial;

        }

        System.out.println("公众号:Java3y" + "     " + sum);
        
    }

В-четвертых, сумма диагональных элементов массива

сумма диагональных элементов массива

Идеи:

  • Элементы диагонали, если строка и столбец равны

    /**
     * 数组对角线之和
     */
    public static void arraySum() {

        int[][] arrays = {
                {23, 106, 8, 234},
                {25, 9, 73, 19},
                {56, 25, 67, 137},
                {33, 22, 11, 44},
        };

        //和
        int sum = 0;

        for (int i = 0; i < arrays.length; i++) {

            for (int j = 0; j < arrays[i].length; j++) {

                if (i == j) {

                    sum = sum + arrays[i][j];

                }
            }
        }


        System.out.println("公众号:Java3y" + sum);
        
    }

5. Печать треугольника Ян Хуэя

Треугольник Ян Хуэй

Треугольник Ян Хуэя выглядит так:

ps: источник изображения находится в сети, захвачен и удален ~

закон:

  • Первая и последняя в каждой строке равны 1
    • Дальнейшие расчеты:Первый столбец - все 1, первая строка - все 1, когда количество столбцов равно количеству строк, это 1
  • Текущее значение равно значению заголовка плюс левое значение заголовка
  • Первая строка и один столбец, вторая строка - два столбца, третья строка - три столбца......

Код:


    /**
     * 打印杨辉三角形
     */
    public static void PascalTriangle() {


        //打印十行的杨辉三角形
        int[][] arrays = new int[10][];


        //行数
        for (int i = 0; i < arrays.length; i++) {


            //初始化第二层的大小
            arrays[i] = new int[i + 1];

            //列数
            for (int j = 0; j <= i; j++) {

                //是第一列,第一行,行数等于列数,那么通通为1
                if (i == 0 || j == 0 || j == i) {
                    arrays[i][j] = 1;
                } else {

                    //当前值等于头上的值+头上左边的值
                    arrays[i][j] = arrays[i - 1][j] + arrays[i - 1][j - 1];
                }

            }
        }

        System.out.println("公众号:Java3y" + "-------------------------------");

        for (int[] array : arrays) {
            for (int value : array) {
                System.out.print(value + "\t");
            }
            System.out.println();

        }


        System.out.println("公众号:Java3y" + "-------------------------------");


    }

результат:

6. Проблема обезьян, едящих персики

Обезьяна сорвала n персиков, в тот же день съела больше половины персиков, а на следующий день съела больше половины оставшихся персиков, на десятый день остался только 1 персик. В: Сколько персиков сорвала обезьяна в первый день?

Идеи:

  • Предположим, что в этот день есть n персиков, это половина персиков предыдущего дня и на один меньше,f(n - 1) = f(n)/2 - 1,
  • Мы можем вычислить количество персиков в этот день: по рекурсивной формуле:f(n) = 2 * f(n - 1) + 2

Это можно решить как с помощью рекурсии, так и с помощью цикла:

Рекурсивный способ:


    /**
     * 猴子吃桃问题
     * @param x 天数
     */
    public static int monkeyQue(int x) {

        if (x <= 0) {
            return 0;

        } else if (x == 1) {
            return 1;

        } else {
            return 2 * monkeyQue(x - 1) + 2;
        }

    }

Циклический путь:


        int x = 1;
        for (int i = 1; i <= 9; i++) {
            x = (x + 1) * 2;
		}

результат:

Семь, посчитай количество слов

Введите абзац символов и подсчитайте количество слов в нем.Слова разделены пробелами, а пробел разделен для обозначения слова.

Идеи:

  • Пройдите символы один раз и накопите количество раз, когда строка пробела преобразуется в строку без пробела, а количество раз равно количеству слов.
  • Определите значок переменной флага, 0 представляет состояние пробела, 1 представляет состояние без пробела

    /**
     * 输入一段字符,计算出里面单词的个数
     *
     * @param str 一段文字
     */
    public static int countWord(String str) {


        // 0 表示空格状态,1 表示非空格状态
        int flag = 0;

        // 单词次数
        int num = 0;


        for (int i = 0; i < str.length(); i++) {

            if (String.valueOf(str.charAt(i)).equals(" ") ) {
                flag = 0;
            } else if (flag == 0) {
                num++;
                flag = 1;
            }

        }

        return num ;

    }

результат:

Восемь, рассудите, точно ли буква такая же

Имея две строки s и t, определите, совпадают ли буквы в этих двух строках (порядок может быть другим).

Идеи:

  • Перебрать две строки, вычитая каждый символ'a', сохраните их в массиве соответственно, а затем проверьте, равны ли два массива

Ключевые моменты:

  • 'c'-'a'=2Место хранения можно рассчитать, если их больше одного, то можно использовать +1.Давайте сравним размеры массивов позже

Код:




    /**
     * 给定两个字符串s和t,判断这两个字符串中的字母是不是完全一样(顺序可以不一样) 
     */
    public static void isAnagram() {

        //分别存储字符串的字符
        char[] array1 = new char[26];
        char[] array2 = new char[26];


        String s1 = "pleasefollowthewechatpublicnumber";
        String s2 = "pleowcnumberthewechatpubliasefoll";


        for (int i = 0; i < s1.length(); i++) {
            char value = s1.charAt(i);

            // 算出要存储的位置
            int index = value - 'a';

            array1[index]++;
        }

        for (int i = 0; i < s2.length(); i++) {
            char value = s2.charAt(i);

            // 算出要存储的位置
            int index = value - 'a';

            array2[index]++;
        }

        for (int i = 0; i < 26; i++) {
            if (array1[i] != array2[i]) {
                System.out.println("不相同");
                return;
            }
        }

        System.out.println("相同");

    }

результат:

Девять, определите, является ли число степенью двойки

Определить, является ли число степенью двойки

Идеи:

  • Разделите 2 и возьмите остаток до тех пор, пока остаток не будет равен 0 [для случая, кратного 2], и посмотрите, равен ли он 1, чтобы определить, является ли он степенью 2.

    /**
     * 判断是否是2的某次方
     */
    public static void isPowerOfTwo() {

        int num = 3;

        if (num == 0) {
            System.out.println("不是");
        }

        while (num % 2 == 0) {
            num = num / 2;
        }

        if (num == 1) {
            System.out.println("是");
        } else {
            System.out.println("不是");

        }

    }

результат:

Есть еще одно решение этой проблемы, которое представляет собой побитовую операцию:

  • 2 в энной степени имеет характеристику, двоичный код равен 1000000
  • Если **2 в энной степени двоичного числа -1 и 2 в энной степени двоичного числа выполняют побитовую операцию И, то результат должен быть 0**

	if(num <= 0){
        System.out.println("不是");
    }
    else if(num == 1){
        System.out.println("是");
    }
    else{
        if( (num & (num-1) ) == 0){
            System.out.println("是");
        }
        else{
            System.out.println("不是");
        }
    }

10. Определите, является ли число уродливым числом

Определите, является ли число уродливым числом (разложенные простые множители - это только 3 числа 2, 3 и 5)

Идеи:

  • Если оно состоит из 2,3,5, то число непрерывно делится на 2,3,5, и конечным результатом будет 1, состоящее исключительно из 2,3,5.
    • Это та же идея, что и раньше, чтобы определить, является ли число степенью 2~.

Код:


    /**
     * 判断一个数字是不是ugly number(分解出来的质因数只有2、3、5这3个数字)
     * @param num
     */
    public static void isUgly(int num) {
        if (num <= 0) {
            System.out.println("不是");
        } else {
            while (num % 2 == 0) {
                num = num / 2;
            }
            while (num % 3 == 0) {
                num = num / 3;
            }
            while (num % 5 == 0) {
                num = num / 5;
            }
            if (num == 1) {
                System.out.println("是");

            } else {
                System.out.println("是");

            }
        }
    }

результат:

Суммировать

Правильно, вы правильно прочитали, простой маленький алгоритм также должен быть обобщен!

На самом деле, я думаю, что эти относительно простые алгоритмы имеют "подпрограммы", о которых можно говорить. Если вы знаете их подпрограммы, вы можете легко их придумать. Если вы не знаете их подпрограмм, то вы, вероятно, не будете этого делать (нет идеи).

Накопив некую «рутину», мы можемОпытЧтобы сделать вывод, попробуйте выяснить, как решить задачу алгоритма.

Возьмем очень простой пример:

  • Умножение основано на сложении, так как же научиться умножению? **Назад (накопление)** вышло,9*9Кто никогда не запоминал таблицу умножения? например, видеть2+2+2+2+2, После изучения умножения (рутины), кто будет складывать его медленно. Когда вы видите 5 двоек, вы можете получить их напрямую2*5охватывать

  1. 1-nсумма факториалов
    • Чтобы найти факториал n, используйте1*2*3*4*...n, на самом деле циклический процесс, просто установите переменную суммы для суммирования!
  2. получить двумерный массивкаждый столбецминимальное значение
    • Внешний цикл контролирует количество столбцов, а внутренний цикл контролирует количество строк., вот как перебирать каждый столбец~
  3. Найдите значение «1!+4!(2 в квадрате)+9!(3 в квадрате)+...+n
    • Сначала найдите квадрат, затем факториал и, наконец, установите переменную суммы
  4. сумма диагональных элементов массива
    • Позиции строки и столбца равны, то есть элементы на диагонали
  5. Распечатайте треугольник Ян Хуэй
    • Узнайте закон треугольника Ян Хуэя: элементы в первой строке, первом столбце и значение столбца, равное значению строки, равны 1, а остальные — это значение в заголовке плюс значение в левой части заголовка.
  6. обезьяна ест персик проблема
    • По условиям мы можем вычислить персики предыдущего дня, а потом запустить персики дня (правило). обезьяныравное условие(осталось больше половины персика), так что надо думатьцикл или рекурсия
  7. посчитать количество слов
    • Используя правило, что между каждым словом есть пробел, используйте переменную, чтобы запомнить этоСостояние (буква и пробел) переход, вы можете посчитать количество слов!
  8. Определить, совпадают ли буквы
    • Загрузите каждую букву в массив отдельно,'c-a'этописьмоcсуществуетположение массива(то есть 2). Поскольку количество вхождений букв не уникально, мысравнивает значения массива(Если это происходит дважды, значение равно 2, а если оно встречается 3 раза, значение равно 3). Пока значения, используемые для загрузки двух массивов, совпадают, буквы одинаковы!
  9. Определить, является ли число степенью двойки
    • Лучшее решение: степень двойки имеет характеристику в двоичном виде: 10000 (n 0s) --->ps: целое число программиста ~...... Тогда на единицу меньше этого числа Двоичный код определенно 01111, они делают&операции, то он должен быть равен 0. Используя эту функцию, очень хорошо судить, является ли число степенью двойки.
    • Подсхема: число степени двойки продолжает уменьшаться (покаnumber % 2 == 0каждый раз можно уменьшатьnumber / 2),ПоследнийЧастное должно быть 1.
  10. Определить, является ли число уродливым числом
    • Разложенные простые множители — это только 3 числа, 2, 3 и 5. Этот вопрос на самом деле является усовершенствованной версией решения о том, является ли число степенью двойки. продолжайте уменьшать это число (покаnumber%2||%3||%5==0,Каждыйnumber / 2 | / 3 /5),ПоследнийЧастное должно быть 1.

Если в статье есть какие-либо ошибки, пожалуйста, поправьте меня, и мы сможем общаться друг с другом. Учащиеся, привыкшие читать технические статьи в WeChat и желающие получить больше ресурсов по Java, могутОбратите внимание на публичный аккаунт WeChat: Java3y