Задачи автоматизированного зачета на массивы. Осень 2011, 1 курс, 1 поток, 105 гр
/* Задача 201. Среднее арифметическое положительных элементов массива */
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void f201(double*, int, double*, int *);
int main(void){
FILE* in;
FILE* out;
int ERROR;
double* A; int q,i; int N; double y;
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", &N);
if (q!=1 || N<0) return -1;
A=(double*) malloc(N*sizeof(double)); assert(A!=NULL);
for(i=0; i<N; i++) q=fscanf(in, "%lf", &A[i]);
assert (q==1);
f201(A,N, &y, &ERROR);
if(ERROR==-1) return ERROR;
fprintf(out,"%lf ", y);
fclose(in); fclose(out); free(A);
return 0;
}
void f201(double A[], int N, double* y, int* err){
int i,n; double s;
assert(N>0);
for (i=0,n=0,s=0.0; i<N; i++)
if(A[i]>0.0) {n=n+1; s=s+A[i];}
if (n==0) *err=-1;else *err=0;
*y=(s+0.0)/n;
return;
}
/* file 202.c
202. Переставить элементы массива вещественных чисел в обратном порядке.
Ответ: последовательно записанные элементы преобразованного массива.
*/
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void f202(double*, int);
int main(void){
FILE* in;
FILE* out;
double* A; int q,i; int N;
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", &N);
if (q!=1 || N<1) return -1;
A=(double*) malloc(N*sizeof(double));
for(i=0; i<N; i++) q=fscanf(in, "%lf", &A[i]);
assert (q==1);
f202(A,N);
for(i=0; i<N; i++) fprintf(out,"%lf ",A[i]);
fclose(in); fclose(out); free(A);
return 0;
}
void f202(double A[], int N){
double tmp;
int ind1=0, ind2=N-1;
assert(N>0);
while (ind1<ind2){
tmp=A[ind1]; A[ind1]=A[ind2]; A[ind2]=tmp;
ind1++; ind2--;
}
return;
}
Замечания. 1) При выводе чисел в файл out.txt они должны быть разделены пробелами, этот пробел предусмотрен в "%lf " . Если этот пробел будет опущен, то все числа сольются.
/* Задача 203. Суммирование: Anew[i]=A[0]+A[1]+...+A[i] */
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void f203(double*, int);
int main(void){
FILE* in;
FILE* out;
double* A; int q,i; int N;
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", &N);
if (q!=1 || N<1) return -1;
A=(double*) malloc(N*sizeof(double));assert(A!=NULL);
for(i=0; i<N; i++) q=fscanf(in, "%lf", &A[i]);
assert (q==1);
f203(A,N);
for(i=0; i<N; i++) fprintf(out,"%lf ",A[i]);
fclose(in); fclose(out); free(A);
return 0;
}
void f203(double A[], int N){
int i;
assert (N>0);
for (i=1; i<N; i++) A[i]=A[i-1]+A[i];
return;
}
/* Задача 204. Циклический сдвиг вправо на 1: Anew[0]=A[N-1];Anew[i]=A[i-1] */
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void f204(int*, int);
int main(void){
FILE* in;
FILE* out;
int* A; int q,i; int N;
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", &N);
if (q!=1 || N<1) return -1;
A=(int*) malloc(N*sizeof(int));
for(i=0; i<N; i++) q=fscanf(in, "%d", &A[i]);
assert (q==1);
f204(A,N);
for(i=0; i<N; i++) fprintf(out,"%d ",A[i]);
fclose(in); fclose(out); free(A);
return 0;
}
void f204(int A[], int N){
int i, tmp;
assert (N>0);
tmp=A[N-1];
for (i=N-1; i>0; i--) A[i]=A[i-1];
A[0]=tmp;
return;
}
Решение задачи 205 с подробными комментариями
При сдаче автоматизированного теста комментарии и часть assert’ов целесообразно опустить
Задача 205. Определить количество различных значений в массиве целых чисел. Ответ: одно число - искомое количество различных значений.
Для решения этой задачи, а также для решения задач 206 и 209 целесообразно предварительно упорядочить массив по неубыванию. Эту операцию будет выполнять функция f205sort. Тем самым в программе в одном файле 205.c будет три функции: main, f205, f205sort.
Сортирующая функция f205sort должна сделать массив неубывающим, то есть обеспечить, чтобы ни одна пара соседних элементов массива (x,y) не находилась в беспорядке:
void f205sort(int A[], int N){
#define Besporyadok(x,y) (x>y) /* Порядок <==> НЕубывание */
... ... ...
/* file 205.c */
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void f205sort(int*, int);
void f205(int*, int, int*); int main(void){
FILE* in; FILE* out;
int* A;
int q, N, i;
int otvet;
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", &N); if (q!=1 || N<1) return -1;
A = (int*) malloc(N*sizeof(int));
for(i=0; i<N; i++) q=fscanf(in,"%d",&A[i]);
assert (q==1);
f205(A,N,&otvet);
fprintf(out,"%d ",otvet);
fclose(in); fclose(out); free(A);
return 0;
}
void f205sort(int A[], int N){
#define Besporyadok(x,y) (x>y)
int i,j,tmp;
int ChisloBespor;
assert (N>0);
for (i=N-1; i>0; i=i-1) {
ChisloBespor=0;
for (j=0; j<i; j=j+1) {
if( Besporyadok(A[j],A[j+1]) ){
tmp=A[j];A[j]=A[j+1];A[j+1]=tmp;
ChisloBespor++;
}
}
if(ChisloBespor==0) return;
}
return;
}
void f205 (int A[], int N, int* y){
int i, n, last;
assert(N>0);
f205sort(A,N);
last=A[0];
for(i=1,n=1;i<N;i++){
if( last<A[i] ) n++;
last=A[i];
}
*y=n;
return;
}
/* Задача 206. Какое значение встречается в массиве наибольшее число раз.
Oтсортируем массив по неубыванию с помощью функции f205sort и будем решать задачу для неубывающего массива, находя в нем постоянный участок максимальной длины за один проход от начала к концу. */
/* (*y,*ny)=(значение максимальной кратности, максимальная кратность) */
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void f205sort(int*, int);
void f205(int*, int, int*); int main(void){
FILE* in; FILE* out;
int* A;
int q, N, i;
int otvet; /* переменная для получения ответа из функции f205 */
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", &N); assert(q==1&&N>0); /* N прочитано успешно */
A = (int*) malloc(N*sizeof(int));/*выделение N*4 байт для массива А*/
for(i=0; i<N; i++) q=fscanf(in,"%d",&A[i]);
assert (q==1); /* все элементы массива А прочитаны успешно */
f205(A,N,&otvet);
fprintf(out,"%d ",otvet);
fclose(in); fclose(out); free(A);
return 0;
}
/* Сортировка массива целых чисел на том же месте по неубыванию.
Массив А считается отсортированным по неубыванию, если для любой пары
x, y соседних элементов массива выполнено нестрогое неравенство x<=y.
*/
void f205sort(int A[], int N){
#define Besporyadok(x,y) (x>y) /* Порядок <==> НЕубывание */
int i,j,tmp;
int ChisloBespor; /* Число беспорядков */
assert (N>0);
for (i=N-1; i>0; i=i-1) {
ChisloBespor=0;
for (j=0; j<i; j=j+1) {
if( Besporyadok(A[j],A[j+1]) ){
tmp=A[j];A[j]=A[j+1];A[j+1]=tmp;
ChisloBespor++;
}
}
if(ChisloBespor==0) return;
}
return;
}
void f206(int A[], int N, int* y, int* ny){
int i, last, znach, dlina, maksdlina;
assert (N>0);
f205sort(A,N);
/* нахождение в неуб. массиве А[N] пост. участка макс. длины */
last=A[0]; znach=A[0]; dlina=1; maksdlina=1;
for (i=1; i<N; i++){
if (A[i]==last){
dlina++;
if(dlina>maksdlina){maksdlina=dlina;znach=A[i];}
}
else {znach=A[i]; dlina=1;}
last=A[i];
}
*y=znach; *ny=maksdlina;
return;
}
/* Задача 207. Удаление отрицательных элементов с уплотнением неотрицательных.
С помощью функции f207sort oтсортируем массив так, чтобы сначала шли неотрицательные элементы, затем – отрицательные.
Далее перебираем элементы от конца к началу и заменяем отрицательные элементы нулями; перебор прерывается, если обнаруживается неотрицательный элемент. */
/* Удаление отрицательных элементов с уплотнением неотрицательных.*/
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void f207sort(int*, int);
void f207(int*, int);
int main(void){
FILE* in;
FILE* out;
int* A;
int q, N, i;
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", &N);
if (q!=1 || N<1) return -1;
A = (int*) malloc(N*sizeof(int));
assert(A!=NULL);
for(i=0; i<N; i++) q=fscanf(in,"%d",&A[i]);
f207(A,N);
for (i=0; i<N; i++) fprintf(out, "%d ", A[i]);
fclose(in); fclose(out); free(A);
return 0;
}
void f207sort(int A[], int N){
#define Besporyadok(x,y) (x<0&&y>=0)
int i,j,tmp;
int ChisloBespor;
assert (N>0);
for (i=N-1; i>0; i=i-1) {
ChisloBespor=0;
for (j=0; j<i; j=j+1) {
if( Besporyadok(A[j],A[j+1]) ){
tmp=A[j];A[j]=A[j+1];A[j+1]=tmp;
ChisloBespor++;
}
}
if(ChisloBespor==0) return;
}
return;
}
void f207(int A[], int N){
int i;
assert (N>0);
f207sort(A,N);
for (i=N-1; i>=0; i--){
if (A[i]>=0)return; else A[i]=0;
}
return;
}
Задача 208. Полусуммы.
Случай одноэлементного массива разбираем отдельно. В массиве из 2-х или более элементов при обработке текущего элемента А[i] будем помнить его и предыдущий элемент А[i-1] в переменных double tek, pred.
/* Аnew[i]=(A[i-1]+A[i+1])/2;
Аnew[0]=(0+A[1])/2; Аnew[N-1]=(A[N-2]+0)/2; */
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void f208(int*, int, int*); int main(void){
FILE* in; FILE* out;
int* A; // Описание имени массива A[]
int q, N, i;
int otvet; /* переменная для получения ответа из функции f205 */
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", &N); assert(q==1&&N>0); /* N прочитано успешно */
A = (int*) malloc(N*sizeof(int));/*выделение N*4 байт для массива А*/
for(i=0; i<N; i++) q=fscanf(in,"%d",&A[i]);
assert (q==1); /* все элементы массива А прочитаны успешно */
f208(A,N,&otvet);
fprintf(out,"%d ",otvet);
fclose(in); fclose(out); free(A);
return 0;
}
void f208(double A[], int N){
int i; double pred, tek, predposl;
assert (N>0);
if(N==1){A[0]=0.0;return;};
predposl=A[N-2];
pred=A[0];
A[0]=A[1]/2.0;
for (i=1; i<N-1; i++){
tek=A[i]; A[i]=(pred+A[i+1])/2.0; pred=tek;
}
A[N-1]=predposl/2.0;
return;
}
Задача 209. Является ли массив «плотным».
Упорядочим массив A по неубыванию с помощью функции f205sort. Для неубывающего массива A отрезок значений равен [ A[0], A[N-1] ]. Неубывающий массив целых чисел плотен, если в нем нет «дыр» - пар соседних элементов с разностью больше 1. Функция f209
будет вычислять три числа: левый и правый концы отрезка значений и число дыр. При нулевом числе дыр основная функция main должна вывести в файл output.txt два конца отрезка значений; при ненулевом – вывести число -1
Пример. Массив {5,3,6,2,8,3,5,7,2} НЕплотный, так как сортировкa по неубыванию дает {2,2,3,3, 5,5,6,7,8} и обнаруживается дыра (3, 5).
/* Является ли массив «плотным» */
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void f209sort(int*, int);
void f209(int*, int, int*); int main(void){
FILE* in; FILE* out;
int* A; // Описание имени массива A[]
int q, N, i;
int otvet; /* переменная для получения ответа из функции f205 */
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", &N); assert(q==1&&N>0); /* N прочитано успешно */
A = (int*) malloc(N*sizeof(int));/*выделение N*4 байт для массива А*/
for(i=0; i<N; i++) q=fscanf(in,"%d",&A[i]);
assert (q==1); /* все элементы массива А прочитаны успешно */
f209(A,N,&otvet);
fprintf(out,"%d ",otvet);
fclose(in); fclose(out); free(A);
return 0;
}
/* Сортировка массива целых чисел на том же месте по неубыванию.
Массив А считается отсортированным по неубыванию, если для любой пары
x, y соседних элементов массива выполнено нестрогое неравенство x<=y.
*/
void f209sort(int A[], int N){
#define Besporyadok(x,y) (x>y) /* Порядок <==> НЕубывание */
int i,j,tmp;
int ChisloBespor; /* Число беспорядков */
assert (N>0);
for (i=N-1; i>0; i=i-1) {
ChisloBespor=0;
for (j=0; j<i; j=j+1) {
if( Besporyadok(A[j],A[j+1]) ){
tmp=A[j];A[j]=A[j+1];A[j+1]=tmp;
ChisloBespor++;
}
}
if(ChisloBespor==0) return;
}
return;
}
void f209(int A[], int N, int* LEV, int* PRAV, int* y){
int i,chislo_dyr,last;
assert (N>0);
f205sort(A,N);
/* подсчет числа дыр в неубывающем массиве: */
last=A[0]; chislo_dyr=0;
for (i=1; i<N; i++){
if (A[i]>(last+1))chislo_dyr++;
last=A[i];
}
*LEV=A[0]; *PRAV=A[N-1]; *y=chislo_dyr;
return;
}
В этой задаче приведем еще основную функцию:
/* file 209.c Является ли массив плотным */
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void f205sort(int*, int);
void f209(int*, int, int*, int*, int*);
int main(void){
FILE *in, *out;
int* A; /* Описание имени массива A[] */
int q,N,i;
int lev,prav, chislo_dyr; /* для получения ответа из f209 */
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",&N); assert(q==1&&N>0);/ *N прочитано успешно */ A = (int*) malloc(N*sizeof(int)); /* выделение N*4 байт для А */
for(i=0; i<N; i++) q=fscanf(in,"%d",&A[i]);
assert (q==1); /* все элементы массива А прочитаны успешно */
f209(A,N,&lev,&prav,&chislo_dyr);
if(chislo_dyr==0) fprintf(out,"%d %d",lev,prav);
if(chislo_dyr >0) fprintf(out,"%d ",-1);
fclose(in); fclose(out); free(A);
return 0;
}
< реализация функции void f209(...){...} >
< реализация функции void f205sort(...){...} >
/* конец файла 209.c */
/* Задача 210. Является ли массив «парным»: А[0]+A[2]+...=A[1]+A[3]+...? */
void f210(int A[], int N, int* y){
int i, s0=0,s1=0;
assert (N>1);
for (i=0; i+1<N; i=i+2) {s0=s0+A[i]; s1=s1+A[i+1];}
/* если индекс последнего элемента четен, то этот элемент не
учитывается в цикле и его нужно добавить к s0 вне цикла: */
if(N%2==1)s0=s0+A[N-1];
if(s0==s1)*y=1;
if(s0!=s1)*y=0;
return;
}
Задача 211. Является ли массив «счастливым», то есть существует ли его разбиение на две непустые части такие, что
A[0]+A[1]+...A[k-1]=A[k]+A[k+1]+...+A[N-1]?
Идея решения.Если массив "счастливый", то суммы в левой и правой частях равны, а значит удвоенная левая часть равна общей сумме.
/* Является ли массив «счастливым», то есть существует k такое, что
A[0]+A[1]+...A[k-1]=A[k]+A[k+1]+...+A[N-1]? */
void f211(int A[], int N, int* addr_k, int* addr_S){
int i,k,s,Slev;
assert (N>1);
for (i=0,s=0; i<N; i++) s=s+A[i];
Slev=A[0];
for(k=1; k<N; k++){
if(2*Slev==s){*addr_k=k; *addr_S=Slev; return;}
Slev=Slev+A[k];
}
*addr_k=-1;
return;
}
Задача 212. Сортировка массива вещественных чисел по неубыванию.
Функция f212 получается из функции 205sort заменой типов величин А и tmp с int на double в строках 1 и 3. Остальные строки не меняются.
/* Сортировка вещественного массива по неубыванию */
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void f212sort(double*, double);
void f212(double*, double, double*);
int main(void){
FILE* in; FILE* out;
double* A; // Описание имени массива A[]
int q, N, i;
int otvet;
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", &N); assert(q==1&&N>0); /* N прочитано успешно */
A = (double*) malloc(N*sizeof(double));
for(i=0; i<N; i++) q=fscanf(in,"%lf ",&A[i]);
assert (q==1); /* все элементы массива А прочитаны успешно */
f212(A,N,&otvet);
fprintf(out,"%lf ",otvet);
fclose(in); fclose(out); free(A);
return 0;
}
/* Сортировка массива целых чисел на том же месте по неубыванию.
Массив А считается отсортированным по неубыванию, если для любой пары
x, y соседних элементов массива выполнено нестрогое неравенство x<=y.
*/
void f212sort(int A[], int N){
#define Besporyadok(x,y) (x>y) /* Порядок <==> НЕубывание */
int i,j,tmp;
int ChisloBespor; /* Число беспорядков */
assert (N>0);
for (i=N-1; i>0; i=i-1) {
ChisloBespor=0;
for (j=0; j<i; j=j+1) {
if( Besporyadok(A[j],A[j+1]) ){
tmp=A[j];A[j]=A[j+1];A[j+1]=tmp;
ChisloBespor++;
}
}
if(ChisloBespor==0) return;
}
return;
}
void f212(double A[], int N){
#define Besporyadok(x,y) (x>y) // Порядок <==> НЕубывание
int i,j; double tmp;
int ChisloBespor; /* Число беспорядков */
assert (N>0);
for (i=N-1; i>0; i=i-1) {
ChisloBespor=0;
for (j=0; j<i; j=j+1) {
if( Besporyadok(A[j],A[j+1]) ){
tmp=A[j];A[j]=A[j+1];A[j+1]=tmp;
ChisloBespor++;
}
}
if(ChisloBespor==0) return;
}
return;
}
Функции f213, f214 и f215 отличаются от функции f212 только двумя первыми строками. В задаче 215 используется библиотечная функция double fabs( double x), вычисляющая модуль вещественного числа. Поэтому в начало файла с решением задачи 215 необходимо добавить строку #include <math.h>
Задача 213. Переставить элементы массива вещественных чисел таким образом, чтобы в начале массива оказались неотрицательные элементы, идущие по возрастанию, а в конце масси-
ва — отрицательные элементы, идущие по убыванию.
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void f213sort(double*, double);
void f213(double*, double, double*);
int main(void){
FILE* in; FILE* out;
double* A; // Описание имени массива A[]
int q, N, i;
int otvet;
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", &N); assert(q==1&&N>0); /* N прочитано успешно */
A = (double*) malloc(N*sizeof(double));
for(i=0; i<N; i++) q=fscanf(in,"%lf ",&A[i]);
assert (q==1); /* все элементы массива А прочитаны успешно */
f213(A,N,&otvet);
fprintf(out,"%lf ",otvet);
fclose(in); fclose(out); free(A);
return 0;
}
/* Сортировка массива целых чисел на том же месте по неубыванию.
Массив А считается отсортированным по неубыванию, если для любой пары
x, y соседних элементов массива выполнено нестрогое неравенство x<=y.
*/
void f213sort(int A[], int N){
#define Besporyadok(x,y) (x>y) /* Порядок <==> НЕубывание */
int i,j,tmp;
int ChisloBespor; /* Число беспорядков */
assert (N>0);
for (i=N-1; i>0; i=i-1) {
ChisloBespor=0;
for (j=0; j<i; j=j+1) {
if( Besporyadok(A[j],A[j+1]) ){
tmp=A[j];A[j]=A[j+1];A[j+1]=tmp;
ChisloBespor++;
}
}
if(ChisloBespor==0) return;
}
return;
}
void f213(double A[], int N){
#define Besporyadok(x,y) ((x>=0&&y>=0&&x>y)||(x<0&&y<0&&x<y)||(x<0&&y>=0))
int i,j; double tmp;
int ChisloBespor; /* Число беспорядков */
assert (N>0);
for (i=N-1; i>0; i=i-1) {
ChisloBespor=0;
for (j=0; j<i; j=j+1) {
if( Besporyadok(A[j],A[j+1]) ){
tmp=A[j];A[j]=A[j+1];A[j+1]=tmp;
ChisloBespor++;
}
}
if(ChisloBespor==0) return;
}
return;
}
Задача 214. Переставить элементы массива вещественных чисел таким образом, чтобы в начале массива оказались отрицательные элементы, а в конце массива – неотрицательные. При
этом взаимный порядок отрицательных элементов и взаимный порядок неотрицательных
элементов должны остаться такими же, как и в исходном массиве.
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void f214sort(double*, double);
void f214(double*, double, double*);
int main(void){
FILE* in; FILE* out;
double* A; // Описание имени массива A[]
int q, N, i;
int otvet;
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", &N); assert(q==1&&N>0); /* N прочитано успешно */
A = (double*) malloc(N*sizeof(double));
for(i=0; i<N; i++) q=fscanf(in,"%lf ",&A[i]);
assert (q==1); /* все элементы массива А прочитаны успешно */
f214(A,N,&otvet);
fprintf(out,"%lf ",otvet);
fclose(in); fclose(out); free(A);
return 0;
}
/* Сортировка массива целых чисел на том же месте по неубыванию.
Массив А считается отсортированным по неубыванию, если для любой пары
x, y соседних элементов массива выполнено нестрогое неравенство x<=y.
*/
void f214sort(int A[], int N){
#define Besporyadok(x,y) (x>y) /* Порядок <==> НЕубывание */
int i,j,tmp;
int ChisloBespor; /* Число беспорядков */
assert (N>0);
for (i=N-1; i>0; i=i-1) {
ChisloBespor=0;
for (j=0; j<i; j=j+1) {
if( Besporyadok(A[j],A[j+1]) ){
tmp=A[j];A[j]=A[j+1];A[j+1]=tmp;
ChisloBespor++;
}
}
if(ChisloBespor==0) return;
}
return;
}
void f214(double A[], int N){
#define Besporyadok(x,y) (x>=0 && y<0)
int i,j; double tmp;
int ChisloBespor; /* Число беспорядков */
assert (N>0);
for (i=N-1; i>0; i=i-1) {
ChisloBespor=0;
for (j=0; j<i; j=j+1) {
if( Besporyadok(A[j],A[j+1]) ){
tmp=A[j];A[j]=A[j+1];A[j+1]=tmp;
ChisloBespor++;
}
}
if(ChisloBespor==0) return;
}
return;
}
Результирующий массив получается из исходного путем многократного приведения в порядок пар соседних элементов (x,y). Eсли Besporyadok(x,y) то пара (x,y) заменяется на пару (y,x). Поскольку в каждой такой паре одно число неотрицательно, а другое отрицательно, любая такая замена не меняет взаимный порядок отрицательных элементов или взаимный порядок неотрицательных элементов.
Задача 215. Переставить элементы массива вещественных чисел по убыванию их модулей (сортировка по абсолютной величине). Ответ: последовательно записанные элементы преобразованного массива, при этом на взаимный порядок чисел, одинаковых по абсолютной величине, не накладывается никаких ограничений, они могут располагаться в преобразованном
массиве в любом порядке друг относительно друга.
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <math.h>
void f215sort(double*, double);
void f215(double*, double, double*);
int main(void){
FILE* in; FILE* out;
double* A; // Описание имени массива A[]
int q, N, i;
int otvet;
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", &N); assert(q==1&&N>0); /* N прочитано успешно */
A = (double*) malloc(N*sizeof(double));
for(i=0; i<N; i++) q=fscanf(in,"%lf ",&A[i]);
assert (q==1); /* все элементы массива А прочитаны успешно */
f215(A,N,&otvet);
fprintf(out,"%lf ",otvet);
fclose(in); fclose(out); free(A);
return 0;
}
/* Сортировка массива целых чисел на том же месте по неубыванию.
Массив А считается отсортированным по неубыванию, если для любой пары
x, y соседних элементов массива выполнено нестрогое неравенство x<=y.
*/
void f215sort(int A[], int N){
#define Besporyadok(x,y) (x>y) /* Порядок <==> НЕубывание */
int i,j,tmp;
int ChisloBespor; /* Число беспорядков */
assert (N>0);
for (i=N-1; i>0; i=i-1) {
ChisloBespor=0;
for (j=0; j<i; j=j+1) {
if( Besporyadok(A[j],A[j+1]) ){
tmp=A[j];A[j]=A[j+1];A[j+1]=tmp;
ChisloBespor++;
}
}
if(ChisloBespor==0) return;
}
return;
}
void f215(double A[], int N){
#define Besporyadok(x,y) ((fabs(x))<(fabs(y)))
int i,j; double tmp;
int ChisloBespor; /* Число беспорядков */
assert (N>0);
for (i=N-1; i>0; i=i-1) {
ChisloBespor=0;
for (j=0; j<i; j=j+1) {
if( Besporyadok(A[j],A[j+1]) ){
tmp=A[j];A[j]=A[j+1];A[j+1]=tmp;
ChisloBespor++;
}
}
if(ChisloBespor==0) return;
}
return;
}
Задача 216. Переставить элементы массива вещественных чисел так, чтобы элементы с четными индексами остались на своих местах, а элементы с нечетными индексами стали упорядоченными по возрастанию. В частности, для массива из одного, двух или трех элементов преобразованный массив будет совпадать с исходным.
void f216(double A[], int N){
#define Besporyadok(x,y) (x>y)
int i,j; double tmp;
int ChisloBespor; // Число беспорядков
assert (N>0);
if (N<=3) return;
for (i=N-1; i>=3; i=i-2) {
ChisloBespor=0;
/* перебираем все элементы с нечетными индексами от 1 до j-1 */
/* и ликвидируем среди них беспорядки */
for (j=1; j+1<i; j=j+2) {
if( Besporyadok(A[j],A[j+2]) ){
tmp=A[j];A[j]=A[j+2];A[j+2]=tmp;
ChisloBespor++;
}
}
if(ChisloBespor==0) return;
}
return;
}