Greedy Change Making Program in C

Problem Statement

Write a C program to solve ‘Change Making Problem’. Put simply, a solution to Change-Making problem aims to represent a value in fewest coins under a given coin system. This program was requested by one of readers on our Facebook Page.

Coin changing

Inputs to program

  • Number of different denominations available
  • List of numbers representing all the denominations
  • Amount to represent in the given coin system

Output

The program should output a way to represent the given amount using fewest number of coins. For example. if you have coins of value 1, 2, 5 and 10 and want to represent 26, the program should output the correct solution 10×2 5×1 2×0 1×1

Solution

The greedy approach is easy to understand and implement as well. We start with using the largest denomination coin/currency possible. Once the owed amount is less than the largest, we move to next largest coin, so on and so forth.

Assumptions

  • Denominations are entered in descending order. That is largest one first. Example: 100, 50, 20, 5, 1. We can add a sort method if it’s not, a minor change.
  • We always have denomination of 1(Just to make sure we have a solution for all the numbers).

Limitation

Greedy approach works best with Canonical Coin systems and may not produce optimal results in arbitrary coin systems. For example, if denominations are {4, 3, 1}, number 6 is represented as 4×1 3×0 1×2 by this program; taking 3 coins. The correct answer in this case is 4×0 3×2 1×0 with just 2 coins.

The Program

#include <stdio.h>
int main () {
int num_denominations, coin_list[100], use_these[100], i, owed;
printf("Enter number of denominations : ");
scanf("%d", &num_denominations);
printf("\nEnter the denominations in descending order: ");
for(i=0; i< num_denominations; i++) {
scanf("%d", &coin_list[i]);
// use_these[i] = 0;
}
printf("\nEnter the amount owed : ");
scanf("%d", &owed);
for(i=0; i < num_denominations; i++) {
use_these[i] = owed / coin_list[i];
owed %= coin_list[i];
}
printf("\nSolution: \n");
for(i=0; i < num_denominations; i++) {
printf("%dx%d ", coin_list[i], use_these[i]);
}
}
view raw greed_coin_changer.c hosted with ❤ by GitHub

Sample Output

Further reading

C Program For Infix To Postfix Conversion and Evaluation of postfix expression

Infix to postfix conversion and postfix expression evaluation. In this C Program, we take an infix expression as input from the user and convert it in to a postfix expression using a stack. Then we evaluate that postfix expression to obtain the result.

Problem Statement

Write a C Program to convert a given infix expression to postfix and evaluate it. Infix expression is the most commonly used expression and we are all familiar with this. In Infix expression, the operator is between two operands, as in 1 + 2, or “5 + ((2 + 6) × 9) − 8”. In Postfix expression, also called as Reverse Polish Notation or postorder expression, operators are written after their operands. For example the above expressions become 12+ and  526+9*+8- respectively when written in postfix notation.

Read more about Infix, Postfix and Prefix

The Solution

The problem is divided into two tasks. First, the given infix expression is converted to a postfix expression. Then we take that postfix expression and evaluate it.  In C Program Examples website, we have already given programs to do these things separately. You can see them here and here.

Here we are doing it in a single program. This is in response to a request from one of our readers in a recent comment.

The Program

