### StrawberryInsha2k's blog

By StrawberryInsha2k, history, 2 months ago, ,

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.

• +3

 » 2 months ago, # |   0 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, # ^ |   0 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, # ^ |   0 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 →   0 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 →   0 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]; }