Shankar
BAN USER#include<stdio.h>
#include<string.h>
#include<conio.h>
int compare(char input[],int star[],int hash[],int low,int high,int *start)
{
int no_star,no_hash;
int max;
int max1,max2;
int start1,start2;
if(input[low]=='*')
{
no_star=star[high]-star[low]+1;
no_hash=hash[high]-hash[low];
}
else
{
no_star=star[high]-star[low];
no_hash=hash[high]-hash[low]+1;
}
if(no_star == no_hash)
{
*start=low;
max=no_hash;
}
else
{
max1=compare(input,star,hash,low+1,high,&start1);
max2=compare(input,star,hash,low,high-1,&start2);
if(max1 > max2)
{
max=max1;
*start=start1;
}
else
{
max=max2;
*start=start2;
}
}
return max;
}
int main()
{
char input[]="*##*###**##**###*";
int *star;
int *hash;
int length;
int i,j,k;
int start;
int no_of_char;
length=strlen(input);
star = (int *)malloc(length*sizeof(int));
hash = (int *)malloc(length*sizeof(int));
if(input[0]=='*')
{
star[0]=1;
hash[0]=0;
}
else
{
hash[0]=1;
star[0]=0;
}
for(i=1;i<length;i++)
{
if(input[i]=='*')
{
star[i]=star[i-1]+1;
hash[i]=hash[i-1];
}
else
{
hash[i]=hash[i-1]+1;
star[i]=star[i-1];
}
}
no_of_char=compare(input,star,hash,0,length-1,&start);
printf("Sub array is ");
no_of_char *= 2;
while(no_of_char > 0)
{
printf("%c",input[start++]);
no_of_char--;
}
getch();
}
#include<stdio.h>
#include<conio.h>
int assign(int serverCapacities[],int tasks[],int no_servers,int tasks_start,int tasks_end)
{
int i,j,k;
if( tasks_end < tasks_start)
return 1;
for( i=0; i<no_servers; i++)
if( tasks[tasks_start] <= serverCapacities[i] )
{
//if current server is capable of handling the cuurent task, then assign it
//Reduce the capacity of current server
serverCapacities[i] -= tasks[tasks_start];
if(assign(serverCapacities,tasks,no_servers,tasks_start+1,tasks_end))
return 1;
//backtracking
serverCapacities[i] += tasks[tasks_start];
}
return 0;
}
int main()
{
int serverCapacities[]={8,16,8,32};
int tasks[]={18,4,8,4,6,6,8,8};
int no_servers;
int no_tasks;
no_servers = sizeof(serverCapacities)/sizeof(int);
no_tasks = sizeof(tasks)/sizeof(int);
if ( assign(serverCapacities,tasks,no_servers,0,no_tasks-1) )
{
printf("True");
}
else
{
printf("False");
}
getch();
}
- Shankar August 07, 2014