|
Re: how to find a mathematical formula for this recursion??
Quote:
|
Originally Posted by transgalactic
in the end we need to come to the formula
b(n,c)=c+(n+2)*2^(n-1)
|
Forum etiquette issues first: - The relevant information to this problem is spread across multiple threads. Since your goal is to persuade people to use their free time to answer your questions, it would be polite to present all necessary information in the same thread, preferably in the initial post starting the thread. Otherwise, you run the risk of being ignored, & the Admin's may even potentially delete the thread altogether. Recognize that the people reading this forum are spread across the world. No one can read your mind. Clarity is a virtue.
- Code which is posted should be bracketed with a [c] tag before the code, & a [/c] tag afterwards to preserve formating & color code keywords & identifiers. This is a simple requirement, & I have seen the Admin's delete messages because posters don't follow this request. Again, your goal is to persuade others to spend their time answering your questions. State your question(s) clearly & make any posted code presentable.
- It would be worth your time to study the following on how to ask smart questions in technical forums:
http://www.catb.org/~esr/faqs/smart-questions.html
Much of it is common sense, but as we find here, common sense isn't very common.
Having said this, I dug up your initial code & modified it to the following:
#include <stdio.h>
#include <stdarg.h>
int k = 0;
int line = 0;
void output(char*, ...);
int a(int n,int count) {
int i;
int t = count;
++k;
output("start a(%d, %d):\n", n, t);
for(i = 0; i < n; i++)
count = a(i, count);
output("end a(%d, %d) = %d\n", n, t, count + 1);
--k;
return count + 1;
}
int b(int n,int count) {
int i;
int t = count;
++k;
output("start b(%d, %d):\n", n, t);
count = a(n, count);
for (i = 0; i < n; i++)
count = b(i, count);
output("end b(%d, %d) = %d\n", n, t, count);
--k;
return count;
}
int main () {
int i;
for (i = 0; i < 4; i++)
printf("%3d. b(%d, 0) = %d\n", ++line, i, b(i, 0));
return 0;
}
void output(char *fmt, ...) {
int i;
printf("%3d.", ++line);
for (i = 0; i < k; i++)
printf("\t");
va_list args;
va_start(args, fmt);
vprintf(fmt, args);
va_end(args);
}
...which upon execution yields the following results:
Code:
1. start b(0, 0):
2. start a(0, 0):
3. end a(0, 0) = 1
4. end b(0, 0) = 1
5. b(0, 0) = 1
6. start b(1, 0):
7. start a(1, 0):
8. start a(0, 0):
9. end a(0, 0) = 1
10. end a(1, 0) = 2
11. start b(0, 2):
12. start a(0, 2):
13. end a(0, 2) = 3
14. end b(0, 2) = 3
15. end b(1, 0) = 3
16. b(1, 0) = 3
17. start b(2, 0):
18. start a(2, 0):
19. start a(0, 0):
20. end a(0, 0) = 1
21. start a(1, 1):
22. start a(0, 1):
23. end a(0, 1) = 2
24. end a(1, 1) = 3
25. end a(2, 0) = 4
26. start b(0, 4):
27. start a(0, 4):
28. end a(0, 4) = 5
29. end b(0, 4) = 5
30. start b(1, 5):
31. start a(1, 5):
32. start a(0, 5):
33. end a(0, 5) = 6
34. end a(1, 5) = 7
35. start b(0, 7):
36. start a(0, 7):
37. end a(0, 7) = 8
38. end b(0, 7) = 8
39. end b(1, 5) = 8
40. end b(2, 0) = 8
41. b(2, 0) = 8
42. start b(3, 0):
43. start a(3, 0):
44. start a(0, 0):
45. end a(0, 0) = 1
46. start a(1, 1):
47. start a(0, 1):
48. end a(0, 1) = 2
49. end a(1, 1) = 3
50. start a(2, 3):
51. start a(0, 3):
52. end a(0, 3) = 4
53. start a(1, 4):
54. start a(0, 4):
55. end a(0, 4) = 5
56. end a(1, 4) = 6
57. end a(2, 3) = 7
58. end a(3, 0) = 8
59. start b(0, 8):
60. start a(0, 8):
61. end a(0, 8) = 9
62. end b(0, 8) = 9
63. start b(1, 9):
64. start a(1, 9):
65. start a(0, 9):
66. end a(0, 9) = 10
67. end a(1, 9) = 11
68. start b(0, 11):
69. start a(0, 11):
70. end a(0, 11) = 12
71. end b(0, 11) = 12
72. end b(1, 9) = 12
73. start b(2, 12):
74. start a(2, 12):
75. start a(0, 12):
76. end a(0, 12) = 13
77. start a(1, 13):
78. start a(0, 13):
79. end a(0, 13) = 14
80. end a(1, 13) = 15
81. end a(2, 12) = 16
82. start b(0, 16):
83. start a(0, 16):
84. end a(0, 16) = 17
85. end b(0, 16) = 17
86. start b(1, 17):
87. start a(1, 17):
88. start a(0, 17):
89. end a(0, 17) = 18
90. end a(1, 17) = 19
91. start b(0, 19):
92. start a(0, 19):
93. end a(0, 19) = 20
94. end b(0, 19) = 20
95. end b(1, 17) = 20
96. end b(2, 12) = 20
97. end b(3, 0) = 20
98. b(3, 0) = 20
As can be seen, my modifications highlight each level of recursion.
Looking at the three more important values, b(1, 0), b(2, 0), & b(3, 0): - First, b(1, 0):
Code:
6. start b(1, 0):
7. start a(1, 0):
8. start a(0, 0):
9. end a(0, 0) = 1
10. end a(1, 0) = 2
11. start b(0, 2):
12. start a(0, 2):
13. end a(0, 2) = 3
14. end b(0, 2) = 3
15. end b(1, 0) = 3
16. b(1, 0) = 3
Recognize that the important statements in function b() are the following:
count = a(n, count);
for (i = 0; i < n; i++)
count = b(i, count);
As noted elsewhere, a(n, count) implements the expression 2^n + count. It appears that each level of recursion a(n, count) results in a multiplication by 2 when n is non-zero. This is seen in lines 7-10.- Line 9 shows where execution is coming out of one level of recursion for a(). This represents 2^0 = 1.
- Line 10 shows where execution is coming out of the first call to a(). Coupled together, this represents 2^0 * 2^1 = 2 or 2^n since n is 1.
The call to b(0, 2) in lines 11-14 shows n being zero, & count being non-zero. This is where function b()'s for-loop is being executed. Because a() is being called with n as 0 & count being non-zero, the value 3, line 14 represents addition. Note that these values are cumulative.
The result is lines 7-14 is the statement b(1, 0) = 2^1 + 2^0 = 2 + 1 = 3. Generalizing, it appears at this point that b(n, 0) = 2^n + 2^(n - 1) when n = 1. - Second, b(2, 0):
Code:
17. start b(2, 0):
18. start a(2, 0):
19. start a(0, 0):
20. end a(0, 0) = 1
21. start a(1, 1):
22. start a(0, 1):
23. end a(0, 1) = 2
24. end a(1, 1) = 3
25. end a(2, 0) = 4
26. start b(0, 4):
27. start a(0, 4):
28. end a(0, 4) = 5
29. end b(0, 4) = 5
30. start b(1, 5):
31. start a(1, 5):
32. start a(0, 5):
33. end a(0, 5) = 6
34. end a(1, 5) = 7
35. start b(0, 7):
36. start a(0, 7):
37. end a(0, 7) = 8
38. end b(0, 7) = 8
39. end b(1, 5) = 8
40. end b(2, 0) = 8
41. b(2, 0) = 8
Again, lines 18-25 ultimately displays the value 4 which represents 2^2 = 2^n given that n is 2.
Lines 26-29 & 30-39 represent the two iterations through function b()'s for-loop.- Lines 26-29 represents the first pass through function b()'s for-loop. Line 29 shows that the cumulative total is incremented by 1 which represents 2^0.
- Lines 30-39 represent the second iteration through b()'s for-loop.
- Note that line 30 begins a new recursion block. Function a() (indicating multiplication...) is called, & the result in line 34 is that the cumulative total has been incremented by 2. This change represents 2^1.
- Lines 35-38 shows the total incremented by 1. This is equivalent to 2^0.
The sum of these terms is b(2, 0) = 2^2 + (2^0) + (2^1 + 2^0) = 4 + (1) + (2 + 1) = 8.
Most important, the above expression can be rearranged as 2^2 + 2^1 + 2 * 2^0. This represents b(n, 0) = 2^n + 2^(n - 1) + n * 2^(n - 2) when n is 2. - Lastly, b(3, 0):
Code:
42. start b(3, 0):
43. start a(3, 0):
44. start a(0, 0):
45. end a(0, 0) = 1
46. start a(1, 1):
47. start a(0, 1):
48. end a(0, 1) = 2
49. end a(1, 1) = 3
50. start a(2, 3):
51. start a(0, 3):
52. end a(0, 3) = 4
53. start a(1, 4):
54. start a(0, 4):
55. end a(0, 4) = 5
56. end a(1, 4) = 6
57. end a(2, 3) = 7
58. end a(3, 0) = 8
59. start b(0, 8):
60. start a(0, 8):
61. end a(0, 8) = 9
62. end b(0, 8) = 9
63. start b(1, 9):
64. start a(1, 9):
65. start a(0, 9):
66. end a(0, 9) = 10
67. end a(1, 9) = 11
68. start b(0, 11):
69. start a(0, 11):
70. end a(0, 11) = 12
71. end b(0, 11) = 12
72. end b(1, 9) = 12
73. start b(2, 12):
74. start a(2, 12):
75. start a(0, 12):
76. end a(0, 12) = 13
77. start a(1, 13):
78. start a(0, 13):
79. end a(0, 13) = 14
80. end a(1, 13) = 15
81. end a(2, 12) = 16
82. start b(0, 16):
83. start a(0, 16):
84. end a(0, 16) = 17
85. end b(0, 16) = 17
86. start b(1, 17):
87. start a(1, 17):
88. start a(0, 17):
89. end a(0, 17) = 18
90. end a(1, 17) = 19
91. start b(0, 19):
92. start a(0, 19):
93. end a(0, 19) = 20
94. end b(0, 19) = 20
95. end b(1, 17) = 20
96. end b(2, 12) = 20
97. end b(3, 0) = 20
98. b(3, 0) = 20
Again, line 58 shows the cumulative total as 8. Seeing that function a() recursed three levels to arrive at this value supports the idea that each level of recursion represents multiplication by 2 with function a().
Lines 59-62, 63-72, 73-96 shows the three iterations through function b()'s for-loop.- Lines 59-62 represents the first pass through b()'s for-loop, & shows an increment of the cumulative total by 1. This is equivalent to 2^0.
- LInes 63-72 displays the second pass through the for-loop.
- Lines 64-67 show an increment by 2. This represents 2^1.
- Lines 68-71 adds 1 to the cumulative total. This represents 2^0.
- Lines 73-96 shows the last pass through b()'s for-loop.
- Lines 74-81 shows a change of 4 which equates to 2^2.
- Lines 82-85 shows a change of 1 which is the same as 2^0.
- Lines 87-90 shows a change of 2 which is equivalent to 2^1.
- Lines 91-94 shows a change in the cumulative total by 1 which can be represented by 2^0.
Summing all terms, b(3, 0) = 2^3 + (2^0) + (2^1 + 2^0) + (2^2 + 2^0 + 2^1 + 2^0) which can be reduce to 2^3 + 2^2 + 2 * 2^1 + 4 * 2^0. Generalizing, this becomes b(n, 0) = 2^ n + 2^( n - 1) + ( n - 1) * 2^( n - 2) + ( n + 1) * 2^( n - 3) when n is 3.
Reviewing the results thus far: - b(n, 0) = 2^n + 2^(n - 1) when n = 1
- b(n, 0) = 2^n + 2^(n - 1) + n * 2^(n - 2) when n is 2
- b(n, 0) = 2^n + 2^(n - 1) + (n - 1) * 2^(n - 2) + (n + 1) * 2^(n - 3) when n is 3
Obviously, b() implements a polynomial equation, & with each iteration, the equation is refined. It also appears that a new term is added with each new test case. It may be that the polynomial gets another term when testing b(4, 0). Maybe not, but this is an exercise left to the reader. Additional test cases need to be analyzed until the generalized equation is stable. What is provided above may be final, or it might not be. Nevertheless, it is a good start. It doesn't quite match what you state at the beginning, but I'm pretty confident of my solution thus far.
Finally, don't take this discussion as being indicative of the level of support you will always get on this forum site. It isn't. You will not get answers handed so generously to you, & you will not get answers at all unless you can articulate questions well & provide supporting evidence.
I answered this question to this depth out of nominal interest. I have put enough time into it, I've satisfied my curiosity, & I suspect it is correct to a large extent. Any other details which may be missing are left to you to fill in yourself.
Quote:
i cant completely understand how to get there
and how to come to a formula from that expression
|
- Study. Study long & hard.
- Test & test again.
- Execute, change, & extend the code. Computers & software are simply tools. Use them.
- Write down what you know & attempt to generalize the results. It's simply an exercise in inductive reasoning.
- Wash, lather, & rinse. Repeat.
Last edited by ocicat : 10-Oct-2008 at 14:29.
|
09-Oct-2008, 15:47
Accepted for Ph.D. program by crystalattice
Similar Threads
