pascal奇怪数列

来源:百度知道 编辑:UC知道 时间:2024/07/04 01:56:29
编程输入3个整数n,p,q,寻找一个由整数组成的数列(a1,a2,……,an),要求:其中任意连续p项之和为正数,任意连续q项之和为负数。0<n<100,0<p,q<n,若不存在这样的整数数列,则输出NO;否则输出满足条件的一个数列即可。
请给出算法和伪代码,谢谢各位大虾啦!

设a[0](等于0)到a[i]的部分和为s[i],则只要求出s[0], s[1], …, s[n]之间的关系即可。而他们之间的关系可以用有向图表示,且在有向图中连成环的即为无解。对于a[i]至a[j]的和的表示方法,可以表示为s[j]-s[i-1]。
求n=6,p=3,q=5时的数列。
设这六个数和a[0]为:
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
部分和为:
s[0] s[1] s[2] s[3] s[4] s[5] s[6]
则可以得出:
s[3]-s[0]>0, s[4]-s[1]>0, s[5]-s[2]>0, s[6]-s[3]>0, s[5]-s[0]<0, s[6]-s[1]<0
即:
s[3]>s[0], s[4]>s[1], s[5]>s[2], s[6]>s[3], s[0]>s[5], s[1]>s[6]
由此可知,这个数列有解,且s数组的大小顺序为:
s[4]>s[1]>s[6]>s[3]>s[0]>s[5]>s[2]
又因为已知s[0]=0,所以将其余数依次加/减1,得:
s[4]=4, s[1]=3, s[6]=2, s[3]=1, s[0]=0, s[5]=-1, s[2]=-2
即s数组依次为:
0, 3, -2, 1, 4, -1, 2
由此可知a数组依次为:
3, -5, 3, 3, -5, 3

我的代码太丑了,这个是sqybi在N年前写过的程序..
Program n_p_q;
Const
m = 10;

Var
s, n, p, q, i, k, L: Integer;
G: Array[0..m, 0..m]Of 0..1;
t: Array[0..m]Of Record
i, o: Integer;
f: Boolean;