ARRAY ORDER REVERSAL

CONTENT

• AIM
  


• PROBLEM DESCRITION
  


• ALGORITHM DISCRIPTION
  


• IMPLIMENTATION
  


• APPLICATION
  

AIM:

WE HAVE TO REVERSE THE NUMBERS IN THE PROBLEM GIVEN

PROBLEM DISCRIPTION

REVERSAL ORDER MEANS JUST REVERSE THE NUMBER. WE HAVE THE NUMBERS IN ORDER OF 1,2,3,4,5,6,7

MEANS THE REVERSE OF THE NUMBERS ARE 7,6,5,4,3,2,1.

WE TAKE THIS AS AN EXAMPLE.

1

2

3

4

5

6

7

N=7 WE HAVE TO INTIALISE THE VALUE OF I IS1.

R IS THE NUMBER OF SWAPING.

WE HAVE CALCULATE R VALUE R=N/2.

A [1] <=> A [7]

A [2] <=> A [6]

A [3] <=> A [5]

A [4] <=> A [4]

I=1 INCREASE THE VALUE. N IS DECREASE VALUE.

WE HAVE ACHIVE ONLY ONE VARIABLE USE BOTH RIGHT & LEFT SIDE.

SO THE FORMULA IS N=N-I+1.

N=7-1+1=7

N=7-2+1=6

N=7-3+1=5

N=7-4+1=4

N=7-5+1=3

N=7-6+1=2

N=7-7+1=1

ALGORITHM DESCRIPTION

READ THE VALUES

INITIALIZ THE I VALUE

FIND THE NO OF SWAP

SUBSTUTE THE FORMULA N=N-I+1.

COLECT THE VALUES AND STORED

STOP THE PROCESS.

IMPLEMENTATION:

#INCLUDE<STDIO.H>

#INCLUDE<CONIO.H>

VOID MAIN ( )

{

INT A [100], T, R, I, N;

PRINTF (“ENTER THE VALUES’);

SCANF (“%D”, &N);

FOR (I=0; I<=N; I++)

R=N/2;

FOR (I=0; I<=R;I++)

{

T=A [I];

A [I] = A [N-I+1];

A [N-I+1] =T;

}

FOR (I=1;I<=N;I++)

PRINTF (“%D “, &D [I]);

}

IF ARRAY IS STARTING WITH 0 TH INDEX IT IS NOT WORK.

N=8 WE HAVE TO INTIALISE THE VALUE OF I IS 0.

R IS THE NUMBER OF SWAPING.

WE HAVE CALCULATE R VALUE R= (N+1)/2.

A [0] <=> A [7]

A [1] <=> A [6]

A [2] <=> A [5]

A [3] <=> A [4]

I=0 INCREASE THE VALUE. N IS DECREASE VALUE.

WE HAVE ACHIVE ONLY ONE VARIABLE USES BOTH RIGHT & LEFT SIDE.

SO THE FORMULA IS N= N-I.

N=7-0=7

N=7-1=6

N=7-2=5

N=7-3=4

N=7-4=3

N=7-5=2

N=7-6=1

PROGRAM FOR STARTING INDEX 0:

#INCLIDE<STDIO.H>

#INCLUDE<CONIO.H>

VOID MAIN ( )

{

INT A [100], T, R,I,N;

PRINTF (“ENTER THE VALUES’);

SCANF (“%D”, &N);

FOR (I=0; I<=N; I++)

R=N/2;

FOR (I=0; I<=R; I++)

{

T=A [I];

A [I] = A [N-I];

A [N-I] =T;

}

FOR (I=1; I<=N; I++)

PRINTF (“%D “, &D [I]);

}

APPLICATION:

SORTING IN MATHEMATICAL.

MATRIX MALTIPLICATION

re

REMOVAL OF DUPLICATES FROM ORDEREDARRAY

Problem definition: To design an algorithm for removal of duplicates using array.

Problem description:

