Hello everyone, I am Han Cao 😈, a grass code ape πŸ’. Intermittent warm blood πŸ”₯, continuous sand sculpture 🌟 if you like my article, you can follow βž• to like it, and grow with me ~ add my wechat: Hancao97, invite you to join the group, learn to communicate with the front end, become a better engineer ~

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

preface

Hi everyone, it’s been a long time since I gave you a full job πŸ”₯. Today at noon, someone in my early sleep group posted this screenshot:

People were laughing, and I thought it was funny, and the screenshot gave me a lot of inspiration. Why don’t I write a copy of the code for the whole job?

When something is in doubt, make it work

But this code is so long, and I’m such a lazy person, that I don’t know how to write this code, so I need to do it in the simplest way possible, dynamically generating 88 W lines of code.

Code implementation

Before we get to the code implementation, let me list the requirements:

Given a positive integer with no more than 5 digits:

  • Figure out what number of digits it is
  • Output each digit separately
  • Print each number in reverse order, for example, the old number 12345, the new number 54321

The main idea is to use node FS related API to complete file writing.

const { writeFileSync } = require('fs');
const { join } = require('path');

const generateFunction = () = > {
  let currentNum = 0;
  let str = ' ';
  while( currentNum < 100000) {
    const stringCurrentNum = String(currentNum);
    const numArr = stringCurrentNum.split(' ').reverse();
    const unitList = ['δΈͺ'.'ten'.'best'.'千'.'δΈ‡']
    str += `    case ${currentNum}: \n`
    str += ` console. The log (' is${stringCurrentNum.length}Digits'); \n`;
    numArr.forEach((char, index) = > {
      str += `      console.log('${unitList[index]}Digits are:${char}')\n`;
    })
    str += 'console.log(' reversed:The ${Number(numArr.join(' '))}'); \n`;
    str += ` break; \n`;
    currentNum ++;
  }
  writeFileSync(join(__dirname, 'func.js'), `
  function handleNumber(num) {
    switch (num) {
      ${str}
    }
  }`, {
    encoding: 'utf-8'
  })
}

generateFunction();
Copy the code

Notice that the 0 at the beginning after the inversion oh, I just changed it to Number ~

Then you can have a look at the content of the file I generated:

88 w lines of code, exhaustive method, eternal God!

888897 lines of code to be exact.

Then let’s look at the results:

No problem!

Analysis of algorithm thought

I understand the algorithm is insufficient, if there is a mistake, but also please give advice ✨

So writing this content can not just be a big smile, I also want to share with you my thinking, and extend more things for you. First of all, you may think that the exhaustive method is LOW, so LET me give you an example:

Liu Cixin’s Poem Clouds discusses the relationship between absolute technology and human art through the dialogue between human poets and the advanced civilization of the universe. Higher civilization tries to prove that technology trumps art by writing better poetry than Li Bai, but he cannot write poetry like Li Bai, whether he drinks wine like Li Bai or wears Li Bai’s clothes. At last he thoughtBrute forceThrough quantum storage, he made all possible permutations of human Characters, including all possible poems.

The exhaustive method has always been useful (after all, it is used by advanced civilizations above) and is widely used (e.g. : ) in computing, a lot of problems for the exhaustive method is extremely good or the best means, such as string matching, is to start from scratch to iterate through all possible results, even familiar KMP algorithm is nothing but go through before the match situation sieve impossible as a result, no more than is processed more advanced exhaustion.

Since speaking of exhaustive method, the chapter of the cold grass 🌿 and you simply talk about several algorithm ideas, is also an extension of this problem.

Reference for this chapter:

  • 8 common algorithm ideas programmers must know
  • Figure out eight commonly used algorithm ideas!

Exhaustive method

The first and easiest idea to understand is the idea of enumeration, also known as enumeration. Exhaustive enumeration, as the name implies, is exhaustive enumeration. The application of exhaustive enumeration is very wide and easy to understand. To put it simply, enumeration is to list the possible solutions of a problem, and then bring them into the problem test one by one, so as to obtain from a series of possible solutions.

The way is simple, using enumeration method can well avoid the redundancy brought by system complexity, and may also reduce the space to a certain extent.

