Задачи автоматизированного зачета на последовательности. Осень 2011, 1 курс, 1 поток, 105 гр

Следующая ⇒

Задача №1.

Вычислить среднее арифметическое непустой последовательности вещественных чисел. Считать, что в последовательности есть хотя бы одно число.

Ответ: одно число – искомое среднее арифметическое n.

#include <stdio.h>

#include <assert.h>

void f101(FILE*, double*);

int main (void) {

FILE* in;

FILE* out;

double result;

out=fopen ("output.txt", "w"); if(out==NULL) return 1;

in=fopen("input.txt", "r"); if(in==NULL) { fclose(out); return 1; }

f101 (in, &result);

fprintf(out, "%lf", result);

fclose(in); fclose(out);

return 0;

}

void f101(FILE* filein, double* y){

double a, s=0.0; int q, n=0;

while( (q=fscanf(filein, "%lf", &a))==1){s=s+a; n=n+1;}

assert(q==EOF);

assert(n>0);

*y=s/n;

return;

}

Задача №2.

Вычислить среднее геометрическое непустой посл-ти вещественных чисел. В последовательности есть хотя бы одно число. Числа неотрицательны.

Ответ: одно число – искомое среднее геометрическое n.

#include <stdio.h>

#include <assert.h>

#include <math.h>

void f102(FILE*, double*, log*);

int main (void) {

FILE* in;

FILE* out;

double result;

out=fopen ("output.txt", "w"); if(out==NULL) return 1;

in=fopen("input.txt", "r"); if(in==NULL) { fclose(out); return 1; }

f102 (in, &result);

fprintf(out, "%lf", result);

fclose(in); fclose(out);

return 0;

}

void f102(FILE* filein, double* y){

double a, p=1.0; int q, n=0;

while( (q=fscanf(filein, "%lf", &a))==1){p=p*a; n=n+1;}

assert(q==EOF);

assert(n>0);

*y=exp(log (p)/n);

return;

}

Задача №3.

Вычислить среднее гармоническое непустой последовательности положительных вещественных чисел. В последовательности есть хотя бы одно число.

Ответ: одно число – искомое среднее гармоническое n.

#include <stdio.h>

#include <assert.h>

void f103(FILE*, double*);

int main(void) {

FILE* in;

FILE* out;

double result;

out=fopen(“output.txt”, “w”); if (out==NULL) return 1;

in = fopen(“input.txt”, “r”); if (in==NULL) { fclose(out); return 1; }

f103(in, &result);

fprintf(out, “%lf”, result);

fclose(in); fclose(out);

return 0;

}

void f103(FILE* filein, double* y) {

double a, s=0.0; int q, n=0;

while ((q=fscanf(filein, “%lf”, &a))==1) {s=s+(1/a); n++;}

assert (q==EOF);

assert (n>0);

*y=n/s;

return;

}

Задача №4.

Вычислить количество чисел, больших предыдущего, в последовательности вещественных чисел.

Ответ: одно число – искомое количество. Для пустой или одноэлементной последовательности – ответ 0.

#include <stdio.h>

#include <assert.h>

void f104(FILE*, double*);

int main(void) {

FILE* in;

FILE* out;

double result;

out=fopen(“output.txt”, “w”); if (out==NULL) return 1;

in = fopen(“input.txt”, “r”); if (in==NULL) { fclose(out); return 1; }

f10(in, &result);

fprintf(out, “%lf”, result);

fclose(in); fclose(out);

return 0;

}

void f102(FILE* filein, double* y) {

double a, s=0.0; int q, n=0;

while ((q=fscanf(filein, “%lf”, &a))==1) {s=s+(1/a); n++;}

assert (q==EOF);

assert (n>0);

*y=n/s;

return;

}

Задача №5.

Определить, есть ли в последовательности целых чисел данное число Х. В файле с данными сначала записано число Х, а далее за ним записываются элементы последовательности.

Ответ: слово true, если такой элемент есть, и слово false, если такого элемента нет. Для пустой последовательности ответ false.

Задача №6.

В последовательности целых чисел определить номер последнего числа, равного данному числу Х. Нумерация элементов последовательности начинается с единицы. В файле с данными записано сначала число Х, а далее за ним записываются элементы последовательности.

