anonymous
  • anonymous
Need help with a discrete math problem.
Discrete Math
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
schrodinger
  • schrodinger
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
anonymous
  • anonymous
I'm not familiar with these type of problems, seems like you need to use the bottom formul a for both, but I don't know how to fill it in.
anonymous
  • anonymous
So if I started filling in the bottom formula for A(3, 3) A(3-1, A(3,3-1)) A(2, A(3,2)) Plug the A(3,2) back into the formula: A(2, A(3-1, A(3, 2-1))) A(2, A(2, A(3, 1))) Now n = 1 so I can use the third formula to get A(3, 1) = 2 A(2, A(2, 2)) A(2, A(2-1, A(2, 2-1))) A(2, A(1, A(2, 1))) Use the third formula again: A(2, A(1, 2)) A(2, A(1-1,A(1, 2-1))) A(2, A(0, A(1, 1))) A(2, A(0, 2)) Use the first formula: A(2, 2n) A(2, 2(2) A(2, 4) A(1, A(2, 3)) A(1, A(1, A(2, 2))) A(1, A(1, A(1,A(2, 1)))) A(1, A(1, A(1, 2))) A(1, A(1, A(0, A(1, 1)))) A(1, A(1, A(0, 2))) A(1, A(1, 2(2))) A(1, A(1, 4)) A(1, A(0, A(1, 3))) A(1, A(0, A(0, A(1, 2)))) A(1, A(0, A(0, A(0, A(1, 1))))) A(1, A(0, A(0, A(0, 2)))) A(1, A(0, A(0, 4))) A(1, A(0, 8)) A(1, 16) A(0, A(1, 15)) A(0, A(0, A(1, 14)) lol, this is going to take a while.

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

anonymous
  • anonymous
Anyone know if this is how you do it, or is there a faster way?
anonymous
  • anonymous
Sorry, this is WAY above my level of math :/ wish i could be more help
anonymous
  • anonymous
@amistre64 Do you know if I am doing this right?
amistre64
  • amistre64
it looks like a recurrsion alright
anonymous
  • anonymous
Yeah, that is what it is.
amistre64
  • amistre64
A( m-1, A(m,n-1) ) ; 3,3 A(m,n) = A( 3-1, A(3,3-1) ) A(3,3) =A( 2, A(3,2) ) A(3,2) = A( 2, A(3,1) ) A(3,1) = 2 A(3,2) = A( 2, 2) = A( 1, A(2,1) ) A(3,2) = A( 0, 2 ) = 4 A(3,3) =A( 2, 4 ) etc ....
amistre64
  • amistre64
multivariables seem to be a pain to do by hand, might help to program a simple loop for it
anonymous
  • anonymous
Well I have to show my work for the homework so I'll probably have to write it out. I guess it is basically just a lot of plugging in the numbers over and over again.
anonymous
  • anonymous
Makes sense though, the way this one is going, I bet the A(3,4) will be really long, haha.
amistre64
  • amistre64
if you can determine a pattern :) but ive never really tried for a multivariable
anonymous
  • anonymous
Oh that makes sense. It's like programming an if-then-else loop
amistre64
  • amistre64
yep
anonymous
  • anonymous
Well I guess I could do a simple program that outputs each step and then just copy the results to the paper.
anonymous
  • anonymous
Having never seen anything like this I was like put what in what now? Lol
anonymous
  • anonymous
Ye, that would be faster I guess
anonymous
  • anonymous
Alrighty thanks for the help guys! I'm gonna hit up some python :D
anonymous
  • anonymous
Well I started on the program. I think it will take a little more work to get it to print all the steps. def A(m, n): print "(", m, ", " , n, ")" if m == 0: return (2*n) elif m >= 1 and n == 0: return 0 elif m >= 1 and n == 1: return 2 elif m >= 1 and n >= 2: return (m - 1, A(m, n - 1)) m = input('m: ') n = input('n: ') answer = A(m,n)
anonymous
  • anonymous
And, I don't think it is working quite right yet.
amistre64
  • amistre64
yeah, i was trying to do it in excel ... its tricky at best
anonymous
  • anonymous
oops, missed an A in the return
anonymous
  • anonymous
Here is my output: ( 3 , 3 ) ( 3 , 2 ) ( 3 , 1 ) ( 2 , 2 ) ( 2 , 1 ) ( 1 , 2 ) ( 1 , 1 ) ( 0 , 2 ) ( 2 , 4 ) ( 2 , 3 ) ( 2 , 2 ) ( 2 , 1 ) ( 1 , 2 ) ( 1 , 1 ) ( 0 , 2 ) ( 1 , 4 ) ( 1 , 3 ) ( 1 , 2 ) ( 1 , 1 ) ( 0 , 2 ) ( 0 , 4 ) ( 0 , 8 ) ( 1 , 16 ) ( 1 , 15 ) ( 1 , 14 ) ( 1 , 13 ) ( 1 , 12 ) ( 1 , 11 ) ( 1 , 10 ) ( 1 , 9 ) ( 1 , 8 ) ( 1 , 7 ) ( 1 , 6 ) ( 1 , 5 ) ( 1 , 4 ) ( 1 , 3 ) ( 1 , 2 ) ( 1 , 1 ) ( 0 , 2 ) ( 0 , 4 ) ( 0 , 8 ) ( 0 , 16 ) ( 0 , 32 ) ( 0 , 64 ) ( 0 , 128 ) ( 0 , 256 ) ( 0 , 512 ) ( 0 , 1024 ) ( 0 , 2048 ) ( 0 , 4096 ) ( 0 , 8192 ) ( 0 , 16384 ) ( 0 , 32768 )
anonymous
  • anonymous
lol
anonymous
  • anonymous
I think one of the hardest parts will be getting it to output the results correctly
anonymous
  • anonymous
Any luck with excel? I'm gonna switch to C++ to try to get the output working right.
anonymous
  • anonymous
So here is what I came up with. Ended up using C. #include #include int m; int n; int answer; void PrintA(m,n) { printf("A(%d, %d) = ", m, n); printf("A(%d, A(%d, %d)\n", m-1, m , n-1); } int A(int m, int n) { if(m == 0) return (2*n); else if(m >= 1 && n == 0) return 0; else if(m >= 1 && n == 1) return 2; else if(m >= 1 && n >= 2) PrintA(m,n); return A(m - 1, A(m, n - 1)); } int main() { printf("m: "); scanf("%d", &m); printf("n: "); scanf("%d", &n); answer = A(m, n); printf("Answer: %d\n", answer); return 0; }
anonymous
  • anonymous
Here is what I get for the first one. A(3,3) Obviously the answer is wrong, but all the steps up to the answer should be correct. So I can calculate the answer myself from the last step, which is 4 I think.
1 Attachment
anonymous
  • anonymous
That works fine, now the problem is when I try A(3, 4) although I get the answer to be 0, it outputs for about 30 seconds, so I get like 1000s of lines of output which would be a bit too much to write. lol. Anyway, I'm thinking there must be some way to recognize a pattern in order to get the answer. :/
myininaya
  • myininaya
So yeah I found a pattern for A(3,3) problem when I got to A(1,16) and got the computer output you got.
myininaya
  • myininaya
which i will most likely leave as 2^16
anonymous
  • anonymous
So the stops working?
myininaya
  • myininaya
I seen 2^n*A(1,16-n)
myininaya
  • myininaya
what do you mean stops working?
anonymous
  • anonymous
So how would I use this pattern in finding a solution? mistyped, you said you found a problem earlier.
myininaya
  • myininaya
pattern not a problem i was referring to your problem/question
anonymous
  • anonymous
oh I get it now, lol.
myininaya
  • myininaya
wow yeah it looks like A(3,4) might take longer to find.
anonymous
  • anonymous
Ah right, so we would need a separate pattern for A(3,4) determined by some of the output?
myininaya
  • myininaya
You said you got 0. That is what I got too.
myininaya
  • myininaya
A(3,4) =A(2,A(3,3)) =A(2,2^16) =A(1,A(2,2^16-1)) ------------------ Let's look at A(2,2^16-1) A(2,2^16-1)=A(1,A(2,2^16-2)) There is like a pattern going on we have A(2,2^16-b) b keeps increasing eventually it will get to 2^16 Since this is happening in the n part of A then the output will be 0.
myininaya
  • myininaya
Is this what you were looking for?
anonymous
  • anonymous
Yes I think so, just trying to get my head around it. I think once I look at it for a bit I will understand.
anonymous
  • anonymous
Thanks so much for all the help though! Really appreciate it.
myininaya
  • myininaya
Like A(something bigger than 1,0)=0 eventually A(1,k) will be A(1,0)
myininaya
  • myininaya
And A(1,0)=0
anonymous
  • anonymous
so b will eventually get to 2^16?
myininaya
  • myininaya
yep.
anonymous
  • anonymous
and then it will be 0. I get it now, thank you so much :D
myininaya
  • myininaya
Like because we keep subtracting 1 each time.
myininaya
  • myininaya
I'm not doing all those steps. It is impossible to do all those steps. You have to look for a pattern.
myininaya
  • myininaya
n=2^16 n-1=2^16-1 (n-1)-1=n-2=2^16-2 (n-2)-1=n-3=2^16-3 ....
myininaya
  • myininaya
we keep subtracting 1 from the n before.
anonymous
  • anonymous
right right, exactly, until n becomes 0, then according to the second formula A(3,4) == 0
anonymous
  • anonymous
@myininaya Hi there, could you look over this one more time. According to my teacher, it is impossible to find the second number for A(3,4) by using a computer algorithm. And the students in my class are saying the answer is a really big number and not 0. Like a lot bigger then the number for A(3,3) Do you have any idea where that would be coming from?
myininaya
  • myininaya
Well it looked like the pattern was going toward it being 0. I can look at it again. Did you explain your thinking to the teacher person? Like why did they say the thinking was wrong?
anonymous
  • anonymous
The teacher hasn't looked at my work yet, he was just giving hints to help with the homework, and he said that this part cannot be done with a computer program because it will run out of memory and lose the answer.
anonymous
  • anonymous
I don't really understand why that would happen, but I just want to make sure to get it right since other students are getting really large numbers.
myininaya
  • myininaya
He didn't say a human couldn't do it though right?
anonymous
  • anonymous
No, he said it was possible to do by hand, but not with an algorithm.
myininaya
  • myininaya
Just because a computer doesn't have the space to use an algorithm to compute doesn't mean we don't have the space.
myininaya
  • myininaya
So the answer is still 0
myininaya
  • myininaya
n=2^16 n-1=2^16-1 (n-1)-1=n-2=2^16-2 (n-2)-1=n-3=2^16-3 remember when I wrote this?
myininaya
  • myininaya
2^16 steps is a lot. I don't know if it is too long for a computer or not. But it will actually take longer than 2^16 steps to compute.
anonymous
  • anonymous
Right, so there isn't some sort of pattern we could figure out to get the answer without the steps?
myininaya
  • myininaya
I said it would take longer than 2^16 because we did some other crap before to get there and we still have to do more stuff after that, but the pattern seems to be leading to the answer being zero.
anonymous
  • anonymous
Hmm, well I'll stick with that then. Perhaps my teacher is wrong. :D
myininaya
  • myininaya
What? You said your teacher said it was possible for a human I thought.
myininaya
  • myininaya
"No, he said it was possible to do by hand, but not with an algorithm."
anonymous
  • anonymous
Yeah, but I got 0 with the program I wrote.
myininaya
  • myininaya
So the answer you are saying is not zero?
anonymous
  • anonymous
Which is just a simple recursive function.
anonymous
  • anonymous
That is what I was led to believe by my fellow students and teacher.
myininaya
  • myininaya
So the teacher said the answer isn't 0 and does exist.
anonymous
  • anonymous
No, the teacher didn't say anything about the answer, just that it couldn't be done with a computer, and since I got the same number with I computer 0, as you got by hand, I figured it couldn't be right unless my teacher was wrong.
myininaya
  • myininaya
Can you copy it here? What you put in as the algorithm into your computer? I will try to follow it.
myininaya
  • myininaya
I just want to see if I agree with your algorithm.
myininaya
  • myininaya
Is that it above? The final draft of your program?
myininaya
  • myininaya
maybe you are accidentally getting 0. lol. i don't know.
myininaya
  • myininaya
or
myininaya
  • myininaya
like you did get the right answer with A(3,3)
myininaya
  • myininaya
maybe we can check another one.
myininaya
  • myininaya
Let's look at A(2,5) Use program and let's do it by hand.
myininaya
  • myininaya
darn that is long. lol.
anonymous
  • anonymous
haha, yeah. Runs for around 15 seconds.
anonymous
  • anonymous
that is probably like a 100th of the output there. lol
myininaya
  • myininaya
is the answer always 0 when n>m?
anonymous
  • anonymous
No, for m = 1 and n = 2 I get A(1, 2) = A(0, A(1, 1) Answer: 4
anonymous
  • anonymous
For 2 and 3
1 Attachment
myininaya
  • myininaya
A(1,2)=A(0,A(1,1)) =A(0,2) =2n =2n=2(2) since n=2. okay.did you computer also get 4 for A(1,2)?
anonymous
  • anonymous
Yep
myininaya
  • myininaya
hmmm... I get 16 by hand for A(2,3)
anonymous
  • anonymous
Yeah, computer seems to be doing it right.
anonymous
  • anonymous
Well I guess it is very possible that my teacher was wrong, idk.
myininaya
  • myininaya
I don't know. There is a possibility I'm wrong. There is always a chance for that.
anonymous
  • anonymous
Well there is a lot less possibility that you are wrong then I am wrong, so I guess I'll stick with that. :P
myininaya
  • myininaya
I don't see anything wrong with your program. Maybe for most computers the algorithm will run too long. Not sure.
anonymous
  • anonymous
Hard to tell, do you have time to look at one more thing really really quick?
myininaya
  • myininaya
ok i will look no guarantees I will be able to help but i certainly will try
anonymous
  • anonymous
http://openstudy.com/study#/updates/5276cbf2e4b0275c53855b4a Alright, thanks, wish I could give you another medal :/

Looking for something else?

Not the answer you are looking for? Search for more explanations.