You can use dynamic programming for this.
(If you have no idea about it, read it on
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg ).
Maintain array dp[3][3][7]. Let the keypad be key[3][3]
dp[i][j][k] -> i,j: indices to identify number, k:how many numbers of length
k+1 possible
Let f(n,x) be the number of ways of tracing out a number of length x
starting at n.
By symmetry, f(1,x)=f(3,x)=f(7,x)=f(9,x)
Simarly f(4,x)=f(2,x)=f(8,x)=f(6,x)
We then just need a reacurrence relation.
f(1,x)=f(5,x-1)+f(9,x-1)
f(2,x)=f(4,x-1)+f(6,x-1)=2*f(2,x-1)
f(5,x)=f(1,x-1)+f(3,x-1)+f(7,x-1)
Hi-
I recently ran across a programming problem that I didn't even know how
to begin to solve. I'm just now learning algorithms, and I imagine
some type of algorithm is required. The problem is as follows:
You are given a phone dial pad that looks like this:
1 2 3
4 5 6
7 8 9
Supposing that y
You need to have a pointer to the head ... the next node will be np[head]
XOR nil ...
On 12/24/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]>
wrote:
but wait a minute, how can I get A or B if I only know C?
>
--~--~-~--~~~---~--~~
You received this message becau
but wait a minute, how can I get A or B if I only know C?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from
Karthik Rathinavelu wrote:
If
A xor B = C,
then
C xor A = B and
C xor B = A
You can use these formulae to implement this ...
That's the point! What a shame I don't know about that!
--~--~-~--~~~---~--~~
You received this message because you are subscribed to
If
A xor B = C,
then
C xor A = B and
C xor B = A
You can use these formulae to implement this ...
On 12/23/06, [EMAIL PROTECTED] <[EMAIL PROTECTED]>
wrote:
I'm reading MIT's book "Introduction to Algorithms".
The following is one of the excercises from it:
<
10.2-8
Explain how to implement
I'm reading MIT's book "Introduction to Algorithms".
The following is one of the excercises from it:
<
10.2-8
Explain how to implement doubly linked lists using only one pointer
value np[x] per item instead of the usual two (next and prev). Assume
that all pointer values can be interpreted as k