Welcome to “Algorithms and the Beauty of Programming” ↑ pay attention to us!
This article was first published on the wechat official account “Beauty of Algorithms and Programming”. Welcome to follow and learn more about this series of blogs in time.
Problem description
Given a positive integer n, find all the different ways to write n as the sum of the integers 1, 3, and 4.
For example, when n=5, there are 6 different ways to write it.
5 = 1 + 1 + 1 + 1 + 1
Lambda is equal to 1 plus 1 plus 3
Lambda is equal to 1 plus 3 plus 1
Lambda is equal to 3 plus 1 plus 1
= 1 + 4
= 4 + 1
Problem analysis
Since junior middle school, we have been exposed to the concept of function. The so-called function refers to a given independent variable x, which will get a value y after operation according to some mapping rules.
For example, y=2·x is a mapping. For example, given x=2, y=2·2=4 can be calculated.
The problem mentioned above is a kind of mapping relationship, but this mapping relationship, we do not know what it is, we need to explore and solve.
So let’s say that we now know this mapping, that given any positive integer x, we can write it in y ways, that f of x is equal to y.
The example shows exactly f(5) = 6, indicating that given a positive integer 5, there are six possible ways to write it.
Now let’s think about the way to write the positive integer n, which is f(n).
One possible way to write n is as follows: n = x1+x2+···+xm
Let’s start with the term xm, which can be written in several different ways. According to the question, the possible values of xm are 1,3,4, because only 1,3,4 can appear in each term.
Let xm = 1, then:
N = x1+x2+···+xm-1+ 1
N – 1 = x1 + x2 +… + xm – 1
According to the above calculation, when xm=1, the way to write the positive integer n is converted to the way to write the positive integer n-1, that is, f(n-1).
And so on, let xm = 3, then:
N = x1+x2+···+xm-1 + 3
N – 3 = x1 + x2 +… + xm – 1
The problem turns out to be the n-3 notation, the f(n-3) notation.
Let xm = 4, then:
N = x1+x2+···+xm-1 + 4
N – 4 = x1 + x2 +… + xm – 1
The problem turns out to be the way to write n minus 4, f of n minus 4.
So if we put the three notations together, we get: f(n) = F (n-1) + F (n-3) + f(n-5). So if we want to figure out how to write the positive integer n, we need to figure out how to write the three integers n minus 1, n minus 3, and n minus 5, and then sum them up.
conclusion
This article through a simple case, introduced the basic idea of function, and its application to solve the problem in the train of thought, to help you deeply understand the function.
\
More interesting articles:
Where2go team
Wechat: The beauty of algorithms and programming
Long press to identify the QR code to follow us!
Tips: Click on the lower right corner of the page “Write a message” to comment, looking forward to your participation! Welcome to forward!