Ответ: одно число – искомый номер, если такой элемент есть, и значение -1, если такого элемента нет. Для пустой последовательности ответ -1.

Задача №7.

Определить, все ли элементы последовательности целых чисел равны между собой.

Ответ: слово yes, если все элементы одинаковы, и слово no в противном случае. Для пустой последовательности ответ yes.

Задача №8.

Определить монотонность последовательности вещественных чисел.

Ответ: 1, если строго возрастающая; -1, если строго убывающая, 0 в противном случае. Для пустой и одноэлементной ответ 0.

Задача №9.

Определить удовлетворяет ли последовательность вещественных чисел данному трехчленному рекуррентному соотношению с точностью е=0.0001. Пусть с1, с2, с3, d – заданные числа и обозначим х1, х2, х3 – 3 любых соседних последовательно идущих элемента последовательности. Тогда должно выполняться неравенство |x1*c1+x2*c2+x3*c3-d| < 0.0001.

Ответ: слово true, если указанное неравенство всегда выполнено, слово false, если неравенство нарушается хотя бы для одной тройки последовательных элементов или если последовательность содержит менее трех членов. В файле данных сначала записаны числа с1, с2, с3, а затем элементы последовательности.

Задача №10.

Определить количество различных элементов неубывающей последовательности чисел (при решении считается, что неубывание последовательности гарантировано, и его проверять не надо).

Ответ: одно число – искомое количество. Для пустой последовательности правильный ответ 0.

Задача №11.

Определить общее количество элементов во всех постоянных участках последовательности целых чисел.

Ответ: одно число-искомое количество. Для пустой последовательности ответ 0.

#include <stdio.h>

#include <assert.h>

void f111(FILE*, int*);

int main(void){

FILE*in;

FILE*out;

int result;

out=fopen("output.txt", "w"); if (out==NULL) return 1;

in=fopen("input.txt", "r"); if (in==NULL) { fclose(out); return 1;}

f111(in, &result);

fprintf(out, "%d", result);

fclose(in); fclose(out);

return 0;

}

void f111(FILE* filein, int*otvet){

int q, a1, a2, d, M;

q=fscanf(filein, "%d", &a1);

if (q==EOF) {*otvet=0; return;}

assert (q==1);

d=1; M=0;

while ((q=fscanf (filein, "%d", &a2))==1){

if (a1==a2) d++;

else {

if (d>=2) {M=M+d; d=1;}

a1=a2;

}

assert (q==EOF);

if (d>=2) M=M+d;

*otvet=M;

return;

}

Задача №12.

Определить порядковый номер первого элемента, который является максимальным во всей последовательности вещественных чисел (нумерация начинается с 1).

Ответ: одно число – искомый номер. Для пустой последовательности правильный ответ -1.

Задача №13.

Определить порядковый номер последнего элемента, который является минимальным во всей последовательности вещественных чисел (нумерация элементов начинается с 1).

Ответ: одно число – искомый номер. Для пустой последовательности правильный ответ -1.

Задача №14.

Определить количество элементов последовательности целых чисел, равных минимальному значению по всем элементам последовательности.

Ответ: одно число – искомое количество. Для пустой последовательности правильный ответ 0.

#include <stdio.h>

#include <assert.h>

void f114(FILE*, int*);

int main (void) {

FILE* in;

FILE* out;

int result;

out=fopen ("output.txt", "w"); if(out==NULL) return 1;

in=fopen("input.txt", "r"); if(in==NULL) { fclose(out); return 1; }

f114 (in, &result);

fprintf(out, "%d", result);

fclose(in); fclose(out);

return 0;

}

void f114(FILE* filein, int* otvet){

int q, n=0, min, a;

q=fscanf(filein, "%d", &a);

if (q==EOF) {*otvet=0; return;}

assert (q==1);

min=a; n=1;

while( (q=fscanf(filein, "%d", &a))==1){

if (a<min) {min=a; n=1;}

else if (a==min) n++;

}

assert(q==EOF);

*otvet=n;

return;

}

Задача №15.

Вычислить среднеквадратическое отклонение от среднего арифметического для вещественной последовательности, т.е. сумму D=1/N sum_{i=1}^{N} (x_i – M)^2, где М – среднее арифметическое последовательности, x_i – элементы последовательности.

Ответ: одно вещественное число – искомое отклонение. При решении задачи можно считать, что исходная последовательность непуста.

Задача №16.

Вычислить максимальное отклонение элементов последовательности вещественных чисел от среднего арифметического этой последовательности.

Задача №17.

Определить количество возрастающих участков в последовательности вещественных чисел.

Возрастающий участок – это группа из более чем одного элемента последовательности, где каждый следующий элемент строго больше предыдущего.

Ответ: одно целое число – искомое количество. Для последовательности, содержащей менее двух элементов, правильный ответ 0.

Задача №18.

Определить сумму всех четных элементов, расположенных в возрастающих участках последовательности целых чисел. (см 17)

Ответ: одно целое число – искомая сумма. Для последовательности, содержащей менее двух элементов или не умеющей возрастающих участков, правильный ответ 0.

#include <stdio.h>
#include <assert.h>
void f118(FILE*, int*);

int main(void){
FILE*in;
FILE*out;
int result;
out=fopen(“output.txt”, “w”); if (out==NULL) return 1;
in=fopen(“input.txt”, “r”); if (in==NULL) {fclose(out); return 1;}
q=fscanf(in, “%d”, &last);
f118(in, &result);
fprintf(out, “%d”, result);
fclose(in); fclose(out);
return 0;
}

void f118(FILE* filein, int* otvet){
int last, s=0.0, n=1.0, q, a;
q=fscanf(filein, “%d”, &last);
if(q==EOF) {*otvet=0; return;}
while ((q=fscanf(filein, “%d”, &a))==1){
if (last<a) {n++;}
if((n>1)&&(last%2==0)) {s+=last; last=a;}
else if(last>=a) {n=1; last=a;}
last=a;
}
if ((n>1)&&(last%2==0)) s+=last;
}
*otvet=s;
assert(q==EOF);
return;
}

