C - Review II 29,30,31

29. I have a lower triangular matrix, all the values above the diagonal are zeros. I want to store my array in an efficient format, such that i will not store upper triangular part of the matrix.

Give me a piece of code to store and retrieve the values from new array.

Note : simulate this matrix in one dimensional array. Find formulas for storing and retrieving.


Answer:

Matrix will be in this fashion

x 0 0 0 .....0

x x 0 0 .....0

x x x 0 ......0

x x x x x ...x


where x can be any value

I will store in single dimensional array as follows (Row Major order)

(0,0) (1,0) (1,1) (2,0) (2,1) (2,2) (3,0).......

Retrieval formula for this is

a[i][j] will be stored at i * (i-1)/2 +j


Column major order is

a[i][j] will be stored at j * (j-1)/2 +i


30. Given a string s1 and a string s2, write a snippet to say whether s2 is a rotation of s1 with a single call to function strrot.

Given s1 = ABCD and s2 = CDAB, return true,
Given s1 = ABCD, and s2 = ACBD , return false.


Solution O(n^2)

#include"stdio.h"

#include"string.h"

main()

{

char a[100],b[100],temp;

int i,j,n;

gets(a);

gets(b);

n=strlen(a)-1;

for(i=0;i<=n;i++)

{

if(!strcmp(a,b)) //strcmp returns 0 if they are same

{

printf("true");

return 0;

}

temp=b[0];

for(j=1;j<=n;j++)

b[j-1]=b[j];

b[n]=temp;

}

printf("false");


}


Another solution is O(n)


#include"stdio.h"

#include "string.h"

main()

{

char a[100],b[100];

gets(a);

gets(b);

strcat(a,a);

if(strstr(a,b)==NULL) // strstr checks whether string b is substring of a or not

printf("false");

else

printf("true");


}

Q. Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes?

Solution:

marking 1 minute man as A

2 minute man as B

5 minute man as C

10 minutes man as D


ABCD __________________ NONE total time taken :0

CD ____________________AB total time taken : 2

CDA ____________________B total time taken 2+1 = 3

A ____________________CDB total time taken 3+10 = 13

AB ____________________CD total time taken 13+2 = 15

____________________ABCD total time taken 15+2 = 17