/*
* C Program to convert a given infix expression to postfix expression and evaluate it.
* (c) www.c-program-example.com
*/
#define SIZE 50 /* Size of Stack */
#include <ctype.h>
#include <stdio.h>
char s[SIZE];
int top = -1; /* Global declarations */
/* Function to remove spaces from given string */
void RemoveSpaces(char* source) {
char* i = source;
char* j = source;
while(*j != 0) {
*i = *j++;
if(*i != ' ')
i++;
}
*i = 0;
}
/* Function for PUSH operation */
void push(char elem) {
s[++top] = elem;
}
/* Function for POP operation */
char pop() {
return (s[top--]);
}
/* Function for precedence */
int pr(char elem) {
switch (elem) {
case '#':
return 0;
case '(':
return 1;
case '+':
case '-':
return 2;
case '*':
case '/':
return 3;
}
}
/*
* Function to convert from infix to postfix expression
*/
void infix_to_postfix(char *infix, char *postfix) {
char ch, elem;
int i = 0, k = 0;
RemoveSpaces(infix);
push('#');
while ((ch = infix[i++]) != '\n') {
if (ch == '(')
push(ch);
else if (isalnum(ch))
postfix[k++] = ch;
else if (ch == ')') {
while (s[top] != '(')
postfix[k++] = pop();
elem = pop(); /* Remove ( */
} else { /* Operator */
while (pr(s[top]) >= pr(ch))
postfix[k++] = pop();
push(ch);
}
}
while (s[top] != '#') /* Pop from stack till empty */
postfix[k++] = pop();
postfix[k] = 0; /* Make postfix as valid string */
}
/*
* Function to evaluate a postfix expression
*/
int eval_postfix(char *postfix) {
char ch;
int i = 0, op1, op2;
while((ch = postfix[i++]) != 0) {
if(isdigit(ch))
push(ch-'0'); /* Push the operand */
else { /* Operator,pop two operands */
op2 = pop();
op1 = pop();
switch(ch) {
case '+' : push(op1+op2);
break;
case '-' : push(op1-op2);
break;
case '*' : push(op1*op2);
break;
case '/' : push(op1/op2);
break;
}
}
}
return s[top];
}
void main() { /* Main Program */
char infx[50], pofx[50];
printf("\nInput the infix expression: ");
fgets(infx, 50, stdin);
infix_to_postfix(infx, pofx);
printf("\nGiven Infix Expression: %sPostfix Expression: %s", infx, pofx);
top = -1;
printf("\nResult of evaluation of postfix expression : %d", eval_postfix(pofx));
}
view raw Infix_postfix_eval.c hosted with ❤ by GitHub

Sample Output

Infix to postfix conversion and evaluation

Related Programs

Site Maintenance Updates

Dear fellow programmers, I have some ‘site maintenance updates’. Before I start on the updates, I would first like to thank you all for your wonderful support over the years. I really appreciate that. As most of you are aware, I have been writing C programs on this website from 2011.

Some of you here have sent emails to thank me for the programs, to ask a doubt or even to report an error you discovered. I’m sorry if I have not replied to your email in time. Our Facebook Page has also seen great response. I regret not being more active there. However, that’s going to change now.

Announcement

This website started as a small blog on Blogger’s sub-domain in 2011. I started writing simple C programs with some help from my friend Chinmaya. Later, as the readership increased, I moved it to it’s own domain www.c-program-example.com. As you can see, it’s still running on the same domain. While Blogger is a great platform to start with, it lacks the flexibility of a full fledged Content Management System. Now that the website gets around 100000 page views every month, I decide to move it to WordPress.

I seem to have successfully imported all the blog posts. However, the move has not been as smooth as I wanted. Old posts had lot of embedded html and JavaScript. WordPress doesn’t play so well with it. As a result, you may see several broken links or nonfunctional buttons/features. I will be working to fix them all over next week or so. Please let me know if you find anything broken.

Let’s get to the details now.

What has changed

  • The website is now hosted on WordPress. This should not affect your website experience directly. You may notice frequent change in color/theme as I experiment with it.
  • Better layout and font options. You will notice them soon.
  • Website loads much faster, thanks to various plug-ins I’m using to optimize the website for speed and performance.
  • The code highlighting has gone! I will find a plug-in for better embedding of source code within post.

What has NOT changed

  • URLs: If I have done the migration and redirection properly, all the posts should be available at their old urls. That means, any posts you have bookmarked in your browser, or shared with someone else should all work as before.
  • Search feature: ‘Search’ continues to be one of the most used feature on our website. I have included it in this website. You can find it in the right side bar. Only difference is that the search box is much smaller 🙂
  • Facebook Page: C Program Example’s official Facebook Page remains unchanged. You can follow that page by clicking on the link in previous sentence. I will be adding a widget in sidebar soon to make it easy to ‘Like’.
  • Contact information. You can still email me on info@c-program-example.com. Oh! And I promise to reply sooner now 😉

