There is a businessman accidentally breaking 40 pounds of weight, falling into 4 pieces, and finding that the 4 weights can be combined into any weight of 1-40, seeking these 4 pieces of weight. the quality of. (The weight coefficient can be taken -1, 0, 1)
Answer: 1, 3, 9, 27
Mathematics basis:
Mathematical propositions are like this (hereinafter used with symbol ^ represents index. For example, 3 ^ 2 representation 3 2): Suppose there is a sequence AN = {3 ^ 0, 3 ^ 1, 3 ^ 2, ..., 3 ^ N}, to demonstrate any integer in SUM (A) by adding 1 to n elements in this sequence. It can be demonstrated by mathematical inductance. Certification: When n = 1, n = 2, it can be verified by manual method to verify that the proposition is correct.
It is assumed that when n = k is established, that is, any integer P in SUM (AK) can be found, such a pure reduction method P (AK) makes P (AK) = P.
Then when n = k 1 ... For any integer P in SUM (AK), we can generate it with the original algorithm P (AK). For integers between SUM (AK) ~ SUM (a [K 1]), we divide it into 2 paragraphs: first: sum (AK) 1, ..., 3 ^ (k 1) -1, paragraph 2: 3 ^ (k 1), 3 ^ (k 1) 1, ..., 3 ^ (k 1) Sum (AK). For the number q of paragraph 2, it can be split into q = 3 ^ (k 1) P, we can use q (a [k 1]) = 3 ^ (k 1) p (AK This method exports the algorithm, so it is also true. Then analyze the paragraph 1 data. High school mathematical knowledge tells us that for the ratio of the ratio {A, A * Q, A * Q ^ 2, ..., A * Q, A * Q ^ 2, ..., A * Q, A * Q ^ 2, ..., A * Q ^ N}, and the formula is S = A * ( 1-q ^ (n 1)) / (1-Q). In this question, SUM (AK) 1 = (3 ^ (k 1) -1) / 2 1 = (3 ^ (k 1) 1) / 2> (3 ^ (k 1) - 1) / 2. Therefore, the digital Q in the first paragraph can split it into q = 3 ^ (k 1) -p, and 0 <= P <= SUM (AK). We can export the algorithm with Q (a [k 1]) = 3 ^ (k 1) -p (ak). Therefore, when n = k 1 is, the proposition is also established.
In addition: For any sequence AN = {A1, A2, ..., AN}, if you can use some additional reduction method to spray all integers in 1 ~ sum (an), then consider adding two possible two possible Algorithm, if A [N 1] <= SUM (AN) 1, the proposition is still established. And 3 is precisely the boundary line.
Java code (traversal all possible):
Class MathDemo {MathDemo () {
N1 = 0; N2 = 0; N3 = 0; N4 = 0;}
Boolean tryit (int a, int sum) {return (a == sum);
}
Boolean tryit (int A, int b, int sum) {return (A B == SUM || -A B == SUM || A-B == SUM);
}
Boolean tryit (int A, int b, int c, int sum) {return (A B C == SUM || A BC == SUM || A-B C == SUM || ABC == SUM || -A B C == SUM || -A BC == SUM || -A-B C == SUM);}
Boolean Tryit (int A, int B, int C, int D, int sum) {
RETURN (A B C D == SUM || A B CD == SUM || A B-C D == SUM || A BCD == SUM || A-B C D == SUM || A-B CD == SUM || AB-C D == SUM || Abcd == SUM || -A B CD == SUM || -A B-C D == SUM || -A BCD == SUM || -A-B C D == SUM || -A-B CD == SUM || -AB-C D == SUM || -ABCD == SUM);
}
Boolean Check (int A, int B, int C, int D) {boolean flag1 = true; for (int i = 1; i <41 && flag1 == true; i ) {system.out.println ("Check:" i ); Flag1 = (Tryit (a, i) || tryit (b, i) || tryit (c, i) || tryit (d, i) || tryit (A, B, I) || Tryit (A , C, I) || Tryit (A, D, I) || Tryit (B, C, I) || Tryit (B, D, I) || Tryit (C, D, I) || Tryit (A , B, C, I) || Tryit (A, C, D, I) || Tryit (B, C, D, I) || Tryit (A, B , C, D, I));}; system.out.println ("THE NUM CAN DO IT: FLAG1); system.out.println (); return flag1;}
Void xunhuan () {while (n1 <41 & (flag == false) {
N2 = 1; N1 ; While (N2 <41 - N1 & (Flag == FALSE)) {
N3 = 1; N2 ; While (N3 <41 - N2 - N1 & (FLAG == FALSE)) {N3 ; N4 = 40 - N1 - N2 - N3; System.out.Print ("Use the Numb:" N1 " N2 " " N3 " " N4 " To Check ");
Flag = CHECK (N1, N2, N3, N4);
}}}}
Public static void main (string [] AGR) {
MathDemo a = new mathdemo (); a.xunhuan (); if (a.flag == true) {system.out.println (A.N1); System.out.Println (A.N2); System.out. Println (A.N3); System.out.Println (A.N4);} else {system.out.println (); system.out.println (a.flag); system.out.println ("can't Find numbs ... ");}}
INT N1, N2, N3, N4;
Boolean flag = false;} /
The above method is too stupid, and too much time is time consuming.
The following ideas are good:
The weight (integer) of 1-N is made, and the number of coins used is the least, so how is it combined?
Key: ------------------------------ weight combination, you can selectively put on the left and right sides
Then it can be an addition, or it can be subtraction --------------------------------
Because you can use subtractions to get:
Assuming that 1-n number has been implemented so the next left and right side of the next number A can "implement" N digits on the left side of the implementation method is also the implementation method of the 1-N right side of A-. 1-N that has been implemented with A
Maybe this is a bit depressed
E.g
Because it is certain that a number is required, it must be realized: 1
Because it is realized, then the next left side of the number B to be taken can be B-1, right side B 1, then a number can be implemented
The second number of the left side 1 implementing a number is: 2
Then
The second to take the number is: 3 So the right to implement a number is: 4 1 number of the left and right sides of this number is because 1 has been implemented
Ok, now we have implemented: 1.2.3.4 four numbers
Similarly, the left and right of the number of the number to be taken can implement 4 numbers so left. 4, is 5.6.7.8 These four numbers are not difficult to see.
The third number is 99 to the right side we can also implement: 10.11.12.13 These 4 numbers
Ok, we have already achieved 1.2.3.4 ... 11.12.13 This 13 numbers can also achieve 13 numbers on the left side of the fourth number: 14.15.16 ........ 25.26
The fourth number is: 2727's right side and method can be achieved: 28.29.30 ........ 38.39.40
Ok, observe it is not difficult to find
The formula is:
(0 1) * 2 1 = 3 (1 3) * 2 1 = 9 (1 3 9) 1 = 8 (1 3 9 27) * 2 1 = 81
Everyone may find that it is similar to the formula upstairs, and the sum of the front 1 but because the method can be used, so the range of each number is 2 times.
4 numbers, only can be added to each other ... to achieve the number of 1-n in the data segment, then N is 40 ...
