Archive

Posts Tagged ‘g++’

Find factorial of a given number


Here I’m going to illustrate the method for finding the factorial of a given number(<100) programmatically, which is different from that of finding factorial using long, int, double etc., In this I’m going to use array to store each digit of solution.

Method:

The method I used in my code is similar to that of natural multiplication.

Let us assume that we have two numbers 43 and 25 to be multiplied. Here I’m considering 43 is kept in an array as digit ‘3’ 0th index and digit ‘4’ 1st index. Now I’m multiplying 25 with 0th index digit and adding temp(which is initially zero), we get the sum. Now find total sum%10 which gives the value to be stored at that index. i.e a[0]=5, temp=7. In the next iteration a[1]=7 temp=10

those two ‘1’ and ‘0’ digits are appended at the end of the array.

Resulting a[0]=5 a[1]=7 a[2]=0 a[3]=1

now the output is printed from the reverse

1075

Let me put it in an algorithmic way.

N //given input

temp=0 //initially

a[200] // array where the given input N is stored

m //stores number of digits in a given input

Repeat until n becomes 1

do

n–

a[index]=(a[index]*n+temp)%10

temp=(a[index]*n+temp)/10

done

while temp is not zero

do //the resultant is more than m digit number so increment m

m++

a[m]=temp%10

temp=temp/10

done

Here is the working code in online editor where you can give input and also check for output.

input should be given in the following way.

3                 — Which means number of inputs to follow

12

23

43

Advertisements

Divide and Conquer method Illustrated


Divide and Conquer is one of the famous algorithmic techniques. It works with the philosophy that divide the whole problem into smaller managable chunks of subproblems and work out these small subproblems there by combining the intermediate partial solutions.

There are many famous examples which use the Divide and Conqure strategy, for example Binary search, Merge sort, Insertion sort, Quick sort etc.,

Let us take a small example of finding minimum and maximum elements in a given array. If we adapt a normal methodology it takes atleast 2*(n-1) comparisions. We can decrease the number of comparisions using this technique which results in [ Ceil(3*n/2)-2 ] comparisions.

The below is the code for finding MIN and MAX of the given array which was compiled and tested using GNU g++compiler.

//Author: Vasanth Raja Chittampally
#include <iostream>

using namespace std;

void findMin(int [],int, int,int &amp;, int &amp;);

int main()

{

int n,min,max;

cout<<"Enter n:";

cin>>n;

int a[n];

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

{

cout<<"Enter a["<<i<<"]:";

cin>>a[i];

}

findMin(a,0,n-1,min,max);

cout<<"Minimun of the given array is: "<<min<<;endl;

cout<<"Maximum of the gvien arrays is: "<<max<<endl;

return 0;

}

void findMin(int a[], int left, int right, int &amp;min, int &amp;max)

{

if(left==right)

{

min=a[left];

max=a[right];

}

else

{

int mid=(left+right)/2;

findMin(a,left,mid,min,max);

int left_min=min;

int left_max=max;

findMin(a,mid+1,right,min,max);

int right_min=min;

int right_max=max;

if(left_min&lt;right_min)

min=left_min;

else

min=right_min;

if(left_max&gt;right_max)

max=left_max;

else

max=right_max;

}

}

In this example it divides whole array into two equal parts recursively and tries to compare partial solutions to find the minimum and maximum elements.

T(n)=2T(n/2) + 2 —–>(2 comparisions are needed one for minimum and the other of maximum)

.

.

.

.

number of comparisions = [ Ceil(3*n/2)-2 ]

The above number of comparisions can be verified by substituting in T(n)

T(n)=2*[3*n/(2*2) – 2]+2

T(n)=3n/2-2 (hence verfied)