What is Missing

  • Pages: Yes. The old site had a few static pages. One that listed all the solutions to exercise problems from K&R C. Another listed useful programs along with links. Those pages are not in the new site. I will add them with some improvements over next week or two.
  • Google+ comments: Blogger allowed visitors to comment on posts using their Google login. With new WordPress sites, you will need to have WordPress login or give your name and email.
  • Embedded Buttons in post: Posts on old site allowed readers to Like our Facebook Page or Follow us on Twitter by intuitive embedded buttons. That’s all gone now. I will clean up every post and add these buttons only in side bar. I hope this makes posts more readable.

Unknowns!

  • Feeds: I haven’t had a chance to test the feeds(RSS/atom). If you are reading this post via rss reader, then it’s most likely working. I’m adding it to my todo list.
  • Posts in Email: One of the last changes I did in old site was to add support for subscribing to posts via email. I don’t even remember which service was used for that. I have got many subscribers through that. That will be added soon.
  • Link to Pages: If posts had links to Pages, it’d all be broken.
  • Links to Search Results: Some posts have links to search results which may be invalid now.

What to expect in future

As I promised earlier, things are going to be much better over here! These are some things you can expect in near future

  • Complete website features with all relevant plugins and widgets
  • All broken links fixed or removed where irrelevant
  • Plug-ins for close integration with Facebook Page and Twitter.
  • Quicker response to comments and better comment moderation.
  • Better code display inside post by using Gists.

and in not-so-near future

  • Sample input and out put for each program
  • Screen-shots of terminal/output where needed
  • Tutorial/guide posts for beginners to learn how to compile and run C programs in various platforms.
  • A static page for listing these tutorial with support for selecting a tutorial based on OS and other options.
  • Screen record or video with audio explaining programs.
  • Weekly open hangout for discussions and/or questions. Keep watching this space (and Facebook Page) for event announcements.

That’s all for now! Thanks for reading through site maintenance updates. Happy coding.

-SN

Subscribe to C Programs updates via Email

Good news programmers! Now you can get C programs in your inbox!

Yes, now you can subscribe to our updates via Email. It’s very simple. Enter your email-id in the box below and click on “Subscribe” button.
Enter your email address:

Delivered by FeedBurner
This form is also available on the right side bar of the site. To get regular updates on new C programs, you can Follow @c_program

You can discuss these programs on our Facebook Page. Start a discussion right now,

our page!

Share this program with your Facebook friends now! by liking it

(you can send this program to your friend using this button)

Like to get updates right inside your feed reader? Grab our feed!
To browse more C Programs visit this link
Or if you can’t find the program you are looking for, you can contact info@c-program-example.com. Thank you for visiting.

(c) www.c-program-example.com

C Aptitude: Endianness, Pointer Arithmetic

C Aptitude 31
In this episode we’ll learn learn more about Endianness, Pointer Arithmetic.

C program is one of most popular programming language which is used for core level of coding across the board. C program is used for operating systems, embedded systems, system engineering, word processors,hard ware drivers, etc.

In this site, we have discussed various type of C programs till date and from now on, we will move further by looking at the C aptitude questions.

In the coming days, we will post C aptitude questions, answers and explanation for interview preparations.

The C aptitude questions and answers for those questions along with explanation for the interview related queries.

We hope that this questions and answers series on C program will help students and freshers who are looking for a job, and also programmers who are looking to update their aptitude on C program.
Some of the illustrated examples will be from the various companies, and IT industry experts.
Read more about C Programming Language . and read the C Programming Language (2nd Edition). by K and R.


Predict the output or error(s) for the following:

C aptitude 31.1

  
main() {
int i = 258;
int *iPtr = &i;
printf("%d %d", *((char*)iPtr), *((char*)iPtr+1) );
}

Answer: 2 1

Explanation: The integer value 257 can be represented in binary as, 00000001 00000001. Remember that the INTEL machines are ‘small-endian’ machines. Small-endian means that the lower order bytes are stored in the higher memory addresses and the higher order bytes are stored in lower addresses. The integer value 258 is stored in memory as: 00000001 00000010.

C aptitude 31.2

main() {
int i=300;
char *ptr = &i;
*++ptr=2;
printf("%d",i);
}

Answer:556

