StrawberryInsha2k's blog

By StrawberryInsha2k, history, 2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

First, I wrote this recursive algorithm, but I wasn't sure it would give the correct answer. I only checked where N was 1, 2, 3, 4, 5, 6, and the algorithm found them correct.

void cointoss(int n, int pre1, int pre2){
    // 1 is heads 0 is tails
    
    if(n == 0){
        sum++;
        return;
    }
    
    if(pre1 == 1 && pre2 == 1){
        cointoss(n - 1, 0, 1);
    }
    else{
        cointoss(n - 1, 0, pre1);
        cointoss(n - 1, 1, pre1);
    }
}

After that, I found this Dynamic Programming solution. I think this algorithm finds the answers correct.

int main(){
    unsigned long long int dp[1000] = {1, 2, 4};
    for(int i = 3; i < 1000; i++){
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
    printf("%llu", dp[32]);
}

When N was 32, both algorithms found 334745777.

I hope it will help.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks a lot. what is pre1 and pre2 and also can you tell about what states you considered in dp and how you deduced it?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Pre1 is the coin we selected from previous recursion and pre2 is the coin we selected from the previous recursion of the previous recursion.

      First of all, I created a tree. When I examined the tree after creating it, I decided that the number of leaves for each N height is the sum of the number of leaves for the heights of N-1, N-2, and N-3.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      For example, if the problem was finding the number of permutations of a 32 coin toss sequence that do not has four consecutive heads in a row, this would be the code we had to write:

      int main(){
          unsigned long long int dp[1000] = {1, 2, 4, 8};
          
          for(int i = 4; i < 1000; i++){
              dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4];
          }
          
          printf("%llu", dp[32]);
      }
      
    • »
      »
      »
      2 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Or we can write like this so that there will be less addition:

      unsigned long long int dp[1000] = {1, 2, 4, 8, 15};
          
          for(int i = 5; i < 1000; i++){
              dp[i] = dp[i - 1] * 2 - dp[i - 5];
          }