Re: [algogeeks] Re: how to optimally compute a matrix (nXn) to the power of k?
You can try like this
#include stdio.h
#include string.h
#define N 3
void copy(int A[N][N],int B[N][N])
{
int i,j;
for(i=0;iN;i++)
for(j=0;jN;j++)
A[i][j]=B[i][j];
}
void mul(int A[N][N],int B[N][N],int M[N][N])
{
int i,j,k;
for(i=0;iN;i++)
for(j=0;jN;j++) {
M[i][j]=0;
for(k=0;kN;k++)
M[i][j]+=A[i][k]*B[k][j];
}
}
void exp(int M[N][N],int n)
{
int R[N][N];
int A[N][N];
int B[N][N];
int i;
memset(R,0,sizeof(R));
for(i=0;iN;i++)
R[i][i]=1;
while(n0) {
if(n%2==1) {
copy(A,R);
mul(M,A,R);
}
n=n1;
copy(A,M);
copy(B,M);
mul(A,B,M);
}
copy(M,R);
}
int main()
{
int i,j;
int M[N][N];
int n;
for(i=0;iN;i++)
for(j=0;jN;j++)
scanf(%d,M[i][j]);
scanf(%d,n);
exp(M,n);
for(i=0;iN;i++)
for(j=0;jN;j++)
printf(%d%c,M[i][j],j==N-1?'\n':' ');
return 0;
}
--
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 this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: how to optimally compute a matrix (nXn) to the power of k?
time complexity is (cost of multiplication)*log(n) -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: how to optimally compute a matrix (nXn) to the power of k?
Yes its running fine at gcc 4.3.2 . And it might show warning in that case just change the name of the function exp(). -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: how to optimally compute a matrix (nXn) to the power of k?
Yes sure , we know if A B C are matrices of same dimension then Ax(BxC)=(AxB)xC So now what SAMM is saying i.e normal exponential of any number can be applied in case of matrix expo too and the same thing I too did but using loop without recursive fashion. I hope its clear now . -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] MS
Better go through following link , its explained nicely their. http://www.ihas1337code.com/2011/01/find-k-th-smallest-element-in-union-of.html -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] X-AmazoN
I don't think so that probability would be exact 1/1000 . suppose number is ( a9 a8 a7 a6 a5 a4 a3 a2 a1 a0) where a0 is least and a9 is most significant bit then you can generate each of the bit ai using given bit generator but if but at a time (a9 , a8 , a7 , a6 , a5 , a3 ) and any other bit are set together then number would exceed given limit 1000 which we don't want . so dave's solution generate numbers with probability 1/(2^n) where n is ceil(log2(b-a+1)) so 1/2^10 = 1/1024 -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] X-AmazoN
but suppose you have to generate numbers between [1,513] then also it would generate numbers them each with probability 1/1024 which could make a big difference and I feel the above solution to be incorrect . May be we could think of a better one . -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] X-AmazoN
@Surender Your solution in correct one . -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Counting the ways.
It can be done in O(2^n) -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Puzzle
suppose bottom 4 teams have won least matches and upper 4 teams have won equal number of matches ... 1 - x 2 - x 3 - x 4 - x 5 - 6 6 - 4 7 - 2 8 - 0 total matches are 56 and let upper four teams have won x matches each so x = (56-(6+4+2+0))/4 x = 11 so in this way to ensure qualification to semi finals team must win 11 matches ... -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Puzzle
No , you are wrong .. problem statement says how many matches should a teams win to ensure its qualification , their no word like minimum or maximum ... 8 gets wrong if following situation arises 1 - 9 2 - 9 3 - 9 4 - 9 5 - 8 6 - 6 7 - 4 8 - 2 -- 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
