c语言算法问题在一个木板上刻一个长度为n的只由“E”，“F”，“O”三种字符组成的字符串（可以只有其中一种或两种字符，但绝对不能有其他字符），同时禁止同时出现“OO”的情况，算

Question

c语言算法问题
在一个木板上刻一个长度为n的只由“E”，“F”，“O”三种字符组成的字符串（可以只有其中一种或两种字符，但绝对不能有其他字符），同时禁止同时出现“OO”的情况，算一下一共有多少种满足要求的不同的字符串

Answer 1

(1)、由E、F、O组成的全部字符串为3^n;
(2)、想法有些麻烦，但应该是正确的，
同时出现"OO"的情况，
《1》、假设第一个位置出现“OO”，则“OO”（非O）（之后任意），则为2*3^(n-3),
《2》、假设第2个位置出现“OO”，则（非O）“OO”（非O之后任意），则为2*2*3^(n-4),
《3》、假设第i个位置出现“OO”，则（前面i-1个为非O）“OO”（非O之后任意），则为2^(i-1)*2*3^(n-i-2)
(3)、所以综上的话，应该是3^n - ∑（2^i*3^(n-i-2)(i=1 to n-1)