Author: Xiao Fu Ge blog: https://bugstack.cn

Precipitation, share, grow, let oneself and others can harvest! 😄

One, foreword

How close is math to programmers?

Whether it’s an Ifelse or a for loop, code is a concrete implementation of mathematical logic. So the programmer who writes code is almost inseparable from math, with varying degrees of difficulty.

That math is bad can’t write code 😳? No, you can also write code, you can write more CRUD out. Don’t always think that because the product requirements are simple, your implementation process becomes “add, delete, change and check”. It is often because you do not have the ability to implement scalable, easy to maintain, high-performance code implementation solutions, that you write more CRUD at a young age!

Dachang and Super Dachang are more likely to focus on mathematical skills than small, one-wall-operated factories.

In 2004, a huge billboard popped up on Silicon Valley’s traffic artery, Route 101, with a mathematical problem: {the first 10 primes in a sequence of E numbers}. Com.

AD: The e here is the mathematical constant, the base of the natural logarithm, an infinite non-repeating decimal. Find the first 10 prime digits in E, and you’ll get a website address. Once you’ve unlocked it, Google will tell you that we might be “like-minded” people. You can send your resume to this email address and we’ll do something to change the world.

The calculation of e value can be derived from Taylor’s formula: e^x≈1 + x + x^2/2! + x^3/3! +… + x^n/n! (1) The derivation calculation process also includesSieve of Eratosthenes,Linear screeningThe use of. Interested partners can use the code to achieve the next.

Two, programming exercises

1. Fibonacci series

@Test public void test_Fibonacci() { int month = 15; // 15 months long f1 = 1L, f2 = 1L; long f; for (int i = 3; i < month; i++) { f = f2; f2 = f1 + f2; f1 = f; Println (number of rabbits in month "+ I +" : "+ f2"); }}
  • Difficulty: ⭐ ⭐ ⭐ ⭐ ⭐
  • Title: have a pair of rabbits, since the 3rd month after birth every month gives birth to a pair of rabbits, a pair of rabbits are born again every month after small rabbits grow the 3rd month, if rabbits are deathless, how many is the total number of rabbits asking every month?
  • Logic: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
  • Extensibility: The Fibonacci sequence, also known as the Golden Section sequence, introduced by the mathematician Leonardoda Fibonacci as an example of rabbit reproduction, refers to a sequence of numbers: One, one, one, two, three, five, eight, thirteen, twenty-one, thirty-four… In mathematics, the Fibonacci sequence is defined recursively as follows: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n ≥ 2, n ∈ N*), the Fibonacci sequence has direct applications in modern physics, quasicrystalline structure, chemistry and other fields. For this reason, Since 1963, the American Mathematical Society has published a mathematical journal under the name of the Fibonacci Quarterly for the purpose of publishing the results of this research.

2. Identify prime numbers

