https://www.algopedia.ro/wiki/index.php?title=Problems_Involving_Sequences&feed=atom&action=history Problems Involving Sequences - Revision history 2021-08-03T20:41:59Z Revision history for this page on the wiki MediaWiki 1.34.0 https://www.algopedia.ro/wiki/index.php?title=Problems_Involving_Sequences&diff=1650&oldid=prev Cristian: Add search in a sequence 2011-01-13T12:59:04Z <p>Add search in a sequence</p> <p><b>New page</b></p><div>= Problems with Sequences =<br /> <br /> This is a small list of exercises involving sequences of numbers, for beginners. They do not require storage, thus they have solutions without using arrays.<br /> <br /> == Problems with sequences (no arrays needed) ==<br /> <br /> === Even Elements ===<br /> How many even elements are in a sequence of &lt;code&gt;n&lt;/code&gt; integer numbers?<br /> === Signed Elements ===<br /> How many negative, zero, and positive elements does a sequence of &lt;code&gt;n&lt;/code&gt; numbers contain?<br /> === Sum and Product ===<br /> Compute the sum and the product of numbers &lt;code&gt;1&lt;/code&gt; to &lt;code&gt;n&lt;/code&gt;, &lt;code&gt;n&lt;/code&gt; given. Is there a complexity difference between the best algorithms you can find for the two?<br /> === Find Element ===<br /> Given a number &lt;code&gt;a&lt;/code&gt; and a sequence of &lt;code&gt;n&lt;/code&gt; elements, on what position does &lt;code&gt;a&lt;/code&gt; appear in the sequence?<br /> === Indices and Elements ===<br /> How many numbers in a sequence of &lt;code&gt;n&lt;/code&gt; elements are equal to the position in which they appear in the sequence?<br /> === Increasing Sequence ===<br /> Are the numbers in a sequence in increasing order?<br /> === Maximum and minimum ===<br /> Compute the maximum and the minimum value in a sequence of &lt;code&gt;n&lt;/code&gt; numbers.<br /> === Fibonacci numbers ===<br /> Compute the &lt;code&gt;n&lt;sup&gt;th&lt;/sup&gt;&lt;/code&gt; number in the Fibonacci sequence. The Fibonacci sequence has &lt;code&gt;f&lt;sub&gt;1&lt;/sub&gt; = 0&lt;/code&gt;, &lt;code&gt;f&lt;sub&gt;2&lt;/sub&gt; = 1&lt;/code&gt; and &lt;code&gt;f&lt;sub&gt;n&lt;/sub&gt; = f&lt;sub&gt;n-1&lt;/sub&gt; + f&lt;sub&gt;n-2&lt;/sub&gt;&lt;/code&gt;. Example: &lt;code&gt;0 1 1 2 3 5 8 13 21 ...&lt;/code&gt;<br /> === Monotonic Sequence ===<br /> Is a sequence of numbers monotonic? We define a &lt;span style=color:green&gt;'''monotonic sequence'''&lt;/span&gt; as a sequence whose numbers are either in increasing order, or in decreasing order.<br /> === Identical Numbers ===<br /> What is the maximum number of consecutive identical numbers in a sequence of &lt;code&gt;n&lt;/code&gt; elements?<br /> === Adding fractions ===<br /> Given a sequence of numbers &lt;code&gt;a&lt;sub&gt;1&lt;/sub&gt; a&lt;sub&gt;2&lt;/sub&gt; ... a&lt;sub&gt;n&lt;/sub&gt;&lt;/code&gt; compute the summation &lt;math&gt;\sum_{k=1}^n \frac{1}{a_k} = \frac{1}{a_1} + \frac{1}{a_2} + ... + \frac{1}{a_n}&lt;/math&gt;<br /> <br /> === Word Counting ===<br /> How many groups of consecutive non-zero numbers are in a sequence? Consider such groups as words, zero being a divider such as space.<br /> === Rotating Sequence &lt;sup&gt;h&lt;/sup&gt; ===<br /> Let's define a &lt;span style=color:green&gt;'''rotating increasing sequence'''&lt;/span&gt; as a sequence of numbers that is either in increasing order, or can be transformed into one by successive rotations (the last element becomes first). Problem: is a sequence of &lt;code&gt;n&lt;/code&gt; numbers a rotating increasing sequence?<br /> === Rotating Monotonic Sequence &lt;sup&gt;h&lt;/sup&gt; ===<br /> Same as before we define a &lt;span style=color:green&gt;'''rotating monotonic sequence'''&lt;/span&gt; as a sequence that is either monotonic, or can be made into one by rotations. Problem: is a sequence of &lt;code&gt;n&lt;/code&gt; numbers a rotating monotonic sequence?<br /> === Bitonic Sequence &lt;sup&gt;h&lt;/sup&gt; ===<br /> Is a sequence of numbers bitonic? We define a &lt;span style=color:green&gt;'''bitonic sequence'''&lt;/span&gt; as a sequence whose numbers are begin in increasing order, and then start decreasing and remain decreasing until the end of the sequence. Increasing and decreasing sequences are also bitonic sequences (that is, it's allowed to skip one of the two sections).<br /> === Rotating Bitonic Sequence &lt;sup&gt;h&lt;/sup&gt; ===<br /> Same as before we define a &lt;span style=color:green&gt;'''rotating bitonic sequence'''&lt;/span&gt; as a sequence that is either bitonic, or can be made into one by rotations. Problem: is a sequence of &lt;code&gt;n&lt;/code&gt; numbers a rotating bitonic sequence?<br /> === Brackets &lt;sup&gt;h&lt;/sup&gt; ===<br /> Given a sequence of &lt;code&gt;0&lt;/code&gt; and &lt;code&gt;1&lt;/code&gt;, where &lt;code&gt;0&lt;/code&gt; means open bracket and &lt;code&gt;1&lt;/code&gt; means close bracket, find out if the sequence represents a correct sequence of brackets, and if so, compute the maximum number of nested brackets. Example: &lt;code&gt;0 1 0 0 1 0 1 1&lt;/code&gt; is correct and has a maximum nesting factor of 2, while &lt;code&gt;0 0 1 1 1 0&lt;/code&gt; is incorrect.<br /> <br /> <br /> <br /> <br /> <br /> ''Legend:''<br /> * '''&lt;sup&gt;h&lt;/sup&gt;''' means '''h'''ard. The problem is difficult.</div> Cristian