This is a reading note for Math for Programmers.

0

Counting is simply counting, counting method is the method of counting, strictly speaking, is to take a thing and the thing to count one to one correspondence, as long as not missing and not repeated, then the number is accurate.

In our small, are generally take your fingers to count number from 1 to 10, and then meng, a wiser will add toes, is not enough to do, this is also the problem of our ancestors, fingers enough to use, can use other more things, such as stone, stone total more than the fingers, but more stones are not enough to do.

So the great decimal system was invented. The numbers we use every day, 1,2,3,999,10000, etc., are actually decimal numbers, but they’re not called that, usually when they’re used with binary, octal, etc.

The decimal system is to enter 1 every 10 digits, and advance 1 toward the highest place for every 10 digits. The decimal system uses 0 to 9 digits, representing the ones, tens, hundreds, and thousands…… from right to left The numbers in each position represent the number of values in the digit place. The overall number represents the number of values in each digit place multiplied by the number of digits in the digit place, and finally added up. For example, 2503 represents the sum of two thousand, five hundred, zero ten and three ones, that is, 2503=21000+5100+010+31. 1000, 100, 10, and 1 can be represented by 10^3 (10^3), 10^2, 10^1, and 10^0, respectively, so the decimal digits are 10^n, where n from right to left is 0, 1, 2, 3, and 4….. 10 is called the base or base of the decimal system and n is called the exponent.

Understand the decimal counting method, binary counting method is also very simple, the computer is using binary counting method, why the computer uses binary, because the number of binary counting method is less, the computer structure can be more simple, more easy to express, such as the circuit of the level of the disconnect and so on. The binary system uses only 0 and 1 digits, which represent 1, 2, 4, and 8 digits…… respectively from right to left For example, 1100, which represents the sum of 1 8, 1 4, 0 2 and 0 1, adds up to the corresponding decimal number 12. The digits 8, 4, 2 and 1 can be expressed as 2^3, 2^2, 2^1 and 2^0, respectively. The digits of the binary counting method are in the form of 2^ N, and n from right to left are 0, 1, 2, 3 and 4…. .

The above two counting methods are also known as bitwise counting, in addition, there are commonly used base 8, base 16. The 8-digit system uses eight digits from 0 to 7. The digits from right to left are 8^0, 8^1… . The hexadecimal system is very special, because there are only 0-9 not enough 16 letters, how to do, complement letters: A, B, C, D, E, F, A stands for 10, B stands for 11….. F is for 16. The digits from right to left are 16^0, 16^1… , the commonly used color values #FFFFFF, #F5F5F5 and so on are hexadecimal.

Can be mutual transformation between different counting method, transfer binary decimal has said, in front of the decimal binary is put the decimal number divided by 2, observe every time unless the remainder is 1 or 0, then the rest continue to divided by 2, and finally the remainder reverse arrangement is the corresponding binary, say are abstract, see example:

Such as 12

12/2 is 6, remainder 0 6/2 is 3, remainder 0 3/2 is 1, remainder 1 1/2 is 0, remainder 1Copy the code

Remainder in reverse order: 1100

Such as 99

99/2=49，余1
49/2=24，余1
24/2=12，余0
12/2=6，余0
6/2=3，余0
3/2=1，余1
1/2=0，余1
Copy the code

Remainder in reverse order: 1100011

Isn’t that easy?

The first place is always represented by exponents, exponents are usually a little bit easier to understand, like 10^2 is two 10s multiplied together, 10^3 is three 10s multiplied together, what about 10^0, 0 10s multiplied together, shouldn’t that be a 0, but it’s actually a 1, so you have to think about it in a different way, If you don’t know, you can write some of them out, and then, if you look for patterns, you can ignore the zero case.

10^3=1000, 10^2=100, 10^1=10, 10^0=? 5^3=125, 5^2=25, 5^1=5, 5^0=? 2^3= 2, 2^2=4, 2^1=2, 2^0=?Copy the code