void f18(FILE* filein, int* otvet){
int h=0, t=0, s=0, a, aold=1000000, q;
while ((q=fscanf(filein, “%d”, &a)==1)){
if (a>aold) {h++; t++;}
if ((h>0)&&(aold%2==0)) {s+=aold;}
if (a<=aold) {h=0;}
aold=a;
}
if ((h>0)&&(aold%2==0)) {s+=aold;}
if (t=0) {*otvet=0;}
else {*otvet=s;}
return;
}

Задача №19.

Определить каких участков в последовательности вещественных чисел больше – возрастающих или невозрастающих. Если в последовательности более одного элемента, то возрастающие и невозрастающие участки в ней естественным образом чередуются так, что конец одного участка является началом другого.

Ответ: 1, если возрастающих больше, -1, если невозрастающих больше, 0, если поровну. Для последовательности, содержащей менее двух элементов, правильный ответ 0.
n-невозрастающих, N-возрастающих

#include <stdio.h>
#include <assert.h>
void f119(FILE*, int*);

int main(void){
FILE*in;
FILE*out;
int result;
out=fopen(“output.txt”, “w”); if(out==NULL) return 1;
in=fopen(“input.txt”, “r”); if(in==NULL) {fclose(out); return 1;}
f119(in, &result);
fprintf(out, “%d”, result);
fclose(in); fclose(out);
return 0;

}

void f119(FILE* filein, int* otvet){
int q, a1, a2, N=0.0, n=0.0, last:

q=fscanf(filein, “%d”, &last);
if(q==EOF) {*otvet=0; return;}
assert(q==1);

while((q=fscanf(filein, “%d”, &a1))==1){
if(last<a1&&a1<a2) N++;
else if(last>=a1&&a1>=a2) n++;

last=a1;

assert(q==EOF);

if(N>n) *otvet=1;

else if(N<n) *otvet=-1;
else if(N=n) *otvet=0;

}

return;

}