Explanation:The integer value 300  in binary notation is: 00000001 00101100. It is  stored in memory (small-endian) as: 00101100 00000001. Result of the expression *++ptr = 2 makes the memory representation as: 00101100 00000010. So the integer corresponding to it  is  00000010 00101100 => 556.

C aptitude 31.3

main()
{
char * str = "hello";
char * ptr = str;
char least = 127;
while (*ptr++)
least = ((*ptr)<(least))?(*ptr):(least);
printf("%d", least);
}

Answer: 0
Explanation: After ‘ptr’ reaches the end of the string the value pointed by ‘str’ is ‘’. So the value of ‘str’ is less than that of ‘least’. So the value of ‘least’ finally is 0.

Read more Similar C Programs 
Learn C Programming
C Aptitude
C Interview questions
 

You can easily select the code by double clicking on the code area above. To get regular updates on new C programs, you can Follow @c_program You can discuss these programs on our Facebook Page. Start a discussion right now,

our page! Share this program with your Facebook friends now! by liking it

(you can send this program to your friend using this button) Like to get updates right inside your feed reader? Grab our feed!
To browse more C Programs visit this link. Or if you can’t find the program you are looking for, you can contact info@c-program-example.com. Thank you for visiting.

(c) www.c-program-example.com

C Program to implement bucket sort

Write C program to implement bucket sort.
The idea of Bucket Sort is to divide the interval [0, 1] into n equal-sized sub intervals, or buckets, and then distribute the n input numbers into the buckets. To produce the output, we simply sort the numbers in each bucket and then go through the buckets in order, listing elements in each.
Bucket sort runs in linear time when the input is drawn from a uniform distribution. Read more about C Programming Language .
/***********************************************************
* You can use all the programs on  www.c-program-example.com
* for personal and learning purposes. For permissions to use the
* programs for commercial purposes,
* contact info@c-program-example.com
* To find more C programs, do visit www.c-program-example.com
* and browse!
* 
*                      Happy Coding
***********************************************************/

#include<stdio.h>
void Bucket_Sort(int array[], int n)
{   
 int i, j;   
 int count[n];  
 for(i=0; i < n; i++)
 {   
  count[i] = 0;   
 }     
 for(i=0; i < n; i++)
 {    
  (count[array[i]])++; 
 }     
 for(i=0,j=0; i < n; i++)
 {   
  for(; count[i]>0;(count[i])--) 
  {       
   array[j++] = i; 
  }  
 }   
}    
int main() 
{ 
 int array[100];   
 int num;   
 int i;  
 printf("Enter How many Numbers : ");    
 scanf("%d",&num);    
 printf("Enter the %d elements to be sorted:n",num);  
 for(i = 0; i < num; i++ )
 {   
  scanf("%d",&array[i]);  
 }   
 printf("nThe array of elements before sorting : n"); 
 for (i = 0;i < num;i++) 
 {    
  printf("%d ", array[i]);   
 }    
 printf("nThe array of elements after sorting : n");  
 Bucket_Sort(array, num);  
 for (i = 0;i < n;i++) 
 {     
  printf("%d ", array[i]);  
 }   
 printf("n");      
 return 0; 
} 

Read more Similar C Programs

Data Structures


C Sorting

You can easily select the code by double clicking on the code area above.

To get regular updates on new C programs, you can Follow @c_program

You can discuss these programs on our Facebook Page. Start a discussion right now,

our page!

Share this program with your Facebook friends now! by liking it

(you can send this program to your friend using this button)

Like to get updates right inside your feed reader? Grab our feed!
To browse more C Programs visit this link
Or if you can’t find the program you are looking for, you can contact info@c-program-example.com. Thank you for visiting.

(c) www.c-program-example.com

C Aptitude Questions and answers with explanation

C Aptitude 30
C program is one of most popular programming language which is used for core level of coding across the board. C program is used for operating systems, embedded systems, system engineering, word processors,hard ware drivers, etc.

In this site, we have discussed various type of C programs till date and from now on, we will move further by looking at the C aptitude questions.

In the coming days, we will post C aptitude questions, answers and explanation for interview preparations.

The C aptitude questions and answers for those questions along with explanation for the interview related queries.