@Test public void test_Prime() { int count = 0; for (int i = 101; i < 200; i++) { boolean b = true; // For (int j = 2; j <= Math.sqrt(i); j++) { if (i % j == 0) { b = false; // This number is not prime break; } } if (b) { count++; System.out.print(i + " "); }} System.out.println("\n number of primes: "+ count); }
  • Difficulty: ⭐ ⭐ ⭐
  • How many primes are there between 101 and 200? Print all the primes.
  • Logic: A method of judging a prime number by dividing 2 by SQRT (the number). If the number is divisible, it is not a prime number and is prime instead.
  • Primes are also called prime numbers. The number of prime numbers is infinite. There is a classical proof in Euclid’s Geometry Original. It uses the usual method of proof: proof by contradiction. The concrete proof is as follows: Suppose there are only a finite number of primes, in descending order P1, P2… , pn, let N=p1×p2×…… Times pn, then, is prime or not prime.

3. Number of daffodils

@Test public void test_narcissus() { for (int num = 101; num < 1000; num++) { int bbb = num / 100; int bb = (num % 100) / 10; int b = (num % 100) % 10; if ((bbb * bbb * bbb + bb * bb * bb + b * b * b) == num) { System.out.println(num); }}}
  • Difficulty: ⭐ ⭐ ⭐ ⭐
  • Title: Print out all the “Narcissus Number”. A “Narcissus Number” is a three-digit number whose cube sum is equal to the number itself. For example, 153 is a “number of daffodils” because 153=1 to the third +5 to the third +3 to the third.
  • Logic: Use for loop to control 100-999 numbers, each number is decomposable into ones, tens, and hundreds.
  • Extension: The number of narcissus is also called pluperfect digital invariant (PPDI), Narcissistic number, self-exponent number, Armstrong number, or Armstrong number. A daffodil number is a three-digit number in which the sum of the third power of the digits in each bit is equal to itself (e.g. 1^3 + 5^3+ 3^3 = 153).

4. Decompose prime factors

@Test public void test_ZhiYinShu() { f(200); } int k = 2; public void f(int n) { while (k <= n) { if (k == n) { System.out.println(n); break; } else if (n > k && n % k == System.out.print(k + "*") n = n / k; f(n); break; } else if (n > k && n % k ! = k++; f(n); break; }}}
  • Difficulty: ⭐ ⭐ ⭐ ⭐
  • The title: Decompose a positive integer into prime factors. For example, type 90 and print out 90=233 * 5.
  • Logic: To decompose prime factors of N, we should first find a minimum prime number k, and then follow this step to complete (1) If this prime number is exactly equal to N, then the process of decompose prime factors has been finished. Print it out. (2) If n>k, but n is divisible by k, then the value of k should be printed out, and n divided by the quotient of k as the new positive integer you n, repeat the first step. (3) If n is not divisible by k, then use k+1 as the value of k and repeat the first step.
  • Extensions: every composite number can be written in the form of the multiplication of several prime numbers, where each prime number is a factor of the composite number, a composite number in the form of prime factor multiplication, called the decomposition of prime factors. Such as 30 = 2 x 3 x 5. The decomposition of prime factors is only for composite numbers.

5. Yanghui Triangle

@Test public void test_YangHuiSanJiao(){ int[][] a = new int[10][10]; for (int i = 0; i < 10; i++) { a[i][i] = 1; a[i][0] = 1; } for (int i = 2; i < 10; i++) { for (int j = 1; j < i; j++) { a[i][j] = a[i - 1][j - 1] + a[i - 1][j]; } } for (int i = 0; i < 10; i++) { for (int k = 0; k < 2 * (10 - i) - 1; k++) { System.out.print(" "); } for (int j = 0; j <= i; j++) { System.out.print(a[i][j] + " "); } System.out.println(); }}
  • Difficulty: ⭐ ⭐ ⭐ ⭐
  • Title: Print out Yang Hui Triangle
  • Logic: Yang Hui triangle properties: each line of numbers is symmetrical, from 1 gradually become larger, then smaller, back to 1. The number of numbers in the NTH row is n. The NTH row sum is 2 to the n minus 1. Each number is equal to the sum of the left and right digits of the previous row. This property can be used to write the entire Yang Hui triangle. In the NTH row, the first number is 1, the second number is 1×(n-1), the third number is 1×(n-1)× (n-2) /2, and the fourth number is 1×(n-1)× (n-2) /2× (n-3) /3… And so on.
  • Yang Hui triangle is a geometric arrangement of binomial coefficients in triangles. It appears in Yang Hui, a Chinese mathematician in the Southern Song Dynasty (1261), who wrote a book called Jiuzhang Algorithm in detail. In Europe, Pasca (1623—-1662) discovered this rule in 1654, so the table is also called Pascal’s Triangles. Pascal’s discovery was 393 years later than that of Yang Hui and 600 years later than that of Jia Xian.

Find the greatest common divisor and the least common multiple

@Test public void test_Prime() { int a = 10, b = 24; int m = division(a, b); int n = a * b / m; System.out.println(" greatest common divisor: "+ m); System.out.println(" Least Common Multiple: "+ n); } public int division(int x, int y) { int t; if (x < y) { t = x; x = y; y = t; } while (y ! = 0) { if (x == y) return 1; else { int k = x % y; x = y; y = k; } } return x; }
  • Difficulty: ⭐ ⭐ ⭐
  • Problem: Find the greatest common divisor and least common multiple of two positive integers m and n.
  • Logic: in a loop, as long as the divisor is not equal to zero, in large Numbers, divided by the number of small, small, large Numbers of a number as the next round of circulation in the remainder of the next round of cycle number of smaller, so the cycle until the number of smaller value is 0, return the larger number, this number is the least common divisor and least common multiple of product divided by the least common multiple of two Numbers.
  • Extensions: the greatest common factor, also known as the greatest common divisor, the greatest common factor, refers to two or more integers share the greatest of the divisors. The greatest common divisor of a, b is denoted by (a, b). Similarly, the greatest common divisor of a, b, and c is denoted by (a, b, c). The greatest common divisor of multiple integers has the same notation. There are many ways to find the greatest common divisor, the common prime factorization method, short division, and more phase subtraction method. The concept corresponding to the greatest common divisor is the least common multiple, where the least common multiple of a and b is denoted as [a, b]. The common multiple of two or more integers is called their common multiple, and the smallest common multiple other than 0 is called the least common multiple of the integers. The least common multiple of the integers a, b is written as [a, b]. Similarly, the least common multiple of a, b, and c is written as [a, b, c]. The least common multiple of multiple integers has the same notation.

7. Perfect squares

@Test public void test_PerfectSquare() { for (long l = 1L; l < 100000; L ++) {if (Math.sqrt((l + 100)) % 1 == 0) {if (Math.sqrt((l + 100)) % 1 == 0) {System.out.println(l + "+ 100 is a perfect square, Plus 168 is another perfect square "); }}}}
  • Difficulty: ⭐ ⭐ ⭐ ⭐
  • An integer that adds 100 to a perfect square, and 168 to a perfect square. What is that number?
  • Logic: within 100,000, first add 100 to the number before taking the square root, and then add 268 to the number before taking the square root. If the result after taking the square root meets the following conditions, it is the result.
  • extension: perfect square means to multiply yourself by an integer such as 11, 2,2,3 *3, and so on. If a number can be represented as the square of an integer, it is said to be a perfect square. Perfect squares are non-negative numbers, and a perfect square has two terms. Be careful not to confuse this with perfectly flat mode.

8. Sum the main diagonals

@Test public void test_Sum() { Scanner s = new Scanner(System.in); int[][] a = new int[3][3]; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { a[i][j] = s.nextInt(); }} System.out.println(" The input 3 * 3 matrix is :"); for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { System.out.print(a[i][j] + " "); } System.out.println(); } int sum = 0; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (i == j) { sum += a[i][j]; }} System.out.println(" sum "+ sum); }
  • Difficulty: ⭐ ⭐ ⭐
  • Find the sum of the diagonal elements of a 3 by 3 matrix
  • Logic: Use double for loop to control input two-dimensional array, and then add AI to output.
  • Expansion: In an n-order square matrix (or determinant), the diagonal of the n elements in the diagonal direction from the upper left to the lower right corner is called the main diagonal of the n-order square matrix (or determinant).

