Register

Incomplete Recursive definition

191 views
0 votes
0 votes

Suppose an array A={a1,a2,…………an} contains a set of n distinct coins types where each ai € N for 1<=n. Suppose also that a1<a2<a3……………<an the coin hanging problem is defined as follows:

Given W € N , find the smallest numbers of coins from A  that adds upto W, given an unlimited number of coins of each type are available. We wish to find minimum number of coins needed from A to get W as c(n,W). Let  c(i,j) be the minimum number of coins needed from any subset of first “i” coin that sum to exactly “j”.

An incomplete recursive definition for the function c(i,j) is given below

C(i,j)=0                                           if j=0

       =∞                                          if i=0 and j≠0

      =expr1                                    if i,j>0 and j<a[i]

     =expr2                                    if  i,j>0 and a[i]<=j

User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
2
radha gogia asked May 6, 2018
1,758 views
Convert the following L-attributed definition to S-attributed definition .
E->TE' E'->*T { printf('*') ;} E' | epsilon T-> id {printf (id.name) ;} A) E->E*T | T {printf('*');} T->id {printf(id.name);} B) E->TE' E'->* ... ;T*E {printf('*');} E->T T->id {printf (id.name) ;} D) None of these Please explain precisely .
E->TE'E'->*T { printf('*') ;} E' | epsilonT- id {printf (id.name) ;}A) E->E*T | T {printf('*');}T->id {printf(id.name);}B) E->TE'E'->*TME' | epsilonM->epsilon { printf('...
User Avatar
Link Copied!