We hope that this questions and answers series on C program will help students and freshers who are looking for a job, and also programmers who are looking to update their aptitude on C program.
Some of the illustrated examples will be from the various companies, and IT industry experts.
Read more about C Programming Language . and read the C Programming Language (2nd Edition). by K and R.

–> Predict the output or error(s) for the following:

C aptitude 30.1

  main()
{
int i;
i = abc();
printf("%d",i);
}
abc()
{
_AX = 1000;
}

Answer:1000

Explanation: Normally the return value from the function is through the information from the accumulator. Here _AH is the pseudo global variable denoting the accumulator. Hence, the value of the accumulator is set 1000 so the function returns value 1000.

C aptitude 30.2

   main( )
{
void *vp;
char ch = ‘g’, *cp = “goofy”;
int j = 20;
vp = &ch;
printf(“%c”, *(char *)vp);
vp = &j;
printf(“%d”,*(int *)vp);
vp = cp;
printf(“%s”,(char *)vp + 3);
}

Answer: g20fy

Explanation: Since a void pointer is used it can be type casted to any other type pointer. vp = &ch stores address of char ch and the next statement prints the value stored in vp after type casting it to the proper data type pointer. the output is ‘g’. Similarly the output from second printf is ‘20’. The third printf statement type casts it to print the string from the 4th value hence the output is ‘fy’.

C aptitude 30.3

     # include<stdio.h>
aaa() {
printf("hi");
}
bbb(){
printf("hello");
}
ccc(){
printf("bye");
}
main()
{
int (*ptr[3])();
ptr[0]=aaa;
ptr[1]=bbb;
ptr[2]=ccc;
ptr[2]();
}

Answer: bye

Explanation: ptr is array of pointers to functions of return type int.ptr[0] is assigned to address of the function aaa. Similarly ptr[1] and ptr[2] for bbb and ccc respectively. ptr[2]() is in effect of writing ccc(), since ptr[2] points to ccc.

Read more Similar C Programs 
Learn C Programming
C Aptitude
C Interview questions
 

You can easily select the code by double clicking on the code area above.

To get regular updates on new C programs, you can Follow @c_program

You can discuss these programs on our Facebook Page. Start a discussion right now,

our page!

Share this program with your Facebook friends now! by liking it

(you can send this program to your friend using this button)

Like to get updates right inside your feed reader? Grab our feed!

–> To browse more C Programs visit this link. Or if you can’t find the program you are looking for, you can contact info@c-program-example.com. Thank you for visiting.
(c) www.c-program-example.com

C Aptitude Questions and answers with explanation

C Aptitude 29
C program is one of most popular programming language which is used for core level of coding across the board. C program is used for operating systems, embedded systems, system engineering, word processors,hard ware drivers, etc.

In this site, we have discussed various type of C programs till date and from now on, we will move further by looking at the C aptitude questions.

In the coming days, we will post C aptitude questions, answers and explanation for interview preparations.

The C aptitude questions and answers for those questions along with explanation for the interview related queries.

We hope that this questions and answers series on C program will help students and freshers who are looking for a job, and also programmers who are looking to update their aptitude on C program.
Some of the illustrated examples will be from the various companies, and IT industry experts.
Read more about C Programming Language . and read the C Programming Language (2nd Edition). by K and R.

Predict the output or error(s) for the following:

C aptitude 29.1

  enum colors {BLACK,BLUE,GREEN}
main()
{

printf("%d..%d..%d",BLACK,BLUE,GREEN);

return(1);
}

Answer: 0..1..2

Explanation: enum assigns numbers starting from 0, if not explicitly defined.

C aptitude 29.2

   void main()
{
char far *farther,*farthest;

printf("%d..%d",sizeof(farther),sizeof(farthest));

}


Answer: 4..2

Explanation: The second pointer is of char type and not a far pointer

C aptitude 29.3

     main()
{
int i=400,j=300;
printf("%d..%d");
}

Answer: 400..300

Explanation: printf takes the values of the first two assignments of the program. Any number of printf’s may be given. All of them take only the first two.

Read more Similar C Programs 
Learn C Programming
C Aptitude
C Interview questions
 

You can easily select the code by double clicking on the code area above.

