Solved

C++ Algorithmn

Posted on 2004-10-22
308 Views
Last Modified: 2012-05-05
Hi People, I need your help,

I would like to know where to find documentation on c++ Algorithm. For exemple, how many ways can I represent a 5 dollar bill if I have loonies, quarters, dimes and nickles ?


Documentation would be greatly appreciated.

Thank You,


C-Bin
0
Question by:C-begin
    3 Comments
     
    LVL 3

    Assisted Solution

    by:Crius
    There are many places to find various C++ algorithms.

    http://www.codeguru.com is a great place. You can find the C++ algorithms page from their home page, or just follow this link: http://www.codeguru.com/Cpp/Cpp/algorithms/.

    They also have a lot of sample programs and non-algorithm specific solutions for a wide variety of problems.

    http://www.codeproject.com is a great palce that deals mostly with MFCs. Their algorithm section is located at http://www.codeproject.com/cpp/#Algorithms.

    MSDN is another good place to find algorithms and samples. If you don't have it installed on your computer, you can go to their website at http://msdn.microsoft.com. Typing "algorithms" into their search page will bring up quite a few of them. You can of course be more specific in your searches.

    Finally, try google. If you know the general type of algorithm you want, you can find it that way.
    0
     
    LVL 9

    Accepted Solution

    by:
    read the comments before count_combos function.

    /*
      File: change.cpp
      Date: 08.13.2003
      Author: Jaydutt Shukla
      Purpose: This program asks for amount of money (in cents) and outputs the number of
      ways in which change can be given back for amounts <= MAX
    */

    #include <iostream>
    #include <iomanip>
    using namespace std;

    const int MAX=2000; //will calculate # of combos only if amount <= MAX. requires very deep recursion

    const int denoms[]={1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000}; //const array for denominations

    unsigned long  count_combos(int, int=0);

    int main(){
        int cents=0, copy=0;
       
        cout << "Enter amount in cents: ";
        cin >> cents;
        copy = cents;
        if(cents <= MAX){
          cout << "Most efficient change is: \n";
          if(cents ==0){
              cout << "0 x $   0.00" << endl;
              cout << "Change can be given in " << count_combos(copy) << " different ways" << endl;
              return 0;
          }
          for(int i=11; i>=0; i--){
              //setiosflags(ios::fixed);
              if(cents/denoms[i])
                cout << cents/denoms[i] << " x " << "$ "
                     << setprecision(2) << setiosflags(ios::fixed) << setw(6)
                     << denoms[i]/100.0 << endl;
              cents %= denoms[i];
          }
          
          cout << "Change can be given in " << count_combos(copy) << " different way(s)" << endl;
        }
        else
          cout << "Amount exceeds the limit." << endl;
       
        return 0;
    }

    /*
     Recursive function:
     Start with pennies and denom d
     counter = 1;
     Determine how many d's do you want. range = [0, amount/d). use a for loop
       recurse with remaining pennies and next higher denomination
       Add this number to counter
       Increment # of d's

     ... and there are stopping conditions.
     */
    /* After you understand the working of this fcn:
       to extend this fcn for higher denominations append those to the const array denoms;
       change MAX to the max amount you want
       */
    unsigned long count_combos(int amount, int d){ //d == index into denoms array
        unsigned long count = 1;
       
        if(amount > MAX) return 1;   //do not exceed MAX denomination
       
        if(amount == 0) return 1;
        if(denoms[d] > amount) //Example: there is no way you can give out 1 cent using nickels
          return 0;
        /* The only problem occurs when starting amount == 0
           should the answer be 0 or 1? I chose 1. see previous line */
       
        for(int i=0; i<amount; i += denoms[d+1])
          count += count_combos(amount - i, d + 1);
       
        return count;
    }
    0
     

    Author Comment

    by:C-begin
    hey guys thank you very much,

    I will try to read a bit more, for now....how do I split the points ?
    0

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Shellfire Box VPN + Lifetime Subscription

    The Shellfire Box easily connects all of your devices, even those that don't offer the possibility to establish a safe vpn connection. Access blocked content and surf safely, no matter where in the world you are located.

    Here we come across an interesting topic of coding guidelines while designing automation test scripts. The scope of this article will not be limited to QTP but to an overall extent of using VB Scripting for automation projects. Introduction Now…
    Since upgrading to Office 2013 or higher installing the Smart Indenter addin will fail. This article will explain how to install it so it will work regardless of the Office version installed.
    In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…
    In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …

    884 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    18 Experts available now in Live!

    Get 1:1 Help Now