9. Complete the solution

@test public void test_solution() {System.out.println("1 to 1000 "); for (int i = 1; i < 1000; i++) { int t = 0; for (int j = 1; j <= i / 2; j++) { if (i % j == 0) { t = t + j; } } if (t == i) { System.out.print(i + " "); }}}
  • Difficulty: ⭐ ⭐ ⭐ ⭐
  • Title: A number that is exactly equal to the sum of its factors is said to be “complete”. For example, 6=1+2+3. Program to find all completions up to 1000
  • Logic: If p is prime and 2^p-1 is prime, then (2^p-1) X2^ (p-1) is a perfect number.
  • Extensions: Perfect numbers, also known as Perfect numbers or complete numbers, are some special natural numbers. The sum of all its true factors (that is, the divisors other than itself) (that is, the factor function) is exactly equal to itself.

S = a + 10. O aa + aaa + aaaa + aa… The value of a

@Test
public void test_asum() {
    long a = 2, b = 0;
    Scanner s = new Scanner(System.in);
    int n = s.nextInt();
    int i = 0;
    long sum = 0;
    while (i < n) {
        b = b + a;
        sum = sum + b;
        a = a * 10;
        ++i;
    }
    System.out.println("input number: " + n);
    System.out.println(sum);
}
  • Difficulty: ⭐ ⭐ ⭐
  • S = A + AA + AAA + AAAA + AA… The value of a, where a is a number. For example, 2+22+222+2222+22222(at this time, there are 5 numbers added), several numbers added with keyboard control.
  • Logic: Define a variable b with an initial value of 0; Define a variable sum, and assign the initial value to 0. After entering the loop, assign the value of a + b to b, and assign the value of sum + b to sum. At the same time, increase a by ten times, ++ I; Continue the cycle; At the end of the loop, the value of sum is printed.