The optimization exhaustive method has two schemes:

  • One is the simplification of the problem, as far as possible to deal with the problem of model structure simplification. This reduction can be embodied in the number of variables in the problem, reducing the number of variables and thus radically reducing the combination of “possible solutions”.
  • Second, strictly judge the scope and conditions of screening “possible solutions” and eliminate most invalid “possible solutions” as much as possible.

Take an example, emmmm, forget it, like the example above, or find a prime number between 1 and 100.

The recursive method

Compared with the idea of enumeration algorithm, recursive algorithm can get the intermediate inference through a known condition, using a specific relationship, and then gradually recurse until the result is obtained. Thus, recursive algorithms are smarter than enumeration algorithms in that they do not try every possible solution.

Recursive algorithms can constantly use existing information to derive new things. In daily application, there are two recursive algorithms as follows.

  • Sequential method: starting from known conditions, gradually calculate the method to solve the problem. The Fibonacci sequence, for example, can be recurred to new data by successive deduction.
  • Inverse method: starting from the known results, using iterative expressions to gradually calculate the conditions of the beginning of the problem, that is, the inverse process of the inverse method.

And a good way to understand recursion is to prove it mathematically:

  1. Because the angles of a triangle add up to 180 degrees, and two of them are 65 degrees and 70 degrees.
  2. So the third Angle is 45 degrees.
  3. Because the straight Angle is 180 degrees.
  4. So the outside of this Angle is 135 degrees.

Finally, for example, a pair of big rabbits can give birth to a pair of little rabbits every month, and each pair of newborn little rabbits can grow into a pair of big rabbits after a month, with reproductive ability, if there is no death, and give birth to a female and a male each time, how many pairs of rabbits will there be in a year?

The recursive method

Recursive algorithm is to transform the problem into smaller sub-problems of the same kind, solve the sub-problems first, and then gradually solve the higher level problems through the same solving process, and finally obtain the final solution. Therefore, compared with recursion, recursion algorithm has a smaller category and requires the same structure of the subproblem and the parent problem. Recursion has no such constraints conceptually.

In a word to describe the implementation of recursive algorithm, is in the function or sub-process of the internal, directly or indirectly call their own algorithm. Therefore, in the process of implementation, the most important thing is to determine the termination condition of the recursive process, that is, the conditional judgment of the iterative process. Otherwise, the program loops endlessly in its own invocation.

An example is the classic Hannotta problem. According to an Indian legend, When Mahama created the world, he built three pillars of steel and stone, one of which was stacked with 64 gold disks from bottom to top. Mahama ordered the Brahmin to rearrange the disks on another pillar, starting from below, in order of size. It is also stipulated that the disk cannot be enlarged on the small disk and that only one disk can be moved at a time between the three columns.

Divide and conquer method

The divide-and-conquer algorithm divides a problem of size N into K smaller sub-problems, which are independent of each other and have the same properties as the original problem. The solution of the original problem can be obtained only by solving the subproblem.

In the process of programming, we often encounter many problems such as processing too much data, solving process is complicated, and direct solving method is time-consuming. In solving this kind of problem, we can adopt the divide-and-conquer method.

The specific approach is: first decompose this problem into several smaller sub-problems, find out the solution of these sub-problems, and then find the appropriate method, combine them into the solution of the whole big problem. If these subproblems are still large, you can continue to divide them into smaller subproblems, and so on, until you can directly solve them. That’s the basic idea of divide-and-conquer.

The general steps for solving a problem using a divide-and-conquer algorithm are as follows.

  • Decompose: The problem to be solved is divided into several similar problems of smaller scale.
  • Solve, when the subproblem is divided enough small, with a simpler method to solve.
  • Merge, according to the requirements of the original problem, the solution of the sub-problem layer by layer merge to form the solution of the original problem.

So, for example, merge sort

Greedy algorithm

Greedy algorithms, also known as greedy algorithms, tend to solve problems using what seems to be the best method at the moment. The idea of this algorithm does not consider the problem from the global optimal, but only in a sense of local optimal solution.

Although greedy algorithm cannot get the whole optimal solution of all problems, it can produce the whole optimal solution or the approximate solution of the whole optimal solution when facing a wide range of problems. It can be seen that greedy algorithms only pursue the optimum within a certain range, which can be called “gentle greed”.

