XTU 1278 Arithmetic Sequence
发布时间
阅读量：
阅读量
||
等差数列
题目描述
给一个整数数列，请判断是否为等差数列。
输入
第一个部分包含一个整数值T（取值范围为1到100），用于表示测试用例的数量；对于每一个测试用例的第一行数据中包含一个整数值N（范围在3到1万之间），它代表了该序列中的元素数目；接下来的一行包含N个整数值（其中每一个值都落在从1到十亿的范围内）。
输出
如果数列构成等差数列，输出"Yes";否则，输出"No"。
样例输入
样例输出
原始代码如下：
#include<stdio.h>
int main()
{
int T;
scanf("%d", &T);
while (T--) {
int N;
scanf("%d", &N);
int ret = 1;
int a, b, d;
scanf("%d%d", &a, &b);
d = a - b;
N -= 2;
a = b;
while (N--) {
scanf("%d", &b);
if (a - b != d) {
ret = 0;
break;
}
a = b;
}
if (ret == 1)printf("Yes\n");
else printf("No\n");
}
return 0;
}
AI写代码所遇困难：
1、输入的未必是已经有序
2、排序的算法选择，小心超时
3、预留位不可以忘记
修改后代码如下：
#include<stdio.h>
int a[10001];
void XE(int s[], int n);
int main()
{
int T;
scanf("%d", &T);
while (T--) {
int N;
scanf("%d", &N);
int i, d;
//输入元素
for (i = 1; i <= N; i++)
scanf("%d", &a[i]);
//希尔排序
XE(a, N);
//判断是否为等差
d = a[1] - a[2];
for (i = 2; i < N; i++)
if (a[i] - a[i + 1] != d)break;
if (i < N)printf("No\n");
else printf("Yes\n");
}
return 0;
}
void XE(int s[], int n)
{
int i, j, d;
d = n / 2;
while (d >= 1)
{
for (i = d + 1; i <= n; i++)
{
s[0] = s[i];
j = i - d;
while ((j > 0) && (s[0] < s[j]))
{
s[j + d] = s[j];
j = j - d;
}
s[j + d] = s[0];
}
d = d / 2;
}
}
AI写代码习得知识：希尔排序
全部评论 (0)
还没有任何评论哟~