jhjfbsbfkbjfnfnfjfj's blog

Coin Toss in Dynamic Programming

By jhjfbsbfkbjfnfnfjfj, history, 7 years ago, In English

I have this programming prompt where I have been asked to find the number of permutations of a 32 coin toss sequence that do not have three consecutive heads in a row.

I have been tasked to find this with dynamic programming and I am having a hell of a time trying to figure out the recursive algorithm.

I have tried a two variable approach where I try and keep track of whether the previous two flips were heads or tails and then incrementing based upon that. I have also tried breaking it into sub-problems where I start with a singular toss and then work my way up the full 32 tosses.

And I'm having a hard time visualizing how to approach this and figuring out how to keep track of everything as the algorithm commences.

Any help would be greatly appreciated.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I solved this using a simple recursive approach.

We keep track of two things: - tosses = number of tosses completed - consecutiveHeads = number of consecutive Heads at the end

If we choose Tail, consecutiveHeads becomes 0. If we choose Head, we can choose it only when consecutiveHeads < 2, otherwise we would create three consecutive Heads.

#include <bits/stdc++.h>
using namespace std;

long long solve(int tosses, int consecutiveHeads) {

    // Base case
    if (tosses == 32) {
        return 1;
    }

    // Choose Tail
    long long ans = solve(tosses + 1, 0);

    // Choose Head
    if (consecutiveHeads < 2) {
        ans += solve(tosses + 1, consecutiveHeads + 1);
    }

    return ans;
}

int main() {

    cout << solve(0, 0) << endl;

    return 0;
}

The recursion explores both possible outcomes at every toss, but the branch that would create HHH is not explored.

The answer for 32 tosses is:

18130386244425

→ Reply