11. No duplicate three-digit numbers

@Test public void test_AC() { int count = 0; for (int x = 1; x < 5; x++) { for (int y = 1; y < 5; y++) { for (int z = 1; z < 5; z++) { if (x ! = y && y ! = z && x ! = z) { count++; System.out.print(x * 100 + y * 10 + z + " "); if (count % 4 == 0) { System.out.println(); }}}}} System. Out. Println (" common "+ count +" of "a three digits). }
  • Difficulty: ⭐ ⭐ ⭐ ⭐
  • Question: How many different three-digit numbers can be composed with 1, 2, 3, and 4 digits? What are they?
  • Logic: The numbers that can be filled in the hundreds, tens and ones place are all 1, 2, 3, 4. Make up all the permutations and then get rid of the ones that don’t satisfy your condition.

12. Output sequence from small to large

public class SmallToBig { public static void main(String[] args) { SmallToBig fnc = new SmallToBig(); int a, b, c; System.out.println("Input 3 numbers:"); a = fnc.input(); b = fnc.input(); c = fnc.input(); if (a > b) { int t = a; a = b; b = t; } if (a > c) { int t = a; a = c; c = t; } if (b > c) { int t = b; b = c; c = t; } System.out.println(a + " " + b + " " + c); } public int input() { int value = 0; Scanner s = new Scanner(System.in); value = s.nextInt(); return value; } public void compare(int x, int y) {if (x > y) {int t = x; x = y; y = t; }}}
  • Difficulty: ⭐ ⭐
  • Question: input three integers x,y,z. Please output the three integers from the smallest to the largest
  • Logic: Put the smallest number on x, first compare x with y, then compare x with y, then compare x with z, then compare x with z, then exchange the value of x with z, so as to minimize x.

13. The problem of monkeys eating peaches

public class Monkey { public static void main(String[] args) { int lastdayNum = 1; for (int i = 2; i <= 10; i++) { lastdayNum = (lastdayNum + 1) * 2; } system.out. println(" The monkey picked the first day "+ lastdayNum +" peach "); }}
  • Difficulty: ⭐ ⭐ ⭐ ⭐
  • The first day the monkey picked a number of peaches, immediately eat half, not addicted, and eat a more the next morning will be left to eat half of the peaches, and eat one more. From then on, I ate half and one of the leftovers of the day before every morning. To the morning of the 10th day want to eat again, see only a peach. Let’s figure out how many we picked on the first day.
  • Logic: Take a backward thinking approach and extrapolate from back to front.

A table tennis match

