home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / lang / c / 20006 < prev    next >
Encoding:
Text File  |  1993-01-21  |  2.7 KB  |  65 lines
  1. Newsgroups: comp.lang.c
  2. Path: sparky!uunet!spool.mu.edu!uwm.edu!linac!att!att!dptg!ulysses!allegra!princeton!fish.Princeton.EDU!lhjensen
  3. From: lhjensen@fish.Princeton.EDU (Leif Jensen)
  4. Subject: Re: Neophyte C programmer needs HELP!
  5. Message-ID: <1993Jan20.044915.12170@Princeton.EDU>
  6. Originator: news@nimaster
  7. Sender: news@Princeton.EDU (USENET News System)
  8. Nntp-Posting-Host: fish.princeton.edu
  9. Organization: Princeton University
  10. References: <1993Jan19.122451.10366@ac.dal.ca> <1993Jan19.213452.4531@organpipe.uug.arizona.edu> <1993Jan19.221115.4901@organpipe.uug.arizona.edu>
  11. Date: Wed, 20 Jan 1993 04:49:15 GMT
  12. Lines: 51
  13.  
  14. In article <1993Jan19.221115.4901@organpipe.uug.arizona.edu> dave@cs.arizona.edu (Dave Schaumann) writes:
  15. >In article <1993Jan19.213452.4531@organpipe.uug.arizona.edu>, dave@cs (Dave Schaumann) writes:
  16. >>In article <1993Jan19.122451.10366@ac.dal.ca>, francis@ac writes:
  17. >>>2.    If Sn denotes the number of subsets of {1,2,3,...,n} that do *not*
  18. >>>    contain two *consecutive* integers, write an algorithm and program
  19. >>>    to compute the value Sn for any set {1,2,3,...,n}.  For example:
  20. >>>    S3=5 since the subsets of {1,2,3} that do not contain consecutive
  21. >>>    integers are {}, {1}, {2}, {3}, {1,3}.
  22.  
  23. >>This one's a bit harder.
  24.  
  25. >Actually, not that hard at all... (tho, I suppose it might be harder
  26. >for those who've never seen dynamic programming before...)
  27.  
  28. >>It might even be possible to use induction to find a formula...
  29.  
  30. >Actually, once you start generating solutions, the formula's
  31. >pretty obvious.  Proving it's correct, on the other hand, would
  32. >be a bit more difficult.
  33.  
  34. First consider...(created easily with vi)
  35.  
  36. S_1 = {{},{1}}
  37. S_1*= {{3},{1,3}}
  38. S_2 = {{},{1},{2}}
  39. S_2*= {{4},{1,4},{2,4}}
  40. S_3 = {{},{1},{2},{3},{1,3}}
  41. S_3*= {{5},{1,5},{2,5},{3,5},{1,3,5}}
  42. S_4 = {{},{1},{2},{3},{1,3},{4},{1,4},{2,4}}
  43. S_4*= {{6},{1,6},{2,6},{3,6},{1,3,6},{4,6},{1,4,6},{2,4,6}}
  44. S_5 = {{},{1},{2},{3},{1,3},{4},{1,4},{2,4},{5},{1,5},{2,5},{3,5},{1,3,5}}
  45.  
  46. It's not so hard to prove.  For S_n = {a1,a2,...,am}, define
  47. S_n* = {a1 union {n+2}, a2 union {n+2},..., am union {n+2}}.  It is
  48. easy to see that every element of S_n* is in S_{n+2} and is not an
  49. element of S_{n+1}.  Trivially every element of S_{n+1} is in S_{n+2},
  50. and it is simple to see that in fact all elements of S_{n+2} are also
  51. in either S_{n+1} or S_n*.  Thus we have a recurrence relation on the
  52. orders of the S_n: |S_{n+2}|=|S_{n+1}|+|S_n|, and the solution is
  53. familiar from the Fibinocci sequence.
  54.  
  55. |S_n| = 5^{-1/2} (\phi^{n+2} - (-1/\phi)^{n+2}),
  56.  
  57. where \phi is the Golden Ratio (1+\sqrt 5)/2.
  58.  
  59. How would the dynamic programming solution go? (and why would it
  60. be preferable to an analytic solution?)
  61.  
  62. --
  63. Leif Jensen
  64. lhjensen@phoenix.princeton.edu
  65.