网易刚刚编程题：暗黑串

f(n-2)里的字符串，每个字符串的末尾都添加和当前末尾相同的字符串，不就是f(n-1)里的结尾为AA,BB或CC的字符串吗。 f(n) = f(n-2)*3 + 2(f(n-1)-f(n-2))     // f(n-1)里面有f(n-2)个以AA,BB,CC结尾的字符串，这种结尾的，新字符可以是任意的 剩下的就是两个不同字符串结尾的，新字符串有两种选择。

你们三道题都撸出来了吗？

没看懂题直接跳过，做了第三题(⊙o⊙)…

f(n)=2*f(n-1)+f(n-2)

求解

只考虑最后两个字符 相同时后面可以跟ABC三种情况，不同时两种，然后找下n最后两个字符和n-1的关系

package com.reno.newwangyi; import java.util.Scanner; public class black { static long summy = 0; public static void same(long deep, long last, long maxdeep) { if (maxdeep == deep) { summy += last; return; } same(deep + 1, last, maxdeep); diff(deep + 1, last * 2, maxdeep); } public static void diff(long deep, long last, long maxdeep) { if (maxdeep == deep) { summy += last; return; } diff(deep + 1, last, maxdeep); same(deep + 1, last, maxdeep); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { summy=0; long n = sc.nextInt(); if (n == 1) { System.out.println(3); continue; } if (n == 2) { System.out.println(9); continue; } same(1, 1, n); long out = 3*summy; System.out.println(out); } } }

2对应9我都没看出来 求解

这个题目考的是推理，不是编程哈