我特灵解决这个问题:“给你一个整数N,考虑一个包含整数{1,2,......,N}的序列,这些整数按递增顺序排列(每个整数恰好出现一次),求出其相邻子序列的最大长度,这些子序列的和为偶数。
这是我想出来的代码
#include <stdio.h>
int Nsum(int n);
int main(void) {
int t, n;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
int z = Nsum(n);
printf("%d\n", z);
// printf("%d\n", sum);
}
return 0;
}
int Nsum(int n) {
int count = 0;
int sum = 0;
for(int i = 1; i <= n; i++)
{
sum = sum + i;
count++;
}
if (sum % 2 == 0)
{
return count;
}
else (Nsum(n - 1));
}
1条答案
按热度按时间4nkexdtk1#
请考虑以下情况:
| 不|序列号|元素总和|一个和为偶数极大子序列|其长度|
| - -|- -|- -|- -|- -|
| 第0页|{一}|第0页|第{ 0 }条|第0页|
| 一个|{ 1 }已安装|一个|{一}|第0页|
| 2个|{ 1、2 }|三个|第二章|一个|
| 三个|{ 1、2、3 }|六个|{ 1、2、3 }|三个|
| 四个|第1、2、3、4页|10个|第1、2、3、4页|四个|
| 五个|{ 1、2、3、4、5 }|十五|{ 2、3、4、5 }|四个|
| 六个|{ 1、2、3、4、5、6 }|二十一个|{ 2、3、4、5、6 }|五个|
| 七个|{ 1、2、3、4、5、6、7 }|二十八人|{ 1、2、3、4、5、6、7 }|七个|
这里我们可以很容易地看到一些模式,其中一种模式是,当和为偶数时,整个序列{ 1,... N }是和为偶数的最大子序列;当和为奇数时,去掉1得到{ 2,... N },得到和为偶数的最大子序列。
另一种模式是,只要N为偶数,{ 1,... N }之和的奇偶性(偶/奇)与前一个N保持相同,因为增加偶数不会改变它。只要N为奇数,奇偶性就会改变。因此,该模式为:
| N的奇偶性|总和奇偶校验|
| - -|- -|
| 偶|保持不变|
| 奇数|变更|
| 偶|说同样的话|
| 奇数|变更|
奇偶性需要两次变化才能恢复到原来的状态。每两个奇数发生两次变化,因此每四步发生一次。因此,当N经过四个值时,和的奇偶性经历了一个完整的循环。因此,N模4的余数告诉我们在循环中的位置:
| N % 4|和的奇偶性|最大子序列的长度|
| - -|- -|- -|
| 第0页|偶|不|
| 一个|奇数|N−1|
| 2个|奇数|N−1|
| 三个|偶|不|
因此,
Nsum
可以实现为:(Note不处理负N。)