问题描述
- 有趣的数 算法的题 求思路
-
问题描述
我们把一个数称为有趣的，当且仅当：
1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。
2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。
3. 最高位数字不为0。
因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：2031和2301。
请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以1000000007的余数。
输入格式
输入只有一行，包括恰好一个正整数n (4 ≤ n ≤ 1000)。
输出格式
输出只有一行，包括恰好n 位的整数中有趣的数的个数除以1000000007的余数。
样例输入
4
样例输出
3答案：
import java.util.*;public class Main {
public static void main(String[] args) {
new Main().run();
}public void run() {
Scanner fin = new Scanner(System.in);int N = fin.nextInt();
long[] count = new long[8];
count[6] = 0;
count[7] = 1;
long mod = 1000000007; for (int i = 2; i <= N; ++i) {
long[] newCount = new long[8];
newCount[0] = (count[0] * 2 + count[1] + count[3]) % mod;
newCount[1] = (count[1] * 2 + count[2] + count[5]) % mod;
newCount[2] = (count[2] + count[6]) % mod;
newCount[3] = (count[3] * 2 + count[4] + count[5]) % mod;
newCount[4] = (count[4] + count[7]) % mod;
newCount[5] = (count[5] * 2 + count[6] + count[7]) % mod;
newCount[6] = 0;
newCount[7] = 1;count = newCount;
}System.out.println(count[0]);
}
}看不懂 求救 到底是什么思路
解决方案
其实算法很简单。
（需要一个假设前提，这个在题目中没有说清楚，会造成一些漏洞。
假设是N进制，否则当 N >10时，会出现 9,10,11,12, 这样数字，排列时需要考虑 10 这个十进制数时，没有任何符合条件的组合。)
恰好有n位的有趣的数的个数 为 (N-2)(N-1)/2
当 N = 4 时, 0,1,2,3 共有 (4-2)(4-1)/2 = 3 个数。
解决方案二：
推导出递推公式：
Fn+1=2Fn+(n-2)*(2^(n-1)-1)
解决方案三：
用字符串记录这个正整数，顺序生成所有可能的数字，然后挨个判断，合格的记录下来，记数加一。
解决方案四：
思路：
如果用程序变量去存储，有可能数字会很大，计算时间会很长。
考虑用大学里学的线性代数和概率来解决此问题。
解决方案五：
纠正一下，
正确的公式是 ** (N-2)! * (N-2)(N-1)/2**
公式的推导是：
一共N个数字，0,1,2,....N
这样除了 0,1 之外，还有 N-2 个数字。 把这 N-2 个数字排列好，则有 (N-2)! 个排列。
然后将0 在 (N-2) 这个排列中找一个位置放入,比如可以放在右起第1个数字后，可以放在第2个数字后，.... 可以放在第N-2个数字后。，则有 N-2 种放法。
假设"0" 放在了第M个数字后， M = (1...N-2) ，那么"1" 能放在位置则必须是否“0”之后，即可以有 M 种放法。这样，当M=1 时，"1" 有1种放法，M=2 时 "1" 有2种放法，...当M=N-2 时，"1" 有N-2种放法， 这个和是 1+2+3+....+(N-2) = (N-2) (N-1)/2
也就是"0","1" 一共有 (N-2) (N-1)/2 放法。
再乘上原来N-2数字的排列，则一共有 ** (N-2)! * (N-2)(N-1)/2**
4 个数字时 6
5 个数字时 36
其实算法很简单。
（需要一个假设前提，这个在题目中没有说清楚，会造成一些漏洞。
假设是N进制，否则当 N >10时，会出现 9,10,11,12, 这样数字，排列时需要考虑 10 这个十进制数时，没有任何符合条件的组合。)恰好有n位的有趣的数的个数 为 (N-2)(N-1)/2
当 N = 4 时, 0,1,2,3 共有 (4-2)(4-1)/2 = 3 个数。
解决方案六：
推导出递推公式：
Fn+1=2Fn+(n-2)*(2^(n-1)-1)
解决方案七：
数组里的七个数都是什么意思？
解决方案八：
请问你这个答案是哪里的？我也正在纠结这道题