To get regular updates on new C programs, you can Follow @c_program

You can discuss these programs on our Facebook Page. Start a discussion right now,

our page!

Share this program with your Facebook friends now! by liking it

(you can send this program to your friend using this button)

Like to get updates right inside your feed reader? Grab our feed!

To browse more C Programs visit this link
(c) www.c-program-example.com

C Aptitude Questions and answers with explanation

C Aptitude 28
C program is one of most popular programming language which is used for core level of coding across the board. C program is used for operating systems, embedded systems, system engineering, word processors,hard ware drivers, etc.

The C aptitude questions and answers for those questions along with explanation for the interview related queries.

We hope that this questions and answers series on C program will help students and freshers who are looking for a job, and also programmers who are looking to update their aptitude on C program.
Some of the illustrated examples will be from the various companies, and IT industry experts.

Read more about C Programming Language . and read the C Programming Language (2nd Edition). by K and R.

–>
Predict the output or error(s) for the following:

C aptitude 28.1

 main()
{
char *p="hai friends",*p1;
p1=p;
while(*p!='') ++*p++;
printf("%s %s",p,p1);
}

Answer: ibj!gsjfoet

Explanation: ++*p++ will be parse in the given order
 *p that is value at the location currently pointed by p will be taken
  ++*p the retrieved value will be incremented
 when ; is encountered the location will be incremented that is p++ will be executed

Hence, in the while loop initial value pointed by p is ‘h’, which is changed to ‘i’ by executing ++*p and pointer moves to point, ‘a’ which is similarly changed to ‘b’ and so on. Similarly blank space is converted to ‘!’. Thus, we obtain value in p becomes “ibj!gsjfoet” and since p reaches ‘’ and p1 points to p thus p1doesnot print anything.

C aptitude 28.2

   #include <stdio.h>
#define a 10
main()
{
#define a 50
printf("%d",a);
}

Answer: 50

Explanation:The preprocessor directives can be redefined anywhere in the program. So the most recently assigned value will be taken.

C aptitude 28.3

     
main()
{
printf("%p",main);
}


Answer:Some address will be printed.
Explanation: Function names are just addresses (just like array names are addresses). main() is also a function. So the address of function main will be printed. %p in printf specifies that the argument is an address. They are printed as hexadecimal numbers.

Read more Similar C Programs 
Learn C Programming
C Aptitude
C Interview questions
 

You can easily select the code by double clicking on the code area above. To get regular updates on new C programs, you can Follow @c_program You can discuss these programs on our Facebook Page. Start a discussion right now,

our page! Share this program with your Facebook friends now! by liking it

(you can send this program to your friend using this button) Like to get updates right inside your feed reader? Grab our feed!

–>
To browse more C Programs visit this link
(c) www.c-program-example.com

C Program to delete a file using remove function.

Write a C program to delete a specified file using remove function.
remove function deletes the specified file, where it takes file name as the argument and if file is successively deleted it returns 0 , other wise returns a non zero value.
Read more about C Programming Language . and read the C Programming Language (2nd Edition). by K and R.

/***********************************************************
* You can use all the programs on  www.c-program-example.com
* for personal and learning purposes. For permissions to use the
* programs for commercial purposes,
* contact info@c-program-example.com
* To find more C programs, do visit www.c-program-example.com
* and browse!
* 
*                      Happy Coding
***********************************************************/

#include<stdio.h>
#include<string.h>
int main()
{
    char file_name[40];
    printf("Enter the file name with location:n Example, c:example.txtnn");
    gets(file_name);
    if(remove(file_name) != 0 )
    puts("Error deleting filenn");
    else
    puts("File successfully deletednn");
    return 0;
}
Read more Similar C Programs
Graphics in C
C Strings
C Aptitude

You can easily select the code by double clicking on the code area above.

To get regular updates on new C programs, you can Follow @c_program

You can discuss these programs on our Facebook Page. Start a discussion right now,

 our page!

Share this program with your Facebook friends now! by liking it

 (you can send this program to your friend using this button)

Like to get updates right inside your feed reader? Grab our feed!

To browse more C Programs visit this link

(c) www.c-program-example.com