Hello, I\'m almost done with the following C code. It does not yet incorporate b
ID: 3756784 • Letter: H
Question
Hello, I'm almost done with the following C code. It does not yet incorporate binary search to search over the already found width. The code already incorporates a method for finding the width but I need to just add a simple binary search to go over the width to make the program go faster. Thank you! The instructions for more clarification are below.
I am assuming we are to incorporate the binary search like this perhaps?
Typedef struct Node
{
Int data;
struct Node *Lptr, *Rptr;
}Node;
#include <stdio.h>
#include <stdlib.h>
#include<math.h>
typedef struct chair{
char arr[25];
int check_chair;
int spot_covered;
}chair;
int BinarySearch(int mid, int high, int low){
mid= low+(high-low)/2;
return mid;
}
//function to check if there is a chair at a given position
int hasChairOnPosition(int pos, int arr[], int numChairs){
for(int i=0;i<numChairs;i++)
if(arr[i]==pos)
return 1;
return 0;
}
int main(){
//Input
int numChairs,numParasols;
int arr[numChairs];
scanf("%d %d",&numChairs,&numParasols);
for(int i=0;i<numChairs;i++)
scanf("%d",&arr[i]);
int totalLength=arr[numChairs-1]; //distance between start of fist chair and end of last chair
int maxParasolLength;
if(totalLength%2==0) // just to get cieling of the division
maxParasolLength=(totalLength)/numParasols; //maximum span of each parasol
else
maxParasolLength=(totalLength+1)/numParasols; //maximum span of each parasol
int parasolCoverage[arr[numChairs-1]]; //array to keep record of whether each piece of floor is covered by parasol
int minParasolLength; //This will hold the resulting minimum span of parasol
int n; //temporary variable for number of parasols
int possible = 1;
for(minParasolLength=maxParasolLength;minParasolLength>1;minParasolLength--){
for(int i=0;i<totalLength;i++) // flush array with 0
parasolCoverage[i]=0;
n=numParasols; //reset n
if(possible==1) //checks for first unsuccessful case
for(int i=0;i<totalLength;i++){
/*
Check if floor is uncovered and has a chair, if uncovered and has chair, parasol is placed such that the floor checked is on the edge of parasol and decrease n.
If out of parasols, we got our answer and break the loop.
*/
//if (minParasolLength==1&&minParasolLength-1==0){
//return minParasolLength;
//}
if(parasolCoverage[i]==0 && hasChairOnPosition(i,arr,numChairs)==1){
if(n>0){
int j;
for(j=i;j<i+minParasolLength-1;j++)
parasolCoverage[j]=1;
i=j-1;
n--;
}
if(n==0){
possible=0;
break;
}
}
}
else
break;
}
printf("%d",minParasolLength);
return EXIT_SUCCESS;
}
Explanation / Answer
The main motive of binary search algorithm is to search and find the desired element in an array. In your case that element is char whether it is available or not. To reduce the time complexity that will make the algorithm more efficient and will have reduced response time we will use iteration because in some cases iteration process increases the length of the code but greatly reduce time complexity in comparison to recursion method.
So I hope following code will help you
Typedef struct Node
{
Int data;
struct Node *Lptr, *Rptr;
}Node;
#include <stdio.h>
#include <stdlib.h>
#include<math.h>
typedef struct chair{
char arr[25];
int check_chair;
int spot_covered;
}chair;
int BinarySearch(int SortList[], int low, int high, int chair)
{
int mid;
if(low>high)
return -1;
int var1=low+high;
mid=(var1)/2;
if(char<SortList[mid])
return BinarySearch(SortList,low,high-1,chair);
else if(chair>SortList[mid])
return BinarySearch(SortList,mid+1,high,chair);
else
return mid;
}
int main(){
//Input
int numChairs,numParasols;
int arr[numChairs];
printf(" Enter number of chairs and number of Parasols: ");
scanf("%d %d",&numChairs,&numParasols);
int sucess=1;
int fail=0;
for(int i=0;i<numChairs;i++)
{
scanf("%d",&arr[i]);
}
for(int i=0;i<numChairs;i++)
{
if(arr[i]==pos)
{
return success;
}
else
{
return fail;
}
int totalLength=arr[numChairs-1]; //distance between start of fist chair and end of last chair
int maxParasolLength;
if(totalLength%2==0) // just to get cieling of the division
maxParasolLength=(totalLength)/numParasols; //maximum span of each parasol
else
maxParasolLength=(totalLength+1)/numParasols; //maximum span of each parasol
int parasolCoverage[arr[numChairs-1]];
int minParasolLength;
int n;
int possible = 1;
for(minParasolLength=maxParasolLength;minParasolLength>1;minParasolLength--){
for(int i=0;i<totalLength;i++) // flush array with 0
parasolCoverage[i]=0;
n=numParasols; //reset n
if(possible==1) //checks for first unsuccessful case
for(int i=0;i<totalLength;i++)
{
if(parasolCoverage[i]==0 && success==1){
if(n>0){
int j;
for(j=i;j<i+minParasolLength-1;j++)
parasolCoverage[j]=1;
i=j-1;
n--;
}
if(n==0){
possible=0;
break;
}
}
}
else
break;
}
printf("%d",minParasolLength);
return EXIT_SUCCESS;
}
//Do not forget to Thumbs up. Thank you
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.