DSA-1/Assignment12.cpp at master · MEHUL25/DSA-1 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <iostream>
using namespace std;

class student
{

public:
    int roll[50],m;
void accept();
void display();
void linear(int);
int binary(int);
//void bubble_sort();
//void sentinel(int);
int fib(int n);
int fibsearch(int ar[],int k,int f,int a,int b);
};
void student::accept()
{
cout<<"enter the total no of students:";
cin>>m;
cout<<"enter the roll no of students attending the program: ";
for(int i=0;i<m;i++)
{
cin>>roll[i];
}
}
void student::display()
{
cout<<"\nRoll no of students attending the program are:\n";
for(int i=0;i<m;i++)
{
cout<<roll[i]<<"\t";
}
}
void student::linear(int x)
{
    int i,l=0;
    for( i=0;i<m;i++)
    {
        if(roll[i]==x)
    {
        cout<<"\nRoll no\t"<<roll[i]<<"is present"<<endl;
        l++;
        break;
    }
    }
    if(l==0)
    cout<<"\nRoll no is absent"<<endl;
    }

int student::binary(int p)
{
int low,high,mid;
low=0;
high=m-1;
mid=(low+high)/2;
while(low<=high && roll[mid]!=p)
{
 if(p>roll[mid])
{
low=mid+1;
}
else
high=mid-1;
mid=(low+high)/2;
}
if(low<=high)
    return mid;
return (-1);
}

int student::fib(int n)
{
    if(n==0)
        return 0;
    if(n==1)
        return 1;
    return (fib(n-1)+fib(n-2));
}
int student::fibsearch(int ar[30],int key,int f,int a,int b)
{
    int temp;
    if(key==ar[f-1])
        return f;
    if(key>ar[f-1])
    {
        if(b==1)
            return (-1);
        f=f+a;
        b=b-a;
        a=a-b;
        return(fibsearch(ar,key,f,a,b));
    }
    else
    {
        if(a==0)
            return(-1);
        f=f-a;
        temp=b-a;
        b=a;
        a=temp;
        return(fibsearch(ar,key,f,a,b));

    }
}

int main()
{
student s;
int t;
char k;
int ch;
do
{
    cout<<"\n_________MENU________\n";
    cout<<"\n1.accept roll no.s and display it \n2.linear search\n3.fibonacci search\n";
cout<<"\n enter your choice";
cin>>ch;
switch(ch)
{
case 1:
    s.accept();
s.display();
break;
case 2:
    cout<<"\n enter the roll no you want to search:";
cin>>t;
    s.linear(t);
    break;

case 3:
    int k,a,b,f,result;
    cout<<"\n enter the roll no you want to search:";
    cin>>t;
    for(k=1;s.fib(k)<=s.m;k++);
    b=s.fib(k-2);
    a=s.fib(k-3);
    f=s.m-b+1;
    result=s.fibsearch(s.roll,t,f,a,b);
    if(result==-1)
        cout<<"roll no is absent";
    else
        cout<<"roll no is present";

    break;
}
cout<<"\n do you want to continue?\t";
cin>>k;
}while(k=='y');

}