I found a mothod.
we can thange the data to zeros row by row.
how to change a row of datas to zeros:
1) change the a row of datas to be same first
2) do many enough B operation on the row, until the datas is zeros
how to change a row of datas to same:
let MAX is the maximum data in the row
let MIN is the minimum data in the row
if MAX>=2*MIN do a A operation on the colum the MIN data in.
else do a B operation on the row
do this until the all data in the row is same
the following is a my test program:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define R 5
#define C 5
#define MAX_NUM 10 // if this value is too large,
// the data in matrix will be overflow
// the matrix
int d[R*C];
int num_a=0; // the total num of a operation
int num_b=0; // the total num of b operation
// some helper macro for 2d array
#define N(a) (sizeof(a)/sizeof(a[0]))
#define D(i,j) (d[i+j*R])
// print all data in current matrix
void print_matrix()
{
int i;
int j;
printf("Data:\n");
for(i=0;i<R;i++)
{
for(j=0;j<C;j++)
{
printf("%5d",D(i,j));
}
printf("\n");
}
}
// do A operation
void A(int c)
{
int i;
printf("do A, %d\n", c);
for(i=0;i<R;i++)
D(i,c)<<=1;
print_matrix();
num_a++;
}
// do B operation
void B(int r)
{
int i;
printf("do B, %d\n", r);
for(i=0;i<C;i++)
D(r,i)--;
print_matrix();
num_b++;
}
int main()
{
int i;
int j;
// generate all data
srand(time(0));
for(i=0;i<N(d);i++)
{
// the data are positive integers, not have zeros
d[i]=rand()%MAX_NUM+1;
}
//
print_matrix();
// archieve the work row by row
for(j=0;j<R;j++)
{
int max;
int c_max;
int min;
int c_min;
// find the maximum data and minimum data in this row
do
{
max=0;
min=INT_MAX; // the max value
for(i=0;i<C;i++)
{
if(D(j,i)>max)
{
max=D(j,i);
c_max=i;
}
if(D(j,i)<min)
{
min=D(j,i);
c_min=i;
}
}
printf("max=%d min=%d\n",max,min);
if(max==min)
break;
if(min*2<=max)
A(c_min);
else
B(j);
}while(1);
for(i=0;i<max;i++)
B(j);
}
printf(" total A operation steps %d\n", num_a);
printf(" total B operation steps %d\n", num_b);
printf(" total steps %d\n",num_a+num_b);
return 0;
}
On 8月26日, 上午2时43分, ankur aggarwal <[email protected]> wrote:
> I've always wanted to feel the excitement in these interviews. I got a
> chance, and I liked it.
>
> Here is the question:
>
> You are given a matrix: r rows, c cols. r x c matrix.
>
> Now they all have positive integers. Assume that the computer has no
> overflow, it can store all possible integer values.
>
> Now there are only two operations you can perform on the matrix:
>
> a. Multiply one whole column (of size r elements) by 2 aij = aij * 2
> b. Decrement a whole row (of size c elements) by 1. aij = aij - 1
>
> Now you are required to find out if it's possible with these operations to
> convert this matrix into the O matrix. (one with all zeroes in it.)
>
> If so, how do you solve it? Or when do you decide to terminate?
>
> give the algo..
> not the code.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
