Try to face the integration by parts
Good evening. It's been a long time (* ´ω ｀)
This challenge is from an array containing arbitrary elements Randomly select elements and add them together. But it's not just about adding up It must be added up to reach the target value.
For example, choose a combination from the array so that the total is 20 !! It's something like that.
Somewhat (; ´ ･ ω ･)
It seems to be quite famous and basic content, I personally had a hard time (laughs)
Suddenly, I will put the code.
Partial_sum.py
def solve(Nlist, target, i=0, sum=0):
if i == len(Nlist):
return sum == target
if (solve(Nlist, target, i + 1, sum)):
return True
if (solve(Nlist, target, i + 1, sum + Nlist[i])):
return True
return False
Nlist = [1,3,5,12,7]
target = 11
print(solve(Nlist, target))
It's simpler than you think, but it's complicated. For example, At first I will only look here.
Partial_sum.py
#Start from here!!
Nlist = [1,3,5,12,7]
target = 11
# ↓[1,3,4...] ↓ 11
print(solve(Nlist, target))
Throw Nlist and target into solve. As an image, an array containing elements and the target total value Just throw the whole thing and say hello !! Let's take a look inside solve.
Partial_sum.py
#i is an image of your current location.
#sum is the sum of the current numbers.
#You are at 0,The total value is also 0
def solve(Nlist, target, i=0, sum=0):
#Nlist is 5 in length, initially i==Since it is 0, Pass!!
if i == len(Nlist):
return sum == target
#that?!There is more solve in the if statement. I don't know!!
#Let's stop reading(Lol)
if (solve(Nlist, target, i + 1, sum)):
I don't know, I want to throw it out (laughs).
No! Run away. .. The answer is that if you have recursion in your if statement, Complete the recursive process and derive true or false. This determines whether or not it is included in the if statement. Hmm, stupid (laughs)
Do you want to leave for the time being? of solve (Nlist, target, i + 1, sum) in if For an adventure to find out what's ahead.
Let's go in order (`) ノ
i=0.py
def solve(Nlist, target, i=0, sum=0):
#pass!
if i == len(Nlist):
return sum == target
#Recursive processing is continued until it is clear whether the conditional statement of the if statement is True or False.
if (solve(Nlist, target, i + 1, sum)):
return True
i=1.py
#solve(Nlist,target,1(=0+1),0)I entered the recursive process with.
def solve(Nlist, target, i=1, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#It is also recursive processing. Let's go without fear!!
if (solve(Nlist, target, i + 1, sum)):
return True
i=2.py
#solve(Nlist,target,2(=1+1),0)I entered the recursive process with.
def solve(Nlist, target, i=2, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#It is also recursive processing. Let's go without fear!!
if (solve(Nlist, target, i + 1, sum)):
return True
i=3.py
#solve(Nlist,target,3(=2+1),0)I entered the recursive process with.
def solve(Nlist, target, i=3, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#It is also recursive processing. Let's go without fear!!
if (solve(Nlist, target, i + 1, sum)):
return True
i=4.py
#solve(Nlist,target,4(=3+1),0)I entered the recursive process with.
def solve(Nlist, target, i=4, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#It is also recursive processing. Let's go without fear!!
if (solve(Nlist, target, i + 1, sum)):
return True
i=5.py
#solve(Nlist,target,5(=4+1),0)I entered the recursive process with.
def solve(Nlist, target, i=5, sum=0):
#i == len(Nlist) ==Finally, in 5, I put it in the if statement at the beginning.
if i == len(Nlist):
#But unfortunately sum(0) != target(11)。False
return sum == target
I see, I went to i = 5, but it turned out to be False. What happens after that? .. For the time being, the result of i = 5 was False, so Let's take it back to the previous layer, i = 4.
i=4.py
def solve(Nlist, target, i=4, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#The conditional statement in the if minute was Flase. That is, the if statement here is pass!!
#Let's go to the next if statement!!
if (solve(Nlist, target, i + 1, sum)):
return True
#Here i=4 so let's substitute
# (solve(Nlist, target, 4 + 1, sum + Nlist[4]))
# (solve(Nlist, target, 5 , 0 + 7 ) //Nlist = [1,3,5,12,7]
if (solve(Nlist, target, i + 1, sum + Nlist[i])):
return True
Yes, move on to the next if statement. Let's check again when i = 5 with a new conditional statement.
i=5.py
#solve(Nlist,target,5,7)I entered the recursive process with.
def solve(Nlist, target, i=5, sum=7):
#i == len(Nlist) == 5 ,Put it in the if statement.
if i == len(Nlist):
#But unfortunately sum(7) != target(11)。False
return sum == target
I think that the figure up to this point will look like the one below.
A good person can do this with his head,
I couldn't do it myself, so I wrote it on paper and organized it.
Returning to the story, it seems that nothing was done until i = 4.
Now let's report this result to i = 3.
i=3.py
#solve(Nlist,target,3(=2+1),0)I entered the recursive process with.
def solve(Nlist, target, i=3, sum=0):
#pass!!
if i == len(Nlist):
return sum == target
#False so pass!!
#Sum has never been 11 from previous processing
if (solve(Nlist, target, i + 1, sum)):
return True
# (solve(Nlist, target, 3 + 1, sum + Nlist[3])): //Nlist = [1,3,5,12,7]
# (solve(Nlist, target, 4 , 0 + 12 )):
#Substitute the above conditions below and enter a new if!!
if (solve(Nlist, target, i + 1, sum + Nlist[i])):
return True
i=4.py
#solve(Nlist,target,4(=3+1),12)I entered the recursive process with.
def solve(Nlist, target, i=4, sum=12):
#pass!!
if i == len(Nlist):
return sum == target
#It is a recursive process. Let's go without fear!!
if (solve(Nlist, target, i + 1, sum)):
return True
i=5.py
#solve(Nlist,target,5(=4+1),12)I entered the recursive process with.
def solve(Nlist, target, i=5, sum=12):
#i == len(Nlist) == 5 ,Put it in the if statement.
if i == len(Nlist):
#But unfortunately sum(12) != target(11)。False
return sum == target
It was false, I will go back one report.
i=4.py
#solve(Nlist,target,4(=3+1),12)I entered the recursive process with.
def solve(Nlist, target, i=4, sum=12):
#pass!!
if i == len(Nlist):
return sum == target
#False with Pass!
if (solve(Nlist, target, i + 1, sum)):
return True
#Next↓
if (solve(Nlist, target, i + 1, sum + Nlist[i]))://Nlist = [1,3,5,12,7]
return True
i=5.py
#solve(Nlist,target,5(=4+1),12 + 7)I entered the recursive process with.
def solve(Nlist, target, i=5, sum=19):
#i == len(Nlist) == 5 ,Put it in the if statement.
if i == len(Nlist):
#But unfortunately sum(19) != target(11)。False
return sum == target
Let's make a figure.
I want to see the tree structure (laughs)
It's a long task, but it's oK if you keep the following points in mind.
** 1. The conditional statement (recursive) of the if statement keeps chasing until True and False are seen. 2. If you see True or False, go back to the previous layer and follow the description in solve faithfully to follow the action **
I wrote it brilliantly, but I didn't know it at all, so To see what is transitioning I mixed pirnt as follows.
Partial_sum.py
def solve(Nlist, target, i=0, sum=0):
print(f"i:{i},sum:{sum}") #Display the current value for clarity during recursive processing
if i == len(Nlist):
#For recursive processing, put the conditional statement when you come to the bottom layer at the beginning.
#So, print a comment that tells you that the bottom layer is when you enter this if statement.
print(f"Result:i={i},sum={sum}")
print() #Line breaks to separate from the next process
return sum == target
if (solve(Nlist, target, i + 1, sum)):
return True
if (solve(Nlist, target, i + 1, sum + Nlist[i])):
return True
return False
Nlist = [1,3,5,12,7]
target = 11
print(solve(Nlist, target))
Let's see the execution result !!
Execution result.py
i:0,sum:0
i:1,sum:0
i:2,sum:0
i:3,sum:0
i:4,sum:0
i:5,sum:0
Result:i=5,sum=0
#↑ Compare with the above figure. i,Does the change in sum match the figure?
#Result:i=5,sum=Returns False because sum is not 11 as it says 0
#I after returning=I'll be back at 4.
#After returning, continue to the next IF statement.
#Therefore, the next display is i below=It becomes pirnt at the time of 5.
#If you don't understand, please return to the above page.
i:5,sum:7
Result:i=5,sum=7
#↑sum(=7) !=Since it is 11, it is False.
#Therefore, i=The two if statements at 4 are both False.
#Next is i=It returns to the if statement at the time of 3, but the processing is the same as above.
i:4,sum:12
i:5,sum:12
Result:i=5,sum=12
i:5,sum:19
Result:i=5,sum=19
i:3,sum:5
i:4,sum:5
i:5,sum:5
Result:i=5,sum=5
i:5,sum:12
Result:i=5,sum=12
i:4,sum:17
i:5,sum:17
Result:i=5,sum=17
i:5,sum:24
Result:i=5,sum=24
i:2,sum:3
i:3,sum:3
i:4,sum:3
i:5,sum:3
Result:i=5,sum=3
i:5,sum:10
Result:i=5,sum=10
i:4,sum:15
i:5,sum:15
Result:i=5,sum=15
i:5,sum:22
Result:i=5,sum=22
i:3,sum:8
i:4,sum:8
i:5,sum:8
Result:i=5,sum=8
i:5,sum:15
Result:i=5,sum=15
i:4,sum:20
i:5,sum:20
Result:i=5,sum=20
i:5,sum:27
Result:i=5,sum=27
i:1,sum:1
i:2,sum:1
i:3,sum:1
i:4,sum:1
i:5,sum:1
Result:i=5,sum=1
i:5,sum:8
Result:i=5,sum=8
i:4,sum:13
i:5,sum:13
Result:i=5,sum=13
i:5,sum:20
Result:i=5,sum=20
i:3,sum:6
i:4,sum:6
i:5,sum:6
Result:i=5,sum=6
i:5,sum:13
Result:i=5,sum=13
i:4,sum:18
i:5,sum:18
Result:i=5,sum=18
i:5,sum:25
Result:i=5,sum=25
i:2,sum:4
i:3,sum:4
i:4,sum:4
i:5,sum:4
Result:i=5,sum=4
i:5,sum:11
Result:i=5,sum=11
True
As mentioned above, after reaching the limit where transition is not possible The method of repeating the process of returning one step and operating to the limit is called ** depth-first search **. The material says that it is relatively easy to write, No, it's awesome for beginners !! (ﾟ Д ﾟ)
It seems that the future is still long (* ´ω ｀)
Recommended Posts