Consider an n × n matrix A = (aij), each of whose elements aij is a nonnegative real number, and suppose that each row and column of A sums to an integer value. We wish to replace each element aij with either ˥ aij ˥ or ˩ aij ˩ without disturbing the row and column sums. Here is an example:
Write a program by defining an user defined function that is used to produce the rounded matrix as described in the above example. Find out the time complexity of your algorithm/function.
Program
#include <stdio.h>
#include <time.h>
int main() {
int n;
printf("\nEnter matrix edge: ");
scanf("%d", & n);
float arr[n][n];
int int_array[n][n];
float column_sum[10] = {0}, row_sum[10] = {0};
printf("Enter %dx%d matrix: \n", n, n);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%f", & arr[i][j]);
row_sum[i] += arr[i][j] - ((int)(arr[i][j]));
column_sum[j] += arr[i][j] - ((int)(arr[i][j]));
int_array[i][j] = (int) arr[i][j];
}
}
clock_t start,end;
double total_cputime;
start=clock();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (row_sum[i] > 0.000001 && column_sum[j] > 0.000001)
{
int_array[i][j] += 1;
row_sum[i]--;
column_sum[j]--;
}
}
}
end=clock();
total_cputime=((double)(end-start))/CLOCKS_PER_SEC;
printf("\n\n");
printf("New array:\n");
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
printf("%d ", int_array[i][j]);
}
printf("\n");
}
printf("\nTotal time taken: %lf", total_cputime);
return 0;
}
Output:
Enter matrix edge: 4
Enter 4x4 matrix:
10.9 2.5 1.3 9.3
3.8 9.2 2.2 11.8
7.9 5.2 7.3 0.6
3.4 13.1 1.2 6.3
New array:
11 3 1 9
4 9 3 11
8 5 7 1
3 13 1 7
Total time taken: 0.000003
Tags:
DAA