We can use array with duplicates and also array without duplicates.In both of this we can use sorted array with duplicates and sorted array without duplicates.

• Two methods:

*Array without duplicates.

*Array with duplicates.

• Two types of condition to compare the given two elements:

(1).i=1; a[i]=a[i+1];

->In this type we assign that the comparison is between the adjacent elements.

->And also this type may have the range of values in the outer bound.

(2).i=2; a[i-1]=a[i];

->In this type we assign that the current i index is compared with (i-1)th index.

->This part also have the range of values and it is supply within the array.

->Comparing with this two type of range of values (2) type of values is best choice for doing removal of duplicates.

• Purpose of usage the condition(i<n) instead of i<=n:

->Though (i<=n) condition is satisfied,no need to use this condition because that one value is count in out of range area.So,we can use the condition(i<n).

(Eg):n=3,i=2.

->Here i<n is condition is more applicable.

@.Explanations:

(1).Array without duplicates:

Consider an (eg): 10 20 30 40 50

->While comparing the elements if they are equal then it is duplicate element.Orelse if the element is not equal then update the i value after that it move on to next comparison.

(1a) Necessary steps:

->Initialize i=2;

->Check condition(i<n&&a[i-1]!=a[i])

->If it is satisfy then update the I value.

i=2

I (1). (eg) 10 _ 20 30 40 50

_ ( comparison symbol)

Here condition is true .So,there is no duplicate element,update the i value.

i=3

I(2).10 20 _ 30 40 50

Here condition is true .So,there is no duplicate element,update the i value.

i=4

I(3).10 20 30 _ 40 50

Here condition is true .So,there is no duplicate element,update the i value.

i=5

I(4).10 20 30 40 _ 50

If i is reach the last element the comparison is not done for the 4 &5 element.

So ,we have include this coding during ‘array without duplicates’:

->a[i-1]!=a[i]

->if this condition is satisfied then i is incremented to 6.

->J=i-1;//this above 6 is in out of range of array values.so,decrement the i value and assign it to ‘j’ value.

Then the result is:10 20 30 40 50

• (2).sorted array with duplicates:

Consider an (eg): 20 30 40 40 40 50

->While comparing the elements if they are equal then it is duplicate element.Orelse if the element is not equal then update the i value after that it move on to next comparison.

(2a)necessary steps:

->Initialize same as i=2;

->Then check (a[i-1]!=a[i]&&i<n).

->If it is satisfy my condition i++ the index.

i=2

I(1).20 _ 30 40 40 40 50

The condition is true because the comparing element is not equal.then update the i value.

i=3

I(2).20 30 _ 40 40 40 50

The condition is true because the comparing element is not equal.then update the i value.

i=3

I(3).20 30 40 _ 40 40 50

->The condition is false because the comparing element is equal.then no update here. It move on to next comparison

->Here we have to maintain the variable j is a unique index that have only the element which are not duplicated.It move on to next comparison.

->J=i-1//it assign the previous element which are not duplicate element by using loop.

j i=3

I(4).20 30 40 40 _ 40 50

->The condition is false because the comparing element is equal.then no update here. It move on to next comparison.

j i=4

I(5).20 30 40 40 40 _ 50 -> (1)

The condition is true because the comparing element is not equal.then update the i value.

j

20 30 40 40/50 ||40 50|| -> (2)

|| || ->virtual value.

/ -> overwrite the value.

->Here no change is happen then j (unique index) is update.

->Overwritten the last element in the place of recent j variable.(40/50).

->This means the duplicate value is removed from array.

->Then finally result is:20 30 40 50.

• Program:

Void main()

{

Int a[100],i,j,n;

Scanf(“%d”,&n);

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

Scanf(“%d”,&a[i]);

i=2;

while(i<n&&a[i-1]!=a[i])

i++;

if(a[i-1]!=a[i])

i++;

j=i-1;

while(i<n)

{

i++;

if(a[i-1]!=a[i])

{

j++;

a[j]=a[i];

}

}

n=j;

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

printf(“%d”,a[i]);

}

