Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > A* algorithm

Reply
Thread Tools

A* algorithm

 
 
Barry Schwarz
Guest
Posts: n/a
 
      04-06-2008
On Sun, 6 Apr 2008 04:46:27 -0700 (PDT), http://www.velocityreviews.com/forums/(E-Mail Removed)
wrote:

>Here is the corrected program
>


It looks much better.

>#include< stdio.h >
>#include< stdlib.h >
>#include< string.h >
>
>
>char bln;
>int subsetsum(int*,int,int,char* ,int);
>int compare(const void*,const void*);
>void printanswer(int*,int,char*);
>
>
>int main(void)
>{
>
>int a[] = {5,3,4,8,9,6};
>int sum = 15;
>int size = sizeof(a)/sizeof(*a);
>int i;
>char *selected = calloc(size,sizeof(*selected));
>
>qsort(a,size,sizeof(int),compare);
>
>for(i=0;i < (size-1);i++)
>{
>printf("\n i = %d",i);
>
>if( subsetsum(a,size,sum,selected,i))
>printanswer(a,size,selected);
>
>memset(selected,0,size * sizeof(*selected));
>}


A style suggestion which will save you a lot of aggravation later
(when you write larger programs). Learn to indent consistently. I
prefer 3 or 4 spaces (not tabs if you post to Usenet) but the
consistency is more important than the value (within reason). This
block should look something like
for
{
printf
if
printanswer
memset
}
It lets you quickly recognize the range of loops and if statements.

>
>return EXIT_SUCCESS;
>}
>
>
>int subsetsum(int *a,int n,int sum,char *selected ,int start)
>{
>int i;
>
>if(sum == 0)
>return 1;
>
>for(i=start;i <= (n-1);i++)


Using size-1 in main and n-1 here eliminates the undefined behavior at
the cost of not handling boundary conditions (also known as extreme
cases or corner conditions). Try the same program with sum set 3.

You should also try with sum set to 4 or 7 and decide how you want to
clean up the output. (Hint: one solution would be a simple if in
front of the call to printanswer.)

>if(selected[i] == 0 && a[i] <= sum)
>{
>selected[i] = 1;
>if(subsetsum(a,n,sum - a[i],selected,i+1))
>return 1;
>
>selected[i] = 0;
>}
>
>return 0;
>}
>
>void printanswer(int* a,int n,char* selected)
>{
>int i;
>
>for(i=0;i< n;i++)
>if(selected[i])
>printf("\t%d",a[i]);


for
if
printf

>
>puts("");
>}
>
>
>int compare(const void* e1,const void* e2)
>{
>return *(int*)e2 - *(int*)e1;


Many lint type programs will complain that you are casting away the
const. Chang the two casts to (const int*), even though technically
unnecessary (especially in this case with such a simple function),
would eliminate that.

Just for your info, the above is not completely safe in that it could
result in overflow. Since your real purpose is the algorithm and not
the sort, I wouldn't change it but the usual recommendation is

const int *i2 = e2;
const int *i1 = e1;
return (*i1 > *i2) ? (-1) : (*i1 < *i2);
(parentheses just for clarity)

I wonder why you changed from an ascending sort to a descending one.

>}



Remove del for email
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
help need in the Radix 4 algorithm of 64 point. senthil VHDL 3 11-25-2011 11:58 AM
Filtered Back Projection Algorithm (FBP Algorithm) Bapaiah Katepalli VHDL 1 06-23-2006 04:50 PM
Word wrap line break code and algorithm for c# Jason Coyne Gaijin42 ASP .Net 0 04-08-2004 07:26 PM
Key generation algorithm and Cipher algorithm Ahmed Moustafa Java 0 11-15-2003 06:35 AM
algorithm problem Adam VHDL 5 11-08-2003 06:26 PM



Advertisments