Greedy algorithm starts from an initial solution of the problem and approaches the given target step by step in order to find a better solution as soon as possible. When a certain step in the algorithm is reached and no further progress can be made, the algorithm is stopped and an approximate solution is given. From the characteristics and ideas of greedy algorithm, it can be seen that greedy algorithm has the following three problems.

  • There is no guarantee that the final solution will be optimal.
  • Can’t be used to find the maximum or minimum solution problem.
  • Only the range of feasible solutions satisfying certain constraints can be found.

The basic idea of greedy algorithms is as follows.

  • Build a mathematical model to describe the problem.
  • Divide the problem into subproblems.
  • The local optimal solution of each subproblem is obtained by solving each subproblem.
  • The local optimal solution of the subproblem is combined into a solution of the original solution problem.

There are many classic examples of greedy algorithms, such as the backpack problem, the sales problem.

heuristics

Heuristics, also known as backtracking, enumerate and test candidate solutions one by one in a certain order. When it is found that the current candidate solution cannot be the correct one, the next candidate solution is chosen.

If the current candidate can satisfy all other requirements except the unsatisfied problem size requirement, the scale of the current candidate solution will continue to be expanded and the trial will continue. The current candidate is a solution to the problem if it satisfies all the requirements, including the problem size. In heuristic algorithms, the process of abandoning the current candidate solution and continuing to search for the next candidate solution is called backtracking. The process of increasing the size of the current candidate solution and continuing to test it is called forward testing.

The basic steps for solving a problem using a heuristic algorithm are shown below.

  • For the given problem, the solution space of the problem is defined.
  • Determine the easily searchable solution space structure.
  • The solution space is searched depth-first, and the pruning function is used to avoid invalid search.

In order to find the correct solution to a problem, heuristic method will first gently test a certain possible situation. In the process of testing, once it is found that the hypothesis of the original choice is incorrect, it will immediately consciously take a step back and choose again, and then continue to test, and so on and so on, until it gets a solution or proves that there is no solution.

Take the classic example, the eight Queens problem. In 8 Γ— 8 squares chess placed 8 queens, so that they can not attack each other, that is, any two queens can not be in the same row, the same column or the same diagonal line, find the pendulum method.

Dynamic programming

Can go to take a look at this question and answer: www.zhihu.com/question/23…

This section would like to add some of their own experience and coding practice, in a while to make up ~

Simulation method

In many real scenarios, due to the large scale of the problem, too many variables and other factors, it is difficult to abstract the specific problem, so it is impossible to design the algorithm according to the characteristics of the abstract problem. At this point, simulation might be the best strategy.

The process of simulation is to simulate the real scene as much as possible, and then predict the results through the powerful computing power of the computer. This is a much bigger idea than the algorithm above. In the simulation of real scene, the realization of system components may need the participation of the above algorithm ideas.

Simulation is a very magical idea, there is no specific implementation ideas, there is no specific optimization strategy. Let’s just say it’s a case by case.

Practice of simulation method — Finding PI

For example, if I find PI, I can convert it to a probability problem: the probability of a random dot landing in a sector.

So I started coding:

let i = 0;
let num = 0;
const sum = 100000000;
while(i < sum) {
    i ++;
    const x = Math.random();
    const y = Math.random();
    if(x * x + y * y < 1) { num++; }}console.log(4 * num / sum);
Copy the code

I ran the simulation 100,000,000 times, and the results are as follows:

conclusion

Reference:

  • 8 common algorithm ideas programmers must know
  • Figure out eight commonly used algorithm ideas!

This article is inspired by that picture, hahaha, the whole thing was fun ✨.

There are plans not to complete the work recently, plans to re-learn the front end, the content and order of the article according to the previous “30 days to organize | 2W word long” with an article to clear the front end learning route and build a knowledge system 🌿, may I start the review will not be HTML and CSS, but some general skills, please keep looking forward to.

If you like my article, like it and follow it is the biggest encouragement. You can also add my friend: Hancao97 to have in-depth communication with me

Write in the last

I also want to

Can light you up

Leave sunshine in your life

Accompany you through the mountains and long water

Grow with you β˜€οΈ