Applications:

#Data compression

#Text processing problems.

v.gokulapriya

PARTITIONING AN ARRAY

PROBLEM DEFINITION:

To partitioning an array element in a given set.

PROBLEM DESCRIPTION:

To divide an array element based on some constrains and some rules.Given a randomly ordered array of n elements,partition the elements into two subsets such that elements ≤x are in one subset and elements >x are in the other subset.

ALGORITHM DEVELOPMENT:

94 64 14 74 26 7

It is random because array element are arranged randomly so,we are going to portioned the element based on the 1^st element.

Input: 44 94 64 14 74 26 7

Output: 14 7 26 44 74 64 94

Here, we portioned is based on 44. The left hand side element must be less than or equal to 44 at the same time and right handside element must be greater than 44.

i→updated when elements is < first value.

j→updated when elements j> first value.

Whatever element in LHS or RHS must be in sorted from according to the rule.

↓i ↓j

44 94 64 14 74 26 7

I am going to maintain i as the second element and j going to be the last element.If the 2^nd no is greater than 1^st no then it must be shifted to some another place.I am going to compare the jth element.

(ie) 94>44→swap

↓i ↓j

44 94 64 14 44 26 7

if the index is not updated.

7<44 Because it is less than 44.

If the condition is true then,

↓j

44 94 64 74 26 7

During my comparision these two no’s are not updated, so, am going to swap the no.

↓i ↓j

44 7 64 14 74 26 94

after swapping it must be updated for next index

↓i ↓j

44 7 64 14 74 26 94

64>44→swap has to be done.so,I am not going to update my index.

↓i ↓j

44 7 64 14 74 26 94

26<44→swap has to be done.

↓i ↓j

44 7 64 14 74 26 94

swap i and j→values.

↓i ↓j

44 7 26 14 74 64 94

next index.

↓i ↓j

44 7 26 14 74 64 94

14<44→update i.

↓i↓j

44 7 26 14 74 64 94

I have to stop my index when a greater no came.(ie) 44.

↓j ↓j

74>44

447 26 12 74 64 94

My index is updated.My index is done when i<j.Then condition wont stastified.so,i came out of the loop.

Swap 0^th element with jth element,because 4<3 so it is false.

14 7 26 44 74 64 94

IMPLEMENTATION:

Main()

{

int a[10],i,j,t,n;

scanf(“%d”,&n);

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

scanf(“%d”,&a[i]);

i=1;

j=n-1;

while(i<j)

{

while(a[i]<a[0])

i++;

while (a[j]>a[0])

j--;

t=a[i];

a[i]=a[j];

a[j]=t;

}

t=a[0];

a[0]=a[j];

a[j]=t;

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

printf(“%”d,a[i]);

}

DESIGN AND ANALYSIS OF ALGORITHM

GENERATION OF THE FIBONACCI SEQUENCE

GENERAL PROPERTIES OF AN ALGORITHM

1.THERE SHOULD BE A FINITE NUMBER OF STEPS.
2.EACH STEP IS EXECUTABLE WITHOUT ANY AMBIGUITY.
3.EACH STEP IS EXECUTABLE WITHIN IN A FINITE AMOUNT OF TIME, USING A FINITE AMOUNT OF MEMORY SPACE.
4.THE ENTIRE PROGRAM SHOULD BE EXECUTED WITHIN A FINITE AMOUNT OF TIME

PROBLEM DEFINITION

1.TO GENERATE ‘N’ FIBONACCI NUMBERS ESSENTIALLY ‘N’ STEPS ARE REQUIRED. THE FUNCTIONS FOR ALL VALUES OF N>=1.
@THE FIRST TWO TERMS IS DERIVED TO GIVE THE SUM OF THE NEAREST TERM AND SO ON TILL THE N TERM.
@SOME OF THE TERMS OF THE SEQUENCE ARE 0,1,1,2,3,5,8,13,21,34,…….

