早教吧 育儿知识 作业答案 考试题库 百科 知识分享

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

题目详情
c语言算法问题
在一个木板上刻一个长度为n的只由“E”,“F”,“O”三种字符组成的字符串(可以只有其中一种或两种字符,但绝对不能有其他字符),同时禁止同时出现“OO”的情况,算一下一共有多少种满足要求的不同的字符串
▼优质解答
答案和解析
(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)