public class Compete { static char[] m = { 'a', 'b', 'c' }; static char[] n = { 'x', 'y', 'z' }; public static void main(String[] args) { for (int i = 0; i < m.length; i++) { for (int j = 0; j < n.length; j++) { if (m[i] == 'a' && n[j] == 'x') { continue; } else if (m[i] == 'a' && n[j] == 'y') { continue; } else if ((m[i] == 'c' && n[j] == 'x') || (m[i] == 'c' && n[j] == 'z')) { continue; } else if ((m[i] == 'b' && n[j] == 'z') || (m[i] == 'b' && n[j] == 'y')) { continue; } else System.out.println(m[i] + " vs " + n[j]); }}}}
  • Difficulty: ⭐ ⭐ ⭐ ⭐
  • Title: Two ping-pong teams are playing, each with three players. Team A has three A, B and C, and Team B has three X, Y and Z. A lot has been drawn to decide the list of players. Someone asked the team for the name list for the match. A says he is not compared to X, C says he is not compared to X, Z, please program to find the names of three teams of players.

Add up the fractions

public class FenShu { public static void main(String[] args) { int x = 2, y = 1, t; double sum = 0; DecimalFormat df = new DecimalFormat("#0.0000"); for (int i = 1; i <= 20; i++) { sum += (double) x / y; t = y; y = x; x = y + t; Println (" + df. Format (sum) "); }}}
  • Difficulty: ⭐ ⭐ ⭐ ⭐
  • There is a sequence of fractions: 2/1, 3/2, 5/3, 8/5, 13/8, 21/13… Find the sum of the first 20 terms of the sequence.
  • Logic: seize the change law of the numerator and denominator.

16. Sum factorial

public class JieCheng { static long sum = 0; static long fac = 0; public static void main(String[] args) { long sum = 0; long fac = 1; for (int i = 1; i <= 10; i++) { fac = fac * i; sum += fac; } System.out.println(sum); }}
  • Difficulty: ⭐ ⭐ ⭐
  • Problem: Find 1+2! + 3! +… + 20! And of the
  • Logic: the accumulation into the tired multiplier
  • Extension: The factorial is a mathematical term invented by Christian Kramp (1760 ~ 1826) in 1808. The factorial of a positive integer is the product of all the positive integers less than or equal to it, and the factorial of 0 is 1. The factorial of the natural number n is written as n! . In 1808, Keyston Karman introduced this notation.

17. Palindromic judgment

public class HuiWen { public static void main(String[] args) { Scanner s = new Scanner(System.in); System.out.print(" Please enter a positive integer: "); long a = s.nextLong(); String ss = Long.toString(a); char[] ch = ss.toCharArray(); boolean is = true; int j = ch.length; for (int i = 0; i < j / 2; i++) { if (ch[i] ! = ch[j - i - 1]) { is = false; } if (is == true) {System.out.println(" This is a palindrome "); } else {System.out.println(" This is not a palindrome "); }}}
  • Difficulty: ⭐ ⭐ ⭐
  • A 5-digit number. Determine if it is a palindrome. That is, 12321 is the palindrome number, the ones place is the same as the ten thousand place, and the ten place is the same as the thousand place.

18. Output the series in order

public class ShunXu { public static void main(String[] args) { Scanner s = new Scanner(System.in); int a = s.nextInt(); int b = s.nextInt(); int c = s.nextInt(); if (a < b) { int t = a; a = b; b = t; } if (a < c) { int t = a; a = c; c = t; } if (b < c) { int t = b; b = c; c = t; } System.out.println(" output in order from largest to smallest :"); System.out.println(a + " " + b + " " + c); }}
  • Difficulty: ⭐ ⭐ ⭐
  • Question: Input three numbers a,b, and c and output them in order of size

19. Position change

public class TiHuan {
    
    static final int N = 8;