PROBLEM DESCRIPTION

FOR GENEREATING THE FIBONACCI SEQUENCE NUMBER SOME FOLLOWING STEPS MUST BE UNDERSTANDABLE TO USER TO EXECUTE THE PROCESS OR GENERATING THE NUMBERS.

FIRST THE DECLARATION PART OF DATA AS A=-1, B=1, C, I AND N.

HERE C -> THE NUMBER TO BE STORED TO RUN THE PROCESS OR WE MAY SAY IT HAS A TEMPORARY VARIABLE.

I -> IT’S USED TO INCREMENT THE VALUE TO ‘N’.

N ->TO GET THE VALUE GIVEN BY THE USER.

HERE, WHILE LOOP IS EXECUTED AS

WHILE (I<=N),

IT IS USED SUCH A WAY THAT TO HAVE THE FIBONACCI SEQUENCE AS 0, 1, 1, 2, 3, 5, 8…

THERE IS AN EXPRESSION,

C=A+B;

THE ELEMENT OF A=-1, B=1 IS FIRST ADDED TO GIVE THE ELEMENT C (I., E) C=-1+1;

THEN, C=0;

THE FIRST TERM IS ‘0’ AS PER THE LOOP AND THEN IT SHOULD BE PRINTED AS OUTPUT AS PER THE NEXT CODING.

HERE, THE RESPECTING STATEMENTS ARE TO EXCHANGE THE VALUE OF THE VARIABLE AS

A=B;

B=C;

IT GIVES THAT THE VALUE OF B IS NOW PLACED OR EXCHANGED IN THE VARIABLE A=1;

AND C=0 (I., E) STORED AS B=0;

THE ROUTINE PROCESS BE RUNNING TO EXPRESS THE VALUES OF FIBONACCI NUMBERS AS 0, 1, 1, 2, 3, 5, 8, 13, 21……

I++ TO INCREMENT THE ‘I’ VALUE IF THE VALUE IS NOT EQUAL TO ‘N’ TERMS WHICH WAS GIVEN BY THE USER, THEN TILL REACHING THE ‘N’ VALUE THE LOOP WILL BE RUNNING TO REPRESENT THE VALUES OF FIBONACCI SEQUENCE NUMBERS.

ALGORITHM

1.READ THE VALUE OF ‘N’ NUMBERS TO BE GENERATED WHEREAS ‘N’ IS THE NUMBER OF FIBONACCI NUMBERS.

2.INITIALIZE THE VARIABLES A & B TO BE -1 AND 1.
3.COMPUTE THE STATEMENT C=A+B TO STORE THE SUM OF FIRST TWO TERMS IN THE NEW TERM.
4.AFTER THE INTERCHANGE OF THE TERM B TO A AND C TO B
5.RUN THE LOOP UNTIL IT REACHES THE NTH VALUE OF THE PROGRAM.

6.PRINT THE VALUES OF N TERMS ACCORDING TO THE FIBONACCI ORDER SUCH AS

0, 1, 1, 2, 3, 5, 8…

IMPLEMENTATION

PROGRAM
Void main ()

{

Int a=-1, b=1, k, i, n;/*DECLARATION OF THE VARIABLES WITH ITS DATA TYPE*/

Clrscr (); /* TO CLEAR THE SCREEN*/

Cout<<"read the value of n:”

Cin>>n; /*READING THE VALUE*/

While (i<=n) /*TESTING*/

{

k=a+b; /*ASSIGNMENT STATEMENT*/

Cout k;end l;/*PRINTING THE VALUES*/

a=b; /*ASSIGNMENT STATEMENT*/

b=k; /*ASSIGNMENT STATEMENT*/

i++; /*INCREMENTING*/

} /*END OF THE LOOP*/

Getch ();

}

APPLICATIONS

THE FIBONACCI SEQUENCE IS MAINLY USED FOR SORTING AND THE SEARCHING THE NUMBERS.