我特灵解决这个问题：“给你一个整数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。）