    public static void main(String[] args) {

        int[] a = new int[N];
        Scanner s = new Scanner(System.in);
        int index1 = 0, index2 = 0;

        System.out.println("please input numbers");
        for (int i = 0; i < N; i++) {
            a[i] = s.nextInt();
            System.out.print(a[i] + " ");
        }

        int max = a[0], min = a[0];
        for (int i = 0; i < a.length; i++) {
            if (a[i] > max) {
                max = a[i];
                index1 = i;
            }
            if (a[i] < min) {
                min = a[i];
                index2 = i;
            }
        }

        if (index1 != 0) {
            int temp = a[0];
            a[0] = a[index1];
            a[index1] = temp;
        }

        if (index2 != a.length - 1) {
            int temp = a[a.length - 1];
            a[a.length - 1] = a[index2];
            a[index2] = temp;
        }
        System.out.println("after swop:");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }
}
  • Difficulty: ⭐ ⭐
  • Input an array, swap the largest element with the first element, swap the smallest element with the last element, and output an array.

The number of 20.1

long startTime = System.currentTimeMillis(); int num = 10000000, saveNum = 1, countNum = 0, lastNum = 0; int copyNum = num; while (num ! = 0) { lastNum = num % 10; num /= 10; If (lastNum == 0) {if (lastNum == 0) {countNum += num * saveNum; } else if (lastNum == 1) {} else if (lastNum == 1) {} else if (lastNum == 1) { countNum += num * saveNum + copyNum % saveNum + 1; } else {// If it is not 1, it is not 0. =(abc+1)*1+(ab+1)*10+(a+1)*100+(1)*1000... countNum += (num + 1) * saveNum; } saveNum *= 10; } System.out.println(" number of 1: "+ countNum); Println (" Calculate time: "+ (System.currentTimeMillis() -startTime) +" milliseconds ");
  • Difficulty: ⭐ ⭐ ⭐ ⭐
  • The number of occurrences of 1 between 1 and n. For example: 1~10 1 appears twice.
  • logic: We can see that the number of 1 in 100, 1000, 10000 is a regular cycle. 11, 12, 13, 14 or 21, 31, 41, 51, and a single one. Finally, the general formula can be obtained: ABCD… =(abc+1)1+(ab+1)10+(a+1)100 + (1)1000… , ABCD stands for bits. In addition, the implementation process also needs to consider such as less than 100 cases, such as 98, 1232, etc.

Third, depth expansion

Java code is a concrete implementation of mathematical logic based on data structures and algorithms, and if you don’t know the underlying mathematics in the code, you’ll ignore it and therefore won’t understand the source code.

It’s like when I ask you:

  • Have you proven why hashCode uses 31 as a multiplier?
  • What is the function of the perturbation function, and what other scenarios is it in use for?
  • What exactly is zipper addressing and open addressing and how to solve the collision problem?
  • Did you know that the ThreadLocal implementation also uses the golden section?
  • CLH, MCS, how to implement fair locking, what is the code?
  • JVMTI can be used to monitor thread pool state non-intrusively. Have you used it?

So Fu compiled a book, “Java Face Book”, which is a PDF book explaining the core technology of Java with the interview title entrance. The content in the book also tries to prove to you that the code is the concrete implementation of mathematical logic. Why do you say that? When you read through the book, there’s a lot of math involved, including: perturbation functions, load factors, zipper addressing, open addressing, Fibonacci hashing, and the use of the golden section point.

Java surface by manual, data download: https://codechina.csdn.net/MiddlewareDesign/doc/-/issues/8

Four,

  • Programming is one of the most difficult branches of applied mathematics; the poorer mathematicians had better remain pure mathematicians. https://www.cs.utexas.edu/use…
  • Simple math can not write the code, can write code do not understand math can only be CRUD code farmers. Mathematics helps you design data structures and implement algorithmic logic, while coding helps you navigate design patterns and architectural models. The combination and use of various knowledge is the main difference between code farmers and engineers, and is also the key point of having core competitiveness.
  • Learning knowledge sometimes can not see how far ahead of the road, but even if it is a mud pit, as long as you keep wriggling, toss, roll, also can catch a loach.The road of knowledge is to discover the happiness of knowledge, but also learn the sense of achievement of knowledge, constantly prompting you to move forward.

Five, series of recommendations

  • A summary of learning route resources from four years of university to five years of graduate work
  • Two years of work with a resume like that, who wants you!
  • Work 3 years, see what data can monthly salary 30K?
  • What is the experience of a programmer publishing a technical book?
  • Sharing and analysis of Meituan (including solutions)