2 t1130386516 t1130386516 于 2014.12.11 11:05 提问

有趣的数 算法的题 求思路

问题描述
我们把一个数称为有趣的,当且仅当:
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]);
}
}

看不懂 求救 到底是什么思路

8个回答

ACMAIN_CHM
ACMAIN_CHM   Ds   Rxr 2014.12.11 15:29

其实算法很简单。

(需要一个假设前提,这个在题目中没有说清楚,会造成一些漏洞。
假设是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 个数。

qq_38276200
qq_38276200 回复qq_22162463: 不可以
3 个月之前 回复
qq_22162463
qq_22162463 这个题目可以出现除了0,1,2,3之外的数字吗?
一年多之前 回复
qq_22162463
qq_22162463 这个题目可以出现除了0,1,2,3之外的数字吗?
一年多之前 回复
qq_22162463
qq_22162463 这个题目可以出现除了0,1,2,3之外的数字吗?
一年多之前 回复
qq_22162463
qq_22162463 这个题目可以出现除了0,1,2,3之外的数字吗?
一年多之前 回复
qq_22162463
qq_22162463 这个题目可以出现除了0,1,2,3之外的数字吗?
一年多之前 回复
qq_22162463
qq_22162463 这个题目可以出现除了0,1,2,3之外的数字吗?
一年多之前 回复
qq_22162463
qq_22162463 这个题目可以出现除了0,1,2,3之外的数字吗?
一年多之前 回复
qq_22162463
qq_22162463 这个题目可以出现除了0,1,2,3之外的数字吗?
一年多之前 回复
Showne92
Showne92 2必须在3前面,(n-2)!就错了哇。。
2 年多之前 回复
ACMAIN_CHM
ACMAIN_CHM 回复t1130386516: 哦,少写了一个阶乘。应该是 (N-2)! * (N-2)(N-1)/2
接近 3 年之前 回复
t1130386516
t1130386516 五位的是20个 公式不对
接近 3 年之前 回复
t1130386516
t1130386516 (N-2)(N-1)/2 怎么归纳出的这个公式
接近 3 年之前 回复
smth_aaa111
smth_aaa111   2014.12.11 11:27

用字符串记录这个正整数,顺序生成所有可能的数字,然后挨个判断,合格的记录下来,记数加一。

t1130386516
t1130386516 有时间跟空间复杂度的 这样应该不行
接近 3 年之前 回复
ACMAIN_CHM
ACMAIN_CHM   Ds   Rxr 2014.12.11 20:55

纠正一下,

正确的公式是 ** (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 个数。

Showne92
Showne92 还有剩下的 n-2 个数中也能有0和1,其中0也必须在1前面,(n-2)!错了。。
2 年多之前 回复
t1130386516
t1130386516 不能出现其他数字
接近 3 年之前 回复
t1130386516
t1130386516 而且数字只能由0 1 2 3 组成 可以重复但是至少出现一次
接近 3 年之前 回复
t1130386516
t1130386516 回复ACMAIN_CHM: n=4的时候 只能是 2013 2301 2031 只能是这3种 看原题 0必须在1前面 2必须在3前面
接近 3 年之前 回复
ACMAIN_CHM
ACMAIN_CHM 回复ACMAIN_CHM: N=5时应该会有36种: 比如 2,3,4 这个排列下就会有6种 2,3,4,0,1 2,3,0,4,1 2,3,0,1,4 2,0,3,4,1 2,0,3,1,4 2,0,1,3,4
接近 3 年之前 回复
ACMAIN_CHM
ACMAIN_CHM N=4 时的 6 种 2,0,1,3 2,0,3,1 2,3,0,1 3,0,1,2 3,0,2,1 3,2,0,1
接近 3 年之前 回复
haiya1994
haiya1994   2014.12.13 01:33

推导出递推公式:
Fn+1=2Fn+(n-2)*(2^(n-1)-1)

htzzll
htzzll 这个递推公式是怎么推导出来的呀
2 年多之前 回复
Hjupan
Hjupan   2014.12.11 13:15

思路:

如果用程序变量去存储,有可能数字会很大,计算时间会很长。
考虑用大学里学的线性代数和概率来解决此问题。

haiya1994
haiya1994   2014.12.13 01:31

推导出递推公式:
Fn+1=2Fn+(n-2)*(2^(n-1)-1)

u012180351
u012180351 求教 公式推导思路啊
大约 2 年之前 回复
htzzll
htzzll   2015.03.18 17:08

数组里的七个数都是什么意思?

using_name
using_name   2015.10.14 23:50

请问你这个答案是哪里的?我也正在纠结这道题

Csdn user default icon
上传中...
上传图片
插入图片