Problem 197. Recurrence relation

Created by Tomasz

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A recurrence relation is given by</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[P(1)   := 1\nP(n+1) := exp(1) - (n+1)*P(n)]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Write a function that, given an integer</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>n</w:t></w:r><w:r><w:t>, returns</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>P(n)</w:t></w:r><w:r><w:t>. The</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>n</w:t></w:r><w:r><w:t> will be smaller than 100 in all test-suite problems and an absolute precision of 10*eps (~2e-15, i.e. almost machine precision) is required.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

223 Solutions
45 Solvers

Last Solution submitted on Aug 26, 2020

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

Franck Dernoncourt on 31 Jan 2012

Maybe you should specify the required precision in the problem description.

Tomasz on 31 Jan 2012

OK, I added a sentence, thanks.

Solution Comments

Solution 118115

1 Comment

1 Comment

Aurelien Queffurust on 24 Jul 2012

different matlab fnction used to solve this problem

Solution 29456

1 Comment

1 Comment

Aurelien Queffurust on 24 Jul 2012

lol ! need a translator for this solution!

Solution 19868

2 Comments

2 Comments

@bmtran (Bryant Tran) on 31 Jan 2012

This solution should provide minimal rounding error since it's done in an essentially symbolic domain and then evaluated at the very end, but it doesn't satisfy the test cases. *sigh*

Tomasz on 31 Jan 2012

The sequence is strictly positive. (Not easy to see, but true). If your pn's get negative at some higher n, you still have the roundoff problem. It would be indeed avoided if the integer calculation within the loop was exact, but the numbers quickly become larger than the 48bit mantissa of a double.

Problem Recent Solvers45

Problem Tags

Problem 197. Recurrence relation

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers45

Suggested Problems

More from this Author7

Problem Tags

Problem 197. Recurrence relation

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers45

Suggested Problems

More from this Author7

Problem Tags

Players