Did you see the pattern? Well, it’s k to the n, and every time you decrease n by 1, it’s 1 over k, so 10 to the 0 is one tenth of 10 to the 1, which is 1, 5 to the 0 is one fifth of 5 to the 1, which is 1, 2 to the 0 is one half of 2 to the 1, which is 1, so k to the 0 is 1.

So it makes sense that k to the minus n, like 10 to the minus 1 is 1/10 of 10 to the 0, which is 1/10 of 10 to the minus 1, which is 1/100.

We used to try to remember that 10 to the 0 and 2 to the 0 are 1, and the negative power is a fraction of that, but we should actually remember this rule, so that we can draw a parallel.

If you look at this and wonder why the title is 0, all of this is based on 0, if there were no 0, there would be no bitwise counting, 0 would be a placeholder. The function of 0 in exponentials is to standardize, to simplify the rules, otherwise you have to deal specifically with the number 1, and you can’t use 10 to the n or 2 to the n.

remainder

The remainder is what’s left after you do the division, or the remainder, just kidding. The remainder is useful because it helps you deal with periodic problems, even if the number is huge, but it simplifies the problem, turns the big number problem into the small number problem; Remainder is also used to group things, such as the common interlacing color change feature in tables, where even and odd rows can be divided into two groups by adding color to n%2=0 rows.

Let’s take a classic question: Today is Sunday, so what day will it be in 100 days?

100 days is not a big number, you can just count it, but what about 1,000 days, 10,000 days, 10^100 days? Forget about the numbers. Computers crash.

We can easily solve this problem with the remainder, because we have 7 days in a week, so we can ignore anything that has 7 days in 100 days, so 100%7 is 2, we have 2 days left, today is Sunday, so 2 days later is Tuesday.

10 to the 100 is too large to compute on a computer, so see if you can find a pattern.

10^0=1 1%7=1 Monday 10^1=10 10%7=3 Wednesday 10^2=100 100%7=2 Tuesday 10^3=1000 1000%7=6 Saturday.....Copy the code

If you’re interested, you can keep going, and you’ll see that as you increase in exponent n, the remainder follows a cycle of six numbers: 1, 3, 2, 6, 4, 5, starting at 0 and going to 100, so it’s 101, so 101%, 6 is 5, and the fifth number is 4, so 10 to the 100 day is Thursday.

Mathematical induction

Mathematical induction is a way of proving assertions about integers for all integers above 0 (0, 1, 2, 3…..) The method used to determine whether or not this is true.

Induction, at first glance, may not sound very reliable, but it is very rigorous.

The proof by induction is a little bit like dominoes, you make sure that every card that falls will fall, and then you make sure that you topple the first card so that all the dominoes fall.

Suppose to prove an assertion P(n) is true for all integers n above 0, then the steps using mathematical induction are as follows:

1. Prove that P(0) is true if n=0. 2. Prove that P(n) is true if n is higher than 0Copy the code

Step 1 is called the basis and step 2 is called induction. After the above two steps, you can prove that the assertion is true.

Let’s look at a problem that you’ve all done before: What’s the sum from 1 to 100?

The most basic method, of course, is to add 1 all the way to 100, but I believe we all know there is another method, 101*50=5050, meaning that the end of the sum: 1+100=101, 2+99=101, 3+98=101….. All the way up to 50 plus 51 is 101, so there are 50 101s, so that’s 5050.

Now assuming the sum from 0 to n, but still as the sum from 1 to n, then the sum of each term is 1+n, there are n/2 terms, and the sum is: (1+n)*(n/2)=(1+n)*n)/2, this expression is also called the Gauss equation, we call A(n), so now we use mathematical induction to prove that A(n) is true for all integers above n is 0, the procedure is as follows:

If A(n) is true, then A(n+1) is also trueCopy the code

Step 1:

So 0 goes in, 0 goes in, 0 goes in, 0 goes in, 0 goes in, 0 goes inCopy the code

Step 2:

