P
PTS
Can someone help me write recursive function from the following
sequence....
1,3,5,11,21,43...
Thanks for your help!
sequence....
1,3,5,11,21,43...
Thanks for your help!
T
Tim Love
PTS said:
It would be useful if you could post your most recent attempt at
writing the code.
Z
Zara
Have you tried to define first which is the law of that series?PTS said:
It's eaasy, it is really adequate to teach recursivity. Nice homework!
P
PTS
Sorry, here it is...
int recseq (int nth)
{
int seq1;
if (nth == 0)
seq1 = 1;
else if (nth == 1)
seq1 = 3;
else
seq1 = ..... (problem is determining the equation here)
return seq1;
}
int recseq (int nth)
{
int seq1;
if (nth == 0)
seq1 = 1;
else if (nth == 1)
seq1 = 3;
else
seq1 = ..... (problem is determining the equation here)
return seq1;
}
P
PTS
I have tried, and came up with two base cases, which equal n-1, and
n-2. This sequence has no relation. That is the problem I am having
with understanding this. It is not easy to me which I why I am on here
trying to get the understanding from someone that will be able to give
me some help and/or advice. Some guidance is what I am asking.
n-2. This sequence has no relation. That is the problem I am having
with understanding this. It is not easy to me which I why I am on here
trying to get the understanding from someone that will be able to give
me some help and/or advice. Some guidance is what I am asking.
R
red floyd
K
Karl Heinz Buchegger
PTS said:
1 3 5 11 21 43
3 = 2 * 1 + 1
5 = 2 * 3 - 1
11 = 2 * 5 + 1
21 = 2 * 11 - 1
43 = 2 * 21 + 1
Does that help ?
V
Victor Bazarov
Karl said:
Actually it seems that the sequence is simpler (confirmed by the page
suggested by 'red floyd'):
5 = 3 + 2 * 1
11 = 5 + 2 * 3
21 = 11 + 2 * 5
43 = 21 + 2 * 11
I suppose the true sequence begins with
0 1 1 3 5 11 ...
(assuming that [ 0 1 ] is the beginning of many sequences)
V
G
Grahamo
the sequence is
N0 = 1
N1 = 3 = 1 + (add 2)
N2 = 5 = 3 + 1 + (add 1)
N3 = 11 = 5 + 3 + 1 +(add 2)
N4 = 21 = 11 + 5 + 3 + (add 1)
N5 = 43 = 21 + 11 + 5 + 3 + 1 + (add 2)
its simlpe the sum of the preceding values plus either 1 or 2
depending on whether N is even or odd.
N0 = 1
N1 = 3 = 1 + (add 2)
N2 = 5 = 3 + 1 + (add 1)
N3 = 11 = 5 + 3 + 1 +(add 2)
N4 = 21 = 11 + 5 + 3 + (add 1)
N5 = 43 = 21 + 11 + 5 + 3 + 1 + (add 2)
its simlpe the sum of the preceding values plus either 1 or 2
depending on whether N is even or odd.
D
Dan Cernat
PTS said:
sequence: 1 3 5 11 21 43 represents the values of the plynomial
function
g(x) = a*x^5 + b*x^4 + c*x^3 + d*x^2 + e*x + f
where:
g(0) = 1
g(1) = 3
g(2) = 5
g(3) = 11
g(4) = 21
g(5) = 43
replace in the function above and you will get a linear system of
equationd with the unknowns a, b, c, d, e, f solve it and you get
a = 1/10
b = -7/6
c = 31/6
d = -53/6
e = 101/15
f = 1
now you can calculate the values of g(x) for any x
do a for loop.
dan
S
Stewart Gordon
PTS said:
What do you mean by this?
What you are asking isn't a C++ question. More of a maths question.
Given a sequence, there are ways to try and work out the formula that
defines it. None of them are guaranteed to work, but there are
certainly methods worth trying.
For example, look at the differences between successive terms.
1 3 5 11 21 43
2 2 6 10 22
Notice a pattern? (Scroll down for the answer.)
If no pattern is obvious, then take differences again on the new
sequence, like this:
1 3 5 11 21 43
2 2 6 10 22
0 4 4 12
You might eventually come up with a sequence that is simpler or has some
obvious relation to the original.
Now for your sequence. You only needed to take the differences once.
If you've been observant, you'll've noticed that the sequence of
differences is double of the original sequence, offset to the right a
bit. Let's stretch it out a bit to make it clearer:
1 3 5 11 21 43
\ \ \ \
\ \ \ \
\ \ \ \
\ \ \ \
\ \ \ \
2 2 6 10 22
Now extending the sequence is trivial. At each step, you are doubling
something and then adding it on.
1 3 5 11 21 43 85
\ \ \ \ \
\ \ \ \ \
\ \ \ \ \
\ \ \ \ \
\ \ \ \ \
2 2 6 10 22 42
This should make it easy to work out the formula by which each element
is calculated from the previous two. Once you've done that, write it in
C++.
Once you've got your head around this, here's another, similar sequence
for you to have a crack at:
1 2 5 11 26 59 ...
Stewart.
--
-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GCS/M d- s:- C++@ a->--- UB@ P+ L E@ W++@ N+++ o K-@ w++@ O? M V? PS-
PE- Y? PGP- t- 5? X? R b DI? D G e++>++++ h-- r-- !y
------END GEEK CODE BLOCK------
My e-mail is valid but not my primary mailbox. Please keep replies on
the 'group where everyone may benefit.
D
Dan Cernat
Dan said:
Darn! I missed the recursive part!
Same approach, but the function is different:
g(x) = a*g(x-1) + b*x^3 + c*x^2 + d*x + e
g(0) = 1
use the values you have and solve the system. ->
a = -2
b = 4/3
c = -6
d = 44/3
e = -5
one can choose a different type of equation (eg. exponential instead of
polynomial)
now, let us calculate the results for x = 6
using the method 1 we get g(6) = 434 + 2/5
using the method 2 we get g(6) = 69
which one is the correct answer?
answer: they are both correct. they both verify the original
assumptions.
/dan
H
Howard
Victor Bazarov said:
Unless the OP gives us the formula for generating the given sequence, there
is no correct (or incorrect) answer, really. Given just a sequence of
numbers, if asked what the next number in that sequence should be, one can
respond with absolutely any number they wish, and be "correct", because it
is possible (and failry simple) to define an equation which will generate
the given sequence and the stated next number for that sequence. You could
argue that the question is "what is the next number, given the _simplest_
formula for the given sequence", but then you're inviting arguments as to
what is _simpler_, as seen here by the two differing formulas provided for
the sequence. To guarantee that only one answer is "correct" (which most
homework problems ought to do, in my opinion), then the foumula itself must
be stated. If you just give the sequence, then it is impossible to argue
that _any_ value for a number later in the sequence is incorrect.
Therefore, and recursive formula f(i) which returns the given values
1,3,5,11,21, and 43 for i=0,1,2,3,4, and 5 is always "correct", regardless
of what it returns for any subsequent values of i!
Of course, tell that to your instructor, and you're likely to generate a
nice, fat 'F' for yourself!
-Howard
G
Greg
If C is the current number in the series, the next number in the
series, D, is calculated by adding 2 x B (C's predecessor) to C. In
other words:
D = C + B * 2
Here is the solution in code:
#include <iostream>
#include <cstdio>
void NextInSeries( int PreviousN , int inCurrentN)
{
const int kRecursionLimit = 10000;
if (inCurrentN > kRecursionLimit)
return; // can't recurse forever...
int nextN = inCurrentN + PreviousN * 2;
std::cout << nextN << " ";
NextInSeries( inCurrentN, nextN);
}
int main()
{
NextInSeries( 0, 1);
std::cout << std::endl;
return 0;
}
And its output:
1 3 5 11 21 43 85 171 341 683 1365 2731 5461 10923
Greg
H
Howard
Greg said:
Actually, that's just your opinion of what the next number in the series
_should_ be. There is no way of knowing for sure that that's what the
series actually _is_, because it's not completely specified. It is quite
easy to pick absolutely _any_ number for the next value in the series, and
create a rule or formula for the series which will generate that number. A
finite list of numbers simply does _not_ specify a series. For example,
what series does the following represent...
2 3
? You could say it represents f(i) = f(i-1) + 1. Or, it could be the list
of all prime numbers. Or, f(i) = f(i-1) * 2 - 1. Or an _infinite_ number
of other series. It's just impossible to know for sure. Adding more
numbers does not change that fact.
(Sorry, but my math background wouldn't let me pass that one by.
)Why would you want to do someone's homework for them? They're not going to
learn diddly that way! Better to prod them in the right direction, and work
with the code _they_ write, then to simply do their homework, don't you
think?
-Howard
P
PTS
That is all I am asking for and by far am not trying to get stuff done.
I appreciate everyone's response and time to reply to my question as I
know you all do not have to. Again thanks and I am trying to figure it
out based on the methods the teacher gave me along with the tips given
here.
I appreciate everyone's response and time to reply to my question as I
know you all do not have to. Again thanks and I am trying to figure it
out based on the methods the teacher gave me along with the tips given
here.