void f19(FILE* filein, int* y){

int up=0, down=0, q, h=0, t=0;

double a, aold;

q=fscanf(filein, “%lf”, &aold);
if (q==EOF) {*y=0; return;}

while ((q=fscanf(filein, “%lf”, &a))==1){
if ((a>aold)&&(k==0)) {t=0; h=1; up++;}

else if (t==0) {t=1; h=1; down++;}

aold=a;

}

if (up==down {*y=0} else
if (up>down) {*y=1} else {*y=-1;}

return;

}

Задача №20.

Определить наибольшее количество подряд идущих элементов последовательности целых чисел, имеющих одно и то же значение.

Ответ: одно число – искомое максимальное количество. Если в последовательности нет соседних элементов с одинаковым значением, то ответ 1, для пустой – 0.

#include <stdio.h>

#include <assert.h>

void f120(FILE*, int*);

int main(void){

FILE* in;

FILE* out;

int result;

out=fopen(“output.txt”, “w”); if (out==NULL) return 1;

in=fopen(“input.txt”, “r”); if (in==NULL) {fclose(out); return 1;}

f120(in, &result);

fprintf(out, “%d”, result);

fclose(in); fclose(out);

return 0;

}

void f120(FILE* filein, int* otvet){

int q, a1, a2, d, M;

q=fscanf(filein, “%d”, &a1;);

if(q==EOF) {*otvet=0; return;}

assert (q==1);

d=1; M=0;

while ((q=fscanf(filein, “%d”, &a2))==1){
if(a1==a2) d++;
else {
if(d>=2&&d>M) {M=d; d=1;}
}
a1=a2;
}
assert(q==EOF);
*otvet=M;
return;
}

Задача №21.

Определить длину (количество элементов) в постоянном участке последовательности целых чисел, имеющем наибольшую сумму своих элементов.

Ответ: одно число – искомое количество элементов. Если в последовательности нет постоянных участков, то в файл ответа вывести слово false. Если же в последовательности несколько участков с максимальной суммой, то нужно вывести длину первого из них.

#include <stdio.h>

#include <assert.h>

void f121(FILE*, int*);

int main(void){

FILE* in;

FILE* out;

int result;

out=fopen(“output.txt”, “w”); if (out==NULL) return 1;

in=fopen(“input.txt”, “r”); if (in==NULL) {fclose(out); return 1;}

f121(in, &result);

fprintf(out, “%d”, result);

fclose(in); fclose(out);

return 0;

}

void f121(FILE* filein, int* otvet){

int q, s=0, sold=-1000000, l=0, lfin=0, b=0, a, aold, h;

q=fscanf(filein, “%d”, &aold);

if(q==EOF) {*otvet=10000000; return;}

while ((q=fscanf(filein, “%d”, &a))==1){

if(a=aold) {
if (h=0) {s=a+aold; l=2; b=1;}

else {s+=a; l++;}

} else {

if(h=1) {

if (s>sold) {

lfin=l;

sold=s;

}
h=0;
}

}

aold=a;

}

if (b=0) {*y=1000000;}

else {*y=lfin;}

return;

}

Задача №22.

Определить наибольшую длину (количество элементов) возрастающих участков последовательности вещественных чисел.

Ответ: одно число – искомое количество элементов. Если в последовательности нет возрастающих участков (в том числе, для пустой и одноэлементной последовательностей), то в качестве ответа надо вывести в файл слово false.

Задача №23.

Определить наибольшую сумму элементов по возрастающим участкам последовательности вещественных чисел (т.е. максимум из сумм элементов по каждому возрастающему участку).

Ответ: одно число – искомая максимальная сумма. Если в последовательности нет возрастающих участков, то в ответ записать слово false.

Задача №24.

Вычислить среднее арифметическое экстремумов последовательности целых чисел. Элемент последовательности называется экстремумом (максимумом или минимумом), если элементы, стоящие рядом с ним, строго меньше (строго больше). В частности, первый и последний элементы также могут быть экстремумами, в этом случае сравнение рассматривается только для одного соответствующего соседнего элемента.

Ответ: одно число – искомое среднее арифметическое. Если в последовательности нет экстремумов (в том числе и для пустой последовательности), то в ответ надо записать слово false.

#include <stdio.h>

#include <assert.h>

void f124(FILE*, int*);

#define False 0

int main(void){

FILE*in;

FILE*out;

int result;

out=fopen(“output.txt”, “w”); if(out==NULL) return 1;

in=fopen(“input.txt”, “r”); if(in==NULL) {fclose(out); return 1;}

f124(in, &result);

if (result==False) fprintf(out, “false”);

fprintf(out, “%d”, result);

fclose(in); fclose(out);

return 0;

}

void f124(FILE* filein, int* otvet){

int q, a1, a2, a3, s=0.0, n=0.0; double y=0.0;

q=fscanf(filein, “%d”, &a1);

if(q==EOF) {*otvet=0; return;}

assert(q==1);

while((q=fscanf(filein, “%d”, &a2))==1){

if(a1<a2&&a3<a2) or (a1>a2&&a3>a2) {s+=a1; n++;}

y=(double)s/(double)n;

*otvet=y;

else {*otvet=False; return ;}

}

assert(q==EOF);

return;

}

Задача №25.

Вычислить максимальное расстояние (разность порядковых номеров) между соседними максимумами в последовательности целых чисел. Первый и последний элементы могут быть максимумами, в этом случае сравнение рассматривается только для одного соседнего элемента.

Ответ: одно число – искомое расстояние. Если в последовательности менее двух максимумов, то в ответ надо записать слово false.

Задача №26.

Определить среднее арифметическое всех значений элементов последовательности целых чисел, учитывая только одно из значений для каждого постоянного участка.

Ответ: одно вещественное число – искомое среднее арифметическое. При решении можно считать, что последовательность не пуста.

#include <stdio.h>

#include <assert.h>

void f126(FILE*, double*);

int main(void) {

FILE*in;

FILE*out;

double result;

out=fopen(“output.txt”, “w”); if(out==NULL) return 1;

in=fopen(“input.txt”, “r”); if(in==NULL) {fclose(out); return 1;}

f126(in, &result);

fprintf(out, “%d”, result);

fclose(in); fclose(out);

return 0;

}

void f126(FILE* filein, double*otvet){

int q, a1, a2, s=0.0, n=0.0; double t;

q=fscanf(filein, “%d”, a1);

s+=a1; n=1.0;

while ((q=fscanf(filein, “%d”, &a2))=1); {

if (a2!=a1) {s+=a2; n++; a1=a2;}

}

assert (q==EOF);

t=(double)s/(double)n;

*otvet=t;

return;

}

Задача №27.

Определить среднее арифметическое значений постоянных участков последовательности целых чисел.

Ответ: одно вещественное число – искомое среднее арифметическое. Если в последовательности нет постоянных участков, то ответ должен быть 0.

#include <stdio.h>

#include <assert.h>

void f127(FILE*, int*);

int main(void){

FILE*in;

FILE*out;

int result;

out=fopen(“output.txt”, “w”); if (out==NULL) return 1;

in=fopen(“input.txt”, “r”); if (in==NULL) {fclose(out); return 1;}

q=fscanf(in, “%d”, &last);

f127(in, &result);

fprintf(out, “%d”, result);

fclose(in); fclose(out);

return 0;

}

void f127(FILE* in, int* otvet){

int a1, a2, s=0.0, n=0.0, q; double y;

q=fscanf(filein, “%d”, &a1);

if(q==EOF) {*otvet=0; return;} assert(q==1);

while ((q=fscanf(filein, “%d”, &a2))==1){

if (a1==a2) {s+=a1; n++;}

y=(double)s/(double)n;

*otvet=y;

return;

}

Задача №28.

Определить максимальную сумму подряд идущих элементов в последовательности вещественных чисел (т.е. элементов, имеющих последовательные номера от некоторого k до некоторого m).

Ответ: одно число – значение искомой максимальной суммы. При решении задачи можно считать, что последовательность не пуста.

Задача №29.

Последовательность вещественных чисел представляет собой коэффициенты многочлена, записанные в порядке возрастания степеней. Требуется вычислить значение многочлена и его производной в заданной точке Х. В файле данных сначала записано число Х, а далее за ним записываются элементы последовательности коэффициентов. Хотя бы одно число из последовательности и число Х обязательно присутствуют в файле.

Ответ: два числа – значение многочлена и производной.

Последовательности w={a1,a2,…,an} сопоставим многочлен Pw(t)=a1+a2 t+…+an t^(n-1), причем будем считать, что пустой последовательности сопоставлен многочлен, тождественно равный 0. Поскольку w*a={a1,…,an,a} при n>1, то получаем Pw*a(t)=Pw(t) + a*t^n, откуда P ҆ w*a(t)=P ҆ w(t)+n*a*t^(n-1)

Для фиксированного вещественного числа х сопоставим последовательности w длины >=1 четыре числа:

P=Pw(x); dp=P ҆ w(x), n-число элементов в w, M=x^(n-1) (считаем, что нулевая степень любого числа х равна 0, в частности 0.0^0=0.0). При переходе от последовательности w к последовательности w*a эти 4 числа пересчитываются следующим образом:

p(new)=p+a*M(new); dp(new)=dp+n*a*M; n(new)=n+1; M(new)=M*x

#include <stdio.h>

#include <assert.h>

void f129(FILE*, double *, double *);

int main(void) {

FILE* in;

FILE* out;

double q;

double y, dy;

out=fopen(“output.txt”, “w”); if (out==NULL) return 1;

in = fopen(“input.txt”, “r”); if (in==NULL) { fclose(out); return 1; }

q=fscanf(in, “%lf”, &x);

f129(in, &y, &dy);

fprintf(out, “%lf”, y, dy);

fclose(in); fclose(out);

return 0;

}

void f129(FILE* filein, double* x, double* y, double* dy) {

int n; double a, p, dp, M, q;

dp=0.0; n=1.0; M=1.0;

while ((q=fscanf(filein, “%lf”, &a))==1) {

dp=dp+n*a*M;

M=M*x;

n++;

p=p+a*M;

}

assert (q==EOF);

*y=p; *dy=dp;

return;

}

Задача №30.

Последовательность вещественных чисел представляет собой коэффициенты многочлена, записанные в порядке убывания степеней. Требуется вычислить значение многочлена и его производной в заданной точке Х. В файле данных сначала записано число Х, а далее за ним записываются элементы последовательности коэффициентов. Хотя бы одно число из последовательности и число Х обязательно присутствуют в файле.

Ответ: два числа – значение многочлена и производной.

Последовательности w={a1,a2,…,an} сопоставим многочлен Pw(t)=a1 t^(n-1)+a2 t^(n-2)+…+an-1 t + an, причем будем считать, что пустой последовательности сопоставлен многочлен, тождественно равный 0. Поскольку w*a={a1,…,an,a} при n>1, то получаем Pw*a(t)=Pw(t)*t + a, откуда P ҆ w*a(t)=P ҆ w(t)*t+Pw(t)

Для фиксированного вещественного числа х: y=Pw(x); dy=P ҆ w(x); y(new)=Pw*a(x); dy(new)=P ‘ w(x). Тогда: y(new)=Pw(x)*x+a; dy(new)=P ҆ w(x)*x+Pw(x); то есть y(new)=y*x+a; dy(new)=dy*x+y.

#include <stdio.h>

#include <assert.h>

#include <stdlib.h>

#include <math.h>

void f130(FILE* f, double* p, double* dp);

int main(void) {

FILE* in;

FILE* out;

int q; double X, Y, DY;

out=fopen(“output.txt”, “w”); if (out==NULL) return 1;

in = fopen(“input.txt”, “r”); if (in==NULL) { fclose(out); return 1; }

q=fscanf(in, “%lf”, &X); assert (q==1);

f130(in, X, &Y, &DY);

fprintf(out, “%lf %lf”, Y, DY);

fclose(in); fclose(out);

return 0;

}

void f130(FILE* filein, double* x, double* y, double* dy) {

int q; double a;

while ((q=fscanf(filein, “%lf”, &a))==1) {

*dy=dy*x+y;

*y=y*x+a;

}

assert (q==EOF);

return;

}

#include <stdio.h>

#include <assert.h>

#include <stdlib.h>

#include <math.h>

void f130(FILE* f, double* p, double* dp);

int main(void) {

FILE* f=fopen(“input.txt”, “r”); if (f==NULL) return (-1);

double p, dp;

f130(f, &p, &dp);

fclose(f);

FILE* out = fopen(“output.txt”, “w”); if (out==NULL) return (-1);

fprintf(out, “%lf %lf\n”, p, dp);

fclose(out);

return 0;

}

void f130(FILE* f, double* p, double* dp) {

double pv=0., dpv=0., a, t;

if (fscanf(filein, “%lf”, &t)<1)

exit(-1);

while (fscanf(filein, “%lf”, &a)==1) {

dp=dpv*t+pv;

pv=pv*t+a;

*p=pv; *dp=dpv;

}

return;

}

Следующая ⇒