求符合条件的正整数序列的数量
本帖最后由 Given2001 于 2020-3-18 13:31 编辑问题描述:
小明想知道,满足以下条件的正整数序列的数量:
1. 第一项为 n;
2. 第二项不超过 n;
3. 从第三项开始,每一项小于前两项的差的绝对值。
请计算,对于给定的 n,有多少种满足条件的序列。
输入格式:
输入一行包含一个整数 n。
输出格式:
输出一个整数,表示答案。答案可能很大,请输出答案除以10000的余数。
样例输入:
4
样例输出:
7
样例说明:
以下是满足条件的序列:
4 1
4 1 1
4 1 2
4 2
4 2 1
4 3
4 4
评测用例规模与约定:
对于 20% 的评测用例,1 <= n <= 5;
对于 50% 的评测用例,1 <= n <= 10;
对于 80% 的评测用例,1 <= n <= 100;
对于所有评测用例,1 <= n <= 1000。
我的疑问
以下是我的代码,纯粹通过递归暴力算的,问题就是数据一大,甚至n超过15都要算半天
有没有更好的办法,或者优化我的方法(本人萌新,代码写的烂大佬勿怪)
#include <iostream>
#include <cmath>
using namespace std;
int n;
int ret;
void ca(int a, int b)
{
int ab = abs(a - b);
int c;
for (c = 1; c < ab; c++)
{
ret++;
//cout << a << '\t' << b << '\t' << c << endl;
ca(b, c);
ret %= 10000;
}
}
int main()
{
cin >> n;
ret = 0;
for (int i = 1; i <= n; i++)
{
ret++;
//cout << n << '\t' << i << endl;
ca(n, i);
}
cout << ret << endl;
return 0;
}
研究了一晚上算是找到了点点规律,发出来大家共同学习=。=
(不一定对,有错误请大佬指正)
首先,我们先手算一下n为6时所有可能的序列(当然你也可以用代码)
6 1
6 1 1
6 1 2
6 1 3
6 1 3 1
6 1 3 1 1
6 1 4
6 1 4 1
6 1 4 1 1
6 1 4 1 2
6 1 4 2
6 1 4 2 1
6 2
6 2 1
6 2 2
6 2 3
6 3
6 3 1
6 3 1 1
6 3 2
6 4
6 4 1
6 4 1 1
6 4 1 2
6 5
6 6
我们可以发现:
当 4 1 的后面分支都是相同的(我也表达不明白,看图)
可以得出:
当前一个数(a)和后一个数(b)相同时,产生的结果数也是相同的
于是我们将结果数保存在一个二维数组中,下一次要用时直接取用
经过测试,有效的减少了运算量,对于n=1000也能1s内得出结果
(虽然我也不知道答案是否准确就对了,希望有做出不同思路的大佬能跟我校对下答案)
贴下我优化后的代码
#include <iostream>
#include <cmath>
//#include <ctime>
using namespace std;
int buff;
//clock_t clSt, clEd;
int ca(int a, int b)
{
if (buff != 0) {
//由于ab相同后续的可能性也相同,这里我直接取用之前保存的结果数
return buff;
}
int ab = abs(a - b);
int c;
int count = 1;
for (c = 1; c < ab; c++)
{
//cout << a << '\t' << b << '\t' << c << endl;
count += ca(b, c);
}
count %= 10000;//每次都对结果取余,防止溢出(可能。。。还是会溢出)
buff = count;//保存结果
return count;
}
int main()
{
int n;
cin >> n;
//初始化
//clSt = clock();
int ret = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
buff = 0;
}
}
//第二个数
for (int i = 1; i <= n; i++)
{
//cout << n << '\t' << i << endl;
ret += ca(n, i);
}
ret %= 10000;
//clEd = clock();
cout << ret << endl;
//double runtime = (double)(clEd - clSt) / CLOCKS_PER_SEC;
//cout << "用时:" << runtime << endl;
return 0;
}
本帖最后由 Given2001 于 2020-3-29 13:19 编辑
2020年3月29日12:50:34 我又回来了{:10_266:}
竞赛老师已经讲解了这道题,看到老师的代码,我……
话不多说,先上代码
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
using namespace std;
int N;
const int MOD = 10000;
int mem;
int dfs(int pre, int cur) {
if (cur <= 0) return 0;
if (mem != 0) return mem;
return mem =
(1 + dfs(pre, cur - 1) + dfs(cur, abs(pre - cur) - 1)) % MOD;
}
void work() {
cin >> N;
cout << dfs(N, N) << endl;
}
int main() {
int a = clock();
work();
int b = clock();
clog << (b - a) << "ms" << endl;
return 0;
}
思路就是在我之前的优化代码上进一步优化。
原本递归函数中研究的是a与b所得出的结果数目
也就是说再最极端的情况下(记忆数组被填满)
我们需要运算结果1000*1000次,
再加上main函数里的一层循环
就是1000*1000*1000次,这时候我们就要考虑把最外层的循环给去掉
也就是把递归研究的问题转换为a与1~b所得出的结果总数
这样即使记忆数组被填满,也只有1000*1000次计算
大概是这样……
测试结果
14ms解决战斗!!
平均12ms就可以
原文地址 也不会 坐等大神回复 一点都不萌新{:10_266:} 冒个泡 跟大佬学习一下 大佬,敬仰 大佬 没有大佬来验证下我的思路吗。。。{:5_107:} 墨羽岚 发表于 2020-3-16 17:13
一点都不萌新
{:10_254:}我是货真价实的萌新啊,大佬可能根本不会考虑枚举把{:10_266:}不懂大佬的世界 完全看不懂,等大神指教 枚举法行不。。。虽然很麻烦 乔珂珂 发表于 2020-3-27 11:37
枚举法行不。。。虽然很麻烦
我一开始的方法就是枚举啊,emmm你指的枚举是啥{:10_277:} 为什么数学界的小明也跑到编程界来了{:10_266:}
纯属冒个泡,但这道题还真不会{:10_266:} 烟肖雨晨 发表于 2020-3-27 14:53
为什么数学界的小明也跑到编程界来了
纯属冒个泡,但这道题还真不会
小明是个神秘的人物{:10_334:} 谢谢谢谢 一点都不萌新{:5_100:} 学习一下~
~~ 墨羽岚 发表于 2020-3-16 17:13
一点都不萌新
老师的标准答案出来了,有兴趣看看嘛
页:
[1]
2