Fibonacci Search in C++.

-
#include <iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
int n;
struct person
{
    char name[20];
    long ph;;
}p[20];
void getdata(struct person p[],int n)
{
    for(int i=0;i<n;i++)
    {
        cout<<"Enter name\n";
        cin>>p[i].name;
        cout<<"enter cntact\n";
        cin>>p[i].ph;
    }
}
void putdata(struct person p[],int n)
{

    for(int i=0;i<n;i++)
    {
        cout<<"name: "<<p[i].name<<endl;
        cout<<"contact: "<<p[i].ph<<endl;
    }

}
void sort(struct person p[],int n)
{
    int i,j,k;
    struct person q;
    for(i=1;i<n;i++)
    {
        for(j=0;j<n-i;j++)
        {
            if(strcmp(p[j].name,p[j+1].name)>0)
            {
                q=p[j];
                p[j]=p[j+1];
                p[j+1]=q;
            }
        }
    }
}
int search(struct person p[],int n, char key[])
{
    int l=0;int h=n-1;
    int mid=(l+h)/2;
    for(mid=(l+h)/2;l<=h;mid=(l+h)/2)
    {
        if(strcmp(p[mid].name,key)==0)
          return mid;
        if(strcmp(p[mid].name,key)<0)
         l=mid+1;
        if(strcmp(p[mid].name,key)>0)
            h=mid-1;

    }
    if(l>h)
        return -1;
}
int b_search(struct person p[],int l,int h,char key[])
{
        int mid=(l+h)/2;
        if(l>h)
            return (-1);
            if(strcmp(p[mid].name,key)==0)
              return mid;
            if(strcmp(p[mid].name,key)<0)
            {
             l=mid+1;
             return(    b_search(p,l,h,key));
            }
            if(strcmp(p[mid].name,key)>0)
            {
                h=mid-1;
                return(    b_search(p,l,h,key));
            }

}
int fib(int n)
{
    if(n==0)
        return 0;
    if(n==1)
        return 1;
    return(fib(n-1)+fib(n-2));
}
int fib_search(struct person p[],int a,int b,int mid,char key[])
{
    int temp;
        if(strcmp(p[mid-1].name,key)==0)
                  return(mid);
        if(strcmp(p[mid-1].name,key)<0)
        {
            if(a==1)
                return(-1);
            mid=mid+b;
            a=a-b;
            b=b-a;
            return(fib_search(p,a,b,mid,key));
        }
        if(strcmp(p[mid-1].name,key)>0)
        {
            if(b==0)
                return(-1);
            mid=mid-b;
            temp=a-b;
            a=b;
            b=temp;
            return(fib_search(p,a,b,mid,key));
        }


}
int add(struct person p[],char key[],int n)
{
    char ch;
    cout<<"do u want to add in contact(y/n)\n";
    cin>>ch;
    if(ch=='y')
    {
    strcpy(p[n].name,key);
    cout<<"enter contact no\n";
    cin>>p[n].ph;
    cout<<"number added to contact\n";
    }
    return(n+1);

}

int main()
{
int n,result,l,h,mid,a,b,k,mid1;
char key[20];
    while(1)
    {
        cout<<"1.input\n"<<"2.display\n"<<"3.sort\n"<<"4.binary search(non recursive)\n"<<"5.binary search(recursive)\n"
                <<"6.fibonacci search\n"<<"Enter your choice\n";
        int ch;
        cin>>ch;
        switch(ch)
        {
        case 1:
            cout<<"Enter the number of contact u want to add\n";
            int n;
            cin>>n;
            getdata(p,n);
            break;
        case 2:
            putdata(p,n);
            break;
        case 3:
            sort(p,n);
            putdata(p,n);
            break;
        case 4:
            cout<<"Enter the name to be search\n";
            cin>>key;
            result=search(p,n,key);
            if(result==-1)
            {
                cout<<"name not found"<<endl;
                n=add(p,key,n);
            }
            else
            {
                cout<<"name is found at location "<<result+1<<endl;
            cout<<p[result].name<<endl;
            cout<<p[result].ph<<endl;
            }
            break;
        case 5:
            cout<<"Enter name to be search\n";
            cin>>key;
            l=0;
            h=n-1;
            mid=(l+h)/2;
            result=b_search(p,l,h,key);
            if(result==-1)
            {
                            cout<<"name not found"<<endl;
                            n=add(p,key,n);
            }
                        else
                        {
                            cout<<"name is found at location "<<result+1<<endl;
                        cout<<p[result].name<<endl;
                        cout<<p[result].ph<<endl;
                        }
            break;
        case 6:
            cout<<"Enter name to be search\n";
                        cin>>key;
            for(k=1;fib(k)<=n;k++);
            a=fib(k-2);
            b=fib(k-3);
            mid1=n-a+1;
            result=fib_search(p,a,b,mid1,key);
            if(result==-1)
            {
                                        cout<<"name not found"<<endl;
                                    n=    add(p,key,n);
            }
            else
            {
                cout<<"name is found at location "<<result<<endl;
                cout<<p[result-1].name<<endl;
                cout<<p[result-1].ph<<endl;
            }
            break;

        }
    }
    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Priority Scheduling Algorithm Java Program.

-
import java.util.Scanner; public class priority{ public static void main(String args[]) { Scanner s = new Scanner(System.in); int x,n,p[],pp[],bt[],w[],t[],awt,atat,i; p = new int[10]; pp = new int[10]; bt = new int[10]; w = new int[10]; t = new int[10]; //n is number of process //p is process //pp is process priority //bt is process burst time //w is wait time // t is turnaround time //awt is average waiting time //atat is average turnaround time System.out.print("Enter the number of process : "); n = s.nextInt(); System.out.print("\n\t Enter burst time : time priorities \n"); for(i=0;i<n;i++) { System.out.print("\nProcess["+(i+1)+"]:"); bt[i] = s.nextInt(); pp[i] = s.nextInt(); p[i]=i+1; } //sorting on the basis of priority for(i=0;i<n-1;i++) { for...
Read more

Implement UNIX system calls like ps, fork, join, exec family, and wait for process management (use shell script/ Java/ C programming).

-
//A small example to show how to use execvp() function in C. We will have two .C files , EXEC.c and execDemo.c and we will replace the execDemo.c with EXEC.c by calling execvp() function in execDemo.c . //EXEC.c  #include<stdio.h>  #include<unistd.h>  int main()   {        int i;       printf("This  is EXEC.c, called by execvp() ");        printf("\n");       return 0;   }  Now,create an executable file of EXEC.c using command  gcc EXEC.c -o EXEC //execDemo.c #include<stdio.h> #include<stdlib.h>  #include<unistd.h>  int main()  {     //A null terminated array of character      //pointers       char *args[]={"./EXEC",NULL};       execvp(args[0],args);     /*All statements are ignored after execvp() call as this whole process(execDemo.c) is replaced by ...
Read more

Implement a class CppArray which is identical to a one-dimensional C++ array (i.e., the index set is a set of consecutive integers starting at 0) except for the following : 1. It performs range checking. 2.It allows one to be assigned to another array through the use of assignment operator. 3.It supports a function that returns the size of the array.

-
#include<iostream> #include<math.h> using namespace std; class array {      int a[10],b[10],i,j,temp,n;           public:             void accept();             void display();             void range();             void sort();             void exchange();             int size(); }; void array::accept() {     cout<<"How many Elements you want to insert into the array=\n";     cin>>n;     cout<<"Enter the array Elements=\n";     for(i=0;i<n;i++)        {             cout<<...
Read more