How do I get the Math equation of Python Algorithm?_问答_开发者

ok so I am feeling a little stupid for not knowing this, but a coworker asked so I am asking here: I have written a python algorithm that solves his problem. given x > 0 add all numbers together from 1 to x.

def intsum(x):
  if x > 0:
    return x + intsum(x - 1)
  else:
    return 0

intsum(10)
55

first what is this type of equation is this and what is the correct way to get this answer 开发者_C百科as it is clearly easier using some other method?

This is recursion, though for some reason you're labeling it like it's factorial.

In any case, the sum from 1 to n is also simply:

n * ( n + 1 ) / 2

(You can special case it for negative values if you like.)

Transforming recursively-defined sequences of integers into ones that can be expressed in a closed form is a fascinating part of discrete mathematics -- I heartily recommend Concrete Mathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik (see. e.g. the wikipedia entry about it).

However, the specific sequence you show, fac(x) = fac(x - 1) + x, according to a famous anecdote, was solved by Gauss when he was a child in first grade -- the teacher had given the pupils the taksk of summing numbers from 1 to 100 to keep them quet for a while, but two minutes later there was young Gauss with the answer, 5050, and the explanation: "I noticed that I can sum the first, 1, and the last, 100, that's 101; and the second, 2, and the next-to-last, 99, and that's again 101; and clearly that repeats 50 times, so, 50 times 101, 5050". Not rigorous as proofs go, but quite correct and appropriate for a 6-years-old;-).

In the same way (plus really elementary algebra) you can see that the general case is, as many have already said, (N * (N+1)) / 2 (the product is always even, since one of the numbers must be odd and one even; so the division by two will always produce an integer, as desired, with no remainder).

Here is how to prove the closed form for an arithmetic progression

S  = 1 +   2   + ... + (n-1) + n
S  = n + (n-1) + ... +   2   + 1
2S = (n+1) + (n+1) + ... + (n+1) + (n+1)
     ^ you'll note that there are n terms there.
2S = n(n+1)
S = n(n+1)/2

I'm not allowed to comment yet so I'll just add that you'll want to be careful in using range() as it's 0 base. You'll need to use range(n+1) to get the desired effect.

Sorry for the duplication...

sum(range(10)) != 55

sum(range(11)) == 55

OP has asked, in a comment, for a link to the story about Gauss as a schoolchild.

He may want to check out this fascinating article by Brian Hayes. It not only rather convincingly suggests that the Gauss story may be a modern fabrication, but outlines how it would be rather difficult not to see the patterns involved in summing the numbers from 1 to 100. That in fact the only way to miss these patterns would be to solve the problem by writing a program.

The article also talks about different ways to sum arithmetic progressions, which is at the heart of OP's question. There is also an ad-free version here.

Larry is very correct with his formula, and its the fastest way to calculate the sum of all integers up to n.

But for completeness, there are built-in Python functions, that perform what you have done, on lists with arbitrary elements. E.g.

sum()

>>> sum(range(11))
55
>>> sum([2,4,6])
12

or more general, reduce()

>>> import operator
>>> reduce(operator.add, range(11))
55

Consider that N+1, N-1+2, N-2+3, and so on all add up to the same number, and there are approximately N/2 instances like that (exactly N/2 if N is even).

What you have there is called arithmetic sequence and as suggested, you can compute it directly without overhead which might result from the recursion.

And I would say this is a homework despite what you say.