Suppose A(n) is true: 0+1+2+... + n = (1 + n * n) / 2 establishment prove A (n + 1) : A (n) of both sides and 1-0 + n + 1 + 2 +... + n + (n + 1) = (n) (n + 1) * 2 + (n + 1)/A (n) on the right side of the generation into the equation: (to the left of the (1 + n)) / 2 * n + (n + 1) = (n) (n + 1) * / 2 + (n + 1) on the right side of the merger: (1+n)*n)/2 +(n+1) = (n^2+3n+2)/2 N squared plus 3n plus 2 over 2 is equal to n squared plus 3n plus 2 over 2, so A of n plus 1 is true and step 1 is true and step 2 is true, so the sum from 0 to n is equal to 1 plus n times n over 2.Copy the code

Permutation and combination

replacement

Putting N things in order is called permutation.

For example, how many kinds of arrangement of ABC three cards, take the first one has three choices, the second one has two choices, and the third one only has one choice, because each choice and other choices can be different, so the total arrangement is to multiply the number of choices of these times, 321=6.

ABCD 4 is 4321=24 rows, more numbers are similar, this multiplication is very regular, gradually decreasing, this is called factorial, use! For example, 321 is 3! , 4321 is 4! .

arrangement

Choosing m(m<=n) things out of n things for permutation is called permutation.

For example, choose 3 out of 5 cards for substitution: the first card has 5 choices, the second card has 4 choices, the third card has 3 choices, the total arrangement: 543=60.

To make an abstraction, take k cards out of n and arrange them:

n*(n-1)*(n-2)*.... *(n-k+1)Copy the code

Unify the above equation into the subtraction form :(n-0)*(n-1)*(n-2)*…. *(n-(k-1)), times 0 all the way to k-1, so that’s the total number of k terms multiplied, and the total number of permutations is denoted as:

Since this formula is hard to write, the following formula is: Pk(top)n(bottom). The above expression is too long to write, so it can be expressed as a factorial:

because

n! =(n-0)*(n-1)*(n-2)*... *(n-(k-1))*(n-k)*... *2*1 (n-k)*... *2*1=(n-k)!Copy the code

so

Pk(top)n(bottom)=n! /((n-k)!) .Copy the code

combination

Taking k(k<=n) elements out of n distinct elements, regardless of order, is a combination.

Ck (top) n (bottom), calculated by the total number of permutations: Pk (top) n (bottom), and then divided by the degree of repetition.

For example, the total number of permutations of 3 out of 4 is 432=24, but there are 321=6 permutations of the 3 elements, so every 3 elements is repeated 6 times, so we need to remove the repetition, 24/6=4. This repetition is exactly the number of permutations of K, so:

Ck (top) n (bottom) = (number of permutations of k(k<=n) elements taken from n different elements)/(number of permutations of K) = (n! /((n-k)!) ) / k! = n! /((n-k)! k!)Copy the code

To practice: king, xiao Wang, J, Q, K five cards lined up in a row, for the left end or right end at least one is trump card row there are several, do not distinguish between big and small wang.

It can be divided into three cases:

1. The left end is the trump case

Choose 2 trumps, the remaining four cards are swapped, and the total is calculated as follows: 2*P(4/4)=2*4*3*2*1=48.Copy the code

2. The right end is trump card

Ditto, 48Copy the code

3. Trump cards at both ends

With the choice of both ends, the permutation P(2/2) of two trumps * the permutation P(3/3) of three remaining cards =2! * 3! = 3 * 2 * 2 * 1 * 1 = 12. 1 and 2 cases include 3 cases, so the total number of ways to distinguish between Kings and small Kings =1 +2 -3, then calculate the number of ways to distinguish between Kings and small Kings, divided by the repetition of trumps P(2/2)=2*1=2, the final total arrangement is: (48+48-12) /2 = 42.Copy the code

This article briefly discusses enumeration, remainder, mathematical induction and permutation and combination related knowledge, the next article will discuss an interesting thing: recursion, stay tuned.