0

I have an assignment that asks for us to make a program in C++ that takes the input from a user for the amount of numbers on a lottery ticket, and the amount of numbers in a lottery drawing. It should then calculates the odds of the user getting the numbers correct. This is (more or less) my first program I am writing in C++, so I am new to this. What I have so far is below. I am seeking help with making the program work. I can get values in for the declared variables, but cannot figure out how to write down what it is I actually need to do - which is a factorial function. I know the function, just don't know how to say it in C++

From what I understand at this point is that it should look something like this:

for (int i = 1; i <= k; i++) { result = (result * (n+1-i)) / i;

or something to that effect?.... at least this is what I have come across in the past couple of hours of searching for an answer online. I think I am getting close to figuring it out but I am at a road block.

I don't want someone to just tell me the answer. If you could explain to me what I am doing wrong and what I can do to fix it that would be most helpful for me.

#include <iostream>
#include <iomanip>

using namespace std;


int main (int argc, char** argv)
{
    int n, k;
    int odds;

    cout<< "How many numbers are printed on the lottery ticket? ";
    cin >> n ;  

    cout<<"How may numbers are selected in the lottery drawing? "; 
    cin >> k ;

    cout << "You entered " << n << " for how many numbers are printed on the lottery ticket, and " 

    << k << " for how many numbers are selected in the lottery drawing." << endl;

    for (int i = 1; i <= k; i++)
    {
        odds = (n * (n-k++))/k;

        cout << odds;    
        }
        return 0;
    }

When I run this I just get an endless stream of "3-3-3-3....". It's non-stop. At one point I was getting a number as the output (one VERY large incorrect number), but while I was tinkering with it I couldn't get it back.

Any guidance would be appreciated.

dewey hafta
  • 1
  • 1
  • 3
    Well, you ARE incrementing `k`, which is used in the condition `i <= k`, so the loop will never end. – E_net4 Sep 11 '14 at 15:03
  • 1
    It might, once k wraps around – Leeor Sep 11 '14 at 15:05
  • You say you know the math but don't know how to say it in C++. Can you write it in normal math notation? Can you show some sample inputs and the the correct output, calculated by hand? – bames53 Sep 11 '14 at 15:07
  • Indeed. Nevertheless, that is the line I would look to change. – E_net4 Sep 11 '14 at 15:07
  • 2
    As you say, you should write the factorial function, `k!`. The next step is to use that function to calculate `n!(n-k)!/k!`. So start with writing the factorial function, and the rest will follow from that. (What you suggest is nowhere near the factorial function, so you may want to look up the definition in a nearby book.) – molbdnilo Sep 11 '14 at 15:10
  • @molbdnilo: No, writing a factorial function is a terrible way to compute combinations or permutation on a real computer. – Ben Voigt Sep 11 '14 at 15:16

2 Answers2

2

This seems slightly difficult for a first assignment, unless you're most of the way through a computer science curriculum and only new to C++.

The formula for the odds, which is commonly known as "number of combinations", is frequently written in terms of factorials. But you can't manipulate those factorials effectively on a computer; they are far too large for any of the built-in data types.

Instead, it's important to cancel like terms from numerator and denominator. Interleaving multiplications and divisions can help even more.

I've previously posted working code for number of combinations on another question:

Your current code actually does have things interleaved pretty well, but you haven't been at all careful with the meanings of i and k and n, and you've also got undefined behavior from both reading and writing a variable between sequence points.

Specifically, this is illegal because the k in the denominator is unstable, since it is in the process of being incremented:

odds = n*(n-k++)/k;

You shouldn't be changing k here at all. The value varying from 1 to k is i. So this becomes:

odds = n * (n-i) / i;

You need all the terms to accumulate across loop iterations, so you should be multiplying by the previous odds value:

odds = odds * (n - i) / i;

But you do need n - 0 in the numerator, but no 0 in the denominator. You're chosen to make i one-based, you it's the numerator that needs to be adjusted:

odds = odds * (n + 1 - i) / i;

And now your code is extremely close to mine. Depending on your values of n and k you might still overflow. Changing the data type of odds to long long or double should help with that.

Community
  • 1
  • 1
Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
  • Thanks for the detailed explanation. It is my first programming class in the CS curriculum, and our first assignment. I have learned that the equation needed for this is (n!)(n-k!)/(k!). Got it. Correct me if I am wrong, but the way that I read for `(int i = 1; i <= k; i++)` is like this: the integer value for `i` is one, where `i` is less than or equal to one, then increment `i` by 1. If I use `odds = odds * (n - i) / i;` that should add a value to the variable `odds`? Then it should run through `odds = odds * (n + 1 - i) / i;` but here the last part `/i;` wouldn't that be just dividing by1? – dewey hafta Sep 12 '14 at 07:31
  • @deweyhafta: I have no idea where you are finding "`i` is less than or equal to one". `i` varies from `1` to `k`. `/i` is dividing by one on the first pass through the loop, the second pass it divides by two, the next pass by three, and so on. – Ben Voigt Sep 12 '14 at 13:53
  • Ahhhhhh, gotcha gotcha gotcha. Ok, I am still getting wrong results but I will keep playing with it and stepping though it to see if I am missing anything. Thanks for your help Ben. – dewey hafta Sep 13 '14 at 04:03
  • @deweyhafta: You can also look at the complete code in the linked answer. – Ben Voigt Sep 13 '14 at 04:16
0

This is the formula you need:

http://en.wikipedia.org/wiki/Lottery_mathematics

Make sure that you have the mathematics well in hand. Start with a function that implements that formula.

Once you have the formula in hand, you'll realize that the naive student factorial will never work. The biggest naive factorial you can have with a long is 20!; after that it overflows.

The right way to do it is logarithms and gamma function:

https://en.wikipedia.org/wiki/Gamma_function

So that formula will turn into: 

ln{n!/k!(n-k)!)} = ln(n!) - ln(k!) - ln((n-k)!)

But since gamma(n+1) = n!

lngamma(n+1) - lngamma(k+1) - lngamma(n-k-1)

The gamma function returns doubles, not integers or longs. It'll behave much better for you.

duffymo
  • 305,152
  • 44
  • 369
  • 561